BRICS RS-99-39 R. Rizzi: On the Steiner Tree \frac{3}{2}-Approximation for Quasi-Bipartite Graphs BRICS

Basic Research in Computer Science

On the Steiner Tree \frac{3}{2}-Approximation for Quasi-Bipartite Graphs

Romeo Rizzi BRICS Report Series RS-99-39 ISSN 0909-0878 November 1999 Copyright \begin{matrix}c \\ ◯ \end{matrix} 1999, Romeo Rizzi.

BRICS, Department of Computer Science University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent BRICS Report Series publications. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK–8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs:

http://www.brics.dk
ftp://ftp.brics.dk

This document in subdirectory RS/99/39/

On the Steiner tree \frac{3}{2}-approximation for quasi-bipartite graphs

Romeo Rizzi

BRICS^{∗} Department of Computer Science University of Aarhus Ny Munkegade DK-8000 Aarhus C, Denmark

               e-mail: romeo@cwi.nl

Abstract

Let G = (V, E) be an undirected simple graph and w : E ↦ IR_{+} be a non-negative weighting of the edges of G. Assume V is partitioned as R ∪ X. A Steiner tree is any tree T of G such that every node in R is incident with at least one edge of T. The metric Steiner tree problem asks for a Steiner tree of minimum weight, given that w is a metric. When X is a stable set of G, then (G, R, X) is called quasibipartite. In [1], Rajagopalan and Vazirani introduced the notion of quasi-bipartiteness and gave a (\frac{3}{2} + ϵ) approximation algorithm for the metric Steiner tree problem, when (G, R, X) is quasi-bipartite. In this paper, we simplify and strengthen the result of Rajagopalan and Vazirani. We also show how classical bit scaling techniques can be adapted to the design of approximation algorithms.

Key words: Steiner tree, local search, approximation algorithm, bit scaling.

1 Introduction

Let G = (V, E) be an undirected simple graph and w : E ↦ IR_{+} be a nonnegative weighting of the edges of G. Assume V is partitioned into R and X = \overline{R}. (From set theory, \overline{R} = V \R). A Steiner tree is any tree T of G such that every node in R is incident with at least one edge of T. The metric Steiner tree problem asks for a Steiner tree of minimum weight, given that w is a metric. (The weight of a tree T is defined as w(T) = ∑_{e∈T} w_{e}). When no edge of G has both endpoints in X, then (G, R) is called quasi-bipartite. In [1], Rajagopalan and Vazirani introduced the notion of quasi-bipartiteness and gave a (\frac{3}{2} +ϵ) approximation algorithm for the metric Steiner tree problem, when (G, R) is quasi-bipartite. In this paper, we greatly simplify the analysis of Rajagopalan and Vazirani and give a local search \frac{3}{2} approximation algorithm for the same problem. We also show how classical bit scaling techniques can be adapted to the design of approximation algorithms.

∗ Basic Research in Computer Science, Centre of the Danish National Research Foundation.

Denote by MST (G, w) the minimum weight of a spanning tree for (G, w). When S ⊆ V, then ⟨S⟩ denotes the set of those edges in E with both endpoints in S and G[S] denotes the subgraph of G induced by S. (That is, G[S] = (S, ⟨S⟩)).

The graph G[V \X], where X ⊆ V, is also denoted by G\X or by G[\overline{X}]. Let T be a minimum weight spanning tree for (G[\overline{X}], w) and x be a node of X. Our arguments base on the following simple and fundamental lemma: if MST (G[\overline{X} ∪ \{x\}], w) ≥ w(T) for every x ∈ X and X is a stable set of G, then MST (G[\overline{X} ∪ X′], w) ≥ w(T) for every X′ ⊆ X.

2 An useful lemma

Let G = (V, E) be an undirected simple graph and w : E ↦ IR_{+} be a nonnegative weighting of the edges of G. Let X ⊆ V be a stable set of G. In the next section, the following lemma is put into use.

Lemma 1 Let X be a stable set of G. Assume MST (G[\overline{X} ∪ \{x\}], w) ≥ MST (G[\overline{X}], w) for every node x ∈ X. Then MST (G[\overline{X} ∪ X′], w) ≥ MST (G[\overline{X}], w) for every X′ ⊆ X.

