Approximation Algorithms for the 0-Extension Problem.
In the 0-extension problem, we are given a weighted graph with some nodes marked as terminals and a semimetric on the set of terminals. Our goal is to assign the rest of the nodes to terminals so as to minimize the sum, over all edges, of the product of the edge's weight and the distance between the terminals to which its endpoints are assigned. This problem generalizes the multiway cut problem of Dahlhaus et al. [SIAM J. Comput.}, 23 (1994), pp. 864--894] and is closely related to the metric labeling problem introduced by Kleinberg and Tardos [Proceedings of the 40th IEEE Annual Symposium on Foundations of Computer Science, New York, 1999, pp. 14--23].We present approximation algorithms for {\sc 0-Extension}. In arbitrary graphs, we present a O(log k)-approximation algorithm, k being the number of terminals. We also give O(1)-approximation guarantees for weighted planar graphs. Our results are based on a natural metric relaxation of the problem previously considered by Karzanov [European J. Combin., 19 (1998), pp. 71--101]. It is similar in flavor to the linear programming relaxation of Garg, Vazirani, and Yannakakis [SIAM J. Comput.}, 25 (1996), pp. 235--251] for the multicut problem, and similar to relaxations for other graph partitioning problems. We prove that the integrality ratio of the metric relaxation is at least $c \sqrt{\lg k}$ for a positive c for infinitely many k. Our results improve some of the results of Kleinberg and Tardos, and they further our understanding on how to use metric relaxations.
Introduction
Let V be a finite set, let T  V , and let d be a semimetric on T . 1 Then a semimetric - on V is an extension of d to
V iff for every in addition, for every
then - is a 0-extension of d to V .
We consider the following optimization problem (denoted 0-EXTENSION): Given a graph E) with non-negative
edge weights c subset T of the nodes, and a semimetric d on T , find a 0-extension - of d to V
that minimizes the total weighted length of the edges.
It helps to compare 0-EXTENSION to the multiway cut problem of Dahlhaus, Johnson, Papadimitriou, Seymour, and
Yannakakis [5, 6]. MULTIWAY CUT is the following problem: Given a graph E) with nonnegative edge
weights R, and a subset T  V of terminals, find a mapping
so as to minimize X
In other words, find a set of edges of minimum total weight whose removal disconnects all terminal pairs. If we
define d to be the uniform metric on T , i.e., exactly
this problem: Find so as to minimize
c(u; v)  d(f(u); f(v));
as Now 0-EXTENSION is the natural generalization
of MULTIWAY CUT in which, instead of being the uniform metric, d is an arbitrary semimetric on T . In
other words, we must find an so as to minimize
c(u; v)  d(f(u); f(v)):
Dahlhaus et al. [6] show that MULTIWAY CUT (and therefore 0-EXTENSION) is APX-hard. Thus there exists a
constant  > 1 such that no polynomial-time algorithm can find a solution within a factor of  of the optimum,
unless P=NP.
In this paper we develop approximation algorithms for the 0-extension problem. We study what seems to us to be
the most natural linear programming relaxation for this problem. Specifically, given the semimetric d on T , extend
d to a semimetric - on the larger set V so as to minimize
uv2E c(u; v)-(u; v). (We call this the metric relaxation.)
Obviously, the set of feasible extensions - is defined by O(jV linear constraints, and the objective function is
linear. Thus, finding the best extension is a linear programming problem, so it can be solved in polynomial time.
We derive approximation algorithms using the metric relaxation, thus bounding also the integrality ratio for the
relaxation. For arbitrary graphs we give a randomized, O(log jT j)-approximation algorithm. We show that the
integrality ratio is at least a constant times
log jT j for infinitely many jT j. We improve the upper bounds to O(1)
for (weighted) planar graphs (or, in fact, for any family of graphs that excludes a K r;r -minor for some fixed r).
Karzanov [11] considers the metric relaxation for the 0-extension problem, and characterizes some of the cases in
which the relaxation gives the optimal solution. For the multiway cut problem, it was known that the metric relaxation
yields a (2 2=jT j)-approximation algorithm (see [2]). Indeed, this observation uses the same idea underlying
the combinatorial algorithm of Dahlhaus et al. [6] that has the same performance guarantee. For the general case,
the quality of the metric relaxation was not known prior to our work. For multiway cut, a different relaxation gives
better approximations, with an asymptotic ratio significantly below 2 (see Calinescu, Karloff, and Rabani [2] and
R is a semimetric on T iff for every
then d is a metric.
the improved bounds of Cunningham and Tang [3] and of Karger, Klein, Stein, Thorup, and Young [10]). It is not
clear if the Calinescu et al. relaxation can be extended to handle the general case of 0-EXTENSION.
In a recent paper, Kleinberg and Tardos [14] give approximation algorithms for a similar problem of classification
with pairwise relations, which they call METRIC LABELING. In their problem, the terminals are distinct from the
vertices and are called labels. There is a semimetric on the labels, and for each node of the graph there is a vector of
assignment costs to each of the labels. The goal is to minimize the total assignment cost plus the sum of weighted
edge lengths. More formally, given a graph E) with nonnegative edge weights c set T of labels,
a metric d on T , and a nonnegative assignment cost function a is the problem
of finding a mapping so as to minimize
c(u; v)  d(f(u); f(v)):
For the case that d is the uniform metric, Kleinberg and Tardos give a 2-approximation algorithm, based on a relaxation
similar to the Calinescu et al. relaxation for multiway cut. Unlike the multiway cut problem, the integrality
ratio for the relaxation here is at least 2 2=jT j. Chuzhoy [4] improves their result for three and four terminals
(achieving a tight 4=3 bound for three terminals). Kleinberg and Tardos further give a constant approximation algorithm
for a class of hierarchically well-separated tree metrics (HST). Following Bartal's small distortion embeddings
of metrics into HST metrics [1], they use the result for trees to give an O(log jT j log log jT j)-approximation algorithm
for arbitrary metrics. Gupta and Tardos [9] later give a local search-based 4-approximation algorithm for the
case that d is a truncated linear metric (i.e.,
Kleinberg and Tardos, and Gupta and Tardos motivate their work by several applications, mostly concerning computer
vision, such as image restoration and visual correspondence. In these applications the nodes of the graph
are pixels in a raster image and the edges model adjacency (so, in fact, the graph is a two-dimensional mesh). In
image restoration applications, the labels model pixel intensities or colors. Assigning a label to a pixel amounts
to determining the "true" intensity (or color) of the pixel from the observed values. The assignment cost penalizes
for the difference between the observed and assigned intensity. In visual correspondence applications, the labels
model possible shifts between two images. Assigning a label to a pixel amounts to determining the shift of that pixel
between the two images. The assignment cost penalizes for the difference between the values of the supposedly
matching pixels. In both types of applications, the structure of the graph arises from assuming that the a priori
distribution of "true" labels is generated by a Markov random field (where the distribution of a pixel depends only
on the distribution of its neighbors).
Notice that 0-EXTENSION is a special case of METRIC LABELING. (Set, for all u 62 T and
c(u; our results improve upon the results in [14] for this case. We note that the 0-
extension formulation seems appropriate for many of the computer vision applications mentioned in [14, 9]. For
example, if we connect each pixel by a weighted edge to the label corresponding to its observed intensity, we get an
assignment cost proportional to the distance between the observed and assigned value. Our algorithm for weighted
planar graphs, which actually only uses the fact that V n T induces a planar graph, is an alternative constant-ratio
approximation algorithm for some of these computer vision problems.
Another problem related to ours is the multicut problem, first considered in the context of approximation algorithms
in two papers by Garg, Vazirani, and Yannakakis [7, 8] (and implicitly in Klein, Agarwal, Ravi, and Rao [12]). In this
problem, we are given a (weighted) graph and k pairs of terminals (nodes in the graph), and the goal is to find a set
of edges of minimum weight whose removal disconnects every pair of terminals. This is a different generalization
of multiway cut (the latter can be viewed as the multicut problem for all k pairs of terminals). It is incomparable
to the 0-extension problem, in the sense that neither problem is a special case of the other. In [8], Garg et al. give an
O(log jT approximation algorithm for the multicut problem, based on a metric relaxation (assign lengths to edges
so that the distance between every specified pair of terminals is at least 1). Their result is tight for the relaxation.
The example achieving (asymptotically) the integrality ratio is an expander. For their upper bounds, they use a
region-growing technique similar to that used by Leighton and Rao [15] for approximating the minimum flux (edge
expansion) of a graph. Klein, Plotkin, and Rao [13] improve the Leighton-Rao technique for planar graphs (and
more generally for graphs that exclude a K r;r -minor), to get a constant factor approximation for the minimum flux.
Using their technique, Tardos and Vazirani [17] exhibit a constant factor approximation algorithm for the multicut
problem in planar graphs (and K r;r
Our result can be seen as a counterpart to the Garg et al. and the Tardos-Vazirani results. The region-growing
technique does not give a good approximation in the case of 0-extension. However, our results can be viewed as a
form of (randomized) region growing after the application of a scaling function to the distances. This is implicit in
the general case algorithm, and explicit in the planar graphs algorithm, where we use the Klein et al. technique on
the scaled distances. It may be worth noting that expanders are not a particularly bad case for our relaxation (see
Section 4).
The rest of the paper is organized as follows. In Section 2 we present the algorithm for the general case. Section 3
has the improved bounds for planar graphs. In Section 4 we discuss the quality of the linear programming relaxation
underlying our approximation algorithms. Throughout the rest of the paper we use k to denote the number jT j of
terminals. We call the vertices in V n T nonterminals.
An O(log k)-Approximation Algorithm
In this section we present the randomized algorithm which finds a 0-extension of weight at most O(log times
the optimum. We begin by computing an optimal solution to the following natural linear programming relaxation,
which we denote by (MET):
Minimize
c(u; v)-(u; v) subject to
(V; -) is a semimetric (1)
If an assignment defines an optimal solution to the 0-extension problem, then putting -(u;
defines a feasible solution of (MET) of the same weight as the optimal solution. Therefore, the
optimal value Z  of (MET) is a lower bound on the minimum weight 0-extension. We exhibit a rounding procedure
that takes any feasible solution - of (MET) of value Z and constructs a 0-extension assignment
weight is O(Z log k).
Our rounding procedure works as follows. Pick uniformly at random a permutation  of T and independently choose,
uniformly at random in the interval [1; 2), a real number . The rounding algorithm iteratively assigns some nodes to
terminal  1 , then some of the remaining nodes to terminal  2 , and so on. For every
The rounding procedure is given below.
The Rounding Procedure
t.
Pick a random permutation of the terminals.
Pick  uniformly at random in the interval [1; 2).
do
for all unassigned nonterminals u such that -(u;  j )  A u , do
set assign u to  j ).
endfor
endfor
We first show that the rounding procedure produces a 0-extension:
Claim 1. The rounding procedure assigns every nonterminal to a terminal.
Proof. Consider a nonterminal v and let t 2 T be a terminal with -(v; Choose j such that
v is not assigned to a terminal in iterations must be assigned to t in iteration j, because   1.
For any pair of nodes u; v 2 V , define a random variable s(u; We say that are
separated if f(u) 6= f(v). Notice that if u; v are not separated, then s(u; Our goal is to bound the
expectation E[s(u; v)]. We first state a bound on the probability that u; v are separated.
Lemma 2. Fix u;
Pr[u; v are separated]  4H k
A u
A v
k is the kth harmonic number.
Before we prove this bound, we state and prove its consequence, a bound for E[s(u; v)] which is the core of the
analysis of our algorithm.
Lemma 3. For any pair of distinct vertices
Proof. Fix u 6= v and put -(u; v). By the triangle inequality, A v  A u
we have
If u is a terminal, then A Therefore, by Inequality (3), s(u; v)  3- always. If both u and v are
nonterminals and then by the triangle inequality, for any terminal j 2 T , -(u; Therefore, u and
are assigned to the same terminal, regardless of the choice of  and , so s(u; always.
Thus, we may assume that both u and v are nonterminals, and that - > 0. We consider two cases, depending on
whether - is small compared to A u or A v , or not. If A u < 4-, then A v < 5-, and by Inequality (3), s(u; v) <
Similarly, if A v < 4-, then s(u; v) < 19-. Therefore, if A u < 4- or A v < 4-, the lemma
holds.
Assume, therefore, that -  1
g. (Recall that we also assume that - > 0.) We have
A u
A v
A u
A v
where the first inequality follows from Lemma 2 and Inequality (3).
We conclude with
Theorem 4. There is a randomized, polynomial-time, O(log k)-approximation algorithm for 0-EXTENSION.
Proof. Let -  be an optimal solution of (MET) of cost Z  . By Lemma 3, the expected weight of the 0-extension
obtained by the rounding procedure is O(Z  log k). Therefore, there exists a choice of  and of  that produces a
solution of weight O(Z  log k). To obtain a polynomial-time algorithm, notice that for a given permutation , two
different values of ,  1 >  2 , produce combinatorially distinct solutions only if there is a terminal j and a node u
such that -  (u; Thus we can enumerate over at most kjV j "interesting" values of
. We can determine these values by sorting the fractions -  (u; j)=A u , over all nodes u with A u > 0 and over all
2 The constant 38 is somewhat arbitrary, and definitely could be improved.
Proof of Lemma 2. Let E(u; v) denote the event that there is a terminal j such that when j is processed u is
assigned to j whereas v remains unassigned; define E(v; u) similarly. We show that
By symmetry, Pr[E(v; u)]  4H k -=A v . Therefore, the lemma follows from Inequality (4).
For . For   1, let
and let
Notice that M() and S() are disjoint subsets of terminals. Put
Assume that the rounding procedure uses  2 [1; 2). Then, v must be assigned to a terminal in S(), because
is equivalent to r j  . Similarly, u cannot be assigned to a terminal which is not in M() [ S().
Indeed, u can only be assigned to a terminal j with l j  , and based on whether r j   or not, j is either in S()
or in M(). Moreover, E(u; v) happens if and only if the first terminal in M()[S() to be processed is in M().
Indeed, if the first such terminal is j 2 S(), then v (and possibly also u) will be assigned to j. Thus,
(Notice that there exists a j for which r so S() is never empty.) As  is distributed uniformly in [1; 2), we
get
Z 2m()
d: (5)
We need the following claim:
5. Fix a positive integer k and let  be a nonnegative real. Let be a nondecreasing
sequence of reals. Let hr another sequence of reals such that r j  1 for all j, and for all
2.
Z 2m()
Proof. Notice that m()  1 for  so the function we are integrating is
well-defined. Let t be the largest index for which l t  2 (so if t < k, l t+1 > 2). We prove by induction on t that
the value of the integral is at most H t   H k . For
Z 2m()
d
Z r 11d
So, assume that the claim is true for the case that t 1 values l j are at most 2, and consider sequences
and exactly t j's are such that l j  2. We compare the value I of the integral in this case to
the value I 0 of the integral for the sequences hl
the first sequence becomes hl Notice that the latter sequences satisfy the conditions of the
claim, and furthermore, only t 1 j's are such that l j  2. Therefore, by the inductive hypothesis, I 0  H t 1 .
If l t  r t , then I = I 0 , so the claim holds in this case. Thus, we may assume that l t < r t . The only range where
the integrands differ is  2 [l t ; minfr t ; 2g). In this range, for every j < t, l j  . Therefore, for the second pair of
sequences, 1. For the original sequences, for  2 [l t ; minfr t ; 2g), m() is greater by 1, and
s() is the same. The difference in the integrands is therefore
Therefore, I I 0  (minfr t ; 2g l t )=t  (r t l t )=t. Because l t  2, r t l t  . Hence, I  I 0
This completes the proof of Claim 5.
We now proceed with the proof of Lemma 2. Notice that if l j  2, then -(u; Using the assumption that
4 A u , we have for such j,
A v
A u
A u -
A u
A u
3-
A u -
4-
A u
Hence, using Claim 5 with
Z 2m()
Combining Equation (5) and Inequality (7), we get Pr[E(u; v)]  4H k -=A u , which proves Inequality (4) and thus
the lemma.
3 An O(1)-Approximation Algorithm for Planar Graphs
In this section we use the linear programming relaxation (MET) to get improved bounds for planar graphs. To achieve
the improved bounds, we present a different rounding procedure. We show that if the input graph E) does
not have a K r;r -minor, then the rounding procedure presented in this section guarantees an O(r 3 ) approximation
ratio. As planar graphs are K 3;3 -minor free, this gives a polynomial-time O(1)-approximation algorithm for planar
graphs (and, more generally, for K r;r -minor free graphs, for every fixed r).
The main tool that we use is the following theorem of Klein, Plotkin, and Rao [13] (the extension to the weighted
case was stated by Tardos and Vazirani [17]).
Theorem 6 (Klein, Plotkin, and Rao). There are constants  and  and a polynomial-time algorithm KPR(H; -;
c;
; r) which takes as input a graph nonnegative integral edge
nonnegative edge costs c : EH ! Q , a positive rational
, and a positive integer r, and finds either (1) a K r;r -minor
in H or (2) a set of edges of total c-cost at most  r
e2EH -(e)c(e) whose removal decomposes H into connected
components such that the shortest path (in H , using edge lengths -) between any two nodes in the same component
is at most r 2
Let r be a positive integer. Let R be a feasible solution of (MET) of weight Z . Using Theorem 6, we
exhibit a deterministic rounding procedure that obtains a 0-extension of weight O(Z), assuming that the input graph
G is K r;r -minor free.
The main idea of the rounding procedure is to partition the nonterminals into clusters such that, for any two nodes
u and v in the same cluster, A u is at most twice A v . We then assign all the nodes in a cluster to a terminal closest
to one of the nodes in the cluster. More formally, the rounding procedure computes a 0-extension
follows.
The Second Rounding Procedure
for every terminal t.
for every nonterminal u 2 V such that A do
endfor
Let
E) be the subgraph of G induced by the remaining nonterminals.
~
v) > 0g.
for every edge uv 2
do
~
~
c(uv) c(u; v)  maxfA g.
endfor
Execute KPR(
G; ~
for each resulting cluster C
V , do
Choose x 2 C to minimize A x .
Choose
endfor
We first establish a few simple facts about this rounding procedure. Let ~
uv2
~
-(uv)~c(uv).
7. ~
Z  2Z= ~
- min .
Proof. Notice that if -(u; v) > 0, then -(u; v)=( ~ - min  maxfA
We have
uv2
uv2
-(u; v)
~
~
uv2
~
8. The total ~ c-cost of the edges removed by KPR(
G; ~ -; ~ c; 1=(2r 2 ~ - min ); r) is O(r 3 Z), and each of the
resulting clusters C has ~
-diameter at most 1=(2 ~ - min ).
Proof. By Theorem 6, the sum of ~ c(uv) over edges uv with u; v in different clusters is at most (r=
Z . By
Claim 7, this is at most 4r 3 Z , which is O(r 3 Z). Also, by Theorem 6, the ~
-diameter of each resulting cluster C
is at most 1=(2 ~
We now relate the ~ -distances to the original -distances.
Lemma 9. Let u; v 2
. If the length of a shortest path in
G between u and v with respect to edge lengths ~
- is at
most 1=(2 ~ - min ), then -(u; v)  A u .
Proof. Let vi be a shortest path in
G between u and v with respect to the edge lengths
~
-. For 1  t  j, let s
By the triangle inequality, A x t  A u
A . Notice that s 1  s 2      s j . Therefore, for i  j, -(x i 1 ;x i )
. Also,
~
, and therefore -(x
Using this, we have s j
1, where the last inequality follows from the hypothesis
that the length of hx is at most 1=(2 ~ - min ). We conclude that s j  A u . Finally, notice that by the
triangle inequality -(u; v)  s j .
We are ready to analyze the performance of the rounding procedure.
Lemma 10. Let r > 0 be an integer. Then for every input graph G which is K r;r -minor free, for every feasible
solution to (MET) of weight Z , the above rounding procedure produces a 0-extension of weight O(r 3 Z).
Proof. Let uv 2 E be an edge of G. If both endpoints u; v 62
, then each endpoint is either a terminal or a node
at distance 0 from some terminal; hence d(f(u);
If u 62
together with the cluster C that contains it, is assigned to some
terminal i. By the definition of the rounding procedure, there is a node x 2 C such that -(x;
Combining Claim 8 and Lemma 9, we have -(v; x)  A v . Therefore, using the triangle inequality, -(v; i)  2A v .
Using the triangle inequality again, d(f(u);
However, -(u; Therefore, d(f(u); f(v))  3-(u; v).
We are left with the edges uv 2
E. For
denote the cluster containing u. Then
uv2
uv2
However,
g. The second inequality follows from the fact that by the definition of the algorithm, for every
nonterminal u, f(u) is a terminal closest to some x 2 C(u) with -(f(u); As argued in the previous
case, -(x; u)  A u . The inequality follows because by the triangle inequality, -(f(u); u)
Therefore,
uv2
uv2
uv2
~
c(uv)
uv2
~
Now states that
uv2
E: C(u)6=C(v) ~ c(uv) is O(r 3 Z).
We conclude with the main result of this section:
Theorem 11. Let r > 0 be a fixed integer. There is a deterministic polynomial-time O(1)-approximation algorithm
for 0-EXTENSION in K r;r -minor free weighted graphs.
Proof. Solve (MET) optimally and then use the rounding procedure from this section, which clearly can be implemented
in polynomial time. Lemma 10 establishes the performance guarantee of this algorithm.
4 The Integrality Ratio
In this section we use the max flow-min cut theorem to prove the following lower bound on the integrality ratio of
the natural relaxation.
Theorem 12. There are c > 0 and infinitely many positive integers k such that there is an instance of 0-
EXTENSION with k terminals for which the optimal value of the objective function is at least c
lg k times the
optimal value of the relaxation.
Proof. There are reals  > 0 and  such that there are infinitely many graphs G (known as expanders) such that
the maximum degree in G is at most  and such that for any subset S of at most jV (G)j=2 nodes, there are at least
jSj nodes not in S which are adjacent to at least one node of S. In fact, given a prime q  13 which is congruent
to 1 mod 4 (of which there are infinitely many), Lubotzky, Phillips, and Sarnak construct a 6-regular expander with
either q(q 2 1) or q(q 2 1)=2 nodes. (Take Given sufficiently large q, we use an
expander E) having need n  maxfn 0 ; 16g (n 0 to be
determined later). Define l = d
dlg nee  n and dn=le. Choose any k distinct nodes h
For new nodes and l new edges to the current graph, so as to get a new path P i starting at h i
and ending at some new node; label that new node i. When finished, let the new graph be G
vertices. jE
Now define an instance I of 0-EXTENSION as follows. The vertex set is V 0 . The set T of terminals is f1; 2; 3; :::; kg.
k, to be the distance in G 0 between i and j. Define c(u; v) to be 1 if uv
and c(u;
We now show that the integrality ratio for this instance I is large. First, we study the relaxation. Define -(u; v) to be
the distance in G 0 between u and v. It is clear that -(i; in T . It is also clear that - is a semimetric
on G 0 . It follows that
u<v c(u; v)-(u; adjacent vertices in G 0 are at distance 1).
Now we prove that there is a universal c > 0 such that any feasible solution to I , i.e., function
u<v c(u; v)d(f(u); f(v))  cn
lg n. Note first of all that the minimum distance
between two distinct terminals i; j is at least 2l  2
lg n. We will see below, however, that there are at least k=2
terminals for which the distance to terminal i  is at least  lg n,  a fixed positive constant, not just
lg n, for any
We need a lemma.
Lemma 13. For any i  2 T , there are at least k=2 vertices h i in G whose distance from h i  exceeds a = d lg k
Proof. For a contradiction, assume that there are more than k=2 vertices of G at distance at most a from h i  . By the
degree bound, the number of vertices in G at distance at most a from h i  is at most 1+ 1
Hence k=2 <  a+1 . Hence 1
Now choose n 0 large enough that
k, which is a function of n, must be at least 4 4 , giving us a contradiction.
Now we show that without loss of generality, every vertex in V 0 V in P i maps to i.
Lemma 14. Given
except that for all all the new vertices in path P i map under f 0 to i. Then f
u<v c(u; v)d(f(u); f(v))
Proof. Name the vertices on the i h i path v 0 (=
u<v
u<v
l 1
By the triangle inequality,
l 1
so the difference is nonpositive.
Let us assume from now on that maps the new vertices in P i to terminal i. Let R
ig. We have two cases.
lg n. Because G is an
expander and jR i j  n=2 for all i, for each i the number of edges uv, u is at least jR i j. Hence
lg n. (Each "cross edge" is counted
twice.)
Case 2: Some R i , say R 1 , has size exceeding n=2. We will use expansion and the max flow-min cut theorem
to prove our theorem.
Choose any dk=2e terminals i such that the distance in G between h i and h 1 is at least a = d lg k
13, they exist. Let F be the set of chosen terminals. Because n  16, a  lg n
4 lg  .
For each be the unique neighbor of h i in V 0 V . Let
Build a (directed) network N on V  [ fs; tg, s; t being new nodes, as follows. Start with the subgraph of G 0
induced by V  and replace each edge by a pair of antiparallel arcs, each of capacity one. Add arcs (u; t) for
all u each of capacity 1. Add arcs (s; x) for all x 2 X , each of capacity 1. Because R 1  V and
has a finite capacity s ! t cut defined by fsg [ X .
Now choose any finite capacity s ! t cut C
. (Possibly C be the set of arcs (u; v) with
S. By the expansion of G, jCj  jSj. Let Sg. Corresponding to each
F such that h i 62 S is an arc in total. Thus the total number of arcs in C  is at
least the penultimate inequality following from the fact that
either h i or x i is in S [M for all i 2 F . It follows that the minimum capacity of an s ! t cut in N is at least
k=2.
By the max flow-min cut theorem, there is a maximum s ! t flow which has value 0 or 1 on each arc. If the
flow on (u; v) and on (v; u) is 1 for some u 6= v, change the flow on both arcs to 0. The result is a maximum
flow that "uses" at most one of (u; v); (v; u) for any u 6= v. This flow can be decomposed into at
least k=2 arc-disjoint s ! t paths in N , such that for all u 6= v, at most one of (u; v); (v; u) appears in
any path. It follows that there are at least k=2 arc-disjoint paths from an x i with i 2 F to some vertex in
is such a path, then, using f(x i
have
a being at least lg n
. Since the
paths are arc-disjoint and there are at least k=2 of them, we infer that
4 lg  .
Using the definition of k, this last sum is at least (=(16 lg
lg n. Since we have a feasible solution to
(MET) of value at most jE 0 j  (=2 + 2)n, the ratio between the two is at least
lg k:
Choose and the proof of Theorem 12 is complete.
The following theorem shows that the above analysis is asymptotically tight. It also suggests an alternative rounding
procedure that for some instances performs better than the results in Section 2 (though in general it is far worse).
Theorem 15. There is a polynomial-time algorithm that takes as input a connected graph E) and a subset
of terminals and computes a function
where d(u; v) is the minimum number of edges in a path between u and v and d
Proof. Add a new vertex s to G and connect s to all the terminals. Run a breadth-first search starting at s, computing
for every node v 2 V its distance l(v) from s. Notice that for every
classes C i , for r be the smallest
positive integer such that jC r j  jEj=
d max . As
d max . We now define f . Let t be an
arbitrary terminal. For every t. For every v 2 V with l(v)  r, set
where t v is a terminal closest to v in G.
and at least one of the inequalities is strict. Therefore d(t
Consider an edge uv 2 C i . If i  r 1, then both l(u); l(v)  r, so d(f(u);
2. If i > r, then both l(u); l(v) > r, so d(f(u); For the remaining case
of we use the trivial bound d(f(u); f(v))  d max . Using the bounds on r and on jC r j, we have
i<r
uv2Cr
i>r
It is interesting to note that for bounded degree expanders the bounds are much better. Using arguments similar to
those of the proofs of Theorems 12 and 15, we can prove
Theorem 16. For every sufficiently large positive integer , there is a constant  > 0 such that for infinitely many
k there is an expander E) with maximum degree at most , jV j being O(k log k), and a set T  V of
size k, such that the integrality ratio of (MET) on the 0-extension instance defined by G, T , and the G-path metric
on T is at least  log log k. On the other hand, for every  there is a  such that for every n-node expander G of
maximum degree at most  and choice of terminals T , the integrality ratio of (MET) on the 0-extension instance
defined by G, T and the G-path metric on T is at most  log log n (and there is a polynomial-time algorithm that
achieves this bound).



--R

On approximating arbitrary metrics by tree metrics.
An improved approximation algorithm for multiway cut.
Optimal 3-terminal cuts and linear programming
Private communication
The complexity of multiway cuts.
The complexity of multiterminal cuts.

Approximate max-flow min-(multi)cut theorems and their applications

Rounding algorithms for a geometric embedding of minimum multiway cut.
Minimum 0-extension of graph metrics
Approximation through multicommodity flow.
Planar graphs

An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms
Ramanujan graphs.

--TR

--CTR
Howard Karloff , Subhash Khot , Aranyak Mehta , Yuval Rabani, On earthmover distance, metric labeling, and 0-extension, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
graph partitioning;linear programming relaxation;approximation algorithm;metric space