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

We prove that B is a shattering set. Otherwise, let f : B → W be a function witnessing that B it is not a shattering set. It is not hard to see that M is a connected component in Gf \ W whose set of legs is a subset of W. We consider three subcases and arrive to a contradiction in each of them (see Figure 8).

Case 1a. M is a trivial component of Gf \ W. Let w be the only leg of M. Let w1 and w2 be other two distinct legs of K in G that are diﬀerent from w. It follows that f maps every vertex of I(w1 ) ∪ I(w2 ) to w implying that there is a w − w1 and a w − w2 path in Gf whose internal vertices w∗ w∗ w∗

**Figure 8: The 3 subcases of Case 1 in Lemma 4.6 for a component with legs {w∗, 1, 2, 3}. Case 1a:**

w is the only leg of M in Gf \ W. The ﬁgure shows two paths in two distinct components connecting w to another leg (assuming w ∈ {1, 3}). Case 1b: f (v) = w for every v ∈ I(w). Case 1c: M is a nontrivial component in Gf \ W and f (v) = 3 for some v ∈ I(2); the ﬁgure shows a 2 − 3 path.

belong to two diﬀerent components adjacent to w1 and w2 in G[K ∪ W ] \ M. Thus Gf has at least two non-trivial components that are subsets of K, in contradiction to the choice of f.

Case 1b. M is a nontrivial component of Gf \ W and f (v) = w for every v ∈ I(w) and w ∈ W (i.e., each vertex on the boundary is mapped to its preimage). As the smallest I(w∗ ) − I(W \ {w∗ }) separator in G[N (M ) ∪ M ] is larger than p, G[M ∪ W ] does not have a w∗ − W \ {w∗ } separator of size at most p, in contradiction to f being a witnessing function.

Case 1c. M is a nontrivial component of Gf \ W and there are distinct w1, w2 ∈ W such that f (v) = w2 for some v ∈ I(w1 ). By deﬁnition of I(w1 ), there is a w1 − v path in G whose internal vertices are fully contained in K \ M. Therefore, there is a w1 − w2 path in Gf whose internal vertices are disjoint from M, implying that Gf has a nontrivial component that is a subset of K, but distinct from the nontrivial component M. Thus the number of nontrivial components increases, a contradiction.

** Case 2. We show that M ⊂ M and M is a good multiway cut in this case.**

Let us show M ⊂ M ﬁrst. Clearly, M = M, as M is disjoint from the (nonempty) set S ⊆ M. Thus M ⊂ M is only possible if M is disjoint from M, but Lemma 4.4 implies that the two disjoint connected sets M and M cannot be both multiway cuts.

For clarity, from now on we use IM (w) and IM (w) for the image of w on the boundary of M and M, respectively. Observe that IM (w) ∩ N (M ) ⊆ IM (w) for every w ∈ W : for every v ∈ IM (w) ∩ N (M ), there is a w − v path disjoint from M, which is obviously disjoint from M ⊂ M as well, and then v ∈ N (M ) implies v ∈ IM (w). We claim that either IM (w∗ ) or IM (W \ {w∗ }) is disjoint from N (M ). Suppose that there are two vertices v1 ∈ IM (w∗ ) ∩ N (M ) and v2 ∈ IM (W \ {w∗ }) ∩ N (M ). Vertices v1 and v2 can be connected by a path P whose internal vertices are in M (hence disjoint from S), contradicting the fact that S is an IM (w∗ )−IM (W \{w∗ })

Figure 9: The two possibilities in Case 2 of Lemma 4.6 (the set of legs is W = {w∗, 1, 2, 3}): either (a) N (M ) ⊆ IM (w∗ ) ∪ S or (b) N (M ) ⊆ IM (W \ {w∗ }) ∪ S holds.

separator. Therefore, either N (M ) ⊆ IM (w∗ ) ∪ S or N (M ) ⊆ IM (W \ {w∗ }) ∪ S holds. The two possibilities are demonstrated in Figure 9.

To show that |IM (w∗ ) \ W | and |IM (W \ {w∗ }) \ W | are both at most p, we argue as follows.

Suppose ﬁrst that N (M ) ⊆ IM (w∗ ) ∪ S. We show that IM (w∗ ) ⊆ IM (w∗ ) and IM (W \ {w∗ }) ⊆ S hold, proving the bounds |IM (w∗ ) \ W | ≤ |IM (w∗ ) \ W | ≤ p and |IM (W \ {w∗ }) \ W | ≤ |S| ≤ p.

Let C1 (resp., C2 ) be the union of all those components of G[W ∪ (K \ M )] that contain a vertex of w∗ (resp., a vertex of W \ {w∗ }). As M is a multiway cut, C1 and C2 are disjoint. Now IM (w∗ ) and IM (W \ {w∗ }) are precisely the neighbors of M in C1 and C2, respectively. We observe that IM (w∗ ) ⊆ C1 : if v ∈ IM (w∗ ) is not in C1, then every w∗ − v path has to go through M ⊂ M, contradicting the deﬁnition of IM (w∗ ). Thus N (M ) ⊆ IM (w∗ ) ∪ S implies that every neighbor of M in C2 is from S (as it cannot be from IM (w∗ ) ⊆ C1 ), further implying IM (W \ {w∗ }) ⊆ S. Next, we show that S ⊆ C2. Suppose that there is a v ∈ S \ C2 and a w∗ − W \ {w∗ } path P intersecting S only in v (recall that S is a minimal w∗ − W \ {w∗ } separator). However, when the path P enters C2 from M, then, as we have seen, it enters a vertex of S ∩ C2 that is diﬀerent from v, a contradiction.

