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

In the second phase, we select a random subset of universe Ip,2 of size n2 ≤ pn, and there is a collection A2 ⊆ Ip,2 of size a2 ≤ 2p and a collection B2 ⊆ Ip,2 of size b2 ≤ p2 such that if every set in A2 is selected and no set in B2 is selected, then (E4) and (E5) hold. As in the ﬁrst phase, we can replace this random choice by enumerating the functions of an (n2, a2 + b2, (a2 + b2 )2 )-splitter and every subset F ⊆ [(a2 + b2 )2 ] of size b2 (there are (a2 +b2 ) = 2O(p ) such sets F ). This time, we b2 select a set X ∈ Ip,2 if f (X) is not in F and it is clear that there is an f and F for which (E4) and (E5) hold.

Let us bound the number of branches of the algorithm. In both phases, the size of the splitter family is 2O(p) · log n and the there are 2O(p ) possible F. (Note that the splitter family can be constructed in time polynomial in the size of the family.) Thus the algorithm produces 2O(p ) · log2 n sets.

4 Reduction to the bipedal case Let (G, T, W, p) be an instance of the Multicut Compression∗ problem. Let us call a component of G \ W having at least two legs a non-trivial component of G w.r.t. W (when the context is clear, we will just refer to a non-trivial component). As the solution of Multicut Compression∗ has to be a set S that is disjoint from W and a multiway cut of W, the number of non-trivial components is a lower bound on the size of the solution.

We present an algorithm that either solves the given instance of the Multicut Compression∗ problem or produces a set of instances of the Bipedal Multicut Compression∗ problem whose number is bounded by a function of p and such that if the considered instance of the Multicut Compression∗ problem has a shadowless solution then one of the output instances of the Bipedal Multicut Compression∗ problem has a solution. In addition, any (not necessarily shadowless) solution of any of these output instances is a solution of the input instance of the Multicut Compression∗ problem. The key ingredient of this algorithm is a procedure that, given an instance of the Multicut Compression∗ problem where at least one component has more than 2 legs, reduces this instance to a set of instances whose number is bounded by a function of p and such that in each instance either the parameter is decreased or the number of non-trivial components is increased.

The main idea for the branching is the following. Let B be a set of vertices in G \ W and let S be a hypothetical shadowless solution for Multicut Compression∗. We try to guess what happens to each vertex of B in the solution S. It is possible that a vertex v ∈ B is in S; in this case, we delete v from the instance and reduce the parameter. Otherwise, as the solution is shadowless, v has to be in the same component as precisely one w ∈ W (since S is a multiway cut of W ). In this case, identifying v and w does not change the solution.

The following lemma formalizes these observations. Given a set B of vertices in G \ W and a function f : B → W, we denote by Gf the graph obtained by replacing each set {w} ∪ f −1 (w) with a single vertex (with removal of loops and multiple occurrences of edges). To simplify the presentation, we will assume that this new vertex is also named w. We denote by Tf the set of terminal pairs where each vertex v ∈ B is replaced by f (v), and we denote by T \ v the set where every pair involving the vertex v is removed.

** Lemma 4.1.**

Let K be a non-trivial component of G \ W with set of legs W and let B ⊆ K. If (G, T, W, p) has a shadowless solution, then one of the following statements is true.

• There is a v ∈ B such that the instance (G \ v, T \ v, W, p − 1) has a shadowless solution.

• There is a function f : B → W such that instance (Gf, Tf, W, p) has a shadowless solution.

Moreover, if any of the above instances has a solution, then (G, T, W, p) has a solution as well.

Proof. Assume that (G, T, W, p) has a shadowless solution S. Then it either intersects or does not intersect with B. In the former case, we can specify a v ∈ S ∩ B such that S \ {v} is a shadowless solution of (G \ v, T \ v, W, p − 1). In the latter case, we can assign each v ∈ B precisely one vertex f (v) of W such that vertex v belongs to the same component of G \ S as f (v). It is not hard to see that S is a shadowless solution of (Gf, Tf, W, p).

For the second statement, we observe that the existence of a solution for any of the above instances implies the existence of a solution for (G, T, W, p). This is certainly true in the ﬁrst case, where we delete a vertex and decrease the parameter by 1. In the second case, the statement follows from the fact that replacing G with Gf by identifying vertices cannot make the problem any easier.

