Finding Separator Cuts in Planar Graphs within Twice the Optimal.
A factor 2 approximation algorithm for the problem of finding a minimum-cost b-balanced cut in planar graphs is presented, for $b \leq {1 \over 3}$. We assume that the vertex weights are given in unary; for the case of binary vertex weights, a pseudoapproximation algorithm is presented. This problem is of considerable practical significance, especially in VLSI design.The natural algorithm for this problem accumulates sparsest cuts iteratively. One of our main ideas is to give a definition of sparsity, called  net-sparsity, that reflects precisely the cost of the cuts accumulated by this algorithm. However, this definition is too precise: we believe it is NP-hard to compute a minimum--net-sparsity cut, even in planar graphs. The rest of our machinery is built to work with this definition and still make it computationally feasible. Toward this end, we use several ideas from the works of Rao [ Proceedings, 28th Annual IEEE Symposium on Foundations of Computer Science, 1987, pp. 225--237;  Proceedings, 24th Annual ACM Symposium on Theory of Computing, 1992, pp. 229--240] and Park and Phillips [ Proceedings, 25th Annual ACM Symposium on Theory of Computing, 1993, pp. 766--775].
Introduction
Given an undirected graph with edge costs and vertex weights, the balance of a cut is the ratio
of the weight of vertices on the smaller side to the total weight in the graph. For
cut having a balance of at least b is called a b-balanced cut; a 1
-balanced cut is given the special
name of a separator. In this paper, we present a factor 2 approximation algorithm for finding a
minimum-cost b-balanced cut in planar graphs, for b - 1
3 , assuming that vertex weights are given
in unary. We also give examples to show that our analysis is tight. For the case of binary vertex
weights, we use scaling to give a pseudo-approximation algorithm: for each ff ? 2=b, it finds a
2=ff)-balanced cut of cost within twice the cost of an optimal b-balanced cut, for b - 1=3, in
time polynomial in n and ff. The previous best approximation guarantee known for b-balanced cuts
in planar graphs was O(log n), due to Rao [8, 9]; for general graphs, no approximation algorithms
are known.
The problem of breaking a graph into "small" sized pieces by removal of a "small" set of edges or
vertices has attracted much attention since the seminal work of Lipton and Tarjan [5], because this
opens up the possibility of a divide-and-conquer strategy for the solution of several problems on
the graph. Small balanced cuts have numerous applications, see for example, [1, 3, 4, 6]. Several
Max-Planck-Institut fur Informatik, Im Stadtwald, 66123 Saarbrucken, Germany.
y Department of Computer Science & Engineering, Indian Institute of Technology, New Delhi 110016, India.
z College of Computing, Georgia Institute of Technology, Atlanta, GA 30332. Supported by NSF Grant CCR-
of these applications pertain to planar graphs, the most important one being circuit partitioning
in VLSI design.
The sparsity of a cut is defined to be the ratio of the cost of the cut and the weight on its smaller
side, and a cut having minimum sparsity in the graph is called the sparsest cut . Rao [9] gave a2 -approximation algorithm for the problem of finding a sparsest cut in planar graphs, and recently
Park and Phillips [7] showed that this problem is polynomial time solvable. A sparsest cut limits
multicommodity flow in the same way that a min-cut limits max-flow. Leighton and Rao [3] derived
an approximate max-flow min-cut theorem for uniform multicommodity flow, and in the process
gave an O(log n)-approximation algorithm for finding a sparsest cut in general graphs. By finding
and removing these cuts iteratively, one can show how to find in planar (general) graphs, a b-
balanced cut that is within an O(1) factor (O(log n) factor) of the optimal b 0 -balanced cut for
3 [8, 9, 3]. For instance, using the Park-Phillips algorithm for sparsest cut in planar
graphs, this approach gives a 1-balanced cut that is within 7.1 times the cost of the best 1-balanced
cut in planar graphs. Notice however, that these are not true approximation algorithms, since the
best 1-balanced cut may have a much higher cost than the best 1-balanced cut.
This iterative algorithm has shortcomings due to which it does not lead to a good true approximation
algorithm; these are illustrated via an example in Section 3. One of our main ideas is to
give a definition of sparsity, called net-sparsity, that overcomes these shortcomings. The notion
of net-cost, on which this definition of net-sparsity is based, reflects precisely the cost of the cuts
accumulated iteratively. Indeed, it is too precise to be directly useful computationally - we believe
that computing the sparsest cut under this definition is NP-hard even in planar graphs. The rest
of our machinery is built to work with this definition and still make it computationally feasible,
and we manage to scrape by narrowly!
Planarity is exploited in several ways: First, a cut in a planar graph corresponds to a set of cycles
in the dual. Secondly, the notion of a transfer function turns out to be very useful. Given a planar
graph with weights on faces, this notion can be used to define a function on the edges of the graph
so that on any cycle it evaluates to the sum of the weights of the faces enclosed by the cycle.
Such an idea has been used in the past by Kasteleyn [2], for computing the number of perfect
matchings in a planar graph in polynomial time. Kasteleyn defined his function over GF [2]. Park
and Phillips [7] first defined the function over reals, thereby demonstrating the full power of this
notion.
Park and Phillips [7] have shown that the problems of finding a sparsest cut and a minimum b-
balanced cut in planar graphs are weakly NP-hard, i.e., these problems are NP-hard if the vertex
weights are given in binary. Indeed, the algorithm they give for finding the sparsest cut in planar
graphs is a pseudo-polynomial time algorithm. As a consequence of this algorithm, it follows that
if P 6= NP, finding sparsest cuts in planar graphs is not strongly NP-hard. On the other hand
it is not known if the b-balanced cut problem in planar graphs is strongly NP-hard or if there
is a pseudo-polynomial time algorithm for it (the present paper only gives a pseudo-polynomial
approximation algorithm). Park and Phillips leave open the question of finding a fully polynomial
approximation scheme for sparsest cuts in planar graphs, i.e., if the vertex weights are given in
binary. We give such an algorithm using a scaling technique.
Preliminaries
E) be a connected undirected graph, with an edge cost function c
vertex weight function . Any function that we define on the elements of a universe,
extends to sets of elements in the obvious manner; the value of the function on a set is the sum
of its values on the elements in the set. Let W be the sum of weights of all vertices in G. A
partition (S; S) of V defines a cut in G; the cut consists of all edges that have one end point in S
and the other in S. A set of vertices, S, is said to be connected when the subgraph induced on it is
connected. If either S or S is connected then cut (S; S) will be called a simple cut and when both
S and S are connected then the cut (S; S) is called a bond.
Given a set of vertices S ae V , we define the cost of this set, cost(S), as the sum of the costs of all
edges in the cut (S; S). The weight of the set S, wt(S), is the sum of the weights of the vertices
included in S.
A cut (S; S) is a separator if W- wt(S); wt(S) - 2W. The cost of a separator is the sum of the
costs of the edges in the separator.
Lemma 2.1 For any connected graph G there exists a minimum-cost separator, (S; S), which is a
simple cut. Further, if S is the side that is not connected, then each connected component of S has
weight strictly less than W
3 .
Proof: Let (S; S) be a minimum-cost separator in G. Consider the connected components obtained
on removing the edges of this separator. Clearly, no component has weight strictly larger than 2W
3 .
If all components have weight strictly less than Wthen both S and S are not connected and we can
arrive at a contradiction as follows. We first pick two components that have an edge between them
and then pick the remaining, one by one, in an arbitrary order till we accumulate a weight of at
least W. The accumulated weight can not exceed 2Wsince each component has weight at most WThus we obtain a separator of cost strictly less than the cost of the separator (S; S); a contradiction.
Hence, at least one component has weight between Wand 2W. If there are two such components
then these are the only components since by switching the side of a third component we obtain a
cheaper separator. If there is only one component of weight between Wand 2Wthen this separator
is optimum iff this component forms one side of the cut and the remaining components the other
side. Thus (S; S) is a bond and if some side of the cut is not connected then all components on
that side have weight strictly less than W
3 .
Hence there always exists a minimum-cost separator that is a simple cut. Let OPT denote the set
of vertices on the side of this separator that is not connected.
3 Overview of the algorithm
Let S be a set of vertices such that wt(S) - wt(S). The sparsity of S is usually defined as the
quotient of the cost and the weight of this set, i.e.
Figure

