# «Fixed-parameter tractability of multicut parameterized by the size of the cutset∗ D´niel Marx† Igor Razgon‡ a August 27, 2013 Abstract Given ...»

Next we show that every vertex r reachable from u in G \ S is reachable from u in G \ S. Let P be an u − r path in G \ S and suppose that it contains a vertex q ∈ S \ S. As S is a minimal v − W separator, there is a q − W path Q that intersects S only in q. The concatenation of the preﬁx of P ending at q and Q is a u − W walk, hence Q has to contain a vertex q ∈ S. Vertex q cannot be on P ; in particular, q = q. By the deﬁnition of Q, this vertex q has to be in S \ S and hence it is reachable from v in G \ S. However, the subpath of Q from q to W does not contain any vertex of S, meaning that v is reachable also from W in G \ S, a contradiction. This shows that every vertex reachable from u in G \ S remains reachable in G \ S, contradicting the assumption that S is an important u − W separator. Therefore, S is indeed an important v − W separator.

(2) By Lemma 3.9, there are at most 4p important v − W separators of size at most p, thus by (1), vertex v can be contained in the exact shadows of at most that many members of Ip.

**Combining Lemmas 3.10 and 3.13, we immediately have:**

Proposition 3.14. Let R be a W -closest set and let S = N (R). Then every vertex v ∈ R ∪ N (R) is in the exact shadow of an some Sv ∈ Ip with Sv ⊆ S.

We use Prop. 3.14 to bound the probability that the constructed set Z satisﬁes the second condition of Theorem 3.6. We need the following simple observation to argue that the selection of these sets does not interfere with the ﬁrst condition of Theorem 3.6.

** Lemma 3.15.**

Let R be a W -closest set and let S = N (R) and S ⊆ S. Then the shadow of S is disjoint from S.

Proof. Suppose that v ∈ S is in the shadow of S ⊆ S, i.e., v ∈ S and S is a v − W separator. As v ∈ N (R), vertex v has a neighbor r ∈ R. We can assume that every component of G[R] contains a vertex of W : otherwise removing a component disjoint from W strictly decreases R without increasing |N (R)|, contradicting the assumption that R is a W -closest set. This means that there is a path from r to W fully contained in R. It follows that there is a path from v to W fully contained in R ∪ {v}, which is disjoint from S, contradicting the assumption that v is in the shadow of S.

In the simpliﬁed proof of Theorem 3.6, we select members of Ip uniformly at random and take the union of their exact shadows. In light of Lemmas 3.10 and 3.13, there is a set of at most 2p members of Ip that have to be selected and there is a set of at most N (R) · 4p members of Ip that have to avoided in order for the random selection to be successful.

Simpliﬁed proof of Theorem 3.6. The algorithm RandomSet(G, W, p) ﬁrst constructs the set Ip ; by Lemma 3.9, the size of Ip is O∗ (4p ) and can be constructed in time O∗ (4p ). Let Ip be the subset of Ip where each element from Ip occurs with probability 1 independently at random. Let Z be the union of the exact shadows of every set in Ip. We claim that the set Z satisﬁes the requirement of the theorem.

Let R be a W -closest set and let S = N (R). Let X1, X2,..., Xd ∈ Ip be the members of Ip that are fully contained in S. As |S| ≤ p, we have d ≤ 2p. By Lemma 3.15, we have that the exact

**shadow of Xj is disjoint from S for every j ∈ [d]. Now consider the following events:**

(E1) Z ∩ S = ∅ (E2) the exact shadow of Xj is a subset of Z for every j ∈ [d].

3.5 Random sampling of important separators—full proof In order to optimize the success probability, we perform the randomized selection of important separators in two phases: ﬁrst we select some members of Ip and add new edges to the graph and in the second phase we restrict our attention to members of Ip that induce cliques in the modiﬁed graph. We observe that important separators that induce cliques are nested, hence we can get a bound of p instead of 4p for the number of such separators.

** Lemma 3.16.**

For every vertex v ∈ V (G) \ W, there are at most p important v − W separators of size at most p inducing a clique.

Proof. Every minimal v − W separator arises as N (X) for some set X with v ∈ X and G[X] connected. The bound follows from observing that important separators inducing cliques are nested.

That is, we show that if X1 and X2 are connected sets containing v such that N (X1 ) and N (X2 ) are important v − W separators inducing cliques, then either X1 ⊂ X2 or X2 ⊂ X1.

