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

Fixed-parameter tractability of multicut parameterized by the size

of the cutset∗

D´niel Marx† Igor Razgon‡

a

August 27, 2013

Abstract

Given an undirected graph G, a collection {(s1, t1 ),..., (sk, tk )} of pairs of vertices, and an

integer p, the Edge Multicut problem ask if there is a set S of at most p edges such that the

removal of S disconnects every si from the corresponding ti. Vertex Multicut is the analogous

problem where S is a set of at most p vertices. Our main result is that both problems can be solved in time 2O(p ) · nO(1), i.e., ﬁxed-parameter tractable parameterized by the size p of the cutset in the solution. By contrast, it is unlikely that an algorithm with running time of the form f (p) · nO(1) exists for the directed version of the problem, as we show it to be W[1]-hard parameterized by the size of the cutset.

1 Introduction From the classical results of Ford and Fulkerson on minimum s − t cuts [20] to the more recent √ O( log n)-approximation algorithms for sparsest cut problems [44, 1, 18], the study of cut and separation problems have a deep and rich theory. One well-studied problem in this area is the Edge Multicut problem: given a graph G and pairs of vertices (s1, t1 ),..., (sk, tk ), remove a minimum set of edges such that every si is disconnected from its corresponding ti for every 1 ≤ i ≤ k. For k = 1, Edge Multicut is the classical s − t cut problem and can be solved in polynomial time. For k = 2, Edge Multicut remains polynomial-time solvable [46], but it becomes NP-hard for every ﬁxed k ≥ 3 [15]. Edge Multicut can be approximated within a factor of O(log k) in polynomial time [22] (even in the weighted case where the goal is to minimize the total weight of the removed edges). However, under the Unique Games Conjecture of Khot [29], no constant factor approximation is possible [7]. One can analogously deﬁne the Vertex Multicut problem, where the task is to remove a minimum set of vertices. An easy reduction shows that the vertex version is more general than the edge version.

Using brute force, one can decide in time nO(p) if a solution of size at most p exists. Our main result is a more eﬃcient exact algorithm for small values of p (the O∗ notation hides factors that are

**polynomial in the input size):**

** Theorem 1.1.**

Given an instance of Vertex Multicut or Edge Multicut and an integer p, one can ﬁnd in time O∗ (2O(p ) ) a solution of size p, if such a solution exists.

∗ A preliminary version of the paper was presented at STOC 2011 [37]. Research of the second author was supported by the European Research Council (ERC) grant “PARAMTIGHT: Parameterized complexity and the search for tight complexity results,” reference 280152.

† Institute for Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI), dmarx@cs.bme.hu ‡ Department of Computer Science and Information Systems, Birkbeck, University of London. igor@dcs.bbk.ac.uk That is, we prove that Vertex Multicut and Edge Multicut are ﬁxed-parameter tractable parameterized by the size p of the solution, resolving a very challenging open question in the area of parameterized complexity. (Recall that a problem is ﬁxed-parameter tractable (FPT) with a particular parameter p if it can be solved in time f (p) · nO(1), where f is an arbitrary computable function depending only on p; see [17, 19, 39] for more background). The question was ﬁrst asked explicitly perhaps in [34]; it has been restated more recently as an open problem in e.g., [25, 8].

Our result shows in particular that multicut is polynomial-time solvable if the size of the optimum √ solution is O( 3 log n) (where n is the input size).

One reason why multicut is a fundamental problem is that it is able to express several other problems. It has been observed that a correlation clustering problem called Fuzzy Cluster Editing can be reduced to (and in fact, equivalent with) Edge Multicut [3, 16, 2]. Our results show that Fuzzy Cluster Editing is FPT parameterized by the editing cost, settling this open problem discussed e.g., in [3].

