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

Acknowledgement We would like to thank the reviewers for the insightful comments that have helped us to ﬁx a number of errors and improve readability.

References [1] S. Arora, S. Rao, and U. Vazirani. Expander ﬂows, geometric embeddings and graph partitioning. J. ACM, 56(2):1–37, 2009.

[2] N. Bansal, A. Blum, and S. Chawla. Correlation clustering. Machine Learning, 56(1-3):89–113, 2004.

[3] H. L. Bodlaender, M. R. Fellows, P. Heggernes, F. Mancini, C. Papadopoulos, and F. A. Rosamond. Clustering with partial information. Theor. Comput. Sci., 411(7-9):1202–1211, 2010.

[5] N. Bousquet, J. Daligault, S. Thomasse, and A. Yeo. A polynomial kernel for multicut in trees.

In STACS, pages 183–194, 2009.

[6] G. Calinescu, C. G. Fernandes, and B. Reed. Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width. Journal of Algorithms, 48(2):333 – 359, 2003.

[7] S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, and D. Sivakumar. On the hardness of approximating multicut and sparsest-cut. Comput. Complexity, 15(2):94–114, 2006.

[8] J. Chen, Y. Liu, and S. Lu. An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica, 55(1):1–13, 2009.

[9] J. Chen, Y. Liu, S. Lu, B. O’Sullivan, and I. Razgon. A ﬁxed-parameter algorithm for the directed feedback vertex set problem. J. ACM, 55(5), 2008.

[10] R. Chitnis, L. Egri, and D. Marx. List H-coloring a graph by removing few vertices. To appear in proceedings of ESA 2013.

[11] R. Chitnis, M. Hajiaghayi, and D. Marx. Fixed-parameter tractability of Directed Multiway Cut parameterized by the size of the cutset. To appear in SIAM Journal on Computing.

[12] R. H. Chitnis, M. Cygan, M. T. Hajiaghayi, and D. Marx. Directed Subset Feedback Vertex Set is ﬁxed-parameter tractable. In ICALP (1), pages 230–241, 2012.

[13] J. Chuzhoy and S. Khanna. Polynomial ﬂow-cut gaps and hardness of directed cut problems.

J. ACM, 56(2):1–28, 2009.

[14] M. Cygan, M. Pilipczuk, M. Pilipczuk, and J. O. Wojtaszczyk. On multiway cut parameterized above lower bounds. TOCT, 5(1):3, 2013.

[15] E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis. The complexity of multiterminal cuts. SIAM J. Comput., 23(4):864–894, 1994.

[16] E. D. Demaine, D. Emanuel, A. Fiat, and N. Immorlica. Correlation clustering in general weighted graphs. Theor. Comput. Sci., 361(2-3):172–187, 2006.

[17] R. G. Downey and M. R. Fellows. Parameterized Complexity. Springer, New York, 1999.

[18] U. Feige, M. Hajiaghayi, and J. R. Lee. Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput., 38(2):629–657, 2008.

[19] J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, Berlin, 2006.

[20] L. R. Ford, Jr. and D. R. Fulkerson. Maximal ﬂow through a network. Canad. J. Math., 8:399–404, 1956.

[21] L. R. Ford, Jr. and D. R. Fulkerson. Flows in networks. Princeton University Press, Princeton, N.J., 1962.

[22] N. Garg, V. V. Vazirani, and M. Yannakakis. Approximate max-ﬂow min-(multi)cut theorems and their applications. SIAM J. Comput., 25(2):235–251, 1996.

[23] G. Gottlob and S. T. Lee. A logical approach to multicut problems. Inf. Process. Lett., 103(4):136–141, 2007.

[24] S. Guillemot. FPT algorithms for path-transversal and cycle-transversal problems. Discrete Optimization, 8(1):61 – 71, 2011.

[25] J. Guo, F. H¨ﬀner, E. Kenar, R. Niedermeier, and J. Uhlmann. Complexity and exact algou rithms for vertex multicut in interval and bounded treewidth graphs. European J. Oper. Res., 186(2):542–553, 2008.

[26] J. Guo and R. Niedermeier. Fixed-parameter tractability and data reduction for multicut in trees. Networks, 46(3):124–135, 2005.

