Approximating the Undirected Multicut Problem with Folklore Algorithm

Approximating the undirected Multicut problem A folklore algorithm. Based on a result of Karloff et al for Multiway cut.

Problem definition Input: Given connected G(V,E) w(e) 0 and a collection {si, ti} of vertex pairs. Required: a minimum cost E so that in G(V,E-E ), siand ti are not in the same connected component In the fractional program: put fractions on edges so that the distance between siand ti is at least 1 for every i.

The LP Minimize e w(e) xe Such that: x,e, e P xe 1 For every P from sito ti

Separating oracle Is there x,e Pxe<1 For some P from sito ti This is a shortest-path problem From now on the xeare treated as distances

A distance cut A distance cut for s toward t is taking a number 1/2 and taking out of the graph all edges with one vertex with xe distance less than from s, and for the other the distance from s is at least No other pairs remain inside the sphere as if so dist(s, si)+dist(s, ti)<1. Contradiction.

The algorithm 1) Choose once R (0,1/2). 2) Order the pairs randomly 3) For i=1 to k do. 3.1 Add to the solution all edges (w, z) so that dist(si, w)< but dist(si, z) 3.2 All edges (w,z) so that dist(si, w) dist(si, z) will not be cut edges.

The algorithm is randomized Let cut(e) be the random variable set to w(e) if e is in the solution and 0 otherwise. Note that Cut= ecut(e) E(Cut)=E( ecut(e))= ePr(e is in the cut) w(e). The question is: how high is the probability that e is in the cut?

The algorithm is randomized The question is: how high is the probability that e is in the cut? We will see that the probability that e is in the cut is at most 2(ln k+2) xe(more precisely, the minimum between this and 1). This implies that E(Cut) 2(ln k+2)optf which means a 2(ln k+1) approximation.

From now on we bound the probability that e is in the cut Let d(i) be the distance of sifrom e (the minimum between the distances to u and v). Assume by renaming the pairs that d(1) d(2) . d(k)

Definition We say that siadds (u, v) to the solution siis the first pair so that dist(si, u)< and dist(si, v) It can be that dist(ti, v)< for example, but we can rename the vertices.

What is the probability that s13 added e? s7 v u This can t happen

If this happens (u,v) no longer can be a cut edge s7 v u This can t happen

And this cant happens s7 v u s7added the edge first before s13

This must happen s7 u v

What happens if s7is before s13in the random order? s7 v u s13

This cant happen since s7is closer to the edge s7 v u s13

A condition For s13to have a chance to add e to the cut, s13must be before s1, s2 ,s12in the cut. Probability 1/13. In general 1/i

The algorithm We have disjoint events. e was taken into the cut by s1, by s2or by s3to e was taken by sk Pr(e is in the cut)=Pr(e was taken by s1)+Pr(e was taken by s2)+ +pr(e was taken by sk).

The first condition for sito add e is that siwill be in the ordering before sjfor all j<i Probability 1/i

The first condition for sito add e is that siwill be in the ordering before sjfor all j<i But even then it is not sure

Say that siis before s1,s2,,si-1 si n 1/2 xe

The blue line doesnt separate, the red does si n 1/2 xe

What is the probability that e=uv is cut by pair i? You have an interval of at most x(e) length out of that implies that e is taken by si

What is the probability that e=uv is cut by pair i? In total, the probability that si takes e is at most 2xe/i

The probability that e is in the solution Pr(e is in the cut)= Pr(e is taken by s1)+Pr(e is taken by s2)+ +Pr(e is taken by sk)

Probability that e is in the cut Pr(e is cut) 2x(e)/1+2x(e)/3+ +2x(e)/k <(2ln k+2)x(e) This is what we claimed

We have shown There is an O(log n) expected ratio approximation algorithm for the Undirected Multicut problem.

The integrality gap It is (log n) on a random graph and expanders. We don t have a good hardness of approximation.