# «Abstract. In this paper, we study a parity based generalization of the classical MULTIWAY CUT problem. Formally, we study the PARITY MULTIWAY CUT ...»

Parameterized Tractability of Multiway Cut with Parity

Constraints

Daniel Lokshtanov1 and M. S. Ramanujan2

University of California, San Diego, USA.

daniello@ii.uib.no

The Institute of Mathematical Sciences, Chennai, India.

msramanujan@imsc.res.in

Abstract. In this paper, we study a parity based generalization of the classical MULTIWAY CUT problem. Formally, we study the PARITY MULTIWAY CUT

problem, where the input is a graph G, vertex subsets Te and To (T = Te ∪ To )

called terminals, a positive integer k and the objective is to test whether there exists a k-sized vertex subset S such that S intersects all odd paths from v ∈ To to T \ {v} and all even paths from v ∈ Te to T \ {v}. When Te = To, this is precisely the classical MULTIWAY CUT problem. If To = ∅ then this is the EVEN MULTIWAY CUT problem and if Te = ∅ then this is the ODD MULTIWAY CUT problem. We remark that even the problem of deciding whether there is a set of at most k vertices that intersects all odd paths between a pair of vertices s and t is NP-complete. Our primary motivation for studying this problem is the recently initiated parameterized study of parity versions of graphs minors (Kawarabayashi, Reed and Wollan, FOCS 2011) and separation problems similar to MULTIWAY CUT. The area of design of parameterized algorithms for graph separation problems has seen a lot of recent activity, which includes algorithms for MULTI-CUT on undirected graphs (Marx and Razgon, STOC 2011, Bousquet, Daligault and Thomass´, STOC 2011), k-WAY CUT (Kawarabayashi and Thorup, e FOCS 2011), and MULTIWAY CUT on directed graphs (Chitnis, Hajiaghayi and Marx, SODA 2012). A second motivation is that this problem serves as a good example to illustrate the application of a generalization of important separators which we introduce, and can be applied even when most of the recently develped tools fail to apply. We believe that this could be a useful tool for several other separation problems as well. We obtain this generalization by dividing the graph into slices with small boundaries and applying a divide and conquer paradigm over these slices. We show that PARITY MULTIWAY CUT is ﬁxed parameter tractable (FPT) by giving an algorithm that runs in time f (k)nO(1). More precisely, we show that instances of this problem with solutions of size O(log log n) can be solved in polynomial time. Along with this new notion of generalized important separators, our algorithm also combines several ideas used in previous parameterized algorithms for graph separation problems including thenotion of important separators and randomized selection of important sets to simplify the input instance.

1 Introduction A fundamental min-max theorem about connectivity in graphs is Menger’s Theorem, which states that the maximum number of vertex disjoint paths between two vertices s and t, is equal to the minimum number of vertices whose removal separates these two vertices. Indeed, a maximum set of vertex disjoint paths between s, t and a minimum size set of vertices separating these two vertices can be computed in polynomial time.

A known generalization of this theorem, commonly known as Mader’s T -path Theorem [21] states that, given a graph G and a subset T of vertices, there are either k vertex disjoint paths with only the end points in T (such paths are called T -paths and if their length is odd (even), then odd (even) T -paths), or there is a vertex set of size at most 2k which intersects every T -path. Although computing a maximum set of vertex disjoint T -paths can be done in polynomial time by using matching techniques, the decision version of the dual problem of ﬁnding a minimum set of vertices that intersects every T -path is NP-complete for |T | 2. Formally, this problem is the classical MULTIWAY CUT problem, where the input is a graph G, a subset of vertices T called terminals, a positive integer k and the objective is to test whether there exists a k-sized vertex subset that intersects every T -path. This is a very well studied problem in terms of approximation, as well as parameterized algorithms [2, 9, 22]. In this paper we study a generalization of this classical MULTIWAY CUT problem to a parity version. Formally, we study the PARITY MULTIWAY CUT problem which is deﬁned as follows.

## PARITY MULTIWAY CUT (PMWC)

Instance: A graph G = (V, E), vertex subsets Te and To (T = Te ∪ To ), integer k.Parameter: k Question: Is there a vertex set S of size at most k which intersects

1. all odd paths from a vertex v ∈ To to some other vertex u ∈ T \ {v},

2. all even paths from a vertex v ∈ Te to some other vertex u ∈ T \ {v}?