[27] A. Gupta. Improved results for directed multicut. In SODA, pages 454–455, 2003.

[28] F. H¨ﬀner, R. Niedermeier, and S. Wernicke. Techniques for practical ﬁxed-parameter algou rithms. The Computer Journal, 51(1):7–25, 2008.

[29] S. Khot. On the power of unique 2-prover 1-round games. In STOC, pages 767–775, 2002.

[31] D. Lokshtanov and D. Marx. Clustering with local restrictions. Inf. Comput., 222:278–292, 2013.

[32] D. Lokshtanov, N. S. Narayanaswamy, V. Raman, M. S. Ramanujan, and S. Saurabh. Faster parameterized algorithms using linear programming. CoRR, abs/1203.0833, 2012.

[33] D. Lokshtanov and M. S. Ramanujan. Parameterized tractability of multiway cut with parity constraints. In ICALP (1), pages 750–761, 2012.

[34] D. Marx. Parameterized graph separation problems. In IWPEC, pages 71–82, 2004.

[35] D. Marx. Parameterized graph separation problems. Theoretical Computer Science, 351(3):394– 406, 2006.

[36] D. Marx and I. Razgon. Constant ratio ﬁxed-parameter approximation of the edge multicut problem. Inf. Process. Lett., 109(20):1161–1166, 2009.

[37] D. Marx and I. Razgon. Fixed-parameter tractability of multicut parameterized by the size of the cutset. In Proceedings of the 43nd ACM Symposium on Theory of Computing, pages 469–478, 2011.

[38] M. Naor, L. J. Schulman, and A. Srinivasan. Splitters and near-optimal derandomization. In FOCS, pages 182–191, 1995.

[39] R. Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006.

[40] R. Pichler, S. R¨mmele, and S. Woltran. Multicut algorithms via tree decompositions. In CIAC, u pages 167–179, 2010.

[41] V. Raman, M. S. Ramanujan, and S. Saurabh. Paths, ﬂowers and vertex cover. In ESA, pages 382–393, 2011.

[42] I. Razgon and B. O’Sullivan. Almost 2-SAT is ﬁxed-parameter tractable. J. Comput. Syst. Sci., 75(8):435–450, 2009.

[45] M. Xiao. Algorithms for multiterminal cuts. In CSR, pages 314–325, 2008.

[46] M. Yannakakis, P. C. Kanellakis, S. S. Cosmadakis, and C. H. Papadimitriou. Cutting and partitioning a graph after a ﬁxed pattern. In ICALP, pages 712–722, 1983.

A Important separators

**First we state without proof some properties of Deﬁnition 3.8 that are easy to see:**

Proposition A.1. Let G be a graph, X, Y ⊆ V (G) be two disjoint sets of vertices, and S be an important X − Y separator.

1. For every v ∈ S, the set S \ {v} is an important X − Y separator in G \ v.

2. If S is an X − Y separator for some X ⊃ X, then S is an important X − Y separator.

Proof (of Lemma 3.9). We prove by induction on 2p − λ that there are at most 22p−λ important X − Y separators of size at most p, where λ is the size of the smallest X − Y separator. If λ p, then there is no X − Y separator of size p, and therefore the statement holds if 2p − λ 0. Also, if λ = 0 and p ≥ 0, then there is a unique important X − Y separator of size at most p: the empty set.

If S is an X − Y separator, then we denote by KS the union of every component of G \ S intersecting X. First we show the well-known fact that there is a unique X − Y separator S ∗ of size λ such that KS ∗ is inclusionwise maximal, i.e., we have KS ⊂ KS ∗ for every other X − Y separator S of size λ. Suppose that there are two separators S and S such that KS and KS are incomparable and inclusionwise maximal. Let us deﬁne the function γ(Z) = |N (Z)|. It is well-known that γ is submodular, that is, γ(A) + γ(B) ≥ γ(A ∪ B) + γ(A ∩ B) for every A, B ⊆ V (G). In particular, the submodularity of gamma implies that γ(KS ) + γ(KS ) ≥ γ(KS ∪ KS ) + γ(KS ∩ KS ).