Thus N (M ) ⊆ IM (w∗ ) ∪ S implies that every neighbor of M in C1 is from IM (w∗ ) (as it cannot be from S ⊆ C2 ), further implying IM (w∗ ) ⊆ IM (w∗ ). Finally, we can deduce that N (M ) = IM (W ), as required by the deﬁnition of good multiway cut: indeed, every vertex of N (M ) ⊆ IM (w∗ ) ∪ S is in C1 ∪ C2, that is, either in IM (w∗ ) or in IM (W \ {w∗ }). Therefore, we have shown that M ⊂ M is a good multiway cut.

A symmetrical argument (exchanging the role of w∗ and W \ {w∗ }) shows that if N (M ) ⊆ IM (W \ {w∗ }) ∪ S, then IM (w∗ ) ⊆ S and IM (W \ {w∗ }) ⊆ IM (W \ {w∗ }), implying the bounds |IM (w∗ ) \ W | ≤ p and |IM (W \ {w∗ }) \ W | ≤ p. Thus in both cases, we proved that M ⊂ M is a good multiway cut.

** Case 3. Assume now that the algorithm returns B := (S ∪ N (M )) \ W as a shattering set.**

This happens because the number of components of G[K \ (N (M ) ∪ S)] which are multiway cuts of (G[K ∪ W ], W ) is not exactly one. According to Lemma 4.5, N (M ) ∪ S is indeed a shattering set in this case. Clearly, its size is at most 3p.

** Lemma 4.3 follows by iterative application of Lemma 4.6.**

Proof (of Lemma 4.3). It is not hard to see that K is a good multiway cut of (G[K ∪ W ], W ); in particular, I(w) = {w} for every w ∈ W, and hence I(w∗ ) \ W = I(W \ {w∗ }) = ∅. Let M0 = K.

Apply the algorithm of Lemma 4.6 to M0. The algorithm either returns a shattering set of size at most 3p or a good multiway cut M1 ⊂ M0. In the former case, we return the shattering set, in the latter case, apply the algorithm of Lemma 4.6 to M1. Continuing this way, we obtain a sequence M0 ⊃ M1 ⊃... of good multiway cuts of decreasing size. It follows that after at most |V (G)| iterative applications of the algorithm of Lemma 4.6, a shattering set of size at most 3p will be returned.

5 Finding a shadowless solution by reduction to Almost 2SAT The goal of this section is to show that we can solve Bipedal Multicut Compression∗ if we know that there is at least one shadowless solution.

Let x1,..., xn be a set of variables; a literal is either a variable xi or its negation xi. Recall that a 2CNF formula is a conjunction of clauses with at most two literals in each clause, e.g., (x1 ∨ x2 ) ∧ (x3 ) ∧ (x1 ∨ x4 ). The classical 2SAT problem asks if a given 2CNF formula has a satisfying assignment. It is well-known that a satisfying assignment for a 2CNF formula can be found in linear time (if exists). However, it is NP-hard to ﬁnd an assignment that maximizes the number of satisﬁed clauses, or equivalently, to ﬁnd a minimum set of clauses whose removal makes the formula satisﬁable. Lokshtanov et al. [32] (improving earlier work [42, 14, 41]) gave an O∗ (2.3146k ) time algorithm for the problem of deciding if a 2CNF formula can be made satisﬁable by the deletion of at most k clauses; they call this problem Almost 2SAT. We need a variant of the result here, where instead of deleting at most k clauses, we are allowed to delete at most k variables. An easy reduction (see Appendix B) gives an algorithm for this variant. If φ is a 2CNF formula and X is a set of variables, then we denote by φ \ X the formula obtained by removing every clause containing a literal of a variable in X.

** Theorem 5.1.**

Given a 2CNF formula φ and an integer k, in time O∗ (2.3146k ) we can either ﬁnd a set X of at most k variables such that φ \ X is satisﬁable, or correctly state that no such set X exists.

It is not diﬃcult to reduce ﬁnding a shadowless solution to the problem solved by Theorem 5.1.

For each vertex v of G\W, we introduce a variable whose value expresses which leg of the component containing v is reachable from v. This formulation cannot express that a vertex is separated from both legs. However, as we assume that there is a shadowless solution, we do not have to worry about such vertices.