When Te = To, this is precisely the classical MULTIWAY CUT problem. If To = ∅ then this is the EVEN MULTIWAY CUT (EMWC) problem and if Te = ∅ then this is the ODD MULTIWAY CUT (OMWC) problem.

Our main motivation for studying this particular generalization is the recently initiated parameterized study of parity versions of graphs minors by Kawarabayashi, Reed and Wollan [15] and separation problems similar to MULTIWAY CUT [1, 4, 23]. The area of design of parameterized algorithms for graph separation problems has seen a lot of recent activity, which includes algorithms for MULTI-CUT on undirected graphs [23, 1], k-WAY CUT [16] and MULTIWAY CUT on directed graphs [4]. Furthermore, recently, Geelen, Gerards, Reed, Seymour and Vetta [10] proved an odd variant of Mader’s T path Theorem. They showed that, given a graph G and a subset T of vertices, there are either k vertex disjoint odd T -paths, or there is a vertex set of size at most 2k which intersects every odd T -path. This result has already turned out to be useful in graph theory [10, 18], as well as in the design of parameterized algorithms [11, 13, 14]. This result was crucial in settling the parameterized complexity of ﬁnding k vertex disjoint odd length cycles in a graph [14]. Observe that, this odd variant of Mader’s T -path Theorem naturally gives rise to the OMWC problem, a special case of PMWC.

The goal of parameterized complexity is to ﬁnd ways of solving NP-hard problems more efﬁciently than by brute force. Here, the aim is to restrict the combinatorial explosion of computational difﬁculty to a parameter that is hopefully much smaller than the input size. Formally, a parameterization of a problem is the assignment of an integer k to each input instance and we say that a parameterized problem is ﬁxed-parameter tractable (FPT) if there is an algorithm that solves the problem in time f (k) · |I|O(1), where |I| is the size of the input instance and f is an arbitrary computable function depending only on the parameter k. For more background, the reader is referred to the monographs [7, 8, 25].

Unlike MULTIWAY CUT, the PMWC is already NP-complete for the case when |T | = 2. Indeed, consider the following reduction from VERTEX COVER to PMWC.

Given an instance (G = (V, E), k) of VERTEX COVER, add two new vertices t1 and t2, make them both adjacent to every vertex in V, and set To = {t1, t2 } and Te = ∅. Call this new graph G. It is easy to see that G has a vertex cover of size at most k if and only if G has k-sized vertex subset that intersects every odd To −path. In fact, our argument shows that OMWC is NP-complete for the case when |T | = 2. One can similarly show that EMWC is NP-complete for the case when |T | = 2.

Marx [22] was the ﬁrst to consider cut problems in the context of parameterized complexity. He gave an algorithm for MULTIWAY CUT with running time O(4k nO(1) ) k O(1) with the current fastest algorithm running in time O(2 n ) [5]. Even the recent developments in techniques to solve graph separation problems [23] and parity based graph problems [17], do not seem to apply to PMWC, a natural companion of these problems. In this paper, we introduce a new notion of generalized important separators, which along with the tools used to solve parameterized cut problems like MULTIWAY CUT and MULTI-CUT, allows us to design an FPT algorithm for PMWC. In general, this notion seems to allow us to bring a number of problems under a single umbrella, and in particular we demonstrate its application to PMWC. The main result of this paper is the following.

O(k) nO(1) time.

** Theorem 1. PMWC can be solved in time 22 Our algorithm combines several ideas used in previous parameterized algorithms for graph separation problems including the notion of important separators and randomized selection of important sets to simplify the input instance.**

Furthermore, we introduce a generalization of important separators, which we believe could be a useful tool for several other separation problems. The algorithm for PMWC has three phases, in the ﬁrst phase using a well-known technique of iterative compression, we bound the number of even terminals by a linear function of k. In the second phase we remove even terminals using the notion of generalized important separators that we deﬁne in this paper and obtain f (k) instances of OMWC. We obtain the generalized important separators by dividing the graph into slices with small boundaries and applying a divide and conquer paradigm over these slices. In the ﬁnal phase we solve these instances of OMWC by designing an FPT algorithm for OMWC. More precisely we obtain the following result.

O(k) nO(1) time.

** Lemma 1. OMWC can be solved in time 22 We note that OMWC can be shown to be FPT be a simple reduction to the SUBSET OCT problem which was shown to be FPT in [17].**