≥λ =λ =λ The left hand side is exactly 2λ, while the second term of the right hand side is at least λ (as N (KS ∩ KS ) is an X − Y separator). Therefore, γ(KS ∪ KS ) ≤ λ. This means that N (KS ∪ KS ) is also a minimum X − Y separator, contradicting the maximality of S and S.

Next we show that for every important X − Y separator S, we have KS ∗ ⊆ KS. Suppose this is

**not true for some S. We use submodularity again:**

γ(KS ∗ ) +γ(KS ) ≥ γ(KS ∗ ∪ KS ) + γ(KS ∗ ∩ KS ).

≥λ =λ By deﬁnition, γ(KS ∗ ) = λ, and N (KS ∗ ∩ KS ) is an X − Y separator, hence γ(KS ∗ ∩ KS ) ≥ λ. This means that γ(KS ∗ ∪ KS ) ≤ γ(KS ). However this contradicts the assumption that S is an important X − Y separator: N (KS ∗ ∪ KS ) is an X − Y separator not larger than S, but KS ∗ ∪ KS is a proper superset of KS (as KS ∗ is not a subset of KS by assumption).

We have shown that for every important separator S, the set KS contains KS ∗. Let v ∈ S ∗ be an arbitrary vertex of S ∗ (note that λ 0, hence S ∗ is not empty). An important X − Y separator S of size at most p either contains v or not. If S contains v, then S \ {v} is an important X − Y separator in G \ v of size at most p := p − 1 (Prop. A.1(1)). As v ∈ X, Y, the size λ of the minimum X − Y separator in G \ v is at least λ − 1. Therefore, 2p − λ 2p − λ and the induction hypothesis implies that there are at most 22p −λ ≤ 22p−λ−1 important X − Y separators of size p in G \ {v}, and hence at most that many important X − Y separators of size p in G that contain v.

Let us count now the important X − Y separators not containing v. Note that by the minimality of S ∗, vertex v of S ∗ has a neighbor in KS ∗. We have seen that KS ∗ ⊆ KS for every such X − Y separator S. As v ∈ S and v has a neighbor in KS, even KS ∗ ∪{v} ⊆ KS is true. Let X = KS ∗ ∪{v};

it follows that S is a X − Y separator and in fact an important X − Y separator by Prop. A.1(2).

There is no X − Y separator S of size λ: such a set S would be an X − Y separator of size λ as well, with KS ∗ ∪ {v} ⊆ KS, contradicting the maximality of S ∗. Thus the minimum size λ of an X − Y separator is greater than λ. It follows by the induction assumption that the number of important X − Y separators of size at most p is at most 22p−λ ≤ 22p−λ−1, which is a bound on the number of important X − Y separators of size p in G that does not contain v.

Adding the bounds in the two cases, we get the required bound 22p−λ. An algorithm for enumerating all the at most 4p important separators follows from the above proof. First, we can ﬁnd a maximum X − Y ﬂow in time O(p(|V (G)| + |E(G)|)) using at most p rounds of the Ford-Fulkerson algorithm. It is well-known that the separator S ∗ in the proof can be deduced from the maximum ﬂow in linear time by ﬁnding those vertices from which Y cannot be reached in the residual graph [21]. Pick any arbitrary vertex v ∈ S ∗. Then we branch on whether vertex v ∈ S ∗ is in the important separator or not, and recursively ﬁnd all possible important separators for both cases. Note that this algorithm enumerates a superset of all important separators: by our analysis above, every important separator is found, but there is no guarantee that all the constructed separators are important.

Therefore, the algorithm has to be followed by a ﬁltering phase where we check for each returned separator whether it is important. Observe that S is an important X − Y separator if and only if S is the unique minimum KS − Y separator, where KS is the set of vertices reachable from X in G \ S. As the size of S is at most p, this can be checked in time O(p(|V (G)| + |E(G)|)) by ﬁnding a maximum ﬂow and constructing the residual graph. The search tree has at most 4p leaves and the work to be done in each node is O(p(|V (G)| + |E(G)|)). Therefore, the total running time of the branching algorithms is O(4p · p(|V (G)| + |E(G)|)) and returns at most 4p separators. This is followed by the ﬁltering phase, which takes time O(4p · p(|V (G)| + |E(G)|)).