Suppose that X1 \ X2 and X2 \ X1 are both nonempty. If X1 \ X2 = ∅ and X1 is connected, then there is a vertex x1 ∈ X1 ∩ N (X2 ). As N (X2 ) is a clique, every vertex of N (X2 ) is adjacent with x1, implying that N (X2 ) ⊆ X1 ∪ N (X1 ). If X2 \ X1 = ∅, then a symmetrical argument shows that N (X1 ) ⊆ X2 ∪ N (X2 ). We claim that N (X1 ∪ X2 ) ⊆ N (X1 ) ∩ N (X2 ) and hence |N (X1 ∪ X2 )| ≤ |N (X1 )|, |N (X2 )|; as X1 ∪ X2 ⊃ X1, X2, this would contradict the assumption that X1 and X2 are important components. Consider a vertex u ∈ N (X1 ∪ X2 ), which must have a neighbor w ∈ X1 ∪ X2. If w ∈ X1 ∩ X2, then u ∈ N (X1 ) ∩ N (X2 ) and we are done. Suppose without loss of generality that w ∈ X1 \ X2. Then u ∈ N (X1 ) ⊆ X2 ∪ N (X2 ), but u ∈ X2 by deﬁnition, hence u has to be in N (X2 ) as well.

Suppose now that X1, X2,..., Xt are connected sets containing v such that N (X1 ), N (X2 ),..., N (Xt ) are important v − W separators inducing cliques. We have shown that the Xi ’s form a chain, i.e., we can assume without loss of generality that X1 ⊂ X2 ⊂ · · · ⊂ Xt. This means that there are at most p of them, as the deﬁnition of important separator implies that |N (X1 )| |N (X2 )| · · · |N (Xt )| has to hold.

**By Lemma 3.13(1), we have the following the bound:**

** Lemma 3.17.**

Every vertex v ∈ V (G) \ W is contained in the exact shadow of at most p sets X ∈ Ip such that G[N (X)] is a clique.

Full proof of Theorem 3.6. The randomized algorithm consists of two phases. For consistency of notation, let G1 = G and Ip,1 = Ip. In the ﬁrst phase, we select a subset of Ip and obtain G2 for G1 by making the selected sets cliques. Let Ip,2 be deﬁned as Ip,1, but for graph G2 : S is in Ip,2 if it is an important v − W separator of size at most p for some vertex v ∈ V (G2 ) \ (W ∪ S) in G2. In the second phase, we select a subset of Ip inducing cliques in G2 and obtain Z as the union of the exact shadows of the selected sets.

** Phase 1. In the ﬁrst phase, we select a subset Ip,1 ⊆ Ip,1 by putting every set of Ip,1 into Ip,1 with probability p1 = 4−p independently at random.**

Then we make every set X ∈ Ip,1 a clique; let G2 be the graph obtained this way.

Let R be a W -closest set and let S = N (R). By Proposition 3.14, there exists a subcollection A2 of Ip,1, all being subsets of S, such that V (G) \ (R ∪ S) is covered by the exact shadows of the sets in A2. Let us estimate the probability that the events (E1) Every S ∈ A2 induces a clique in G2.

(E2) Every S ∈ A2 has the same exact shadow in G1 and in G2.

(E3) Every S ∈ A2 is in Ip,2.

occur.

Let us make a subset A1 of A2 such that for every S2 ∈ A2 and x, y ∈ S2, there is a set S1 ∈ A1 with x, y ∈ S1. In other words, the sets in A1 cover every pair {x, y} of vertices covered by the sets in A2. Since there are |S| ≤ p such pairs, it is clear that there exists a collection A1 of size at most p. Observe that, by Lemma 3.15, the shadow of every set in A1 is disjoint from S.

Let B1 contain those members of Ip,1 whose exact shadows intersect S; by Lemma 3.13, we have |B1 | ≤ |S| · 4p ≤ p · 4p. We claim that if every member of A1 is in Ip,1 and no member of B1 is in Ip,1, then (E1–E3) occur.

Consider an S ∈ A2. Assuming that every member of A1 is in Ip,1, the set G2 [S ] becomes a clique. This shows (E1).

To show (E2), that is, that S ∈ A2 has the same exact shadows in G1 and G2, we show that a subset S ⊆ S is a v − W separator for some vertex v in G1 if and only if it is in G2. This shows that S is a minimal v − W separator in G1 if and only if it is in G2, implying the equalities of the exact shadows. One direction is clear, as G1 is a subset of G2. For the other direction, suppose that S is not a v − W separator in G2. Let K be the connected component of v in G1 \ S ; by assumption K is disjoint from W. Then there have to be two vertices a ∈ K and b ∈ K ∪ S that are adjacent in G2 but not in G1. The reason why a and b are adjacent in G2 is that there is some X ∈ Ip,1 with a, b ∈ X. As we assumed that no member of B1 is in Ip,1, this means that the exact shadow of X is disjoint from S (and hence from S ). As X ∈ Ip,1, it is an important (hence minimal) q − W separator for some vertex q in its exact shadow. This means that there are paths from q to a and b in the exact shadow of X. Therefore, there is a path P from a to b in G1 whose internal vertices are in the exact shadow of X, hence disjoint from S. It follows that b is also in the component K of v in G1 \ S, a contradiction.

Finally, let us show (E3). As S ∈ Ip,1, it is an important v − W separator for some vertex v.