** Lemma 4.1 determines a set of recursive calls to be applied in order to ﬁnd a solution for the given instance (G, T, W, p) of the Multicut Compression∗ problem, if a shadowless solution is guaranteed to exist.**

It is clear that in each step, the number of directions we branch into is bounded by a function of p, |B|, and |W | (observe that the number of functions f : B → W can be bounded by |W ||B| ≤ |W ||B| ). However, in order to ensure that the size of the search tree is bounded, we need to ensure that the height of the search tree is bounded as well. This is obvious for the ﬁrst type of branches, as p decreases. The following property ensures that in every branch of the second type, either the number of nontrivial components increases or we get an instance that trivially has no solution.

Deﬁnition 4.2. Let K be a non-trivial component and let W ⊆ W be its set of legs. Let B be a subset of K. We say that B is a shattering set if for any function f : B → W one of the following statements is true regarding the instance (Gf, Tf, W, p) of the Multicut Compression∗.

• There is a w ∈ W such that there is no w −(W \{w}) separator of size at most p in Gf [K ∪ W ].

• The number of non-trivial components of Gf \ W is greater than the number of non-trivial components of G \ W.

Note that the ﬁrst possibility includes the case when Gf [W ] is not an independent set (recall that an X −Y separator is disjoint from X ∪Y by deﬁnition). In Section 4.1, we present a polynomial-time algorithm for ﬁnding a shattering set.

** Lemma 4.3.**

Given an instance (G, T, W, p) of the Multicut Compression∗ problem and a component K of G \ W with more than two legs, we can ﬁnd a shattering set B ⊆ K of size at most 3p in polynomial time.

With Lemma 4.3 in mind, we are ready to prove Lemma 2.6, the main statement of this section.

Proof (of Lemma 2.6). The desired algorithm looks as follows. If the given instance (G, T, W, p) of Multicut Compression∗ satisﬁes one of the following cases, then we can determine the answer

**without any further branching:**

• All the terminal pairs of T are separated: solve the multiway cut problem (G, W, p).

• The parameter is zero while there are unseparated terminals: this is a “NO” instance.

• There is a w ∈ W such that there is no w − (W \ {w}) separator of size at most p in G: this is a “NO” instance. The situation where W is not an independent set is a special subcase of this case.

• The number of non-trivial components is greater than p: this is a “NO” instance since each non-trivial component contributes at least one vertex to any solution.

• Every component has at most two legs: this is an instance of Bipedal Multicut Compression∗ problem and hence it is returned as the output.

Otherwise, we choose a component K of G \ W having more than two legs, and use Lemma 4.3 to compute a shattering subset B of K of size at most 3p. We apply recursively the branches speciﬁed in the statement of Lemma 4.1. If the “YES” answer is obtained on at least one of these branches, then we return “YES”. If all the branches return “NO”, we return “NO”. According to Lemma 4.1, the resulting answer is correct. Furthermore, assume that no one of branches produces a “YES” or “NO” answer. Then, according to Lemma 4.1, if the parent instance has a shadowless solution, then the instance on one of the branches has a shadowless solution. It is also not hard to notice that any solution for a branch instance can be easily transformed into a solution of the parent instance. Applying this argument inductively, we conclude that the same relationship exists between the original instance (G, T, W, p) and the Bipedal Multicut Compression∗ problem instances at the leaves of the recursion tree.

