«Fixed-parameter tractability of multicut parameterized by the size of the cutset∗ D´niel Marx† Igor Razgon‡ a August 27, 2013 Abstract Given ...»
Proof. Let G and G = torso(G, V (G) \ Z) be the graphs in instances I and I/Z, respectively. To prove the ﬁrst statement, we show that if S ⊆ V (G ) is a solution of I/Z, then S is a solution of I as well. Suppose that some pair (x, y) of I is not separated by S. Let P be a path in G \ S going from x to y. Let x and y be the ﬁrst and last vertex of P not in Z, respectively, and let P be the subpath of P from x to y. (Note that P cannot be fully contained in Z, as it contains at least one vertex of the multicut W.) By the way I/Z is deﬁned, (x, y ) is a pair in I/Z, hence S separates x and y in G = torso(G, C). Using Prop. 3.3 with C = V (G) \ Z, we get that S separates x and y in G, which is in contradiction with the existence of the path P. A similar argument shows that there is no path in G \ S that connects two vertices of W.
For the second statement, suppose that S is a solution of I with S ∩ Z = ∅. Let us show that S is a solution of I/Z as well. Suppose that S does not separate x and y in G for some pair (x, y ) of I/Z. Using Prop. 3.3 with C = V (G) \ Z, we get that S does not separate x and y in G, i.e., there is an x − y path P in G \ S. By the way the pairs in I/Z were deﬁned, there is a pair (x, y) of I and there is an x − x path P1 such that x is the only vertex of P1 not in Z, and there is a y − y path P2 such that y is the only vertex of P2 not in Z. Clearly, these paths are disjoint form S. Therefore, the concatenation of P1, P, P2 is an x − y path in G \ S, contradicting that S is a solution of I.
To see that S is shadowless in G, consider a vertex v of G \ S. As v ∈ Z is not in the shadow of the solution S of I, there is a path P in G \ S going from v to a vertex w ∈ W. Again by Prop. 3.3, this means that there is a v − w path in G \ S as well, which means that v is not in the shadow of the solution S of I.
3.2 Closest sets Lemma 3.4 shows that in order to reduce the Multicut Compression∗ problem to ﬁnding a shadowless solution, all we need is a set Z that covers the shadow of a hypothetical solution S, but disjoint from S itself. It is not obvious how this observation is of any help: it seems that there is no way of constructing such a set without actually knowing a solution S. Nevertheless, we present a randomized procedure that constructs such a set with non-negligible probability.
The main idea of the randomized procedure is that a solution of a Multicut Compression∗ instance can be characterized by the set of vertices reachable from W, and we can assume that this set has the property that it cannot be made smaller without increasing the size of the boundary.
The following deﬁnition formalizes this property:
Deﬁnition 3.5. Let G be an undirected graph and let W ⊆ V (G) be a subset of vertices. We say that a set R ⊇ W is a W -closest set if there is no R ⊂ R with R ⊇ W and |N (R )| ≤ |N (R)|.
The main technical idea of the paper is the following randomized procedure, which, in some sense, ﬁnds the boundary of a closest set. Note that this statement could be of independent interest, as it is about closest sets in general and contains nothing speciﬁc to multicut problems.
Theorem 3.6 (random sampling).
There is a randomized algorithm RandomSet(G, W, p) that, given a graph G, a set W ⊆ V (G), and an integer p, produces a set Z ⊆ V (G) \ W such that the following holds. For every W -closest set R with |N (R)| ≤ p, the probability that the following two events both
occur is at least 2−O(p ) :
1. N (R) ∩ Z = ∅, and
2. V (G) \ (R ∪ N (R)) ⊆ Z.
That is, the two events say that Z covers every vertex outside R ∪ N (R) and may cover some vertices inside R, but disjoint from N (R). To prove Theorem 3.6, we introduce the main new technique of the paper: random sampling of important separators. In Section 3.3, we review the notion of important separators. Section 3.4 contains a simpliﬁed proof of Theorem 3.6 (with probability O(p) 3 bound 2−2 instead of 2−O(p ) ). The full proof appears in Section 3.5. We show below that Theorem 3.6 can be used to prove Lemma 3.1. Section 3.6 shows how to derandomize Theorem 3.6, which immediately proves Lemma 2.4.
Proof (of Lemma 3.1). Let I = (G, W, T, p) be an instance of Multicut Compression∗. Let us use the algorithm RandomSet(G, W, p) of Theorem 3.6 to obtain a set Z and let I = I/Z. By Lemma 3.4, every solution of I is a solution of I as well.
Assume now that I has a solution S; let S be a solution such that |S| is minimum possible, and among such solutions the set R of vertices reachable from W in G \ S is as small as possible. Clearly, N (R) ⊆ S. We claim that R is a W -closest set. Suppose that there is a set R ⊂ R containing W such that |N (R )| ≤ |N (R)|. Let S = N (R ), we have that |S | ≤ |S|. We claim that S is a solution, contradicting the minimality of S. Suppose that there is a path P in G \ S connecting the two terminals in a pair (x, y) ∈ T or two vertices of W. In both cases, P has to go through a vertex of W (here we use that the deﬁnition of Multicut Compression∗ requires that W is a multicut).
Therefore, P is fully contained in R ⊂ R, which implies that it is disjoint from N (R) ⊆ S, i.e., S is not a solution. Thus S is indeed a solution with |S | ≤ |S| and |R | |R|, contradicting the choice of the solution S. This contradiction proves our claim that R is a W -closest set. The same argument shows that N (R) is a solution, hence S = N (R) has to hold.
As R is a W -closest set, the probability that both S ∩ Z = ∅ and V (G) \ (R ∪ S) ⊆ Z hold is −O(p3 ). The later inclusion is equivalent to saying that the shadow of the solution S is contained in Z. Therefore, by Lemma 3.4, set S is a shadowless solution of instance I.
Figure 5: Set S1 is the unique minimum X − Y separator and therefore it is an important X − Y separator. Set S2 is not an important X − Y separator, as |S2 | = |S3 | and a superset of vertices is reachable from X in G\S3 compared to G\S2. Sets S3 and S4 are both important X −Y separators.
Deﬁnition 3.8. Let X, Y ⊂ V (G) be disjoint sets of vertices, S ⊆ V (G) be an X − Y separator, and let K be the union of every component of G \ S intersecting X. We say that S is an important X − Y separator if it is inclusionwise minimal and there is no X − Y separator S with |S | ≤ |S| such that K ⊃ K, where K is the union of every component of G \ S intersecting X.
See Figure 5 for illustration. Note that the order of X and Y matters: an important X − Y separator is not necessarily an important Y − X separator. It is easy to see that if S is an important X − Y separator, then S = N (R) for some set R with X ⊂ R and (R ∪ N (R)) ∩ Y = ∅: we can deﬁne R to be the set of vertices reachable from X in G \ S. Observe that if R is deﬁned this way, then every component of G[R] contains at least one vertex of X. In particular, if X contains only a single vertex, then we can assume that G[R] is connected.
A bound on the number of important separators was given in  (although the notation there is slightly diﬀerent). A better bound is implicit in . For the convenience of the reader, we give a self-contained proof of the following fact in the appendix.
Let X, Y ⊆ V (G) be disjoint sets of vertices in a graph G. For every p ≥ 0, there are at most 4p important X − Y separators of size at most p. Furthermore, we can enumerate all these separators in time 4p · p · (|E(G)| + |V (G)|).
Note that one can give an exponential lower bound on the number of important separators as a function of p and in fact the bound 4p in Lemma 3.9 is asymptotically tight up to factors polynomial in p.
The following lemma connects closest sets and important separators by showing that the boundary of a closest set is formed by important separators. Intuitively, every vertex v outside the closest set R “sees” a part of the boundary N (R) that is an important v − W separator: otherwise, we could “push” this part of the boundary away from v and towards W, contradicting the assumption that R is a closest set.
Lemma 3.10 (pushing).
Let G be an undirected graph, W a set of vertices, and R a W -closest set.
For every vertex v ∈ R ∪ N (R), there is an important v − W separator Sv ⊆ N (R).
Proof. Let v be an arbitrary vertex of G not in R ∪ N (R) and let K be the component of G \ N (R) containing v. As v ∈ R ∪ N (R) and W ⊆ R, we have that K is disjoint from W. We show that K R
Figure 6: Proof of Lemma 3.10. Note that, in general, K can intersect other components of G \ (R ∪ N (R)).
N (K) is an important v − W separator. First, we observe that N (K) is a minimal v − W separator:
we have N (K) ⊆ N (R), thus every vertex of N (K) is adjacent to both K and R. Thus, if N (K) is not an important v − W separator, then there is a K ⊃ K such that K ∪ N (K ) is disjoint from W and |N (K )| ≤ |N (K)|. We may assume that G[K ] is connected. Let R := R \ (K ∪ N (K )). Now N (R ) ⊆ (N (R) \ N (K)) ∪ N (K ): it is clear that every neighbor of R is in N (R) ∪ N (K ) (as it cannot be in K ) and every vertex of N (K) \ N (K ) is fully contained in K. Thus |N (R )| ≤ |N (R)| follows from |N (K )| ≤ |N (K)|. Furthermore, the connectivity of G[K ] and K ⊂ K implies that K contains a vertex of N (K) ⊆ N (R) and therefore K ∪ N (K ) contains a vertex of R. This means that R is a proper subset of R with |N (R )| ≤ |N (R)|, contradicting the assumption that R is a W -closest set.
3.4 Random sampling of important separators—simpliﬁed proof In this section, we present a simpler version of the proof of Theorem 3.6, where the probability of success is double exponentially small in p. This simpler proof highlights the main idea of the randomized reduction. The full proof, which improves the probability to 2−O(p ) with additional ideas, appears in Section 3.5.
By Lemma 3.9 we can enumerate every separator of size at most p that is an important v − W separator for some v.
Deﬁnition 3.11. The set Ip contains a set S ⊆ V (G) \ W if S is an important v − W separator of size at most p for some vertex v ∈ V (G) \ (W ∪ S).
By Lemma 3.9, the size of Ip is at most 4p · |V (G)| and we can construct Ip in time O∗ (4p ).
Recall that the shadow of a set S is the set of vertices not reachable from W in G \ S. By Lemma 3.10, every vertex of the shadow of N (R) is covered by the shadow of a member of Ip that is a subset of N (R). This means that the shadow of 2p members of Ip fully cover the shadow of N (R).
This suggests that we may construct a set Z satisfying the conditions of Theorem 3.6 by guessing these members of Ip and obtaining Z as the union of the shadows of the selected sets. However, in general the size of Ip cannot be bounded as a function of p only. Thus complete enumeration of all possible ways of selecting 2p members of Ip is not feasible. Instead, we randomly select a subset of Ip and hope that it contains these at most 2p members and it does not contain any member of Ip whose shadow intersects N (R).
The probability of randomly selecting a member of Ip should not be too high, because we want to avoid selecting any member whose shadow contains a vertex of N (R). We need a bound on the number such members of Ip. Intuitively, the bound of Lemma 3.9 on the number of important separators should imply that each vertex of N (R) is contained in the shadow of a bounded number of members of Ip, but in order to make this claim precise, we need to consider a slightly diﬀerent
notion of a shadow:
Deﬁnition 3.12. The exact shadow of a set S ⊆ V (G)\W contains those vertices v ∈ V (G)\(W ∪S) for which S is a minimal v − W separator.
For example, in Figure 2, set C2 is in the exact shadow of S, but C1 is not, as a 2-vertex subset of S separates every vertex of C1 from W.
The following lemma is true only for exact shadows: the bound in (2) is not true with the original deﬁnition of shadow.
(1) For every S ∈ Ip, we have that v ∈ V (G) \ (W ∪ S) is in the exact shadow of S if and only if S is an important v − W separator.
(2) Each vertex v ∈ V (G) \ W is contained in the exact shadow of at most 4p members of Ip.
Proof. (1) By deﬁnition, if S is an important v − W separator, then S is a minimal v − W separator, hence v is in the exact shadow of S. For the other direction, suppose that v is in the exact shadow of some S ∈ Ip. By deﬁnition of Ip, there is a vertex u ∈ V (G) \ (W ∪ S) such that S is an important u − W separator. If S is not an important v − W separator, then (as the deﬁnition of exact shadow implies that S is a minimal v − W separator) there is a v − W separator S with |S | ≤ |S| and such that a superset of vertices is reachable from v in G \ S compared to G \ S.
We claim that S is a u − W separator as well. Suppose that there is a u − W path P in G \ S.
This path has to go through S \ S ; let s be the ﬁrst vertex of S \ S on P when going from u to W. Since S is a minimal v − W separator, s has a neighbor reachable from v in G \ S and hence in G \ S. Therefore, s ∈ S is also reachable from v in G \ S. It follows that s is reachable from both u and v in G \ S, i.e., u and v are in the same component of G \ S, contradicting the assumption that S is a v − W separator.