Again, let K be the connected component of v in G1 \ S. By the previous paragraph, S is a K − W separator in G2. This implies that S is an important v − W separator in G2 as well: if there is a separator S contradicting that S is an important v − W separator in G2, then S is a v − W separator in G1 as well (as G1 is a subgraph of G2 ) and at least one vertex of S is reachable from v in G1 \ S, which means that S contradicts that S is an important v − W separator in G1.

We can conclude that the probability that (E1–E3) occur can be bounded from below by the probability of the event that every set in A1 is selected and no set from B1 is selected. As the sets A1 and B1 are disjoint (recall that the exact shadow of every member of A1 is disjoint from S by Lemma 3.15 while the exact shadow of every member of B1 intersects S by deﬁnition), this probability is at least p 2 3 3 (1 − 4−p )p·4 · (4−p )p ≥ e−2p · 4−p = 2−O(p ) (in the inequality, we use that 1 + x ≥ exp(x/(1 + x)) for every x −1 and 1 − 4−p ≥ 1/2).

** Phase 2. Ip,2 be a subset of Ip,2 where every X ∈ Ip,2 with G2 [X] being a clique appears with probability p2 = 1 − 2−p independently at random (and if a set X ∈ Ip,2 does not induce a clique in G2, then it is never selected).**

Let Z be the union of the exact shadows of the sets in Ip,2.

If (E1–E3) occur, then every set in A2 is in Ip,2 and they induce cliques in G2. If additionally the events (E4) Z ∩ S = ∅, and (E5) A2 ⊆ Ip,2 occur, then every v ∈ R ∪ N (R) is in the exact shadow of some S ∈ Ip,2 and v ∈ Z follows.

Let us estimate the probability that both (E4) and (E5) hold on condition that (E1–E3) hold.

Let B2 contain those members of Ip,2 (inducing cliques) whose exact shadow in G2 intersects S; we have |B2 | ≤ p|S| ≤ p2 (by Lemma 3.17, every vertex of S is contained in the exact shadow of at most p members of Ip,2 inducing cliques in G2 ). If no member of B2 is selected, then no exact shadow of a set of Ip,2 contains a vertex of S, and hence Z ∩ S = ∅. Note that A2 and B2 are disjoint: by (E2), every S ∈ A2 has the same exact shadow in G1 and G2, therefore the exact shadow of S ∈ A2 is disjoint from S in G2 as well. Therefore, the probability that (E4) and (E5) hold can be bounded from below by the probability of the event that every member of A2 is selected and no member of B2 is selected, which is at least 2 p 3 3) (2−p )p · (1 − 2−p )2 ≥ 2−p · e−2 2−O(p (again, we use that 1 + x ≥ exp(x/(1 + x)) for every x −1 and 1 − 2−p ≥ 1/2).

Taking into account the probability of success in both phases, we get that for each W -closest set R, the set Z satisﬁes the requirements with probability 2−O(p ).

3.6 Derandomization By running 2O(p ) times the algorithm of Lemma 3.1, we get a collection of instances such that at least one of them satisﬁes the requirements of Lemma 2.4 with arbitrary large constant probability.

To obtain a deterministic version of Lemma 2.4, we derandomize the algorithm of Theorem 3.6 using the standard technique of splitters.

** Lemma 3.18.**

There is an algorithm DeterministicSets(G, W, p) that, given a graph G, a set W ⊆ V (G), and an integer p, produces t = 2O(p ) log2 |V (G)| subsets Z1,..., Zt of V (G) \ W such that the following holds. For every closest set R with |N (R)| ≤ p, there is at least one 1 ≤ i ≤ t with

Proof. An (n, r, r2 )-splitter is a family of functions from [n] to [r2 ] such that for any subset X ⊆ [n] with |X| = r, one of the functions in the family is injective on X. Naor, Schulman, and Srinivasan [38] gave an explicit construction of an (n, r, r2 )-splitter of size O(r6 log r log n).

Observe that in the ﬁrst phase of the algorithm of Theorem 3.6, a random subset of a universe Ip,1 of size n1 = |Ip,1 | ≤ 4p · n is selected, where n = |V (G)|. There is a collection A1 ⊆ Ip,1 of a1 ≤ p2 sets and a collection B1 ⊆ Ip,1 of b1 ≤ p · 4p sets such that if every set in A1 is selected and no set in B1 is selected, then (E1–E3) hold. Instead of selecting a random subset, we try every function f in an (n1, a1 + b1, (a1 + b1 )2 )-splitter family and every subset F ⊆ [(a1 + b1 )2 ] of size a1 (there are (a1 +b1 ) = 2O(p ) ) such sets F ). For a particular choice of f and F, we select those sets a1 X ∈ Ip,1 for which f (X) ∈ F. By the deﬁnition of the splitter, there will be a function f that is injective on A1 ∪ B1, and there is a subset F such that f (X) ∈ F for every A1 and f (X) ∈ F for every B1. For such an f and F, the selection will ensure that (E1–E3) hold.