To prove Lemma 1, we need to introduce some notations and facts. Usually, we consider a tree T to be just a set of edges. Sometimes however, and depending on our convenience, a tree T will be regarded as the graph (V (T), T), where V (T) is the set of endnodes of edges in T. Let V_{1}, …, V_{k} be a partition of V. Denote by G < V_{1}, …, V_{k} > the graph obtained from G by identifying all nodes of V_{i} into a single node (for i = 1, …, k).

Lemma 2 Let v_{1}, …, v_{k} the neighbors of a node x in G and C_{1}, …, C_{k} a partition of V \ {x} such that v_{i} ∈ C_{i} (for i = 1, …, k). Assume w(δ(x)) < MST (G[V \ {x}] < C_{1}, …, C_{k} >, w). Then MST (G, w) < MST (G \ {x}, w).

Proof: Let T be any spanning tree for (G \ {x}, w). It suffices to show that there always exists a spanning tree F of T < C_{1}, …, C_{k} > such that T \ F ∪ δ(x) is a spanning tree of G. Let v be a leaf of T and let vu be the edge of T incident with v. W.l.o.g. assume v ∈ C_{1}. Case 1: Assume that v ≠ v_{1}. Let T′ = T \{vu} and G′ be the graph obtained from G by identifying node v with node u. (All edges previously incident with v will become incident with u, and v is removed). Note that T′ is a spanning tree for G′\{x}. Let F be a spanning tree of T′ < C_{1}\{v}, C_{2}, …, C_{k} > such that T′ \ F ∪ δ(x) is a spanning tree of G′. But then, F is a spanning tree of T < C_{1}, …, C_{k} > such that T \ F ∪ δ(x) is a spanning tree of G. Case 2: Assume therefore that v = v_{1}. This time G′ and T′ are obtained from G and T as follows. First remove edge vu from T, and in G, remove xv and identify v with u. Next, as long as T contains an edge ab with a ∈ C_{1}, then remove ab from T and in G identify a with b. Let G′ and T′ be the graph and the tree so obtained. Note that T′ is a spanning tree for G′ \ {x}. Let F be a spanning tree of T′ < C_{2}, …, C_{k} > such that T′ \ F ∪ δ(x) is a spanning tree of G′. But then, F ∪ {vu} is a spanning tree of T < C_{1}, …, C_{k} > such that T \ F ∪ δ(x) is a spanning tree of G. □

Proof of Lemma 1: It suffices to show that if MST (G[\overline{X} ∪ X′], w) < MST (G \ \{x\}, w) for some X′ ⊆ X with |X′| ≥ 2, then MST (G[\overline{X} ∪ X′′], w) < MST (G \ {x}, w) for some proper subset X′′ of X′. Let T′ be a spanning tree of G[\overline{X} ∪ X′] with w(T′) < MST (G \ \{x\}, w). In a minimal counterexample, we can always assume that X′ = X and that every edge of G with an endpoint in X is contained in T′. Let x be any node in X and X′′ = X \ {x}. Let v_{1}, …, v_{k} be the neighbors of x in G. Consider the connected components C̃_{1}, …, C̃_{k} of the graph obtained by removing node x from the graph T′. (Assume w.l.o.g. that v_{i} ∈ C̃_{i}, for i = 1, …, k). If MST (G[\overline{X} ∪ X′′], w) ≥ w(T′), then w(δ(x)) < MST (G[V \ \{x\}] < C̃_{1}, …, C̃_{k} >, w). For i = 1, …, k, let C_{i} = C̃_{i} ∩ \overline{X}. Since X is a stable set of G, then G[\overline{X}] < C_{1}, …, C_{k} >= G[V \ \{x\}] < C̃_{1}, …, C̃_{k} >. Hence MST (G[\overline{X}] < C_{1}, …, C_{k} >, w) > w(δ(x)). By Lemma 2, MST (G[\overline{X} ∪ \{x\}], w) < MST (G[\overline{X}], w). □

3 The result

Let G = (V, E) be an undirected simple graph and w : E ↦ IR_{+} be a nonnegative weighting of the edges of G. In this section, we also assume that w satisfies the triangle inequality and that (G, R) is quasi-bipartite.

