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

** Method 1. Let us use the polynomial-time approximation algorithm of Gupta [27] to ﬁnd a multicut W of size at most c · OPT2, where c is a universal constant and OPT is the minimum size of a multicut.**

If |W | ≥ c · p2, then we can safely answer “NO”, as there is no multicut of size at most p. Otherwise, we run the algorithm of Lemma 2.1 for this set W to obtain a solution in time O∗ (2O((p+log |W |) ) = O∗ (2O(p ) ).

** Method 2. The standard technique of iterative compression [43, 28] allows us to reduce Vertex Multicut to at most |V (G)| instances of Multicut Compression with |W | = p + 1.**

This technique was used for the 2-approximation of Edge Multicut in [36] and its application is analogous in our case. Let (G, T, p) be an instance of Vertex Multicut. Suppose that V (G) = {v1,..., vn }, let Gi = G[{v1,..., vi }], and let Ti be the subset of T containing the pairs with both endpoints in Gi. One by one, we consider the instances (Gi, Ti, p) in ascending order of i, and for each instance we ﬁnd a solution Si of size at most p. We start with S0 = ∅. For some i 0, we compute Si provided that Si−1 is already known. Observe that Si−1 ∪ {vi } is a multicut of size at most p + 1 for (Gi, Ti ). Thus we can use the algorithm for Multicut Compression, which either returns a multicut Si of (Gi, Ti ) having size at most p or returns “NO”. In the ﬁrst case, we can continue the iteration with i + 1. In the second case, we know that there is no multicut of size p for (G, T) (as there is no such multicut even for (Gi, Ti )), and hence we can return “NO”.

Both methods result in O∗ (2O(p ) ) time algorithms. However, we feel it important to mention both approaches, as improvements in Lemma 2.1 might have diﬀerent eﬀects on the two methods.

It will be convenient to work with a slightly modiﬁed version of the compression problem. We say that a set S ⊆ V (G) is a multiway cut of W ⊆ V (G) if every component of G \ S contains at most one vertex of W.

Multicut Compression∗ Input: A graph G, an integer p, a set T of pairs of vertices of G, and a multicut W of (G, T).

Output: A set S of size at most p such that

That is, Multicut Compression∗ has two additional constraints on the solution S. In Sections 4–5,

**we prove that this problem is FPT:**

** Lemma 2.2.**

Multicut Compression∗ can be solved in time O∗ (2O((p+log |W |) ) ).

It is not diﬃcult to reduce Multicut Compression to Multicut Compression∗ (an analogous reduction was done in [36] for the the edge case). We brieﬂy sketch such a reduction. In order to solve an instance (G, T, W, p) of Multicut Compression, we ﬁrst guess the intersection X of the multicut W given in the input and the solution S we are looking for. This guess results in at most p |W | branches; in each branch, we remove the vertices of X from G and decrease i=1 i p by |X|. Thus in the following, we can restrict our attention to solutions disjoint from W. Next, we branch on all possible partitions (W1,..., Wt ) of W, contract each Wi into a single vertex, and solve Multicut Compression∗ on the resulting instance (G, T, W, p ). One of the partitions (W1,..., Wt ) corresponds to the way the solution S partitions W into connected components, and in this case S is a multiway cut of W in G. Thus if the original Multicut Compression instance has a solution S, then it is a solution of one of the constructed Multicut Compression∗ instances.

Conversely, any solution of the constructed instances is a solution of the original instance. As the number of partitions of W can be bounded by |W |O(|W |), the running time claimed in Lemma 2.1 follows from Lemma 2.2. Thus in the rest of the paper, it is suﬃcient to prove Lemma 2.2 to obtain the main result, i.e., Theorem 1.1. Thus proving Lemma 2.2 implies the main result Theorem 1.1.

2.2 Shadows An important step in our algorithm for Multicut (and in further applications of the randomized sampling of important separators method) is to argue about solutions that are “shadowless” in the sense deﬁned below. Intuitively, we imagine the vertices in W as light sources, light spreads on the edges, and S blocks the light (see Figure 2).

Deﬁnition 2.3. Let I = (G, T, W, p) be an instance of the Multicut Compression∗ problem, and let S be a solution for I. The shadow of the set S is the set of vertices not reachable from any vertex of W in G \ S. We say that the solution S is shadowless if the shadow is empty, i.e., G \ S has exactly |W | components.

In Section 3, we present a randomized algorithm that modiﬁes the instance such that if a solution exists, then it makes the solution shadowless with positive probability. The algorithm is based on a randomized contraction of sets deﬁned by “important separators”; we review this concept in

**Section 3.3. The algorithm can be derandomized to obtain the following lemma:**

** Lemma 2.4 (shadowless reduction).**

Given an instance I of the Multicut Compression∗ problem, we can construct in time O∗ (2O(p ) ) a set of t = 2O(p ) log n instances I1,..., It, each with the same parameter p as I, such that

1. Any solution of Ii for any 1 ≤ i ≤ t is a solution of I.

Figure 3: An instance with 7 components. The strong circles are the vertices of W, the numbers show the number of legs for each component.

2. If I has a solution, then Ii has a shadowless solution for at least one 1 ≤ i ≤ t.

Thus Lemma 2.4 allows us to reduce the Multicut Compression∗ problem into a variant where the task is to ﬁnd a shadowless solution.

2.3 Components and legs In order to ﬁnd a shadowless solution for a Multicut Compression∗ instance, the problem is further transformed in Section 4 using the concept of legs.

Deﬁnition 2.5. Given an instance (G, T, W, p) of Multicut Compression∗, we say that a component C of G \ W has -legs if C is adjacent with vertices of W (see Figure 3). We say that a Multicut Compression∗ instance is bipedal if every component of G \ W has at most two legs;

Bipedal Multicut Compression∗ is the problem restricted to such instances.

The transformation presented in Section 4 reduces Multicut Compression∗ to a bounded number of bipedal instances.

** Lemma 2.6 (bipedal reduction).**

Given an instance I of the Multicut Compression∗ problem with parameter p, in time O∗ (2O((p+log |W |) ) ) we can either solve this instance or construct a set of t = 2O(p+log |W |) instances I1,..., It, of Bipedal Multicut Compression∗ each with parameter at most p, such that

1. Any solution of Ii for any 1 ≤ i ≤ t is a solution of I.

2. If I has a shadowless solution, then Ii has a shadowless solution for at least one 1 ≤ i ≤ t.

Finally, in Section 5, we show how this solution can be found by a quite intuitive reduction to an FPT problem Almost 2SAT.

** Lemma 2.7.**

Let I = (G, T, W, p) be an instance of Bipedal Multicut Compression∗ that has a shadowless solution S of size at most p. In time O∗ (4p ), we can ﬁnd a (not necessarily shadowless) solution S.

Combining Lemmas 2.4–2.7 allows us to prove Lemma 2.2 and therefore to solve Vertex Multicut.

Proof (of Lemma 2.2). Let us apply the Algorithm of Lemma 2.4 to an instance I = (G, T, W, p) of Multicut Compression∗. This algorithm takes time O∗ (2O(p ) ) and produces t = 2O(p ) log n instances Ii of the Multicut Compression∗ problem, each with parameter at most p, so that the original instance I has a solution if and only if one of these t instances has a shadowless solution.

Moreover a (not necessarily shadowless) solution of any of these instances is also a solution of the orginal instance.

Apply to each instance Ii the algorithm of Lemma 2.6, which in time O∗ (2O((p+log |W |) ) ) either returns an answer or produces 2O((p+log |W |) ) instances Ii,j, each with parameter at most p, of the Bipedal Multicut Compression∗ problem such that Ii has a shadowless solution if and only if at least one Ii,j has a shadowless solution. Moreover a (not necessarily shadowless) solution of any new instance Ii,j is also a solution of Ii.

Combining the above two steps, we conclude that in time O∗ (2O((p+log |W |) ) ) the algorithm produces 2O((p+log |W |) ) log n instances of the Bipedal Multicut Compression∗ problem such that the original instance I has a solution if and only if at least one of the these 2O((p+log |W |) ) log n instances has a shadowless solution. Moreover a (not necessarily shadowless) solution of any instance Ii,j is also a solution of I.

Finally, we apply to each resulting instance Ii,j of the Bipedal Multicut Compression∗ problem the algorithm of Lemma 2.7. By the discussion above, if the algorithm returns a solution for at least one of the instances, then this is a solution of the original instance I. If the algorithm returns “NO” for all the instances, this means that no one of them has a shadowless solution. It follows that the original instance does not have a solution either. Taking into account that the algorithm of Lemma 2.7 takes time O∗ (4p ), processing of 2O((p+log |W |) ) log n instances takes time O∗ (2O((p+log |W |) ) ). Consequently, the instance I of the Multicut Compression∗ problem can be solved in time O∗ (2O((p+log |W |) ) ).

3 Making the solution shadowless The purpose of this section is to reduce solving Multicut Compression∗ to ﬁnding a shadowless solution. We present a randomized transformation that, given an instance having a solution, modiﬁes the instance in such a way that the new instance has a shadowless solution with probability 2−O(p ).

**More precisely:**

** Lemma 3.1.**

Given an instance I of the Multicut Compression∗ problem, we can construct in time O∗ (2O(p) ) an instance I with the same parameter p as I such that

1. Any solution of I is a solution of I.

2. If I has a solution, then I has a shadowless solution with probability 2−O(p ).

This means that if I has a solution, then by invoking Lemma 3.1 2O(p ) times, with constant probability at least one of the instances has a shadowless solution. Thus if we are able to solve the problem with the assumption that a shadowless solution exists, then this way we can get a solution for I with constant probability. The main result of this section is a derandomized version of this transformation (Lemma 2.4).

The main idea in the proof of Lemma 3.1 is to try to randomly guess a set Z whose removal does not change the instance substantially, but makes the instance shadowless. Section 3.1 introduces the torso operation, which is used to remove the set Z, and states what properties the set Z needs to satisfy. The construction of Z is based on the observation that the solution can be characterized by a “closest set” and we need to locate the boundary of such a set (Section 3.2). We develop a randomized algorithm for this purpose in Sections 3.3–3.6. The algorithm uses the notion of C

important separators; Section 3.3 reviews this concept and shows why it is relevant for our problem.

Sections 3.4–3.5 describe and analyze the randomized selection process. Section 3.6 shows how the random selection can be derandomized to obtain the deterministic version, Lemma 2.4.

3.1 Torsos and shadowless solutions The randomized transformation can be conveniently described using the operation of taking the torso of a graph.

Deﬁnition 3.2. Let G be a graph and C ⊆ V (G). The graph torso(G, C) has vertex set C and two vertices a, b ∈ C are adjacent if {a, b} ∈ E(G) or there is a path P in G connecting a and b whose internal vertices are not in C.

In particular, every edge of G[C] is in torso(G, C). It is easy to show that this operation

**preserves separation inside C:**

Proposition 3.3. Let C ⊆ V (G) be a set of vertices in G and let a, b ∈ C two vertices. A set S ⊆ C separates vertices a and b in torso(G, C) if and only if S separates these vertices in G.

Proof. Let P be a path connecting a and b in G and suppose that P is disjoint from the set S. The path P contains vertices from C and from V (G) \ C. If u, v ∈ C are two vertices such that every vertex of P between u and v is from V (G) \ C, then by deﬁnition there is an edge uv in torso(G, C).

Using these edges, we can modify P to obtain a path P that connects a and b in torso(G, C) and avoids S.

Conversely, suppose that P is a path connecting a and b in the graph torso(G, C) and it avoids S ⊆ C. If P uses an edge uv that is not present in G, then this means that there is a path connecting u and v whose internal vertices are not in C. Using these paths, we can modify P to obtain a path P that uses only the edges of G. Since S ⊆ C, the new vertices on the path are not in S, i.e., P avoids S as well.

Let I = (G, W, T, p) be an arbitrary instance of Multicut Compression∗. Given a set Z ⊆

**V (G) \ W of vertices, the reduced instance I/Z = (G, W, T, p) is deﬁned the following way:**

1. The graph G is torso(G, V (G) \ Z).

2. For every v ∈ V (G), let φ(v) = N (C) if v belongs to component C of G[Z], and let φ(v) = {v} if v ∈ Z. The set T is obtained by by replacing every pair (x, y) ∈ T with the set of pairs {(x, y ) | x ∈ φ(x), y ∈ φ(y)}.

The main observation is that if we perform this torso operation for a Z that is suﬃciently large to cover the shadow of a hypothetical solution S and suﬃciently small to be disjoint from S, then S becomes a shadowless solution of I/Z. Furthermore, the torso operation is “safe” in the sense that it does not make the problem easier, i.e, does not create new solutions.

** Lemma 3.4.**

Let I = (G, T, W, p) be an instance of Multicut Compression∗ and let Z ⊆ V (G) \ W be a set of vertices.

(1) Every solution of I/Z is a solution of I.

(2) If I has a solution S such that Z covers the shadow and Z ∩ S = ∅, then S is a shadowless solution of I/Z.