1: Graph with vertex weights and edge costs showing how minimum sparsity increases. Here natural approach to finding good separators is to repeatedly find a set of minimum sparsity and
remove it from the graph; eventually reporting the union of the removed vertices. It is easy to
concoct "bad" examples for this approach by ensuring that the picked vertices always come from
the smaller side of the optimal separator, and thereby ensuring that the minimum sparsity available
in the remaining graph keeps increasing. This is illustrated in Figure 1; here the first cut picked
has a sparsity of 1
m whereas the last cut has a sparsity of 1
.
This approach has two shortcomings: it removes the vertices picked in each iteration and deals only
with the remaining graph in subsequent iterations, and it assumes that edges of the cuts found in
each iteration are picked permanently, even though they may not be needed in the final cut. One
of our main ideas is to give a definition of "sparsity" under which this algorithm does not suffer
from either of these shortcomings.
be two sets of vertices. Define, the net-cost of S with respect to T as,
net-cost
and the net-weight of S with respect to T as,
net-weight
Thus, if we have already picked the set of vertices T , then net-cost T (S) measures the extra cost
incurred and net-weight T (S) the weight added, in picking the set S [ T . Finally, define the net-
sparsity of S with respect to T as
net-sparsity net-cost T (S)
net-weight
For any algorithm that picks a cut by accumulating sets of vertices, the notion of net-cost gives
precisely the extra cost incurred in each iteration. But is it so precise that computing the sparsest
cut under this definition turns out to be NP-hard even in planar graphs? Although we do not have
an answer to this question, we believe that it is "yes"! Indeed, the rest of our machinery is built to
work with this definition and still make it computationally feasible, and we manage to scrape by
Let us first show that it is not sufficient to just keep picking sets of minimum net-sparsity. Consider
the following example: Suppose very sparse set of weight W\Gamma ffl, and
S 2 is a set of high sparsity and weight ffl, for a small ffl. Having picked S 1 , we might pick another
set, S 3 of sparsity almost that of S 2 , and weight W\Gamma ffl, and hence, the cost incurred would be
arbitrarily high compared to the optimum.
We get around this difficulty by ensuring that in each iteration the set of vertices we pick is such
that the total weight accumulated is strictly under W
3 . More formally: Let T i\Gamma1 be the set of
vertices picked by the end of the (i-1) th iteration (T In the i th iteration we pick a set D i
such that
[minimality] D i has minimum net-weight among all sets satisfying the above conditions.
We call set D i a dot and denote it by ffl. Thus, at the end of the i th iteration the set of vertices we
have picked is given by T . This is how we augment the "partial solution"
in each iteration.
How do we ever obtain a "complete solution" (a separator)? In the i th iteration, besides augmenting
the partial solution T i\Gamma1 to the partial solution T i we also augment it to a complete solution, i.e.
we pick a set of vertices B i such that
3 .
finding the set B 1 corresponds to finding the minimum-cost separator. To avoid this
circularity in the argument we restrict B i to a smaller class of sets:
is a bond and W- wt(T
We call the set B i a box and denote it by 2. Notice that a box set need not be a bond, and
that we count a 2 at its cost rather than its net-cost. This is done only to simplify the algorithm
and its analysis. The example which shows that the analysis of our algorithm is tight also shows
that counting the 2 at its net-cost would not have led to any improvement in the approximation
guarantee.
So, in each iteration we obtain a separator. The solution reported by the algorithm is the one of
minimum cost from among all these separators. The algorithm, which we call the dot-box algorithm
is the following.
Algorithm Dot-Box Algorithm;
1. minsol /1, i / 0, T 0 / OE
2. while wt(T
2.1.
2.2. Find ffl and 2 sets, D i and B i respectively.
If there is no ffl set, exit.
2.3. minsol / min(minsol; cost(T
2.4.
end.
We make two remarks regarding step (2.2): First, we conjecture that finding the ffl set is NP-hard.
Our procedure to find ffl sets may not always succeed; however, we will prove that if it fails, then the
set found in the current iteration gives a separator within twice OPT. Second, at some iteration
it might be the case that no subset of vertices satisfies the weight criterion for a ffl, since each set
takes the total weight accumulated to W=3 or more. In this case, the Dot-Box Algorithm halts,
and outputs the best separator found so far.
4 Analysis of the Dot-Box Algorithm
We first prove some properties of net-cost and net-weight which will be useful for the analysis.
From the definition of net-cost and net-weight we have that net-cost T net-cost
net-weight The following property also follows from the
definitions
Property 4.1 Let S 1 be two sets of vertices not necessarily disjoint. Then
net-cost net-cost net-cost T[S 1
net-weight
Property 4.2 net-cost T (S) - net-cost S"T (S).
Proof:

Figure

2 shows the edges between the sets from which the
above property is immediate. The net-cost of S with respect to S " T may be higher because it
includes the cost of edges from S \Gamma T to T \Gamma S.
The following property is immediate from Figure 3.

Figure

2: Computation of net-cost T (S) and net-cost S"T (S). A +/- on an edge signifies that the edge is
counted in the positive/negative term in the net-cost computation.

Figure

3: Computation of net-cost T net-cost T (S 1 )+net-cost T (S 2 ).
Property 4.3 Let S 1 be two disjoint sets of vertices with no edges between them. Then
net-cost net-cost net-cost T (S 2 )
Remark 4.1 For positive real numbers a; b; c; d,
min( a
d
- max( a
d
Further, let a positive real numbers. Then, such that a i
Lemma 4.1 The net-sparsity of the ffl's is increasing, i.e.
Proof: Since the set D i [ D i+1 satisfies the weight requirement for a ffl at the i th iteration,
net-sparsity T
By Property 4.1,
net-cost T net-cost T net-cost
net-weight T
which using Remark 4.1 gives us:
min(net-sparsity T
Now, by the first inequality, it must be the case
max(net-sparsity T
The lemma follows.
Let k be the first iteration at which some connected component of OPT meets the weight requirement
of a 2.
Lemma 4.2
Proof: Since OPT 6' T i\Gamma1 there are connected components of OPT which are not completely
contained in T i\Gamma1 . By assumption, none of these components satisfies the weight requirement for
a 2; hence each of these components meets the weight requirement for a ffl. Hence the ffl picked in
this iteration should have net-sparsity at most that of any of these components.
By Property 4.3, the net-cost of OPT is the sum of the net-costs of these components of OPT.
The same is true for net-weight and hence the component of OPT with minimum net-sparsity has
net-sparsity less than that of OPT. The lemma follows.
The above two lemmas imply that the net-sparsity at which the ffl's are picked is increasing and
that for any iteration before the k th , this net-sparsity is less than the net-sparsity of OPT in that
iteration.
Lemma 4.3
Proof: To establish this inequality for i we consider two processes:
1. The first process is our algorithm which picks the set of vertices D j at the j th step, 1
2. The second process picks the vertices " OPT at the j th step, 1 At the i th step it
picks the remaining vertices of OPT.
Let P j be the set of vertices picked by the second process in the first j steps. Then
OPT. At the j th step the second process picks an additional weight of
net-weight P at a cost of net-cost P By the fact that the second process picks a subset
of what the first process picks at each step we have:
4.1 For
4.2 For
4.2 we have
net-cost T net-cost P
Further,
net-weight T
and hence net-sparsity T
the claim follows since P j satisfies the weight requirement for a ffl and D j was picked as
the ffl. For and the claim follows from Lemma 4.2.
The above claims imply that in each iteration (1 through i) the first process picks vertices at a
lower net-sparsity than the second process. If both these processes were picking the same additional
weight in each iteration then this fact alone would have implied that the cost of the vertices picked
by the first process is less than the cost of the vertices picked by the second. But this is not the case.
What is true, however, is the fact that in iterations 1 through i-1 the first process picks a larger
additional weight than the second process. In the i th iteration, the second process picks enough
additional weight so that it now has accumulated a total weight strictly larger than that picked
by the first process (since wt(OPT) - W? wt(T i )). But the net-sparsity at which the second
process picks vertices in the i th iteration is more than the maximum (over iterations 1 through
i) net-sparsity at which the first process picks vertices. So it follows that the cost of the vertices
picked by the first process is strictly less than the cost of the vertices picked by the second, i.e.
Consider the separator found in the k th iteration, i.e. the cut (T This solution
is formed by picking ffl's in the first k-1 steps and a 2 in the k th step.
Lemma 4.4 cost(T

Figure

4: A tight example for our analysis. Vertex weights and edge costs are given and
Proof: Any connected component of OPT is a bond. In the k th iteration there exists a connected
component of OPT, say OPT j such that W- wt(T Hence the 2 at the k th
step should have cost at most cost(OPT j ), i.e.
From Lemma 4.3 we know that cost(T Hence
Since the Dot-Box Algorithm outputs the best separator found, we have:
Theorem 4.5 The cost of the separator found by the Dot-Box Algorithm is at most twice the
cost of OPT.
Our analysis of the Dot-Box Algorithm is tight; when run on the example in Figure 4, it
picks a separator of cost almost twice the optimum. In this example,
ffl. For ffl ? 3=n, the ffl in the first iteration is the set C and the 2 is the set A.
This separator, which is also the one returned by the Dot-Box Algorithm, has cost
hence the approximation ratio is 2
5 Structural properties of our solution, and a computationally
easier definition of net-cost
In this section we prove some structural properties of the solution found by the Dot-Box Algorithm.
This allows us to redefine net-cost in such a manner that it becomes computationally easier and
yet the analysis from the previous section continues to hold.
Lemma 5.1 For
Proof: For contradiction assume that T i is not connected. Let A be a connected component of T i .
There are three cases:
W=3 The set A satisfies the weight requirement for a ffl at the (i+1) th iteration.
Since A has edges only to vertices in T i , the net-cost of A with respect to T i is negative.
Hence net-sparsity T i (A) is negative, contradicting Lemma 4.1.
The cut is a separator of cost, cost(T i [ contradiction

the condition of this case implies that wt(A) ? W=3. If wt(A) - 2W=3
then once again we have a contradiction since now the cut (A; A) is a separator of cost,
cost(OPT). Thus it must be the case that wt(A) ? 2W=3.
Since the above argument implies that each connected component of T i has weight greater than
must have only one connected component.
Lemma 5.2 For
Proof: For contradiction assume that T is not connected. Let A be a connected component
of be the rest of T also denote by A; B the corresponding sets of
vertices).
If D i is the ffl at the i th iteration then net-cost T net-cost T are
disjoint set of vertices with no edges between them, by Property 4.3
net-cost T net-cost net-cost
Further,
net-weight T
Thus either it is the case that one of A; B has smaller net-sparsity than D i which contradicts the
assumption that D i is a ffl or else, both A; B have the same net-sparsity as D i but this contradicts
the minimality requirement on D i .
Lemma 5.3 For every iteration there exists a ffl, D i , satisfying
1. (D
2. Each connected component of T i\Gamma1 is contained in D i or D i and there is no edge between D i
and components of T i\Gamma1 in D i .
Proof: The set T together with any subset of T i\Gamma1 is also a ffl for the i th iteration. We form
a new ffl, D i , by merging with connected components of T which have an edge to
connected, so is D i . Further, since the graph is connected, every
remaining component of T i\Gamma1 has an edge to T i so that D i is also connected. Thus (D
bond. It follows from the definition of D i that there is no edge between D i and components of T
in D i .
Since every ffl in iterations 1 through the conditions in Lemma 5.3, we can restrict our
search for the ffl at the i th iteration to sets that satisfy these conditions as additional requirements.
(D
Each connected component of T i\Gamma1 is contained in D i or D i and there is no edge between
D i and components of T i\Gamma1 in D i .
be the graph obtained by shrinking each connected component of T i\Gamma1 into a
single vertex, removing the self-loops formed and replacing each set of parallel edges by one edge
of cost equal to the sum of the cost of the edges in the set. For finding a ffl at the i th iteration
we consider only such sets, S, such that no connected component of T i\Gamma1 is split across (S; S) and
(S; S) is a bond. Therefore we need to look only at subsets of V i that correspond to bonds in G i .
Let S be a subset of vertices in G i . The trapped cost of S with respect to T i\Gamma1 , denoted by
trapped-cost T i\Gamma1 (S), is the sum of the costs of the components of T i\Gamma1 that are contained in S. We
now redefine the net-cost of S with respect to T i\Gamma1 as
net-cost T trapped-cost T
Note that for any subset of vertices in G i , the net-cost under this new definition is at least as
large as that under the previous definition. However, and this is crucial, the net-cost of the ffl set
remains unchanged. This is so because by Lemma 5.3 there are no edges between D i and the
components of T i\Gamma1 not in D i . Therefore, a ffl under this new definition of net-cost will also be a ffl
under the previous definition, and so our analysis of the Dot-Box Algorithm continues to hold.
6 Onto planar graphs
We do not know the complexity of computing ffl sets; we suspect that it is NP-hard even in planar
graphs. Yet, we can implement the Dot-Box Algorithm for planar graphs - using properties
of cuts in planar graphs, and by showing that if in any iteration, the algorithm does not find the ffl
set, then in fact, the separator found (using the 2 set found in this iteration) is within twice the
optimal (this is proven in Theorem 7.1).
6.1 Associating cycles with sets
Let G D be the planar dual of G and we fix an embedding of G D .
Proposition 6.1 There is a one-to-one correspondence between bonds in G and simple cycles in
G D .
Proof: Let (S; S) be a bond in G. Since S is connected, the faces corresponding to S in G D are
adjacent and so the edges of G D corresponding to (S; S) form a simple cycle.
For the converse, let C be a simple cycle in G D which corresponds to the cut (S; S) in G. Let u; v
be two vertices in G that are on the same side of the cut (S; S). To prove that (S; S) is a bond it
suffices to show a path between u and v in G that does not use any edge of (S; S).
Embed G and G D in R \Theta R, and consider the two faces of G D corresponding to vertices u and v.
Pick an arbitrary point in each face, for instance, the points corresponding to u and v. Since C is a
simple cycle in G D (and hence in R \Theta R) there is a continuous curve (in R \Theta R) that connects the
two points without intersecting C. By considering the faces of G D that this curve visits, and the
edges of G D that the curve intersects, we obtain a path in G that connects vertices u; v without
using any edge of (S; S).
Since for finding a ffl and 2 we only need to consider sets, S, such that (S; S) is a bond, we can
restrict ourselves to simple cycles in G D . Furthermore, the two orientations of a simple cycle can be
used to distinguish between the two sides of the cut that this cycle corresponds to. The notation we
adopt is: with a cycle C directed clockwise we associate the set of faces in G D (and hence vertices
in G) enclosed by C (the side that does not include the infinite face is said to be enclosed by C
and the side containing the infinite face is said to be outside C).
Let ~
G D be the graph obtained from G D by replacing each undirected edge (u; v) by two directed
edges u). By the preceding discussion, there exists a correspondence between
sets of vertices, S, in G such that (S; S) is a bond and directed simple cycles in ~
G D .
6.2 Transfer function
We associate a cost function, c, with the edges of ~
G D in the obvious manner; an edge in ~
G D is
assigned the same cost as the corresponding dual edge in G. Thus, for a directed cycle, C, c(C),
denotes the sum of the costs of the edges along the cycle. We would also like to associate functions,
with the edges of ~
G D so that if S is the set corresponding to a directed simple cycle C,
trapped-cost T We achieve this by means of a
transfer function.
The notion of a transfer function was introduced by Park and Phillips [7], and can be viewed as
an extension of a function given by Kasteleyn [2]. A function g defined on the edges of ~
G D is
u). (Notice that the function c defined above is symmetric.)
R be a function on the vertices of G. The transfer function corresponding to f is an
anti-symmetric function, f t , on the edges of ~
G D such that the sum of the values that f t takes on
the edges of any clockwise (anticlockwise) simple cycle in ~
G D , is equal to the (negative of the) sum
of the values that f takes on the vertices corresponding to the faces enclosed by this cycle.
That a transfer function exists for every function defined on the vertices of G and that it can be
computed efficiently follows from the following simple argument. Pick a spanning tree in G D , and
set f t to zero for the corresponding edges in ~
G D . Now, add the remaining edges of G D in an order
so that with each edge added, one face of this graph is completed. Note that before the edge e is
added, all other edges of the face that e completes have been assigned a value under f t . One of the
two directed edges corresponding to e is used in the clockwise traversal of this face, and the other
in the anti-clockwise traversal. Since the value of f for this face is known and since f t should sum
to this value (the negative of this value) in a clockwise (anti-clockwise) traversal of this face, the
value of f t for the two directed edges corresponding to e can be determined. Note that the function
obtained in this manner is anti-symmetric and this together with the fact that the edges of any
simple cycle in G D can be written as a GF [2] sum of the edges belonging to the faces contained in
the cycle implies that f t has the desired property.
7 Finding ffl sets
Recall that a ffl at the i th iteration is a bond in the graph G hence we can restrict
our search for a ffl at the i th iteration to directed simple cycles in ~
G D
7.1 Obtaining net-weight and net-cost from transfer functions
Let ~
be two functions defined on the vertices of G i as follows. The
vertices in V i obtained by shrinking connected components of T i\Gamma1 have ~
equal to the
cost of the corresponding component of T i\Gamma1 . The remaining vertices have ~
denote the transfer functions corresponding to functions ~
We now relate the values of
the functions c; on a directed simple cycle to the net-cost, net-weight and net-sparsity of the
set corresponding to the cycle.
Let C be a directed simple cycle in ~
G D
i and S ae V the set corresponding to it. If C is clockwise
then the net-weight and trapped-cost of S are given by the values of the transfer functions on C,
i.e.
net-weight T
trapped-cost T
If C is anti-clockwise then the values of the transfer functions w equal the negative of the
net-weight and the trapped-cost of the set enclosed by C (which is S in our notation). Hence
net-weight T
trapped-cost T trapped-cost T
Recalling our new definition of net-cost
net-cost T trapped-cost T
We conclude that if C is clockwise
net-sparsity T
and for anti-clockwise C,
net-sparsity T
Hence, for a simple directed cycle C, once we know the values of the transfer functions w
is easy to determine the net-weight and net-sparsity of the corresponding set S. Note that the
orientation of C can be determined by the sign of w i (C) since w implies that
C is clockwise (anti-clockwise).
7.2 The approach to finding a ffl
For a fixed value of w i (C), net-sparsity T i\Gamma1 (S) is minimized when
suggests the following approach for finding a ffl:
For each w in the range (0 - w - W
compute min-cycle(w): a directed simple cycle with minimum
directed cycles C with w Find the net-sparsity of the set corresponding to
each of these cycles. The set with the minimum net-sparsity is the ffl for this iteration.
However, we can implement only a weaker version of procedure min-cycle. Following [7], we
construct a graph H i whose vertices are 2-tuples of the kind (v; is a vertex in ~
G D
j is an integer between \GammanW and nW . For an edge
G D
i we have, for all possible
choices of j, edge (u; (e). The shortest path between (v;
and (v; w) in H i gives the shortest cycle among all directed cycles in ~
G D
which contain v and for
which w i By doing this computation for all choices of v, we can find the shortest cycle
with
Two questions arise:
1. Is negative cycles? This is essential for computing shortest paths efficiently.
2. Is the cycle obtained in ~
G D
The answer to both questions is "no". Interestingly enough, things still work out. We will first
tackle the second question (in Theorem 7.1), and then the first (in Lemma 7.2).
7.3 Overcoming non-simple cycles
Before we discuss how to get over this problem, we need to have a better understanding of the
structure of a non-simple cycle, C. If C is not a simple cycle in ~
G D
arbitrarily into
a collection of edge-disjoint directed simple cycles, C. Let (S be the cut (in G i ) corresponding
to a cycle C be the side of the cut that has smaller net-weight. Further, let S be
the collection of sets S j , one for each C j 2 C.
trapped-cost T
\Gammatrapped-cost T
trapped-cost T
trapped-cost T

Figure

5: Relationship between net-weight T
(S) and w i (C) for the four cases.
The value of the transfer functions w is the sum of their values over the cycles C j in the
collection C. Also,
For each cycle C we need to relate the net-weight, trapped-cost of S j to the value of the
transfer functions w might either be clockwise or anti-clockwise. Further S j might
either be inside C j or outside C j . This gives us a total of four different cases. The relationship
between net-weight T trapped-cost T Figure 5
and can be captured succinctly as follows
trapped-cost T
\Gamma1g.
Hence we get a decomposition rule relating the value of the functions w on a non-simple cycle
C to the net-weight and trapped-cost of the sets induced by this cycle.
trapped-cost T
is an integer.
7.4 A key theorem
Let D i be a ffl at the i th iteration (i - the directed simple cycle in ~
G D
corresponding
to it. Further, let C be the directed cycle reported by min-cycle(w i (C   )).
Theorem 7.1 If C is not simple then the separator found in this iteration has cost at most 2 \Delta
cost(OPT), i.e.
Proof: Since C is the directed cycle for which among all cycles with
claim the following.
If C   is clockwise, i.e. w i (C
net-cost T
and if C   is anti-clockwise, i.e. w i (C
net-cost T
Substituting for w i (C) and t i (C) by the decomposition rule we get
\Gammaz \Delta cost(T
trapped-cost T net-cost T
where z is x if C   is clockwise and x
We now prove that there exists S j 2 S which meets the weight requirement for a 2 and has cost
no more than the cost of T i , i.e,
1. W- wt(T net-cost T
Assume for contradiction that no such exists. The following observations about the cost/net-cost
of a set S j 2 S are immediate.
Observation 7.1 if net-weight T
net-cost T
which implies
net-cost T net-cost T
Observation 7.2 if net-weight T
net-sparsity T
and hence
net-cost T
From the above two observations it follows that
Observation 7.3 All sets S j 2 S have non-negative net-cost, i.e. net-cost T
The idea behind obtaining a contradiction is as follows. For every integral choice of z we use
equation 1 to provide a lower bound on the total net-weight of the sets S j 2 S and equation 2 to
provide an upper bound on the total net-cost of the sets S j 2 S. We then use the above observations
on the cost/net-cost of sets S j 2 S to argue that there is no way of having sets with so large a total
net-weight at so little a total net-cost.
We shall consider 3 cases depending upon whether z is positive/negative/zero.
Equation 2 implies
net-cost T
trapped-cost T
net-cost T
and from equation 1 we have
net-weight T
net-weight T
Since the net-cost of each set is non-negative (Observation 7.3) each set in S has net-cost no
more than net-cost T (D i ). This in turn implies that every set in S has net-weight strictly
less than W=3 \Gamma wt(T Thus every set in S meets the weight requirement
for a ffl. Since the net-cost of every set in S is non-negative, Remark 4.1 applied to the above
two inequalities implies that either there exists S j 2 S of lower net-sparsity than D i or that
every set in S has the same net-sparsity as D i and that the sum of the net-weight of the sets
in S is equal to the net-weight of D i . The first setting leads to a contradiction since every
set in S satisfies the weight requirement for a ffl and D i is the ffl at this iteration. The second
setting in turn contradicts the minimality requirement on D i .
denote the collection of sets S j 2 S with y now yields
net-cost T
trapped-cost T
trapped-cost T
where the second inequality follows from the fact that all sets in S non-negative
net-cost. We shall develop a contradiction by showing that the costs of the sets in S \Gamma is more
than the left hand side of the above inequality. A lower bound on the total net-weight of the
sets in S \Gamma can be obtained from equation 1 as follows
net-weight T
What is the cheapest way of picking sets so that their net-weight is at least z(W \Gamma wt(T
net-weight T 7.2 a set S j such that net-weight T
can be picked only at a net-sparsity of at least net-sparsity T On the other
hand Observation 7.1 says that we could be picking sets with large net-weight for cost little
more than cost(T net-cost T any set in S has net-weight at most
cost of picking these large sets could be as small as
net-cost T
net-cost T
net-cost T
net-weight T
net-sparsity T
where the last inequality follows from the fact that sparsity(T
which in turn is a consequence of Lemma 4.1.
Thus the cheapest possible way of picking sets is to pick sets of net-weight W \Gammawt(T
incurring a cost of little more than cost(T net-cost T for each set picked. Since we
need to pick a net-weight of at least z(W \Gamma wt(T would have to
pick at least 2z \Gamma 1 such sets and so the cost incurred is at least
net-cost T
net-cost T
where the last inequality follows from the fact that z - 1 (hence
This however contradicts the upper bound on the sum of the costs of the sets in S \Gamma , that we
derived at the beginning of this case.
denote the collection of sets S j 2 S with y Equation 2 now yields
net-cost T
trapped-cost T
net-cost T
The total net-weight of the sets in S + can be bounded using equation 1 as follows.
net-weight T
net-weight T
where the last inequality follows from the fact that the net-weight of D i is non-negative.
What is the cheapest way of picking sets so that their net-weight is at least \Gammaz(W \Gamma wt(T
Once again by Observation 7.2 a set S j of net-weight less than W
can be picked
only at a net-sparsity of at least net-sparsity T On the other hand Observation 7.1
says that we could be picking a set of net-weight as large as (W \Gamma wt(T i\Gamma1 ))=2 for a net-cost
that is only strictly larger than net-cost T
net-cost T
net-cost T
net-weight T
net-sparsity T
the cheapest possible way of picking sets is to pick sets of net-weight W \Gammawt(T
2 and incur
a net-cost strictly larger than net-cost T for each set picked. Since we need to pick a
net-weight of at least \Gammaz(W \Gamma wt(T i\Gamma1 )), we should pick at least \Gamma2z such sets. Since z - \Gamma1,
the total net-cost of these sets is strictly larger than net-cost T contradicting the upper
bound derived at the beginning of this case.
We have thus established that there exists a set S j 2 S which meets the weight requirement for a
2 and has cost no more than cost(T i ). Further, S j corresponds to a directed simple cycle in ~
G D
Our procedure for finding a 2 returns a set of cost less than the cost of any set that meets the
weight requirement for a 2 and corresponds to a directed simple cycle in ~
G D . Hence
Therefore
where the last inequality follows from Lemma 4.3 and the fact that i - k \Gamma 1.
For each w in the range [0:: W
suffices to find in G i a
directed cycle (not necessarily simple) with minimum among all directed cycles C
with some w the shortest cycle is not simple we discard the cycle and do not
consider that w for the purpose of computing the ffl. If in the process we discard the cycle with
then by the above theorem the separator found in this iteration is within twice
the optimum. Else, we obtain a simple cycle C with w and the set corresponding to
this cycle is a ffl.
Finally we have to deal with the case that there are negative cycles in H i . A negative cycle in H i
corresponds to a cycle C in ~
G D
i such that w i
Lemma 7.2 If C is a cycle in ~
G D
i such that w i then the separator
found in this iteration has cost at most 2 \Delta cost(OPT).
Proof: The proof of this lemma is along the lines of Theorem 7.1. We decompose C into a collection
C of directed simple cycles. For C be the side of the cycle with smaller net-weight and
let S be the collection of sets S j , one for each C j 2 C. Using the decomposition rule we have
\Gammaz \Delta cost(T
trapped-cost T
For contradiction we assume that every S j 2 S which satisfies the weight requirement for a 2 has
cost more than cost(T i ). By Observation 7.3 every set S j 2 S has non-negative net-cost. Hence
equation 4 yields
z
trapped-cost T
trapped-cost T
which implies that z ? 0.
A lower bound on the total net-weight of sets in S \Gamma can be obtained using equation 3.
net-weight T
Beyond this point the argument is almost identical to that for the case when z ? 0 in the proof
of Theorem 7.1. This contradicts our assumption that every set S j 2 S which meets the weight
requirement of a 2 has cost more than cost(T i ). As in the proof of Theorem 7.1, the 2 picked
in this iteration has cost at most cost(T i ) and hence the cost of the separator output is at most
By Lemma 7.2, we need to compute shortest paths in graph H i only if it has no negative cycles.
Finding 2 sets
We will use Rao's algorithm [8, 9] to find a 2 set. Let be a weight function on
the vertices of G such that in the i th
iteration, then (B b-balanced bond in G when the weights on the vertices are given by w
to find the 2 we need to find the minimum-cost simple cycle in G D
which corresponds to a b-balanced bond in G.
Rao [8, 9] gives an algorithm for finding a minimum cost b-balanced connected circuit in G D . A
connected circuit in G D is a set of cycles in G D connected by an acyclic set of paths. Intuitively,
a connected circuit can be viewed as a simple cycle with 'pinched' portions corresponding to the
paths. The cost of a connected circuit is defined to be the cost of the closed walk that goes through
each pinched portion twice and each cycle once. A connected circuit in G D defines a simple cut in
G; the vertices corresponding to faces included in the cycles of the connected circuit form one side
of the cut. A connected-circuit is b-balanced if the cut corresponding to it is b-balanced. Note that
the cost of the cut defined by a connected circuit is just the sum of the costs of the cycles in it.
Hence, the definition of cost of a connected circuit is an upper bound on the cost of the underlying
cut; the two are equal if the connected circuit is a simple cycle.
Notice that for a 2 we do not really need to find a minimum-cost b-balanced bond in G; any cut
that is b-balanced and has cost no more than the minimum-cost b-balanced bond will serve our
purpose. Hence we can use Rao's algorithm to find a 2. The total time taken by Rao's algorithm
to obtain an optimal b-balanced connected circuit cut is O(n 2 W ).
9 Running time
Clearly, the algorithm terminates in at most n iterations. The running time of each iteration
is dominated by the time to find a ffl. In each iteration, computing a ffl involves O(n) single
source shortest path computations in a graph with O(n 2 W ) vertices and O(n 2 W ) edges; the edge-
lengths may be negative. This requires O(n 4 W 2 log nW using Johnson's extension of the
all-pairs shortest path algorithm of Floyd and Warshall. Hence, the total running time of the
Dot-Box Algorithm is O(n 5 W 2 log nW ). This is polynomial if W is polynomially bounded.
Theorem 9.1 The Dot-Box Algorithm finds an edge-separator in a planar graph of cost within
twice the optimum, and runs in time O(n 5 W 2 log nW ), where W is the sum of weights of the
vertices.
Dealing with binary weights
The size of the graph in which we compute shortest paths (and hence the running time of the
Dot-Box Algorithm) depends on the sum of the vertex weights. Using scaling we can make
our algorithm strongly polynomial; however, the resulting algorithm is a pseudo-approximation
algorithm in the sense that it compares the cut obtained with an optimal cut having a better
balance. Finally, we use our scaling ideas to extend the algorithm of Park and Phillips into a fully
polynomial approximation scheme for finding sparsest cuts in planar graphs with vertex weights
given in binary, thereby settling their open problem.
10.1 b-balanced cut
Let us scale the vertex weights so that the sum of the weights is no more than ffn (ff ? 1). This
can be done by defining a new weight function -
The process of obtaining the new weights can be viewed as a two step process: first we scale the
weights by a constant factor ffn
W and then truncate. The first step does not affect the balance of any
cut since all vertex weights are scaled by the same factor. However, the second step could affect
the balance of a cut. Thus a cut (S; S) with balance b under the weight function wt might have a
worse balance under -
wt since all vertices on the side with smaller weight might have their weights
truncated. However, the total loss in weight due to truncations is at most n (1 for each vertex).
The balance would be worst when the total weight stays at ffn (not drop by the truncations) and
then the loss of weight of the smaller side is a 1=ff fraction of the total weight. Thus the balance
of the cut (S; S) under -
wt might be b \Gamma 1=ff but no worse.
Similarly a cut (S; S) with balance - b under -
wt might have a worse balance under wt. It is easy to
show by similar a argument that under wt, (S; S) has a balance no worse than -
Let OPT denote the cost of the optimum b-balanced cut under the weight assignment wt. Since this
cut might be (b \Gamma 1=ff)-balanced under -
wt, we use the Dot-Box Algorithm to find a (b \Gamma 1=ff)-
balanced cut of cost within 2OPT. The cut returned by our algorithm, while being (b \Gamma 1=ff)-
balanced under -
wt, might only be (b \Gamma 2=ff)-balanced under wt. Thus we obtain a (b \Gamma 2=ff)-balanced
cut of cost within twice the optimum b-balanced cut.
Theorem 10.1 For ff ? 2=b, the Dot-Box Algorithm, with weight scaling, finds a (b \Gamma 2=ff)-
balanced cut in a planar graph of cost within twice the cost of an optimum b-balanced cut for b - 1
in O(ff 2 n 7 log nff) time.
10.2 Sparsest cut
Assume that vertex weights in planar graph G are given in binary. Let 2 p be the least power of
2 that bounds the weight of each vertex and let W be the sum of weights of all vertices. We
will construct each having the same edge costs as G. In G i ,
vertex weights are assigned as follows: Let ff be a positive integer; ff determines the approximation
guarantee as described below. Vertices having weights in the range [2 are assigned
their original weight, those having weight are assigned weight 0, i.e., they can be deleted from
the graph, and those having weight ? 2 i+2 log n+ff+2 are assigned weight 2 i+2 log n+ff+2 . The sparsest
cut is computed in each of these graphs using the algorithm of Park and Phillips. For the purpose
of this computation, the weights of all vertices in G i are divided by 2 notice that this leaves the
weights integral, and the total weight of vertices is at most O(2 ff n 3 ). The running time of [7] is
O(n 2 w log nw), where w is the total weight of vertices in the graph. So, this computation takes
time O(ff2 ff n 5 log W log n), which is polynomial in the size of the input, for fixed ff. The sparsity
of the cuts so obtained is computed in the original graph, and the sparsest one is chosen.
Let (S; S) be an optimal sparsest cut in G, and let S be its lighter side. Let the weight of S
be t, and let q be the weight of the heaviest vertex in S. Pick the smallest integer i such that
Lemma 10.2 The cut found in G i has cost at most that of (S; S), and weight at least
Therefore this cut has sparsity within a factor of 1
of the sparsity of (S; S).
Proof: The algorithm of Park and Phillips searches for the cheapest cut of each weight, for all
choices of weight between 0 and half the weight of the given graph. It then outputs the sparsest of
these cuts.
First notice that for the choice of i given above, the weight of S in G i , say t
t. Indeed, any set of vertices whose weights are at most 2 i+2 log n+ff+2 in G satisfies that its
weight drops by a factor of at most
. On the other hand, any set of vertices containing
a vertex having weight ? 2 i+2 log n+ff+2 in G has weight exceeding t in G i . Therefore, the cut found
in G i for the target weight of t 0 satisfies the conditions of the lemma.
For a given choice of ffi ? 0, pick the smallest positive integer ff so that 1
. Then, we
get the following:
Theorem 10.3 The above algorithm gives a fully polynomial time approximation scheme for the
minimum-sparsity cut problem in planar graphs. For each ffi ? 0, this algorithm finds a cut of
sparsity within a factor of (1 + ffi) of the optimal in O( 1
log n) time.
Open problems
Several open problems remain:
1. Is the problem of finding the cheapest b-balanced cut in planar graphs strongly NP-hard, or
is there a pseudo-polynomial time algorithm for it?
2. What is the complexity of finding a minimum net-sparsity cut in planar graphs, assuming
that the vertex weights are given in unary?
3. What is the complexity of finding ffl sets in planar graphs, assuming that the vertex weights
are given in unary?
4. Can the algorithm given in this paper be extended to other submodular functions?
5. Can it be extended to other classes of graphs? In particular, can the notion of transfer
function be extended to other classes of graphs?



--R

A framework for solving vlsi graph layout problems.
Dimer statistics and phase transitions.
An approximate max-flow min-cut theorem for uniform multicommodity flow problems with application to approximation algorithms

A separator theorem for planar graphs.
Applications of a planar separator theorem.
Finding minimum-quotient cuts in planar graphs
Finding near optimal separators in planar graphs.
Faster algorithms for finding small edge cuts in planar graphs.
--TR

--CTR
Eyal Amir , Robert Krauthgamer , Satish Rao, Constant factor approximation of vertex-cuts in planar graphs, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
approximation algorithms;planar graphs;separators