Let \overline{T} be an optimal Steiner tree for (G, R, w). If we knew which of the nodes of X, say \overline{I} ⊆ X, are actually in V (\overline{T}), then we could find an optimal Steiner tree by computing a minimum spanning tree of (G[R∪\overline{I}], w). Moreover, since w is a metric, there always exists an optimal solution \overline{T} such that no node in \overline{I} is incident with less than 3 edges in \overline{T}. As observed by Rajagopalan and Vazirani in [1], the following local search algorithm returns a \frac{3}{2}-optimal Steiner tree, i.e. a Steiner tree T̃ with w(T̃) ≤ \frac{3}{2}w(\overline{T}).

Algorithm 1 Local Steiner tree (G, R, w)

1. I ← ∅; T ← any minimum spanning tree of (G[R ∪ I], w);

2. while ∃x ∈ X \ I such that MST (G[R ∪ I ∪ {x}], w) < w(T) do

3. I ← I ∪ {x}; T ← any minimum spanning tree of (G[R ∪ I], w);

4. remove from I all nodes with degree one in T; update T accordingly; (drop the corresponding leafs);

5. remove from I all nodes with degree two in T; update T accordingly; (shortcut the pairs of consecutive edges si and it with the single edges st);

6. return T;

We offer a direct and simple proof of the following result.

Theorem 3 The Steiner tree output by Algorithm 1 is within a factor of \frac{3}{2} from optimum.

Proof: Let T̃ be the Steiner tree output by Algorithm 1 and let \overline{T} be an optimal Steiner tree for (G, R, w). Let Ĩ = V (T̃) \ R and \overline{I} = V (\overline{T}) \ R. In T̃, consider the stars of the nodes in Ĩ. Since (G, R) is quasi-bipartite, then these stars are all disjoint. Moreover, by steps 4 and 5, each star contains at least three edges. For every x ∈ Ĩ, let e_{x} be any edge of T̃ incident with x and with smallest possible weight. By the above remarks, ∑_{x∈Ĩ}w(e_{x}) ≤ \frac{1}{3}w(T̃). Since for every x ∈ Ĩ one of the two endpoints of e_{x} is in R, then there exists a spanning tree T of G[R ∪ \overline{I} ∪ Ĩ] with w(T) ≤ w(\overline{T}) + \frac{1}{3}w(T̃). (Take any spanning tree in \overline{T} ∪ \{e_{x} : x ∈ Ĩ\}). By step 3, MST (G[R ∪ Ĩ∪ {x}], w) ≥ w(T̃) for every x ∈ X \ Ĩ. By Lemma 1, w(T) ≥ w(T̃). Combining, w(\overline{T}) + \frac{1}{3}w(T̃) ≥ w(T̃). So, w(T̃) ≤ \frac{3}{2}w(\overline{T}). □

4 Running time

In this section, we show how a bit-scaling technique can be employed to derive an implementation of Algorithm 1 with running time polynomial in the size of the input.

Consider the sequence of weightings w = w_{0}, w_{1}, …, where, for i > 0, w_{i} is defined as follows: w_{i}(e) = ⌊\frac{w_{i−1}(e)}{2}⌋. Let k be the smallest index for which w_{k}(e) ≤ 1 for every edge e of G. Therefore k ≤ log_{2}(max{w(e) : e ∈ E}). When Algorithm 1 is executed on (G, R, w_{k}) as input, then loop 2–5 will cycle at most n times, since w_{k} is a 0, 1-vector. The output will be a tree T^{k}_{AP X}. Note that T^{k}_{AP X} is a \frac{3}{2}-optimal Steiner tree for (G, R, w_{k}).

For i = 0, 1, …, k, let T^{i}_{OP T} be an optimal and T^{i}_{AP X} be a \frac{3}{2}-optimal Steiner tree in (G, w_{i}). Hence,

w_{i}(T^{i}_{AP X}) − w_{i}(T^{i−1}_{OP T}) ≤ w_{i}(T^{i}_{AP X}) − w_{i}(T^{i}_{OP T}) ≤ \frac{1}{2}w_{i}(T^{i}_{OP T})

Moreover, since every tree has less that n edges, we have:

w_{i−1}(T^{i}_{OP T}) − w_{i−1}(T^{i−1}_{OP T}) ≤ (2w_{i}(T^{i}_{OP T}) + n) − 2w_{i}(T^{i−1}_{OP T}) ≤ n

Therefore,

