Directed Multicut Problem and Algorithm Insights

The Directed Multicut problem Problem definition: Input: a directed graph G(V,E) with cost on the edges and a collection of pairs {si,ti} Goal: remove minimum cost edges so that no sihas a directed path to tiin the resulting graph.

A simple algorithm for Directed Multicut But ratio O(sqrt{n}) f e T(2) S(1) S(2) T(1)

Difficulties s2and t2can be inside the sphere of s1even if we took a -cut <1/2. While its is true that dist(s1,t2)<1/2 and dist(s1,s2)<1/2 it is not true that dist(s2,t2)<1 There is no divide and conquer.

Directed Multicut Continued A path P is an important path if it is a directed path from some sito some ti. The optimum must take at least one edge of any such path.

The difficulties are real Chuzhoy and Khanna showed that this problem is Labelcover-hard. Remarkable paper. This means that better than a polynomial ratio is not possible. Apparently the best ratio known is the O(sqrt{n}) of Gupta. Agarwal et al claimed a better than O(sqrt{n}) ratio but there is no journal version and nobody that I know read and understood the paper. It seems that the paper is mistaken. And nobody of the authors claims it is correct (or has the energy to check ).

The LP relaxation Minimize optf= ewe xe Subject to Pxe 1 For every important path P de 0 For every edge e E

A middle: take all these edges ti 2/3 R 1/3 si

The cut has to be at a point of distance at least 1/3 from siand distance at least 1/3 to ti ti 2/3 1/3 si

We take all edges like uv in the figure ti 2/3 V U 1/3 si

Good news: such edges separate tifrom si ti 2/3 V U 1/3 si

Bad news: There is a high probability that e is in the cut ti 2/3 V U 1/3 si

We shall see that each time that an edge e is on a path from sito tithe probability it is taken is at most 3xe ti 2/3 V U 1/3 si

We say that an edge e=ab is important for a pair i if there is a path from sito a and from b to ti ti 2/3 b a 1/3 si

Events Say that e is important for q pairs. Then the probability that e is added to the cut is Pr(e is added by the first pair e is added by the second pairs .. e is added by the q pair) q Pr(e is added by a pair)

Expectation Let cut(e) be w(e) if e is in the cut and 0 otherwise. E(cut(e)) q 3xe w(e) E(Cut) =q O(optf) and the ratio is O(q). For the rest of the talk, we bound q.

Random choice Choose at random R [1/3,2/3] and take into the cut edges a b so that dist(si,a)<R and dist(si,b) R. What is the expected contribution of e to the cut if e is important for the pair? The contribution of e is we Pr(R cuts e). The contribution of e to a given pair is at most xew(e)/(1/3) =3 xew(e)

To find the cut Break the distance from sito tito length intervals. Take all breakpoints j between 2/3 and 1/3 for a small For one of the j and j+1 the expectation per edge is as we claim

The algorithm of Gupta 1) Add to the Sol any edge e so that xe 1/sqrt{n}. 2) As long as there is a non-separated pair siti 2.1 Find a middle cut for si,ti,and add the edges of the cut to Sol 3) Return Sol.

Bounding the number of pairs e is important for Let R(a) for e=a b be the number of vertices that can reach or can be reached from a and the same for b. For an edge a b let R(e)=R(a)+R(b). R(e) 4n when the algorithm starts.

If e=ab is an important edge There is a path from sito a and b to ti. Both these paths have a length of at least 1/3. Therefore we have a path si x1 x2 a b y1 y2 ..->ti Note that for every e xe 1/sqrt{n}, the distance between s and a is at least a 1/3. There are at least 1/(3sqrt{n}) vertices xi. The same for yi

R(e) goes down In the cut, all the xiare at the side of si. all the yiare at the side of ti All the xino longer can reach b. All the yican no longer be reached from a After every cut is found, R(e) goes down by (sqrt{n}). Therefore e is in the cut with probability at most O(sqrt{n})xe. And the approximation is O(sqrt{n}).

Remark Another paper gave O(n2/3/ opt1/3) ratio. From the paper of Gupta, O(optf ) ratio follows. Assuming opt and optfare the same we get that the bad point is n2/3= opt4/3. This implies opt=sqrt{n}. Joining the two papers implies that for other values of opt, we can break the sqrt{n} ratio. But breaking the sqrt{n} ratio when opt=sqrt{n} seems hard.

A problem from extreme graph theory This paper that gave the other approximation solved an extremal problem on graphs Given a directed graph and a collection of pairs so that dist(si,ti) R. How many edges do you need to remove to disconnect all pairs? The answer is (n2/R2) Non-trivial