Proof (of Lemma 2.7). We encode the Bipedal Multicut Compression∗ instance I = (G, T, W, p) as a 2CNF formula φ the following way. For each component C of G \ W having two legs, let 0 (C) and 1 (C) be the two legs. If component C has only one leg, then let 0 (C) be this leg, and let 1 (C) be undeﬁned. For every vertex v ∈ C, let 0 (v) = 0 (C) and 1 (v) = 1 (C). We construct a formula φ whose variables correspond to V (G) \ W. The intended meaning of the variables is that v has value b ∈ {0, 1} if v is in the same component as b (v) after removing the solution. To enforce this

**interpretation, φ contains the following clauses:**

This completes the description of φ. Note that no clause is introduced for pairs (u, v) ∈ T with u, v ∈ W, but these pairs are automatically separated by a solution that is a multiway cut of W.

Furthermore, we can assume that W induces an independent set, otherwise there is no solution.

We show ﬁrst that if I has a shadowless solution S, then removing the corresponding variables of φ makes it satisﬁable. As S is shadowless and it is a multiway cut of W, every vertex of G \ S is in the same component as exactly one of 0 (v) and 1 (v); let the value of variable v be b if vertex v is in the same component as b (v). It is clear that this assignment satisﬁes the clauses in the ﬁrst two groups. Consider a clause (u = bu ∨ v = bv ) from the third group. This means that (u, v) ∈ T and bu (u) = bv (v) = w ∈ W. If this clause is not satisﬁed, then u = bu and v = bv. By the way the assignment was deﬁned, this is only possible if u is in the same component of G \ S as bu (u) = w and v is in the same component of G \ S as bv (v) = w. Therefore, u and v are in the same component of G \ S, contradicting the assumption that S is a solution of I. Clauses in Group 4 can be checked similarly.

We have shown that φ can be made satisﬁable by the deletion of p variables. By Theorem 5.1, we can ﬁnd such a set S of variables in time O∗ (4p ). To complete the proof, we show that such a set S corresponds to a (not necessarily shadowless) solution of I. Let us show ﬁrst that S is a multiway cut of W. Suppose that there is a path P connecting w0, w1 ∈ W in G \ S. We can assume that the internal vertices of P are disjoint from W, i.e., they are in one component C of G \ W with two legs.

Thus there is a path P from a neighbor v0 of w0 to a neighbor v1 of w1 in C \ S. Suppose without loss of generality that 0 (C) = w0 and 1 (C) = w1. As the clauses in Group 1 are satisﬁed, every variable of P has the same value. However, because of the clauses in Group 2, we have xv0 = 0 and xv1 = 1, a contradiction. Therefore, we can assume that S is a multiway cut of W.

Suppose now that there is some (u, v) ∈ T such that u, v ∈ W are in the same component of G \ S ; let P be a u − v path in G \ S. As W is a multicut of T, it is clear that P goes through at least one vertex of W. We have seen that S is a multiway cut of W, thus P goes through exactly one vertex of W. Let P = P1 wP2 for some path P1 that is fully contained in the component of G \ W containing u and path P2 fully contained in the component containing v. Let bu, bv ∈ {0, 1} be such that bu (u) = bv (v) = w. Group 1 ensures that every variable of P1 has the same value and Group 2 ensures that the last variable of P1 has value bu, thus u = bu. A similar argument shows that v = bv. However, this means that clause (u = bu ∨ v = vu ) of Group 3 is not satisﬁed, a contradiction. Finally, a similar argument shows that the clauses in Group 4 ensure that pairs (u, v) ∈ T with u ∈ W, v ∈ W are separated.

6 Hardness of Directed Multicut We prove that Directed Edge Multicut is W[1]-hard parameterized by the solution size, thus it is not ﬁxed-parameter tractable (assuming the widely-held complexity hypothesis FPT = W[1]).

Recall that the edge and vertex versions are equivalent, thus the hardness result holds for both versions. The proof below proves the hardness result for the weighted version of the problem, where each edge has a positive integer weight, and the task is to ﬁnd a multicut with total weight at most p. If the weights are polynomial in the size of the input (which is true in the proof), then the weighted version can be reduced to the unweighted version by introducing parallel edges. Thus the proof proves the hardness of the unweighted version as well. For notational convenience, we allow edges with weight ∞; such edges can be easily replaced by edges with suﬃciently large ﬁnite weight.

** Theorem 6.1.**

Directed Edge Multicut is W[1]-hard parameterized by the size p of the cutset.

Proof. We prove hardness for the weighted version of the problem by parameterized reduction from Clique. Let G be a graph with m edges and n vertices where a clique of size t has to be found. We construct an instance of Directed Edge Multicut containing t(t − 1) gadgets: for each ordered pair (i, j) (1 ≤ i, j ≤ t, i = j), there is a gadget Gi,j. Intuitively, each gadget Gi,j has 2m possible states and a state represents an ordered pair (vi, vj ) of adjacent vertices. We would like to ensure that the gadgets describe a t-clique {v1,..., vt } in the sense that Gi,j represents the pair (vi, vj ).

In order to enforce this interpretation, we need to connect the gadgets in a way that enforces two

**properties:**

(1) if Gi,j represents (vi, vj ), then Gj,i represents (vj, vi ), and (2) if Gi,j represents (vi, vj ) and Gi,j represents (ui, uj ), then vi = ui.