w_{i−1}(T^{i}_{AP X}) − w_{i−1}(T^{i−1}_{OP T}) ≤ (2w_{i}(T^{i}_{AP X}) + n) − 2w_{i}(T^{i−1}_{OP T}) ≤ n + 2 (w_{i}(T^{i}_{AP X}) − w_{i}(T^{i−1}_{OP T})) ≤ n + 2 (\frac{1}{2}w_{i}(T^{i}_{OP T})) ≤

n + \frac{2}{2} (\frac{1}{2}w_{i−1}(T^{i}_{OP T})) ≤

n + \frac{1}{2} ( w_{i−1}(T^{i}_{OP T}) + w_{i−1}(T^{i−1}_{OP T}) − w_{i−1}(T^{i−1}_{OP T}) ) ≤

n + \frac{1}{2}w_{i−1}(T_{OP T}^{i−1} ) + \frac{1}{2} ( w_{i−1}(T^{i}_{OP T}) − w_{i−1}(T^{i−1}_{OP T}) ) ≤ n + \frac{1}{2}w_{i−1}(T^{i−1}_{OP T}) + \frac{1}{2} (n) = \frac{3}{2}n + \frac{1}{2}w_{i−1}(T^{i−1}_{OP T})

We conclude that w_{i−1}(T^{i}_{AP X}) ≤ \frac{3}{2}n + \frac{3}{2}w_{i−1}(T^{i−1}_{OP T}). Therefore, by executing loop 2–5 at most \frac{3}{2}n times, then Algorithm 1 finds a \frac{3}{2}-optimal Steiner tree in (G, w_{i−1}) starting from any \frac{3}{2}-optimal Steiner tree in (G, w_{i}).

Acknowledgements

I thank Devdatt Dubashi for stimulating conversations.

References

[1] Sridhar Rajagopalan and Vijay V. Vazirani, On the Bidirected Cut Relaxation for the Metric Steiner Tree Problem. SODA ’99 (1999) 742– 751.

Recent BRICS Report Series Publications

RS-99-39 Romeo Rizzi. On the Steiner Tree \frac{3}{2}-Approximation for Quasi-Bipartite Graphs. November 1999. 6 pp.

RS-99-38 Romeo Rizzi. Linear Time Recognition of P_{4}-Indifferent Graphs. November 1999. 11 pp.

RS-99-37 Tibor Jordán. Constrained Edge-Splitting Problems. November 1999. 23 pp. A preliminary version with the title Edge-Splitting Problems with Demands appeared in Cornujols, Burkard and Woeginger, editors, Integer Programming and Combinatorial Optimization: 7th International Conference, IPCO ’99 Proceedings, LNCS 1610, 1999, pages 273–288.

RS-99-36 Gian Luca Cattani and Glynn Winskel. Presheaf Models for CCS-like Languages. November 1999.

RS-99-35 Tibor Jordán and Zoltán Szigeti. Detachments Preserving Local Edge-Connectivity of Graphs. November 1999. 16 pp.

RS-99-34 Flemming Friche Rodler. Wavelet Based 3D Compression for Very Large Volume Data Supporting Fast Random Access. October 1999. 36 pp.

RS-99-33 Luca Aceto, Zoltán Ésik, and Anna Ingólfsdóttir. The Max-Plus Algebra of the Natural Numbers has no Finite Equational Basis. October 1999. 25 pp. To appear in Theoretical Computer Science.

RS-99-32 Luca Aceto and François Laroussinie. Is your Model Checker on Time? — On the Complexity of Model Checking for Timed Modal Logics. October 1999. 11 pp. Appears in Kuty�owski, Pacholski and Wierzbicki, editors, Mathematical Foundations of Computer Science: 24th International Symposium, MFCS ’99 Proceedings, LNCS 1672, 1999, pages 125–136.

RS-99-31 Ulrich Kohlenbach. Foundational and Mathematical Uses of Higher Types. September 1999. 34 pp.

RS-99-30 Luca Aceto, Willem Jan Fokkink, and Chris Verhoef. Structural Operational Semantics. September 1999. 128 pp. To appear in Bergstra, Ponse and Smolka, editors, Handbook of Process Algebra, 1999.

RS-99-29 Søren Riis. A Complexity Gap for Tree-Resolution. September 1999. 33 pp.