To bound the number of leaves of the recursion tree, let us deﬁne κ to be the number of nontrivial components. Observe that removing a vertex of V (G) \ W from G can decrease the number of nontrivial components only by at most one. Thus inspection of Lemma 4.1 shows that the measure 2p − κ strictly decreases in each branch. This means that the height of the search tree is at most 2p. The number of branches in each step can be bounded by 3p + |W |3p. Thus the number of leaves of the recursion tree can be generously bounded by 2O((p+log |W |). Taking into account that the runtime per node of the recursion tree is polynomial, it follows that the runtime of this algorithm is O∗ (2O((p+log |W |) ) ).

4.1 Finding a shattering set We try to ﬁnd a shattering set by selecting a set that separates one leg from all the other. If it is not a shattering set, then we can characterize quite well how it can look like, and where should we continue our search for a shattering set. Let us start with two simple lemmas.

** Lemma 4.4.**

Let K be a non-trivial component with a set W of at least 3 legs. If G[M1 ] and G[M2 ] are both connected for two disjoint sets M1, M2 ⊆ K, then at most one of M1 and M2 can be a multiway cut of (G[K ∪ W ], W ).

Proof. Assume the opposite. Since no two vertices of W belong to the same component of G[K ∪ W ] \ M1 and |W | ≥ 3, we can specify two vertices w and w of W whose respective components C and C in G[K ∪ W ] \ M1 are disjoint from the connected set M2. As G[K] is connected, there is a w − w path in G[K ∪ W ] that ﬁrst uses vertices from C, then vertices from (the connected set) M1, then vertices from C. This path is disjoint from M2, contradicting the assumption that M2 is a multiway cut.

** Lemma 4.5.**

Let K be a non-trivial component with a set W of at least 3 legs. Let B ⊆ K be a non-shattering set. Then there is exactly one connected component of G[K \ B] that is a multiway cut of (G[K ∪ W ], W ).

Proof. Let f : B → W be the mapping witnessing that B is not a shattering set. Let K ⊆ K \ B be the unique non-trivial component of Gf \ W that is a subset of K (witnessing B being a nonshattering set). As every neighbor of K is in B ∪ W, it is easy to see that K is a component of G[K \ B] as well. Furthermore, we claim that K is a multiway cut of (G[K ∪ W ], W ). Otherwise, a path between vertices of W in G[K ∪ W ] \ K would correspond to a walk of Gf between the same vertices which belong to a non-trivial component that is a subset of K but diﬀerent from K, in contradiction to the deﬁnition of f. Finally, Lemma 4.4 implies that K is the unique connected component of G[K \ B] being a multiway cut of G[K ∪ W ].

Let K be a non-trivial component with a set of legs W. Let M ⊆ K be a multiway cut of (G[K ∪ W ], W ). We call N (M ) (i.e., the open neighborhood of M ) the boundary of M (which possibly includes vertices of W ). For each w ∈ W, the image I(w) of w is the set of vertices of N (M ) reachable from w in G[K ∪ W ] \ M (the image may include vertex w itself, but it cannot include any other member of W ), see Figure 7. Note that I(w) is nonempty for any w ∈ W : consider the ﬁrst vertex of N (M ) on a path from w to some other leg in W. Furthermore, as M is a multiway cut, the sets I(w ) and I(w ) are disjoint for w = w : otherwise, there would be a w − w path disjoint from M. For X ⊆ W, we let I(X) = w∈X I(w). Let us select a distinguished leg w∗ ∈ W.

We say that M is good if all of the following conditions are true.

Our goal is to obtain a shattering set from the boundary of a good multiway cut. The following lemma gives a polynomial-time algorithm that either produces a shattering set, or ﬁnds a smaller good multiway cut. Interestingly, the algorithm does not check that the returned set B is a shattering using Deﬁnition 4.2 directly: this would require trying every function f : B → W. Instead, the way the set B is produced guarantees that B is indeed a shattering set.

Figure 7: M is a multiway cut of the 4 legs {1, 2, 3, 4}. The dark region represents the boundary of M. Observe that I({1, 2, 3, 4}) is a proper subset of the boundary: vertices of the boundary that are adjacent only to C and C are not in I(w) for any w ∈ {1, 2, 3, 4}.

** Lemma 4.6.**

Let K be a non-trivial component with a set W of at least 3 legs and a distinguished leg w∗. Let M be a good multiway cut of (G[K ∪ W ], W ). Then there is a polynomial-time algorithm that either returns a shattering set of size at most 3p or a good multiway cut M ⊂ M.

Proof. The desired algorithm ﬁrst computes a smallest I(w∗ )−I(W \{w∗ }) separator S of G[N (M )∪ M ] (recall that the images are nonempty). Observe that S is an inclusionwise minimal w∗ − W \{w∗ }

**separator in G[K ∪ W ] (and hence nonempty). We consider three cases:**

1. If |S| p, then the algorithm returns B := N (M ) \ W reporting it as a shattering set.

2. If |S| ≤ p and there is a unique connected component M of G[K \ (N (M ) ∪ S)] that is a multiway cut of (G[K ∪ W ], W ), then the algorithm returns M reporting it as a good multiway cut.

3. If |S| ≤ p and there is no such unique M, then the algorithm returns B := (N (M ) ∪ S) \ W reporting it as a shattering set.

This algorithm clearly takes polynomial time. The remaining proof establishes correctness of the algorithm in each of these three cases.

** Case 1. The deﬁnition of good multiway cut implies that that B := N (M ) \ W has size at most 2p.**