Previous work. The ﬁxed-parameter tractability of multicut and related problems has been thoroughly investigated in the literature. Edge Multicut is NP-hard on trees, but it is known to be FPT, parameterized by the maximum number p of edges that can be deleted, and admits a polynomial kernel [5, 26]. Multicut problems were studied in [25] for certain restricted classes of graphs. For general graphs, Vertex Multicut is FPT if both p and and the number of terminal pairs k are chosen as parameters (i.e, the problem can be solved in time f (p, k) · nO(1) [35, 45, 24] for some function f ). The algorithm of Theorem 1.1 is superior to these result in the sense that the running time depends polynomially on the number k of terminals pairs, and the exponential dependence is restricted to the parameter p, the number of deletions. For the special case of Multiway Cut (where terminals in a set T have to be pairwise separated form each other), algorithms with running time of the form f (p) · nO(1) were already known [35, 8, 24], but apparently these algorithms do not generalize in an easy way to multicut. An FPT 2-approximation algorithm was given in [36] for Edge Multicut: in time O∗ (2O(p log p) ), one can ﬁnd a solution of size 2p if a solution of size p exists. There is no obvious FPT algorithm for the problem even on bounded-treewidth graphs, although one can obtain linear-time algorithms if the treewidth remains bounded after adding an edge si ti for each terminal pair [23, 40]. A PTAS is known for bounded-degree graphs of bounded treewidth [6].

Our techniques. The ﬁrst two steps of our algorithm follows [36]. We start by an opening step that is fairly standard in the design of FPT algorithms. Instead of solving the original Vertex Multicut problem, we solve the compression version of the problem, where the input contains a solution W of size p + 1, and the task is to ﬁnd a solution of size p (if exists). A standard argument called iterative compression [43, 28] shows that if the compression problem is FPT, then the original problem is FPT. Alternatively, we can use the polynomial-time approximation algorithm of Gupta [27], which produces a solution W of size p2 if a solution of size p exists. In this case, O(p2 ) iterations of the compression algorithm gives a solution of size p.

Next, as in [36], we try to reduce the compression problem to Almost 2SAT (delete k clauses to make a 2-CNF formula satisﬁable; also known as 2CNF Deletion), which is known to be FPT [42, 14, 41]. However, our 2SAT formulation is very diﬀerent from the one in [36]: we introduce a single variable xv only for each vertex of G, while in [36] there is a variable xv,w for every vertex v ∈ V (G) and vertex w ∈ W of the initial solution. This simpler reduction to Almost 2SAT is

**correct only if the instance satisﬁes two quite special properties:**

(1) every component of G \ W is adjacent to at most two vertices of W (“has at most two legs”), and (2) there is a solution S such that every component of G \ S contains a vertex of W (“no vertex is isolated from W after removing the solution S” or “no vertex is in the shadow of S”).

The main part of the paper is devoted to showing how these properties can be achieved. In order to achieve property (1), we show by an analysis of cuts and performing appropriate branching steps that the set W can be extended in such a way that every component has at most two legs (Section 4).

To achieve property (2), we describe a nontrivial way of sampling random subset of vertices such that if we remove this subset by a certain contraction operation (taking the torso of the graph), then without changing the solution, we get rid of the parts not reachable from W with some positive probability (Section 3). This random sampling uses the concept of “important separators,” which was introduced in [35], and has been implicitly used in [9, 42, 8] in the design of parameterized algorithms. We consider the random sampling of important separators the main new technical idea of the paper. This technique and its generalizations have turned out to be useful for other problems as well [11, 31, 12, 11, 10, 33, 30] and we expect it to have further application in the future.

Directed graphs. Having resolved the ﬁxed-parameter tractability of Vertex Multicut, the next obvious question is what happens on directed graphs. Note that for directed graphs, the edge and vertex versions are equivalent. In directed graphs, multicut becomes much harder to 1− approximate: there is no polynomial-time 2log n -approximation for any 0, unless NP ⊆ ZPP [13]. From the ﬁxed-parameter tractability point of view, the directed version of the problem received particular attention because Directed Feedback Vertex Set or DFVS (delete p vertices to make the graph acyclic) can be reduced to Directed Multicut. The ﬁxed-parameter tractability of DFVS had been a longstanding open question in the area of parameterized complexity until it was solved by Chen et al. [9] recently. The main idea that led to the solution is that DFVS can be reduced to a variant (in fact, special case) of Directed Multicut called Skew Multicut, where the task is to break every path from si to tj for every i j. By showing that Skew Multicut is FPT parameterized by the size of the solution, Chen et al. [9] proved the ﬁxed-parameter tractability of DFVS. We show in Section 6 that, unlike Skew Multicut, the general Directed Multicut problem is unlikely to be FPT.