However, such an algorithm for OMWC would have a much worse dependence on the parameter k when compared to the algorithm we present in this paper. We also point out that in the case of the EMWC problem with two terminals, we may subdivide the edges incident on one of them, thus converting all even paths between these terminals into odd paths and vice versa. This reduction shows that OMWC is equivalent to EMWC in the case of two terminals and hence Lemma 1 immediately gives an FPT algorithm for EMWC in the case of two terminals. We also consider the edge version of PMWC, the EDGE PARITY MULTIWAY CUT (EPMWC) problem, where the input is a graph G, a subset of vertices T = Te ∪ To, a positive integer k and the objective is to determine whether there exists a k-sized edge subset that intersects every even path from a vertex v ∈ Te to T \ {v} and every odd path from a vertex v ∈ To to T \ {v}. We show that this problem is also FPT by establishing a parameter preserving reduction from EPMWC to PMWC.

Related Work. Parity problems hold a lot of promise and remain hitherto unexplored from the perspective of parameterized complexity, with exceptions that are few and far between. The ﬁrst parameterized algorithm for ODD CYCLE TRANSVERSAL, ﬁnding a k sized vertex subset that intersect all odd cycles only appeared in 2004 [28]. Recently, Kawarabayashi and Reed [13] obtained an almost linear time parameterized algorithm for ODD CYCLE TRANSVERSAL, albeit with a much worse dependence on solution size than in [28]. Kawarabayashi and Reed [14] settled the parameterized complexity of ODD CYCLE PACKING, ﬁnding k vertex disjoint odd cycles in a graph, by showing it to be FPT. The Parameterized Complexity of ODD CYCLE PACKING was a long standing open problem and is much more general problem than the famous DISJOINT PATHS problem, ﬁnding vertex disjoint paths between given pairs of vertices. Recently, Kawarabayashi, Reed and Wollan [15] initiated the parameterized study of parity versions of graphs minors and gave an algorithm to ﬁnd odd minors. Other studies include ﬁnding odd subdivision, parity paths passing through speciﬁc vertices [12, 11]. On the cut side, as we mentioned before, the area was initiated by the paper of Marx [22].

The notions used in this paper has been useful in settling parameterized complexity of variety of problems including DIRECTED FEEDBACK VERTEX SET [3], ALMOST 2 SAT [27] and ABOVE GUARANTEE VERTEX COVER [27, 26]. Recently, Marx and Razgon [23] and Bousquet, Daligault and Thomass´ [1] independently showed that e MULTI-CUT, ﬁnding k vertices to disconnect given pairs of terminals is FPT. Continuing this line of study, Chitnis, Hajiaghayi and Marx studied MULTIWAY CUT on directed graphs and showed it to be FPT [4].

**2 Preliminaries**

Given a path P, we refer to the number of edges in P as the length of P and denote it by |P |. We call a path an odd (even) path if the length of the path is odd (respectively even). We refer to the parity of |P | as the parity of the path P. If P is a path from some vertex in a set X to some vertex in a set Y, we say that P is an X-Y path. If A contains a single vertex x, we say that P is an x-Y path. Given a graph G = (V, E) and T ⊆ V, paths with only the end points in T are called T -paths and if their length is odd (even), then odd (even) T -paths. Given a vertex set S, we denote by P ∩ S, the set of vertices in S which intersect P. Given two paths P1 = v1,..., vl and P2 = u1,..., ur, such that one end point of P1 (say vl ) is the same vertex as some endpoint of P2 (say u1 ) and no other vertices of the two paths coincide, we deﬁne the concatenated path P1 + P2 as v1,..., vl, u2,..., ur. Given a walk W = v1,..., vl from t1 = v1 to t2 = vl, we deﬁne a closed loop (or loop) of W, as a closed walk W = vi, vi+1,..., vj, vp, vp+1,..., vr where vi = vr and vj = vp, vi+1,..., vj−1 and vp+1,..., vr−1 are either vertex disjoint simple paths which are subpaths of W, or are the same exact path which is a subpath of W. By deleting a closed loop W = vi,..., vr from W, we obtain the walk W = v1,..., vi, vr+1,..., vl. Note that deleting an even closed loop does not affect the parity of the walk, while deleting an odd closed loop ﬂips the parity of the walk.

Hence, loops of the second type (for eg. v1, v2, v1 ), where the two internal subpaths coincide exactly can be removed without changing the parity of the walk since such loops are by deﬁnition, even. Hence, in our discussions, we will assume that such loops do not occur, that is, if W = vi, vi+1,..., vj, vp, vp+1,..., vr is a loop, then it is a cycle.