Constant Factor Approximation of Vertex-Cuts in Planar Graphs

There has been a long time I couldn’t remember to write memos for the papers I’ve read, and it’s time for me to come back to this blog, coz my memory is fading all the time and blogging is a good way to remind me of ideas. I’ve been working on planar graph separators with Christian Sommer for a semester, and learned many interesting stuff.

This time I’m going to blog Amir-Krauthgamer-Rao’s STOC 2003 result on planar graph vertex-cut problem.

Motivations

In planar graph, we can define quotient edge-cut being the number (total cost) of edges in the cut over the min of number (total weight) of vertices of either side. Then one can achieve constant approximation in almost linear time [Rao’92], and exact solution in pseudo-polynomial time O(n^2W\log(nW)) [Park-Phillips’93]. I have written memos for those two papers separately, and will eventually blog them some day.

For quotient vertex-cut, such notion can be similarly defined, although oen should be careful about the total weight of the vertices on the cut. A vertex cut is a tuple (A,B,C) where vertex set C separates A from B, ahd the \alpha-quotient cost is (where \alpha is either 0 or 1, and in terms of constant approximations, this constant \alpha does not matter too much).

\frac{c(C)}{\min\{w(A),w(B)\} + \alpha \cdot w(C)}

One general idea to work on vertex cut is by considering the radial graph G' of the original planar graph G, and then find the edge cut. The only difficulty here is that, unlike the edge cut case, the optimal quotient vertex cut might not have both sides connected, see for instance:

Recall that if both sides are connected, the optimal cut can be assumed WLOG to be a simple cycle, and then finding it is an easy job using techniques like knapsack, dynamic programming, or shortest path.

Technique 1

The first technique is to show that one can always assume (by losing a factor of $latex \frac{4}{3}$) that the optimal cut will force one side to be connected. Notice that if we are only interested in cuts with balance factor b\leq \frac{1}{3} then there is no loss in the ratio. The way to prove this is by simply defining connected regions and then doing greedy algorithm to move weights around the two sides of the cut, while keeping the vertex set C in the cut unchanged.

Technique 2

The second technique follows from a simple observation: the region on the other side of the cut, though may not be connected, has to form a tree. (BTW, if it is a forest, one can always make sure that it is a tree only.) See below:

Call this tree a CAST, or d-CAST when it is of depth d+1. Then it is not hard to show that after removing every the (d+1)-th level of the tree, one loses a factor of \frac{d+1}{d} in the approximation but the “0ptimal” cut can be assumed to be of form depth (d+1).

Now the final algorithm looks straightfoward, one can use knapsack based shortest path, to compute the optimal d-CAST in time O(n^{2d+3}), and this is the first polynomial algorithm to compute quotient vertex-cut. The approximation ratio is roughly \frac{4}{3}\frac{d+1}{d}, while it changes slightly if one varies the weight \alpha when defining quotient cost.

Advertisements
This entry was posted in Algorithm, Readings. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s