** Theorem 1.2.**

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

Independent and followup work. A preliminary version of this paper appeared in [37]; the current version contains essentially the same algorithm, but the terminology and organization of Section 5 were signiﬁcantly changed. Independently from our work, Bousquet et al. [4] presented in the same volume a proof that Multicut is FPT parameterized by the size p of the solution. The two algorithms have certain parts in common: both reduce the problem to the compression version and both ensure that we have to deal with components having only two legs. However, the main part of the two algorithms are substantially diﬀerent: the current paper introduces the technique of random sampling of important separators and uses it to reduce the problem to Almost 2SAT, while Bousquet et al. [4] uses an approach based on a series of problem-speciﬁc reductions to reduce the problem to 2SAT.

Subsequently to the ﬁrst version of this paper, random sampling of important separators has been used in several other applications. For undirected graphs, the technique was used by Lokshtanov and Ramanujan [33] to solve a parity version of Multiway Cut and by Chitnis et al. [10] to solve a homomorphism problem generalizing certain deletion problems. For directed graphs, even though Directed Multicut is W[1]-hard parameterized by p (see Section 6), Chitnis et al. [11] proved that the special case Directed Multiway Cut (Given a set T of terminals, break every directed path between two diﬀerent terminals by removing at most p edges/vertices) is FPT parameterized by p. A consequence of this result is that Directed Multicut with k = 2 is FPT parameterized by p is FPT. Kratsch et al. [30] proved that Directed Multicut on directed acyclic graphs (DAGs) is FPT with combined parameters k and p, and strenghed our hardness result by showing that Directed Multicut remains W[1]-hard parameterized by p even on DAGs. However, the complexity of Directed Multicut for k = 3 or with combined parameters k and p remains an interesting open question.

Chitnis et al. [12] use the random sampling technique to show the ﬁxed-parmeter tractability of Directed Subset Feedback Vertex Set. They present an

**Abstract**

framework that formalizes under which conditions this technique can be used, and they improve the randomized selection and its analysis to obtain better success probability and improved running time.

A very diﬀerent application of the technique is given by Lokshtanov and Marx [31] in the context of clustering problems. They study a family of clustering problems such as partitioning the vertices of an undirected graph into clusters of size at most p such that at most q edges leave each cluster.

The problem boils down to being able to check whether a given vertex v is contained in such a cluster. It turns out that the random sampling of important separators technique can be used to show that this task (and therefore the original clustering problem) is FPT parameterized by q by reducing it to a knapsack-like problem.

2 Framework: compression, shadows, legs Let G be an undirected graph and let T = {(s1, t1 ),..., (sk, tk )} be a set of terminal pairs. We say that a set S ⊆ V (G) of vertices is a multicut of (G, T) if there is no component1 of G \ S that contains both si and ti for some 1 ≤ i ≤ k (note that it is allowed that S contains si or ti ). The

**central problem of the paper is the following:**

We prove the ﬁxed-parameter tractability of Vertex Multicut by a series of reductions (see Figure 1). First we argue that it is suﬃcient to solve an easier solution compression problem. Then we present two reductions that modify the problem in such a way that it is suﬃcient to look for solutions that are shadowless and we can assume that the instance is bipedal. The last step of the proof is reducing this special variant of the problem to Almost 2SAT.

2.1 Compression The ﬁrst step in the proof of Theorem 1.1 is a standard technique in the design of parameterized algorithms: we deﬁne and solve the compression problem, where it is assumed that the input contains a feasible solution of size larger than p. As this technique is standard (and in particular, we follow the approach of [36] for Edge Multicut), we keep this section short and informal.

Intuitively, it is clear that proving Lemma 2.1 could be easier than proving that Vertex Multicut is FPT: the extra input W can give us useful structural information about the graph (and as |W | appears in the running time, a large W is also helpful). What’s not obvious is how solving Multicut Compression gives us any help in the solution of the original Vertex Multicut problem. We sketch two methods.