**Theorem 11.** For every integers $a, k \ge 1$ there exists an integer $g$ such that for every directed graph $G$ with distinguished $s, t \in V(G)$, and a family $\mathcal{U}$ of pairwise disjoint minimal st-cuts of size $k$ each, if $|\mathcal{U}| \ge g$, then $\mathcal{U}$ contains an a-bowtie.

The next two lemmata are key observations to prove Theorems 3 and 4, respectively, with the help of Theorem 11.

**Lemma 12.** Let $k, g, G, s, t, \mathcal{F}$, and $\mathcal{G}$ be as in the statement of Theorem 3. Then $\mathcal{G}$ does not contain an a-bowtie for $a > \binom{k+2}{2}$.

**Proof.** Assume the contrary, let $(C_i, A_i, B_i)_{i=1}^a$ be such a bowtie. Since $a > \binom{k+2}{2}$, there exists $i < j$ with $|A_i| = |A_j|$ and $|B_i| = |B_j|$ (there are $\binom{k+2}{2}$ choices for $(|A_i|, |B_i|)$). However, then $A_i \cup B_j$ and $A_j \cup B_i$ have also cardinality $k$, are st-cuts, and have together twice the minimum weight. Furthermore, the set of vertices reachable from $s$ in $G - (A_j \cup B_i)$ is a strict superset of the set of vertices reachable from $s$ in $G - C_i$ and $G - C_j$. This contradicts the fact that $C_i, C_j \in \mathcal{G}$. $\quad \blacksquare$

**Lemma 13.** Let $k, \ell, I = (G, s, t, (P_i)_{i=1}^m, k)$, $\mathcal{F}$, and $\mathcal{G}$ be as in the statement of Theorem 4. Then $\mathcal{G}$ does not contain a 4-bowtie $(C_i, A_i, B_i)_{i=1}^4$ in which the edge set of every path $P_j$ intersects at most one cut $C_i$.

**Proof.** Assume the contrary. Let $(C_i, A_i, B_i)_{i=1}^4$ be such a 4-bowtie. Consider $i \in \{2, 3\}$ and two edges $e \in A_i$ and $f \in B_i$. In $G - C_4$, the edge $e$ is reachable from $s$ while $f$ is not; consequently, $e$ and $f$ cannot appear on the same input path with $e$ being earlier (by assumption, $C_4$ is disjoint from the input path in question). A similar reasoning for $G - C_1$ shows that $e$ and $f$ cannot appear on the same input path with $f$ being earlier than $e$.

Hence, $e$ and $f$ cannot appear together on a single path $P_j$. For a set of edges $D$, by the cost of $D$ we denote $|\{j|D \cap P_j \neq \emptyset\}|$. Since the choice of $e$ and $f$ was arbitrary, we infer that the sum of costs of $A_2 \cup B_3$ and of $A_3 \cup B_2$ equals the sum of costs of $C_2$ and of $C_3$. Hence, both these st-cuts have minimum cost. However, $A_2 \cup B_3$ is closer to $t$ than $C_2$, a contradiction. $\quad \blacksquare$

**Proof of Theorem 3.** Assume $|\mathcal{G}| > g$ for some sufficiently large $g$ to be fixed later. For $i \in [k]$, let $\mathcal{G}^i$ be the set of $u \in \mathcal{G}$ of cardinality $i$. We apply the Sunflower Lemma to the largest set $\mathcal{G}^i$: If $g > k \cdot k! g_1^k$ for some integer $g_1$ to be chosen later, there exists $\mathcal{G}_1 \subseteq \mathcal{G}$ with $|\mathcal{G}_1| > g_1$, every element of $\mathcal{G}_1$ being of the same size $k'$, and a set $c$ such that $u \cap v = c$ for every distinct $u, v \in \mathcal{G}_1$.

Let $\hat{k} = k' - |c|$, $\hat{u} = u \setminus c$ for every $u \in \mathcal{G}_1$, $\hat{G}_1 = \{\hat{u} | u \in \mathcal{G}_1\}$ and $\hat{G} = G - c$. Since every $u \in \mathcal{U}$ is a minimal st-cut of size $k'$ in $G$, every $\hat{u} \in \hat{G}_1$ is a minimal st-cut of size $\hat{k}$ in $\hat{G}$. Furthermore, every $\hat{u} \in \hat{G}_1$ is a minimal st-cut of size at most $\hat{k}$ in $\hat{G}$ of minimum possible weight: if there existed an st-cut $\hat{x}$ of smaller weight and cardinality at most $\hat{k}$, then $x = \hat{x} \cup c$ would be an st-cut in $G$ of cardinality at most $k$ and weight smaller than every element of $\mathcal{G}_1$. Similarly, if there were a minimal st-cut $\hat{x}$ in $\hat{G}$ of minimum weight and cardinality at most $\hat{k}$ that is closer to $t$ than $\hat{u}$ for some $\hat{u} \in \hat{G}_1$, then $\hat{x} \cup c$ would be an st-cut in $G$ of cardinality at most $k$ and minimum weight that is closer to $t$ than $u$, a contradiction. By construction, the elements of $\hat{G}_1$ are pairwise disjoint.

Lemma 12 bounds the maximum possible size of a bowtie in $\hat{G}_1$. Hence, Theorem 11 asserts that $\hat{G}_1$ has size bounded by a function of $k$. This finishes the proof of the theorem. $\quad \blacksquare$

**Proof of Theorem 4.** We proceed similarly as in the proof of Theorem 3, but we need to be a bit more careful with the paths $P_j$. Assume $|\mathcal{G}| > g$ for some sufficiently large integer $g$.
**Theorem 11.** For every integers $a, k \ge 1$ there exists an integer $g$ such that for every directed graph $G$ with distinguished $s, t \in V(G)$, and a family $\mathcal{U}$ of pairwise disjoint minimal st-cuts of size $k$ each, if $|\mathcal{U}| \ge g$, then $\mathcal{U}$ contains an a-bowtie.

The next two lemmata are key observations to prove Theorems 3 and 4, respectively, with the help of Theorem 11.

**Lemma 12.** Let $k, g, G, s, t, \mathcal{F}$, and $\mathcal{G}$ be as in the statement of Theorem 3. Then $\mathcal{G}$ does not contain an a-bowtie for $a > \binom{k+2}{2}$.

**Proof.** Assume the contrary, let $(C_i, A_i, B_i)_{i=1}^a$ be such a bowtie. Since $a > \binom{k+2}{2}$, there exists $i < j$ with $|A_i| = |A_j|$ and $|B_i| = |B_j|$ (there are $\binom{k+2}{2}$ choices for $(|A_i|, |B_i|)$). However, then $A_i \cup B_j$ and $A_j \cup B_i$ have also cardinality $k$, are st-cuts, and have together twice the minimum weight. Furthermore, the set of vertices reachable from $s$ in $G - (A_j \cup B_i)$ is a strict superset of the set of vertices reachable from $s$ in $G - C_i$ and $G - C_j$. This contradicts the fact that $C_i, C_j \in \mathcal{G}$. $\quad \blacksquare$

**Lemma 13.** Let $k, \ell, I = (G, s, t, (P_i)_{i=1}^m, k)$, $\mathcal{F}$, and $\mathcal{G}$ be as in the statement of Theorem 4. Then $\mathcal{G}$ does not contain a 4-bowtie $(C_i, A_i, B_i)_{i=1}^4$ in which the edge set of every path $P_j$ intersects at most one cut $C_i$.

**Proof.** Assume the contrary Let $(C_i, A_i, B_i)_{i=1}^4$ be such a 4-bowtie. Consider $i \in \{2, 3\}$ and two edges $e \in A_i$ and $f \in B_i$. In $G - C_4$, the edge $e$ is reachable from $s$ while $f$ is not; consequently, $e$ and $f$ cannot appear on the same input path with $e$ being earlier (by assumption, $C_4$ is disjoint from the input path in question). A similar reasoning for $G - C_1$ shows that $e$ and $f$ cannot appear on the same input path with $f$ being earlier than $e$.

Hence, $e$ and $f$ cannot appear together on a single path $P_j$. For a set of edges $D$, by the cost of $D$ we denote $|\{j|D \cap P_j \neq \emptyset\}|$. Since the choice of $e$ and $f$ was arbitrary, we infer that the sum of costs of $A_2 \cup B_3$ and of $A_3 \cup B_2$ equals the sum of costs of $C_2$ and of $C_3$. Hence, both these st-cuts have minimum cost. However, $A_2 \cup B_3$ is closer to $t$ than $C_2$, a contradiction. $\quad \blacksquare$

**Proof of Theorem 3.** Assume $|\mathcal{G}| > g$ for some sufficiently large $g$ to be fixed later. For $i \in [k]$, let $\mathcal{G}^i$ be the set of $u \in \mathcal{G}$ of cardinality $i$. We apply the Sunflower Lemma to the largest set $\mathcal{G}^i$: If $g > k \cdot k! g_1^k$ for some integer $g_1$ to be chosen later, there exists $\mathcal{G}_1 \subseteq \mathcal{G}$ with $|\mathcal{G}_1| > g_1$, every element of $\mathcal{G}_1$ being of the same size $k'$, and a set $c$ such that $u \cap v = c$ for every distinct $u, v \in \mathcal{G}_1$.

Let $\hat{k} = k' - |c|$, $\hat{u} = u \setminus c$ for every $u \in \mathcal{G}_1$, $\hat{G}_1 = \{\hat{u} | u \in \mathcal{G}_1\}$ and $\hat{G} = G - c$. Since every $u \in \mathcal{U}$ is a minimal st-cut of size $k'$ in $G$, every $\hat{u} \in \hat{G}_1$ is a minimal st-cut of size $\hat{k}$ in $\hat{G}$. Furthermore, every $\hat{u} \in \hat{G}_1$ is a minimal st-cut of size at most $\hat{k}$ in $\hat{G}$ of minimum possible weight: if there existed an st-cut $\hat{x}$ of smaller weight and cardinality at most $\hat{k}$, then $x = \hat{x} \cup c$ would be an st-cut in $G$ of cardinality at most $k$ and weight smaller than every element of $\mathcal{G}_1$. Similarly, if there were a minimal st-cut $\hat{x}$ in $\hat{G}$ of minimum weight and cardinality at most $\hat{k}$ that is closer to $t$ than $\hat{u}$ for some $\hat{u} \in \hat{G}_1$, then $\hat{x} \cup c$ would be an st-cut in $G$ of cardinality at most $k$ and minimum weight that is closer to $t$ than $u$, a contradiction. By construction, the elements of $\hat{G}_1$ are pairwise disjoint.

Lemma 12 bounds the maximum possible size of a bowtie in $\hat{G}_1$. Hence, Theorem 11 asserts that $\hat{G}_1$ has size bounded by a function of $k$. This finishes the proof of the theorem. $\quad \blacksquare$

**Proof of Theorem 4.** We proceed similarly as in the proof of Theorem 3, but we need to be a bit more careful with the paths $P_j$. Assume $|\mathcal{G}| > g$ for some sufficiently large integer $g$.
18:12 Multi-Budgeted Directed Cuts

As before, we partition $\mathcal{G}$ according to the sizes of elements: for every $i \in [k\ell]$, let $\mathcal{G}^i = \{u \in \mathcal{G} \mid |u| = i\}$. Let $i \in [k\ell]$ be such that $|\mathcal{G}^i| > g/(k\ell)$. For $u \in \mathcal{G}^i$, let $J(u) = \{j \mid u \cap P_j \neq \emptyset\}$. By the assumptions of the theorem, every set $J(u)$ is of cardinality exactly $k$. We apply the Sunflower Lemma to $\{J(u) \mid u \in \mathcal{G}^i\}$: If $g > (k\ell) \cdot k! \cdot g_1^k$ for some integer $g_1$ to be fixed later, then there exists $\mathcal{G}_1 \subseteq \mathcal{G}^i$ of size larger than $g_1$ and a set $I \subseteq [m]$ such that for every distinct $u, v \in \mathcal{G}_1$ we have $J(u) \cap J(v) = I$. For every $u \in \mathcal{G}_1$, let $u_I = u \cap \bigcup_{j \in I} P_j$. Since $|I| \le k$, there are at most $2^{k\ell}$ choices for $u_I$ among elements $u \in \mathcal{G}_1$. Consequently, there exists $\mathcal{G}_2 \subseteq \mathcal{G}_1$ of cardinality larger than $g_2 := g_1/2^{k\ell}$ such that $u_I = v_I$ for every $u, v \in \mathcal{G}_2$. Denote $c = u_I$ for any $u \in \mathcal{G}_2$.

Let $\hat{u} := u - c$ for every $u \in \mathcal{G}_2$. Let $\hat{\mathcal{G}}_2 = \{\hat{u} \mid u \in \mathcal{G}_2\}$.

Define now $\hat{\mathcal{G}} = \mathcal{G} - c$ and define a partition $\hat{\mathcal{P}}$ of $E(\hat{\mathcal{G}})$ into paths of length at most $\ell$ as follows: we take all paths $P_i$ for $i \notin I$ and, for every $i \in I$, each edge of $P_i \setminus c$ as a length-1 path. Furthermore, denote $\hat{k} = k - |I|$. Note that $(\hat{\mathcal{G}}, s, t, \hat{\mathcal{P}}, \hat{k})$ is a CHAIN $\ell$-SAT instance for which every $\hat{u} \in \hat{\mathcal{G}}_2$ is a solution. Furthermore, $(\hat{\mathcal{G}}, s, t, \hat{\mathcal{P}}, \hat{k} - 1)$ is a no-instance, as if $\hat{x}$ were its solution, then $\hat{x} \cup c$ would be a solution to $(\mathcal{G}, s, t, (P_i)_{i=1}^m, k - 1)$, a contradiction. Similarly, if there were a solution $\hat{x}$ to $(\hat{\mathcal{G}}, s, t, \hat{\mathcal{P}}, \hat{k})$ that is closer to $t$ than $\hat{u}$ for some $\hat{u} \in \hat{\mathcal{G}}_2$, then $\hat{x} \cup c$ would be a solution to $(\mathcal{G}, s, t, (P_i)_{i=1}^m, k)$ that is closer to $t$ than $u$, a contradiction. Furthermore, by construction, the elements of $\hat{\mathcal{G}}_2$ are pairwise disjoint and no path of $\hat{\mathcal{P}}$ intersects more than one element of $\hat{\mathcal{G}}_2$.

Lemma 13 bounds the maximum possible size of a bowtie in $\hat{\mathcal{G}}_2$. Hence, Theorem 11 asserts that $\hat{\mathcal{G}}_2$ has size bounded by a function of $k$ and $\ell$. This finishes the proof of the theorem. ◄

6 Conclusion

We would like to conclude with a discussion on future research directions. First, our upper bound of $2^{O(k^2 \log k)}$ on the number of multi-budgeted important separators (Theorem 9) is far from the $4^k$ bound for the classic important separators. As pointed out by an anonymous reviewer at IPEC 2018, there is an easy lower bound of $k!$ for the number of multi-budgeted important separators: Let $\ell = k$, $k_i = 1$ for every $i \in [\ell]$, and let $\mathcal{G}$ consist of $k$ paths from $s$ to $t$, each path consisting of $\ell$ edges of different colors. Then there are exactly $k!$ distinct multi-budgeted important separators, as we can freely choose a different color $i \in [\ell]$ to cut on each path. We are not aware of any better lower bound, leaving a significant gap between the lower and upper bounds.

Second, our existential statement of Theorems 3 and 4 can be treated as a weak support of tractability of CHAIN $\ell$-SAT and WEIGHTED st-CUT. Are they really FPT when parameterized by the cardinality of the cut?

References

1. Amit Agarwal, Noga Alon, and Moses Charikar. Improved approximation for directed cut problems. In David S. Johnson and Uriel Feige, editors, *Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007*, pages 671–680. ACM, 2007. doi:10.1145/1250790.1250888.

2. Chandra Chekuri, Sudipto Guha, and Joseph Naor. The Steiner $k$-Cut Problem. *SIAM J. Discrete Math.*, 20(1):261–271, 2006. doi:10.1137/S0895480104445095.

3. Jianer Chen and Iyad A. Kanj. Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms. *J. Comput. Syst. Sci.*, 67(4):833–847, 2003. doi:10.1016/j.jcss.2003.09.003.
18:12 Multi-Budgeted Directed Cuts

As before, we partition $\mathcal{G}$ according to the sizes of elements: for every $i \in [k\ell]$, let $\mathcal{G}^i = \{u \in \mathcal{G} \mid |u| = i\}$. Let $i \in [k\ell]$ be such that $|\mathcal{G}^i| > g/(k\ell)$. For $u \in \mathcal{G}^i$, let $J(u) = \{j \mid u \cap P_j \neq \emptyset\}$. By the assumptions of the theorem, every set $J(u)$ is of cardinality exactly $k$. We apply the Sunflower Lemma to $\{J(u) \mid u \in \mathcal{G}^i\}$: If $g > (k\ell) \cdot k! \cdot g_1^k$ for some integer $g_1$ to be fixed later, then there exists $\mathcal{G}_1 \subseteq \mathcal{G}^i$ of size larger than $g_1$ and a set $I \subseteq [m]$ such that for every distinct $u, v \in \mathcal{G}_1$ we have $J(u) \cap J(v) = I$. For every $u \in \mathcal{G}_1$, let $u_I = u \cap \bigcup_{j \in I} P_j$. Since $|I| \le k$, there are at most $2^{k\ell}$ choices for $u_I$ among elements $u \in \mathcal{G}_1$. Consequently, there exists $\mathcal{G}_2 \subseteq \mathcal{G}_1$ of cardinality larger than $g_2 := g_1/2^{k\ell}$ such that $u_I = v_I$ for every $u, v \in \mathcal{G}_2$. Denote $c = u_I$ for any $u \in \mathcal{G}_2$.

Let $\hat{u} := u - c$ for every $u \in \mathcal{G}_2$. Let $\hat{\mathcal{G}}_2 = \{\hat{u} \mid u \in \mathcal{G}_2\}$.

Define now $\hat{G} = G - c$ and define a partition $\hat{\mathcal{P}}$ of $E(\hat{G})$ into paths of length at most $\ell$ as follows: we take all paths $P_i$ for $i \notin I$ and, for every $i \in I$, each edge of $P_i \setminus c$ as a length-1 path. Furthermore, denote $\hat{k} = k - |I|$. Note that $(\hat{G}, s, t, \hat{\mathcal{P}}, \hat{k})$ is a CHAIN $\ell$-SAT instance for which every $\hat{u} \in \hat{\mathcal{G}}_2$ is a solution. Furthermore, $(\hat{G}, s, t, \hat{\mathcal{P}}, \hat{k} - 1)$ is a no-instance, as if $\hat{x}$ were its solution, then $\hat{x} \cup c$ would be a solution to $(G, s, t, (P_i)_{i=1}^m, k - 1)$, a contradiction. Similarly, if there were a solution $\hat{x}$ to $(\hat{G}, s, t, \hat{\mathcal{P}}, \hat{k})$ that is closer to $t$ than $\hat{u}$ for some $\hat{u} \in \hat{\mathcal{G}}_2$, then $\hat{x} \cup c$ would be a solution to $(G, s, t, (P_i)_{i=1}^m, k)$ that is closer to $t$ than $u$, a contradiction. Furthermore, by construction, the elements of $\hat{\mathcal{G}}_2$ are pairwise disjoint and no path of $\hat{\mathcal{P}}$ intersects more than one element of $\hat{\mathcal{G}}_2$.

Lemma 13 bounds the maximum possible size of a bowtie in $\hat{\mathcal{G}}_2$. Hence, Theorem 11 asserts that $\hat{\mathcal{G}}_2$ has size bounded by a function of $k$ and $\ell$. This finishes the proof of the theorem. $\quad$

6 Conclusion

We would like to conclude with a discussion on future research directions. First, our upper bound of $2^{O(k^2 \log k)}$ on the number of multi-budgeted important separators (Theorem 9) is far from the $4^k$ bound for the classic important separators. As pointed out by an anonymous reviewer at IPEC 2018, there is an easy lower bound of $k!$ for the number of multi-budgeted important separators: Let $\ell = k$, $k_i = 1$ for every $i \in [\ell]$, and let $\mathcal{G}$ consist of $k$ paths from $s$ to $t$, each path consisting of $\ell$ edges of different colors. Then there are exactly $k!$ distinct multi-budgeted important separators, as we can freely choose a different color $i \in [\ell]$ to cut on each path. We are not aware of any better lower bound, leaving a significant gap between the lower and upper bounds.

Second, our existential statement of Theorems 3 and 4 can be treated as a weak support of tractability of CHAIN $\ell$-SAT and WEIGHTED st-CUT. Are they really FPT when parameterized by the cardinality of the cut?

References

1. Amit Agarwal, Noga Alon, and Moses Charikar. Improved approximation for directed cut problems. In David S. Johnson and Uriel Feige, editors, *Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007*, pages 671–680. ACM, 2007. doi:10.1145/1250790.1250888.

2. Chandra Chekuri, Sudipto Guha, and Joseph Naor. The Steiner $k$-Cut Problem. *SIAM J. Discrete Math.*, 20(1):261–271, 2006. doi:10.1137/S0895480104445095.

3. Jianer Chen and Iyad A. Kanj. Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms. *J. Comput. Syst. Sci.*, 67(4):833–847, 2003. doi:10.1016/j.jcss.2003.09.003.
4 Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, and Igor Razgon. A fixed-parameter algorithm for the directed feedback vertex set problem. *J. ACM*, 55(5):21:1-21:19, 2008. doi:10.1145/1411509.1411511.

5 Rajesh Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, Marcin Pilipczuk, and Michal Pilipczuk. Designing FPT Algorithms for Cut Problems Using Randomized Contractions. *SIAM J. Comput.*, 45(4):1171-1229, 2016. doi:10.1137/15M1032077.

6 Rajesh Chitnis, László Egri, and Dániel Marx. List H-Coloring a Graph by Removing Few Vertices. *Algorithmica*, 78(1):110-146, 2017. doi:10.1007/s00453-016-0139-6.

7 Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, and Dániel Marx. Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable. In Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer, editors, *ICALP (1)*, volume 7391 of *Lecture Notes in Computer Science*, pages 230-241. Springer, 2012. doi:10.1007/978-3-642-31594-7_20.

8 Rajesh Hemant Chitnis, Mohammad Taghi Hajiaghayi, and Dániel Marx. Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset. *SIAM J. Comput.*, 42(4):1674-1696, 2013. doi:10.1137/12086217X.

9 Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. *Parameterized Algorithms*. Springer, 2015. doi:10.1007/978-3-319-21275-3.

10 Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk. On multiway cut parameterized above lower bounds. *TOCT*, 5(1):3, 2013. doi:10.1145/2462896.2462899.

11 Guy Even, Joseph Naor, Baruch Schieber, and Madhu Sudan. Approximating Minimum Feedback Sets and Multicuts in Directed Graphs. *Algorithmica*, 20(2):151-174, 1998. doi: 10.1007/PL00009191.

12 Piotr Faliszewski, Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Shmuel Onn, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh, and Meirav Zehavi. What's next? Future directions in Parameterized Complexity. *Recent Advances in Parameterized Complexity, Tel-Aviv, Israel*, 2017. Accessed 18.09.2018. URL: https://rapctelaviv.weebly.com/uploads/1/0/5/3/105379375/future.pdf.

13 Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis. Approximate Max-Flow Min-MultiCut Theorems and Their Applications. *SIAM J. Comput.*, 25(2):235-251, 1996. doi:10.1137/S0097539793243016.

14 Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis. Multiway cuts in node weighted graphs. *J. Algorithms*, 50(1):49-61, 2004. doi:10.1016/S0196-6774(03)00111-1.

15 Sylvain Guillemot. FPT algorithms for path-transversal and cycle-transversal problems. *Discrete Optimization*, 8(1):61-71, 2011. doi:10.1016/j.disopt.2010.05.003.

16 Yoichi Iwata. Linear-Time Kernelization for Feedback Vertex Set. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, *44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland*, volume 80 of *LIPIcs*, pages 68:1-68:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. doi:10.4230/LIPIcs.ICALP.2017.68.

17 Yoichi Iwata, Magnus Wahlström, and Yuichi Yoshida. Half-integrality, LP-branching, and FPT Algorithms. *SIAM J. Comput.*, 45(4):1377-1411, 2016. doi:10.1137/140962838.

18 David R. Karger, Philip N. Klein, Clifford Stein, Mikkel Thorup, and Neal E. Young. Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut. *Math. Oper. Res.*, 29(3):436-461, 2004. doi:10.1287/moor.1030.0086.

19 Stefan Kratsch and Magnus Wahlström. Representative Sets and Irrelevant Vertices: New Tools for Kernelization. In *53rd Annual IEEE Symposium on Foundations of Computer*
4 Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, and Igor Razgon. A fixed-parameter algorithm for the directed feedback vertex set problem. *J. ACM*, 55(5):21:1-21:19, 2008. doi:10.1145/1411509.1411511.

5 Rajesh Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, Marcin Pilipczuk, and Michal Pilipczuk. Designing FPT Algorithms for Cut Problems Using Randomized Contractions. *SIAM J. Comput.*, 45(4):1171-1229, 2016. doi:10.1137/15M1032077.

6 Rajesh Chitnis, László Egri, and Dániel Marx. List H-Coloring a Graph by Removing Few Vertices. *Algorithmica*, 78(1):110-146, 2017. doi:10.1007/s00453-016-0139-6.

7 Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, and Dániel Marx. Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable. In Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer, editors, *ICALP (1)*, volume 7391 of *Lecture Notes in Computer Science*, pages 230-241. Springer, 2012. doi:10.1007/978-3-642-31594-7_20.

8 Rajesh Hemant Chitnis, Mohammad Taghi Hajiaghayi, and Dániel Marx. Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset. *SIAM J. Comput.*, 42(4):1674-1696, 2013. doi:10.1137/12086217X.

9 Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. *Parameterized Algorithms*. Springer, 2015. doi:10.1007/978-3-319-21275-3.

10 Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk. On multiway cut parameterized above lower bounds. *TOCT*, 5(1):3, 2013. doi:10.1145/2462896.2462899.

11 Guy Even, Joseph Naor, Baruch Schieber, and Madhu Sudan. Approximating Minimum Feedback Sets and Multicuts in Directed Graphs. *Algorithmica*, 20(2):151-174, 1998. doi: 10.1007/PL00009191.

12 Piotr Faliszewski, Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Shmuel Onn, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh, and Meirav Zehavi. What's next? Future directions in Parameterized Complexity. *Recent Advances in Parameterized Complexity, Tel-Aviv, Israel*, 2017. Accessed 18.09.2018. URL: https://rapctelaviv.weebly.com/uploads/1/0/5/3/105379375/future.pdf.

13 Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis. Approximate Max-Flow Min-MultiCut Theorems and Their Applications. *SIAM J. Comput.*, 25(2):235-251, 1996. doi:10.1137/S0097539793243016.

14 Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis. Multiway cuts in node weighted graphs. *J. Algorithms*, 50(1):49-61, 2004. doi:10.1016/S0196-6774(03)00111-1.

15 Sylvain Guillemot. FPT algorithms for path-transversal and cycle-transversal problems. *Discrete Optimization*, 8(1):61-71, 2011. doi:10.1016/j.disopt.2010.05.003.

16 Yoichi Iwata. Linear-Time Kernelization for Feedback Vertex Set. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, *44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland*, volume 80 of *LIPIcs*, pages 68:1-68:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. doi:10.4230/LIPIcs.ICALP.2017.68.

17 Yoichi Iwata, Magnus Wahlström, and Yuichi Yoshida. Half-integrality, LP-branching, and FPT Algorithms. *SIAM J. Comput.*, 45(4):1377-1411, 2016. doi:10.1137/140962838.

18 David R. Karger, Philip N. Klein, Clifford Stein, Mikkel Thorup, and Neal E. Young. Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut. *Math. Oper. Res.*, 29(3):436-461, 2004. doi:10.1287/moor.1030.0086.

19 Stefan Kratsch and Magnus Wahlström. Representative Sets and Irrelevant Vertices: New Tools for Kernelization. In *53rd Annual IEEE Symposium on Foundations of Computer*
18:14 Multi-Budgeted Directed Cuts

*Science*, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 450–459. IEEE Computer Society, 2012. doi:10.1109/FOCS.2012.46.

20 Stefan Kratsch and Magnus Wahlström. Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal. *ACM Transactions on Algorithms*, 10(4):20, 2014. doi:10.1145/2635810.

21 Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, and Meirav Zehavi. Parameterized Complexity and Approximability of Directed Odd Cycle Transversal. *CoRR*, abs/1704.04249, 2017. arXiv:1704.04249.

22 Dániel Marx. Parameterized graph separation problems. *Theor. Comput. Sci.*, 351(3):394–406, 2006. doi:10.1016/j.tcs.2005.10.007.

23 Dániel Marx. What's Next? Future Directions in Parameterized Complexity. In Hans L. Bodlaender, Rod Downey, Fedor V. Fomin, and Dániel Marx, editors, *The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday*, volume 7370 of *Lecture Notes in Computer Science*, pages 469–496. Springer, 2012. doi:10.1007/978-3-642-30891-8_20.

24 Dániel Marx, Barry O'Sullivan, and Igor Razgon. Finding small separators in linear time via treewidth reduction. *ACM Transactions on Algorithms*, 9(4):30, 2013. doi:10.1145/2500119.

25 Dániel Marx and Igor Razgon. Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset. *SIAM J. Comput.*, 43(2):355–388, 2014. doi:10.1137/110855247.

26 Marcin Pilipczuk and Magnus Wahlström. Directed multicut is W[1]-hard, even for four terminal pairs. In Robert Krauthgamer, editor, *Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016*, pages 1167–1178. SIAM, 2016. doi:10.1137/1.9781611974331.ch81.

27 Igor Razgon and Barry O'Sullivan. Almost 2-SAT is fixed-parameter tractable. *J. Comput. Syst. Sci.*, 75(8):435–450, 2009. doi:10.1016/j.jcss.2009.04.002.
18:14 Multi-Budgeted Directed Cuts

*Science*, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 450–459. IEEE Computer Society, 2012. doi:10.1109/FOCS.2012.46.

20 Stefan Kratsch and Magnus Wahlström. Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal. *ACM Transactions on Algorithms*, 10(4):20, 2014. doi:10.1145/2635810.

21 Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, and Meirav Zehavi. Parameterized Complexity and Approximability of Directed Odd Cycle Transversal. *CoRR*, abs/1704.04249, 2017. arXiv:1704.04249.

22 Dániel Marx. Parameterized graph separation problems. *Theor. Comput. Sci.*, 351(3):394–406, 2006. doi:10.1016/j.tcs.2005.10.007.

23 Dániel Marx. What's Next? Future Directions in Parameterized Complexity. In Hans L. Bodlaender, Rod Downey, Fedor V. Fomin, and Dániel Marx, editors, *The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday*, volume 7370 of *Lecture Notes in Computer Science*, pages 469–496. Springer, 2012. doi:10.1007/978-3-642-30891-8_20.

24 Dániel Marx, Barry O'Sullivan, and Igor Razgon. Finding small separators in linear time via treewidth reduction. *ACM Transactions on Algorithms*, 9(4):30, 2013. doi:10.1145/2500119.

25 Dániel Marx and Igor Razgon. Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset. *SIAM J. Comput.*, 43(2):355–388, 2014. doi:10.1137/110855247.

26 Marcin Pilipczuk and Magnus Wahlström. Directed multicut is W[1]-hard, even for four terminal pairs. In Robert Krauthgamer, editor, *Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016*, pages 1167–1178. SIAM, 2016. doi:10.1137/1.9781611974331.ch81.

27 Igor Razgon and Barry O'Sullivan. Almost 2-SAT is fixed-parameter tractable. *J. Comput. Syst. Sci.*, 75(8):435–450, 2009. doi:10.1016/j.jcss.2009.04.002.
# Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact Exponential Algorithms

## Christian Komusiewicz

Fachbereich Mathematik und Informatik, Philipps-Universität Marburg, Marburg, Germany
komusiewicz@informatik.uni-marburg.de

<figure><img src="image_100.png" /></figure>

https://orcid.org/0000-0003-0829-7032

## Dieter Kratsch

Laboratoire de Génie Informatique, de Production et de Maintenance, Université de Lorraine,
Metz, France

dieter.kratsch@univ-lorraine.fr

## Van Bang Le

Universität Rostock, Institut für Informatik, Rostock, Germany

van-bang.le@uni-rostock.de

## Abstract

In a graph, a matching cut is an edge cut that is a matching. MATCHING CUT, which is known to be NP-complete, is the problem of deciding whether or not a given graph $G$ has a matching cut. In this paper we show that MATCHING CUT admits a quadratic-vertex kernel for the parameter distance to cluster and a linear-vertex kernel for the parameter distance to clique. We further provide an $O*(2^{dc(G)})$ time and an $O*(2^{dc(G)})$ time FPT algorithm for MATCHING CUT, where $dc(G)$ and $dc(G)$ are the distance to cluster and distance to co-cluster, respectively. We also improve the running time of the best known branching algorithm to solve MATCHING CUT from $O*(1.4143^n)$ to $O*(1.3803^n)$. Moreover, we point out that, unless NP $\subseteq$ coNP/poly, MATCHING CUT does not admit a polynomial kernel when parameterized by treewidth.

**2012 ACM Subject Classification** Mathematics of computing $\rightarrow$ Graph theory, Theory of computation $\rightarrow$ Graph algorithms analysis, Theory of computation $\rightarrow$ Parameterized complexity and exact algorithms

**Keywords and phrases** matching cut, decomposable graph, graph algorithm

**Digital Object Identifier** 10.4230/LIPIcs.IPEC.2018.19

# 1 Introduction

In a graph $G = (V, E)$, a *cut* is a partition $V = A \cup B$ of the vertex set into disjoint, nonempty sets $A$ and $B$, written $(A, B)$. The set of all edges in $G$ having an endvertex in $A$ and the other endvertex in $B$, also written $(A, B)$, is called the *edge cut* of the cut $(A, B)$. A *matching cut* is an (possibly empty) edge cut that is a matching. Note that, by our definition, a matching whose removal disconnects the graph need not be a matching cut.

Another way to define matching cuts is as follows ([13, 7]). A partition $V = A \cup B$ of the vertex set of the graph $G = (V, E)$ into disjoint, nonempty sets $A$ and $B$, is a matching cut if and only if each vertex in $A$ has at most one neighbor in $B$ and each vertex in $B$ has at most one neighbor in $A$. Not every graph has a matching cut; the MATCHING CUT problem is the problem of deciding whether or not a given graph has a matching cut:

## MATCHING CUT

*Instance:* A graph $G = (V, E)$.

*Question:* Does $G$ have a matching cut?

<figure><img src="image_101.png" /></figure>

© Christian Komusiewicz, Dieter Kratsch, and Van Bang Le;

licensed under Creative Commons License CC-BY

13th International Symposium on Parameterized and Exact Computation (IPEC 2018).

Editors: Christophe Paul and Michal Pilipczuk; Article No. 19; pp. 19:1–19:13

<figure><img src="image_102.png" /></figure>

LIPICS

Leibniz International Proceedings in Informatics

Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
# Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact Exponential Algorithms

## Christian Komusiewicz

Fachbereich Mathematik und Informatik, Philipps-Universität Marburg, Marburg, Germany
komusiewicz@informatik.uni-marburg.de

https://orcid.org/0000-0003-0829-7032

## Dieter Kratsch

Laboratoire de Génie Informatique, de Production et de Maintenance, Université de Lorraine, Metz, France
dieter.kratsch@univ-lorraine.fr

## Van Bang Le

Universität Rostock, Institut für Informatik, Rostock, Germany
van-bang.le@uni-rostock.de

### Abstract

In a graph, a matching cut is an edge cut that is a matching. MATCHING CUT, which is known to be NP-complete, is the problem of deciding whether or not a given graph $G$ has a matching cut. In this paper we show that MATCHING CUT admits a quadratic-vertex kernel for the parameter distance to cluster and a linear-vertex kernel for the parameter distance to clique. We further provide an $O*(2^{dc(G)})$ time and an $O*(2^{d\bar{c}(G)})$ time FPT algorithm for MATCHING CUT, where $dc(G)$ and $d\bar{c}(G)$ are the distance to cluster and distance to co-cluster, respectively. We also improve the running time of the best known branching algorithm to solve MATCHING CUT from $O*(1.4143^n)$ to $O*(1.3803^n)$. Moreover, we point out that, unless NP $\subseteq$ coNP/poly, MATCHING CUT does not admit a polynomial kernel when parameterized by treewidth.

**2012 ACM Subject Classification** Mathematics of computing $\rightarrow$ Graph theory, Theory of computation $\rightarrow$ Graph algorithms analysis, Theory of computation $\rightarrow$ Parameterized complexity and exact algorithms

**Keywords and phrases** matching cut, decomposable graph, graph algorithm

**Digital Object Identifier** 10.4230/LIPIcs.IPEC.2018.19

## 1 Introduction

In a graph $G = (V, E)$, a *cut* is a partition $V = A \cup B$ of the vertex set into disjoint, nonempty sets *A* and *B*, written $(A, B)$. The set of all edges in *G* having an endvertex in *A* and the other endvertex in *B*, also written $(A, B)$, is called the *edge cut* of the cut $(A, B)$. A *matching cut* is an (possibly empty) edge cut that is a matching. Note that, by our definition, a matching whose removal disconnects the graph need not be a matching cut.

Another way to define matching cuts is as follows ([13, 7]). A partition $V = A \cup B$ of the vertex set of the graph $G = (V, E)$ into disjoint, nonempty sets *A* and *B*, is a matching cut if and only if each vertex in *A* has at most one neighbor in *B* and each vertex in *B* has at most one neighbor in *A*. Not every graph has a matching cut; the MATCHING CUT problem is the problem of deciding whether or not a given graph has a matching cut:

### MATCHING CUT

*Instance:* A graph $G = (V, E)$.

*Question:* Does *G* have a matching cut?

<figure><img src="image_103.png" /></figure>

© Christian Komusiewicz, Dieter Kratsch, and Van Bang Le;

licensed under Creative Commons License CC-BY

13th International Symposium on Parameterized and Exact Computation (IPEC 2018).

Editors: Christophe Paul and Michal Pilipczuk; Article No. 19; pp. 19:1–19:13

<figure><img src="image_104.png" /></figure>

LIPICS

Leibniz International Proceedings in Informatics

Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
19:2 Matching Cut

Farley and Proskurowski [11] studied matching cuts in graphs in the context of network applications. Patrignani and Pizzonia [18] pointed out an application of matching cuts in graph drawing. Graphs having no matching cut were first discussed by Graham in [13] under the name *indecomposable graphs*, and have been recently used by Araújo et al. [1] in the context of WDM (Wavelength Division Multiplexing) networks.

**Previous results.** Chvátal [7] showed that MATCHING CUT is NP-complete, even when restricted to graphs of maximum degree four, and polynomially solvable for graphs of maximum degree three. These results triggered a lot of research on the computational complexity of MATCHING CUT in graphs with additional structural assumptions [4, 6, 14, 16, 15, 17, 18]. In particular, the NP-hardness of MATCHING CUT has been further strengthened to planar graphs of maximum degree four [4] and bipartite graphs of maximum degree four [16]. As noted previously [14], the NP-hardness reduction by Chvátal [7] also shows that MATCHING CUT cannot be solved in $2^{o(n)}$ time, where $n$ is the number of vertices of the input graph, if the Exponential Time Hypothesis (ETH) is true.

Exact exponential algorithms for MATCHING CUT on graphs without any restriction have been recently considered by Kratsch and Le [14] who provided the first exact branching algorithm for MATCHING CUT running in time $O^*(1.4143^n)^1$, and a single-exponential algorithm of running time $2^{\tau(G)}O(n^2)$, where $\tau(G)$ is the vertex cover number. We note that MATCHING CUT can be expressed in MSOL, see for example [4]; hence MATCHING CUT is fixed-parameter tractable when parameterized by $tw(G)$, the treewidth of $G$. Very recently, Aravind et al. [2] presented a tree-decomposition-based dynamic programming algorithm that solves MATCHING CUT in $O^*(12^{tw(G)})$ time and fixed-parameter algorithms for further parameters describing the structure of the input graph. For example, MATCHING CUT can be solved in $O^*(2^{tc(G)})$ time where $tc(G) \le \tau(G)$ is the size of a smallest twin cover of $G$ [2].

**Our contributions.** We give the first polynomial kernels for MATCHING CUT by showing that MATCHING CUT admits a quadratic-vertex kernel for the parameter distance to cluster and a linear-vertex kernel for the parameter distance to clique. Second, we show that MATCHING CUT can be solved by single-exponential algorithms running in time $2^{dc(G)}O(n^2)$ and $2^{d\bar{c}(G)}O(nm)$, respectively, where $dc(G)$ is the distance to cluster and $d\bar{c}(G)$ is the distance to co-cluster. This improves upon the FPT algorithms for MATCHING CUT with running time $2^{\tau(G)}O(n^2)$ [14], where $\tau(G) \ge \max\{dc(G), d\bar{c}(G)\}$ is the vertex cover number of $G$ which can be much larger than $dc(G)$ and $d\bar{c}(G)$. Similarly, this improves upon the FPT algorithm with $O^*(2^{tc(G)})$ [2] since $tc(G) \ge dc(G)$. Third, we provide an exact branching algorithm for MATCHING CUT that has time complexity $O^*(1.3803^n)$. This result improves upon the first exact branching algorithm for MATCHING CUT that has time complexity $O^*(1.4143^n)$ [14].

**Notation and terminology.** Let $G = (V, E)$ be a graph with vertex set $V(G) := V$ and edge set $E(G) := E$. We assume that a (input) graph has $n$ vertices and $m$ edges. A *stable set* (a *clique*) in $G$ is a set of pairwise non-adjacent (adjacent) vertices. The neighborhood of a vertex $v$ in $G$, denoted by $N_G(v)$, is the set of all vertices in $G$ adjacent to $v$; if the context is clear, we simply write $N(v)$. Set $\deg(v) := |N(v)|$, the degree of the vertex $v$. For a subset $W \subseteq V$, $G[W]$ is the subgraph of $G$ induced by $W$, and $G - W$ stands for $G[V \setminus W]$.

<footnote n="1">¹ Throughout the paper we use the $O^*$ notation which suppresses polynomial factors.</footnote>
19:2 Matching Cut

Farley and Proskurowski [11] studied matching cuts in graphs in the context of network applications. Patrignani and Pizzonia [18] pointed out an application of matching cuts in graph drawing. Graphs having no matching cut were first discussed by Graham in [13] under the name *indecomposable graphs*, and have been recently used by Araújo et al. [1] in the context of WDM (Wavelength Division Multiplexing) networks.

**Previous results.** Chvátal [7] showed that MATCHING CUT is NP-complete, even when restricted to graphs of maximum degree four, and polynomially solvable for graphs of maximum degree three. These results triggered a lot of research on the computational complexity of MATCHING CUT in graphs with additional structural assumptions [4, 6, 14, 16, 15, 17, 18]. In particular, the NP-hardness of MATCHING CUT has been further strengthened to planar graphs of maximum degree four [4] and bipartite graphs of maximum degree four [16]. As noted previously [14], the NP-hardness reduction by Chvátal [7] also shows that MATCHING CUT cannot be solved in $2^{o(n)}$ time, where $n$ is the number of vertices of the input graph, if the Exponential Time Hypothesis (ETH) is true.

Exact exponential algorithms for MATCHING CUT on graphs without any restriction have been recently considered by Kratsch and Le [14] who provided the first exact branching algorithm for MATCHING CUT running in time $O^*(1.4143^n)^1$, and a single-exponential algorithm of running time $2^{\tau^{(G)}}O(n^2)$, where $\tau(G)$ is the vertex cover number. We note that MATCHING CUT can be expressed in MSOL, see for example [4]; hence MATCHING CUT is fixed-parameter tractable when parameterized by $tw(G)$, the treewidth of $G$. Very recently, Aravind et al. [2] presented a tree-decomposition-based dynamic programming algorithm that solves MATCHING CUT in $O^*(12^{tw^{(G)}})$ time and fixed-parameter algorithms for further parameters describing the structure of the input graph. For example, MATCHING CUT can be solved in $O^*(2^{tc^{(G)}})$ time where $tc(G) \le \tau(G)$ is the size of a smallest twin cover of $G$ [2].

**Our contributions.** We give the first polynomial kernels for MATCHING CUT by showing that MATCHING CUT admits a quadratic-vertex kernel for the parameter distance to cluster and a linear-vertex kernel for the parameter distance to clique. Second, we show that MATCHING CUT can be solved by single-exponential algorithms running in time $2^{dc^{(G)}}O(n^2)$ and $2^{d\bar{c}^{(G)}}O(nm)$, respectively, where $dc(G)$ is the distance to cluster and $d\bar{c}(G)$ is the distance to co-cluster. This improves upon the FPT algorithms for MATCHING CUT with running time $2^{\tau^{(G)}}O(n^2)$ [14], where $\tau(G) \ge \max\{dc(G), d\bar{c}(G)\}$ is the vertex cover number of $G$ which can be much larger than $dc(G)$ and $d\bar{c}(G)$. Similarly, this improves upon the FPT algorithm with $O^*(2^{tc^{(G)}})$ [2] since $tc(G) \ge dc(G)$. Third, we provide an exact branching algorithm for MATCHING CUT that has time complexity $O^*(1.3803^n)$. This result improves upon the first exact branching algorithm for MATCHING CUT that has time complexity $O^*(1.4143^n)$ [14].

**Notation and terminology.** Let $G = (V, E)$ be a graph with vertex set $V(G) := V$ and edge set $E(G) := E$. We assume that a (input) graph has $n$ vertices and $m$ edges. A *stable set* (a *clique*) in $G$ is a set of pairwise non-adjacent (adjacent) vertices. The neighborhood of a vertex $v$ in $G$, denoted by $N_G(v)$, is the set of all vertices in $G$ adjacent to $v$; if the context is clear, we simply write $N(v)$. Set $\deg(v) := |N(v)|$, the degree of the vertex $v$. For a subset $W \subseteq V$, $G[W]$ is the subgraph of $G$ induced by $W$, and $G - W$ stands for $G[V \setminus W]$.

<footnote n="1">¹ Throughout the paper we use the $O^*$ notation which suppresses polynomial factors.</footnote>
We write $N_W(v)$ for $N(v) \cap W$ and call the vertices in $N(v) \cap W$ the W-neighbors of $v$. A graph is a cluster graph if it is a vertex disjoint union of cliques. The maximal cliques of a cluster graph are called clusters. A graph is a co-cluster graph if it is a complete multipartite graph or, equivalently, the complement graph of a cluster graph. Observe that a clique is a cluster graph and a co-cluster graph.

A vertex cover of $G$ is a subset $C \subseteq V$ such that every edge of $G$ has at least one endvertex in $C$, i.e., $V \setminus C$ is a stable set in $G$. The vertex cover number of $G$, denoted by $\tau(G)$, is the smallest size of a vertex cover of $G$. More generally, given a graph property $\mathcal{P}$, a distance to $\mathcal{P}$ set of a graph $G$ is a subset $U \subseteq V$ such that $G - U$ has the property $\mathcal{P}$. The distance to $\mathcal{P}$ is the smallest size of a distance to $\mathcal{P}$ set. This number is called distance to cluster, denoted by $\text{dc}(G)$, in case $\mathcal{P}$ is the set of cluster graphs, it is called distance to co-cluster, denoted by $\text{d}\bar{c}(G)$, in case $\mathcal{P}$ is the set of co-cluster graphs, and it is called distance to clique, denoted by $\text{dq}(G)$, in case $\mathcal{P}$ is the set of cliques. By the definition of cluster graphs and co-cluster graphs, we have $\tau(G) \ge \max\{\text{dc}(G), \text{d}\bar{c}(G)\}$ and $\text{dq}(G) \ge \max\{\text{dc}(G), \text{d}\bar{c}(G)\}$ for any graph $G$.

Throughout the paper we use the concept of monochromatic vertex subsets and induced subgraphs. Let $G = (V, E)$ be a graph and $U \subseteq V$. Then we call $U$ monochromatic in $G$ if for every matching cut $(A, B)$ of $G$, either $U \subseteq A$ or $U \subseteq B$; slightly abusing notation we shall sometimes also call $G[U]$ monochromatic in $G$. Being monochromatic is hereditary: if $G[U]$ is monochromatic, then so is $G[U']$ for every $U' \subseteq U$. Note that a complete subgraph $K_n$ is monochromatic if $n = 1$ or $n \ge 3$, and that a complete bipartite subgraph $K_{n,m}$ is monochromatic if $n \ge 3$ and $m \ge 2$ or vice versa. Moreover, disconnected graphs and graphs having a vertex of degree at most one admit a matching cut. Hence, we may assume that all graphs considered are connected and have minimum degree at least two.

When an algorithm branches on the current instance of size $n$ into $r$ subproblems of sizes at most $n - t_1, n - t_2, \dots, n - t_r$, then $(t_1, t_2, \dots, t_r)$ is called the branching vector of this branching, and the unique positive root of $x^n - x^{n-t_1} - x^{n-t_2} - \dots - x^{n-t_r} = 0$, denoted by $\tau(t_1, t_2, \dots, t_r)$, is called its branching number. The running time of a branching algorithm is $O^*(\alpha^n)$, where $\alpha = \max_i \alpha_i$ and $\alpha_i$ is the branching number of branching rule $i$, and the maximum is taken over all branching rules. We refer to [12] for more details on exact branching algorithms. For the basic notions of parameterized complexity we refer to [8].

## 2 A Polynomial Kernel for the Distance to Cluster

In this section we present a polynomial kernel for the parameter $\text{dc}(G)$, the distance of $G$ to a cluster graph. First, however, we motivate the study of the parameter $\text{dc}(G)$ by a negative result. Recall that there is an FPT algorithm for MATCHING CUT when parameterized by treewidth [2, 4]. Hence, a natural question is whether MATCHING CUT admits a polynomial kernel for this parameter. A further candidate parameter for a polynomial kernel is the minimum number $k$ of edges crossing any matching cut; this could be considered the standard solution size parameter for MATCHING CUT. Finally, a common parameter in kernelizations is the maximum degree of the input graph. We rule out polynomial kernels for all three parameters.

**Proposition 1.** MATCHING CUT does not admit polynomial kernel with respect to the sum of the treewidth of $G$, the minimum number of edges crossing any matching cut of $G$, and the maximum degree in $G$ unless $NP \subseteq \text{coNP}/\text{poly}$.

The proof of Proposition 1 uses cross-composition and is deferred to the full version of this work.
We write $N_W(v)$ for $N(v) \cap W$ and call the vertices in $N(v) \cap W$ the *W-neighbors* of $v$. A graph is a *cluster graph* if it is a vertex disjoint union of cliques. The maximal cliques of a cluster graph are called *clusters*. A graph is a *co-cluster graph* if it is a complete multipartite graph or, equivalently, the complement graph of a cluster graph. Observe that a clique is a cluster graph and a co-cluster graph.

A *vertex cover* of $G$ is a subset $C \subseteq V$ such that every edge of $G$ has at least one endvertex in $C$, i.e., $V \setminus C$ is a stable set in $G$. The vertex cover number of $G$, denoted by $\tau(G)$, is the smallest size of a vertex cover of $G$. More generally, given a graph property $\mathcal{P}$, a *distance to* $\mathcal{P}$ set of a graph $G$ is a subset $U \subseteq V$ such that $G - U$ has the property $\mathcal{P}$. The *distance to* $\mathcal{P}$ is the smallest size of a distance to $\mathcal{P}$ set. This number is called *distance to cluster*, denoted by $\text{dc}(G)$, in case $\mathcal{P}$ is the set of cluster graphs, it is called *distance to co-cluster*, denoted by $\text{d}\bar{c}(G)$, in case $\mathcal{P}$ is the set of co-cluster graphs, and it is called *distance to clique*, denoted by $\text{dq}(G)$, in case $\mathcal{P}$ is the set of cliques. By the definition of cluster graphs and co-cluster graphs, we have $\tau(G) \ge \max\{\text{dc}(G), \text{d}\bar{c}(G)\}$ and $\text{dq}(G) \ge \max\{\text{dc}(G), \text{d}\bar{c}(G)\}$ for any graph $G$.

Throughout the paper we use the concept of monochromatic vertex subsets and induced subgraphs. Let $G = (V, E)$ be a graph and $U \subseteq V$. Then we call $U$ *monochromatic* in $G$ if for every matching cut $(A, B)$ of $G$, either $U \subseteq A$ or $U \subseteq B$; slightly abusing notation we shall sometimes also call $G[U]$ monochromatic in $G$. Being monochromatic is hereditary: if $G[U]$ is monochromatic, then so is $G[U']$ for every $U' \subseteq U$. Note that a complete subgraph $K_n$ is monochromatic if $n = 1$ or $n \ge 3$, and that a complete bipartite subgraph $K_{n,m}$ is monochromatic if $n \ge 3$ and $m \ge 2$ or vice versa. Moreover, disconnected graphs and graphs having a vertex of degree at most one admit a matching cut. Hence, we may assume that all graphs considered are connected and have minimum degree at least two.

When an algorithm branches on the current instance of size $n$ into $r$ subproblems of sizes at most $n - t_1, n - t_2, \dots, n - t_r$, then $(t_1, t_2, \dots, t_r)$ is called the *branching vector* of this branching, and the unique positive root of $x^n - x^{n-t_1} - x^{n-t_2} - \dots - x^{n-t_r} = 0$, denoted by $\tau(t_1, t_2, \dots, t_r)$, is called its *branching number*. The running time of a branching algorithm is $O^*(\alpha^n)$, where $\alpha = \max_i \alpha_i$ and $\alpha_i$ is the branching number of branching rule $i$, and the maximum is taken over all branching rules. We refer to [12] for more details on exact branching algorithms. For the basic notions of parameterized complexity we refer to [8].

## 2 A Polynomial Kernel for the Distance to Cluster

In this section we present a polynomial kernel for the parameter $\text{dc}(G)$, the distance of $G$ to a cluster graph. First, however, we motivate the study of the parameter $\text{dc}(G)$ by a negative result. Recall that there is an FPT algorithm for MATCHING CUT when parameterized by treewidth [2, 4]. Hence, a natural question is whether MATCHING CUT admits a polynomial kernel for this parameter. A further candidate parameter for a polynomial kernel is the minimum number $k$ of edges crossing any matching cut; this could be considered the standard solution size parameter for MATCHING CUT. Finally, a common parameter in kernelizations is the maximum degree of the input graph. We rule out polynomial kernels for all three parameters.

**Proposition 1.** MATCHING CUT does not admit polynomial kernel with respect to the sum of the treewidth of $G$, the minimum number of edges crossing any matching cut of $G$, and the maximum degree in $G$ unless $NP \subseteq \text{coNP}/\text{poly}$.

The proof of Proposition 1 uses cross-composition and is deferred to the full version of this work.
<figure><img src="image_103.png" /><figcaption>Figure 1 An example for the definition of $N^2(U_i)$ with $U_i = \{u, v\}$. We have $\{x, a\} \subseteq N^2(U_i)$ since $x$ and $a$ have two neighbors in $U_i$. Moreover, $\{y, z\} \subseteq N^2(U_i)$ since $y$ and $z$ are in a cluster of size at least three with $x$. Alternatively, $\{x, y, z\} \subseteq N^2(U_i)$ since $u \in U_i$ is adjacent to $x$ and $y$. Finally, $b \notin N^2(U_i)$ even though $a \in N^2(U_i)$, since the cluster $\{a, b\}$ has only size two.</figcaption></figure>

This excludes many natural candidate parameters for kernelization and motivates our study of kernelization for $dc(G)$, the distance of $G$ to a cluster graph. Let $U = \{u_1, \dots, u_{|U|}\}$ denote a vertex set such that $G-U$ is a cluster graph. We may assume that $|U| \le 3dc(G)$ since a 3-approximation of CLUSTER VERTEX DELETION can be computed in time $O(\text{dc}(G)(n+m))$ based on the observation that a graph is a cluster graph if and only if it does not contain an induced path on three vertices. During the kernelization, we maintain a partition of $U$ into $U_1, \dots, U_\ell$ such that each $U_i$ is monochromatic. The initial partition contains one set for each vertex of $U$, that is, $U_i := \{u_i\}$, $1 \le i \le |U|$. We call the sets of the partition the monochromatic parts of $U$.

During the kernelization, we may merge two sets $U_i$ and $U_j$, $i \neq j$, which is to remove $U_i$ and $U_j$ from the partition and to add $U_i \cup U_j$. We say that merging $U_i$ and $U_j$ is safe if $U_i \cup U_j$ is monochromatic in $G$.

The main idea of the kernelization is to find opportunities to merge monochromatic parts of $U$ or to transform distinct clusters into a single cluster because we infer that they form a larger monochromatic set. Intuitively, an opportunity for merging arises when there are many vertices in $V \setminus U$ with at least two neighbors in $U$. The first step handles some clusters that have no such vertex.

**Reduction Rule 1.** If $V \setminus U$ contains a degree-one vertex or a cluster $C$ such that $(V \setminus C, C)$ is a matching cut, then output "yes".

The correctness of the rule is obvious. After its application, every cluster $C$ contains either a vertex $v$ with two neighbors in $U$ or there is a vertex in $u \in U$ with two neighbors in $C$.

To identify clusters that form monochromatic sets together with some monochromatic parts of $U$, we introduce the following notation. For each monochromatic part $U_i$ of $U$, we let $N^2(U_i)$ denote the set of vertices $v \in V \setminus U$ such that at least one of the following holds:

- $v$ has two neighbors in $U_i$,

- $v$ is in a cluster of size at least three in $G - U$ that contains a vertex that has two neighbors in $U_i$, or

- $v$ is in a cluster $C$ in $G - U$ and some vertex in $U_i$ has two neighbors in $C$.

**Proposition 1.** $U_i \cup N^2(U_i)$ is monochromatic.

**Proof.** In the first case, $v$ has two neighbors in the monochromatic set $U_i$ and thus $U_i \cup \{v\}$ is monochromatic. In the second case, the cluster $C$ containing $v$ is monochromatic and contains a vertex $w$ such that $U_i \cup \{w\}$ is monochromatic. Hence, $U_i \cup C$ is monochromatic. In the third case, the cluster $C$ contains two vertices $x$ and $y$ that form a triangle with some vertex from $U_i$ and thus $U_i \cup \{x, y\}$ is monochromatic. If $|C| = 2$, then $x = v$ or $y = v$, if $|C| > 3$, then $C$ is monochromatic and thus $U_i \cup C$ is monochromatic. $\quad \blacksquare$
<figure><img src="image_105.png" /><figcaption>Figure 1 An example for the definition of $N^2(U_i)$ with $U_i = \{u, v\}$. We have $\{x, a\} \subseteq N^2(U_i)$ since $x$ and $a$ have two neighbors in $U_i$. Moreover, $\{y, z\} \subseteq N^2(U_i)$ since $y$ and $z$ are in a cluster of size at least three with $x$. Alternatively, $\{x, y, z\} \subseteq N^2(U_i)$ since $u \in U_i$ is adjacent to $x$ and $y$. Finally, $b \notin N^2(U_i)$ even though $a \in N^2(U_i)$, since the cluster $\{a, b\}$ has only size two.</figcaption></figure>

This excludes many natural candidate parameters for kernelization and motivates our study of kernelization for $dc(G)$, the distance of $G$ to a cluster graph. Let $U = \{u_1, \dots, u_{|U|}\}$ denote a vertex set such that $G-U$ is a cluster graph. We may assume that $|U| \le 3dc(G)$ since a 3-approximation of CLUSTER VERTEX DELETION can be computed in time $O/dc(G)(n+m))$ based on the observation that a graph is a cluster graph if and only if it does not contain an induced path on three vertices. During the kernelization, we maintain a partition of $U$ into $U_1, \dots, U_\ell$ such that each $U_i$ is monochromatic. The initial partition contains one set for each vertex of $U$, that is, $U_i := \{u_i\}$, $1 \le i \le |U|$. We call the sets of the partition the *monochromatic parts of $U$*.

During the kernelization, we may *merge* two sets $U_i$ and $U_j$, $i \ne j$, which is to remove $U_i$ and $U_j$ from the partition and to add $U_i \cup U_j$. We say that merging $U_i$ and $U_j$ is *safe* if $U_i \cup U_j$ is monochromatic in $G$.

The main idea of the kernelization is to find opportunities to merge monochromatic parts of $U$ or to transform distinct clusters into a single cluster because we infer that they form a larger monochromatic set. Intuitively, an opportunity for merging arises when there are many vertices in $V \setminus U$ with at least two neighbors in $U$. The first step handles some clusters that have no such vertex.

**Reduction Rule 1.** If $V \setminus U$ contains a degree-one vertex or a cluster $C$ such that $(V \setminus C, C)$ is a matching cut, then output "yes".

The correctness of the rule is obvious. After its application, every cluster $C$ contains either a vertex $v$ with two neighbors in $U$ or there is a vertex in $u \in U$ with two neighbors in $C$.

To identify clusters that form monochromatic sets together with some monochromatic parts of $U$, we introduce the following notation. For each monochromatic part $U_i$ of $U$, we let $N^2(U_i)$ denote the set of vertices $v \in V \setminus U$ such that at least one of the following holds:

- $v$ has two neighbors in $U_i$,

- $v$ is in a cluster of size at least three in $G - U$ that contains a vertex that has two neighbors in $U_i$, or

- $v$ is in a cluster $C$ in $G - U$ and some vertex in $U_i$ has two neighbors in $C$.

**Proposition 1.** $U_i \cup N^2(U_i)$ is monochromatic.

**Proof.** In the first case, $v$ has two neighbors in the monochromatic set $U_i$ and thus $U_i \cup \{v\}$ is monochromatic. In the second case, the cluster $C$ containing $v$ is monochromatic and contains a vertex $w$ such that $U_i \cup \{w\}$ is monochromatic. Hence, $U_i \cup C$ is monochromatic. In the third case, the cluster $C$ contains two vertices $x$ and $y$ that form a triangle with some vertex from $U_i$ and thus $U_i \cup \{x, y\}$ is monochromatic. If $|C| = 2$, then $x = v$ or $y = v$, if $|C| > 3$, then $C$ is monochromatic and thus $U_i \cup C$ is monochromatic. $\quad \blacksquare$
The next two rules identify monochromatic parts that can be merged because they belong to overlapping monochromatic sets.

**Reduction Rule 2.** If there is a vertex $v$ that is contained in $N^2(U_i)$ and $N^2(U_j)$ for $i \neq j$, then merge $U_i$ and $U_j$.

**Proof of safeness.** By Proposition 1, $\{v\} \cup U_i$ and $\{v\} \cup U_j$ are monochromatic in $G$. Thus, $U_i \cup U_j \cup \{v\}$ is monochromatic. ◀

**Reduction Rule 3.** If there are three vertices $v_1, v_2, v_3$ in $V$ that have two common neighbors $u \in U_i$ and $u' \in U_j$, $i \neq j$, then merge $U_i$ and $U_j$.

**Proof of safeness.** The proof is based on the fact that a $K_{n,m}$ is monochromatic for $n \ge 3$ and $m \ge 2$: Assume that $u$ and $u'$ are not in the same part of a matching cut $(A, B)$. Then, at most one vertex of $\{v_1, v_2, v_3\}$ is in $A$ and at most one is in $B$. This is absurd and, thus, $\{u, u'\}$ is monochromatic which makes $U_i \cup U_j$ monochromatic. ◀

In the following, a cluster consisting of two vertices is an *edge cluster*, all other clusters are *nonedge clusters*. As we will show, after application of the above rules, we have essentially reached a situation in which there is a bounded number of nonedge clusters that are not contained in some $N^2(U_i)$, we call these clusters *ambiguous*. More precisely, we say that a vertex in $V \setminus U$ is *ambiguous* if it has neighbors in $U_i$ and $U_j$ where $i \neq j$. A cluster is *ambiguous* if it contains at least one ambiguous vertex. In contrast, we call a cluster *fixed* if it is contained in $N^2(U_i)$ for some $U_i$.

**Proposition 2.** If $G$ is reduced with respect to Reduction Rule 1, then every nonedge cluster in $G$ is ambiguous or fixed.

**Proof.** Since $G$ is reduced with respect to Reduction Rule 1, every cluster $C$ contains at least one vertex $v$ that has two neighbors in $U$ or there is a vertex $u$ from some monochromatic part $U_i$ that has two neighbors in $C$. In the latter case, $C$ is contained in $N^2(U_i)$ and thus fixed. In the first case, if $v$ has two neighbors in the same part $U_i$, then $C \subseteq N^2(U_i)$ and $C$ is fixed. Otherwise, $v$ is ambiguous which means that $C$ is ambiguous. ◀

Observe that according to this definition, a nonedge cluster may be ambiguous and fixed at the same time. We will decrease the number of fixed clusters with the following rule.

**Reduction Rule 4.** If there are two clusters $C_1$ and $C_2$ that are contained in $N^2(U_i)$, then add all edges between these clusters.

**Proof of safeness.** Let $G$ denote the graph to which the rule is applied and let $G'$ denote the resulting graph. If $G'$ has a matching cut, then so does $G$, because $G$ is a subgraph of $G'$ on the same vertex set.

For the converse, consider the following: $C_1 \cup C_2$ is monochromatic since $C_1$ and $C_2$ are contained in $N^2(U_i)$. Thus, if $G$ has a matching cut, then so does $G'$ because adding edges between vertices of a monochromatic set does not destroy the matching cut property. ◀

The following is obvious by the pigeonhole principle and the fact that the number of monochromatic parts is at most $|U|$.

**Lemma 1.** Let $G$ be an instance of MATCHING CUT with cluster vertex deletion set $U$ that is reduced with respect to Reduction Rule 4. Then $G$ has $O(|U|)$ fixed clusters.

The next rules will help in bounding the number of vertices in the clusters.
The next two rules identify monochromatic parts that can be merged because they belong to overlapping monochromatic sets.

**Reduction Rule 2.** If there is a vertex $v$ that is contained in $N^2(U_i)$ and $N^2(U_j)$ for $i \neq j$, then merge $U_i$ and $U_j$.

**Proof of safeness.** By Proposition 1, $\{v\} \cup U_i$ and $\{v\} \cup U_j$ are monochromatic in $G$. Thus, $U_i \cup U_j \cup \{v\}$ is monochromatic. ◀

**Reduction Rule 3.** If there are three vertices $v_1, v_2, v_3$ in $V$ that have two common neighbors $u \in U_i$ and $u' \in U_j$, $i \neq j$, then merge $U_i$ and $U_j$.

**Proof of safeness.** The proof is based on the fact that a $K_{n,m}$ is monochromatic for $n \ge 3$ and $m \ge 2$: Assume that $u$ and $u'$ are not in the same part of a matching cut $(A, B)$. Then, at most one vertex of $\{v_1, v_2, v_3\}$ is in $A$ and at most one is in $B$. This is absurd and, thus, $\{u, u'\}$ is monochromatic which makes $U_i \cup U_j$ monochromatic. ◀

In the following, a cluster consisting of two vertices is an *edge cluster*, all other clusters are *nonedge clusters*. As we will show, after application of the above rules, we have essentially reached a situation in which there is a bounded number of nonedge clusters that are not contained in some $N^2(U_i)$, we call these clusters *ambiguous*. More precisely, we say that a vertex in $V \setminus U$ is *ambiguous* if it has neighbors in $U_i$ and $U_j$ where $i \neq j$. A cluster is *ambiguous* if it contains at least one ambiguous vertex. In contrast, we call a cluster *fixed* if it is contained in $N^2(U_i)$ for some $U_i$.

**Proposition 2.** If $G$ is reduced with respect to Reduction Rule 1, then every nonedge cluster in $G$ is ambiguous or fixed.

**Proof.** Since $G$ is reduced with respect to Reduction Rule 1, every cluster $C$ contains at least one vertex $v$ that has two neighbors in $U$ or there is a vertex $u$ from some monochromatic part $U_i$ that has two neighbors in $C$. In the latter case, $C$ is contained in $N^2(U_i)$ and thus fixed. In the first case, if $v$ has two neighbors in the same part $U_i$, then $C \subseteq N^2(U_i)$ and $C$ is fixed. Otherwise, $v$ is ambiguous which means that $C$ is ambiguous. ◀

Observe that according to this definition, a nonedge cluster may be ambiguous and fixed at the same time. We will decrease the number of fixed clusters with the following rule.

**Reduction Rule 4.** If there are two clusters $C_1$ and $C_2$ that are contained in $N^2(U_i)$, then add all edges between these clusters.

**Proof of safeness.** Let $G$ denote the graph to which the rule is applied and let $G'$ denote the resulting graph. If $G'$ has a matching cut, then so does $G$, because $G$ is a subgraph of $G'$ on the same vertex set.

For the converse, consider the following: $C_1 \cup C_2$ is monochromatic since $C_1$ and $C_2$ are contained in $N^2(U_i)$. Thus, if $G$ has a matching cut, then so does $G'$ because adding edges between vertices of a monochromatic set does not destroy the matching cut property. ◀

The following is obvious by the pigeonhole principle and the fact that the number of monochromatic parts is at most $|U|$.

**Lemma 1.** Let $G$ be an instance of MATCHING CUT with cluster vertex deletion set $U$ that is reduced with respect to Reduction Rule 4. Then $G$ has $O(|U|)$ fixed clusters.

The next rules will help in bounding the number of vertices in the clusters.
**▶ Reduction Rule 5.** If there is a cluster C with more than three vertices that contains a vertex v with no neighbors in U, then remove v.

**Proof of safeness.** Let $G$ denote the original graph and let $G'$ be the graph obtained from the application of the reduction rule. Since $|C| \ge 4$, $C$ is monochromatic in $G$ and $C-v$ is monochromatic in $G'$. This and the fact that $v$ has only neighbors in $C$ immediately implies that $G$ and $G'$ are equivalent. ◀

After application of Rule 5, every vertex in a cluster of size at least three has a neighbor in $U$. The next rule removes unnecessary edges between monochromatic parts and clusters.

**▶ Reduction Rule 6.** If there is a cluster $C$ with at least three vertices and a monochromatic set $U_i$ such that $C \subseteq N^2(U_i)$, then remove all edges between $C$ and $U_i$ from $G$, choose an arbitrary vertex $u \in U_i$ and two vertices $v_1, v_2 \in C$, and add two edges $\{u, v_1\}$ and $\{u, v_2\}$. If $|U_i| = 2$, then add an edge between $u' \in U_i \setminus \{u\}$ and $v_3 \in C \setminus \{v_1, v_2\}$. If $|U_i| > 2$, then make $U_i$ a clique.

**Proof of safeness.** Let $G$ denote the original graph and let $G'$ be the graph obtained from the application of the reduction rule. Since $C \subseteq N^2(U_i)$, we have, by Proposition 1, that $U_i \cup C$ is monochromatic. Thus, if $G$ has a matching cut $(A, B)$, then without loss of generality we have $U_i \cup C \subseteq A$. This implies that $(A, B)$ is a matching cut of $G'$ since $G'$ is obtained from $G$ by removing and adding certain edges between vertices in $U_i \cup C \subseteq A$.

Conversely, assume that $G'$ has a matching cut. In $G'$, $U_i$ is monochromatic and thus the cluster $C$ is contained in $N^2(U_i)$. By Proposition 1, $U_i \cup C$ is monochromatic in $G'$. As above, since $G$ can be obtained from $G'$ by removing and adding certain edges between vertices in $U_i \cup C$, $G$ also has a matching cut. ◀

After application of these rules, the size of the instance is, with exception of the edge clusters, already bounded by a polynomial function of $|U|$ as we show in the following.

**▶ Lemma 2.** Let $G$ be an instance of MATCHING CUT with cluster vertex deletion set $U$ that is reduced with respect to Reduction Rules 1–6. Then $G$ has

- $O(|U|^2)$ ambiguous vertices, and

- $O(|U|^2)$ nonedge clusters, each containing $O(|U|)$ vertices.

The proof of Lemma 2 is deferred to the full version of this work.

To obtain a first bound on the instance size, it remains to reduce the overall number of edge clusters. To this end, we consider for each edge cluster $\{u, v\}$ the neighborhoods of $u$ and $v$ in $U$. First, observe that, assuming $G$ is reduced with respect to Reduction Rule 1, $u$ and $v$ have neighbors in $U$. Now we call an edge cluster $\{u, v\}$ *simple* if $u$ has only neighbors in $U_i$ and $v$ has only neighbors in $U_j$ (possibly $i = j$). Observe that the number of non-simple edge clusters is already bounded: Each such cluster is ambiguous because at least one of its vertices is ambiguous. By Lemma 2, there are $O(|U|^2)$ such vertices and thus $O(|U|^2)$ clusters containing them. To obtain a bound on the overall number of edge clusters, we show that all simple edge clusters can be removed.

**▶ Reduction Rule 7.** If there is a simple edge cluster $\{u, v\}$, then remove $u$ and $v$ from $G$.

The proof of the safeness of this rule is deferred to the full version of this work.

Thus, with the above rules we obtain a kernel with $O(\mathrm{dc}(G)^3)$ vertices: a reduced instance has $O(|U|^2) = O(\mathrm{dc}(G)^2)$ clusters, each containing $O(|U|) = O(\mathrm{dc}(G))$ vertices. To obtain a kernel with an overall quadratic number of vertices, we observe first that after applications
**► Reduction Rule 5.** If there is a cluster *C* with more than three vertices that contains a vertex *v* with no neighbors in *U*, then remove *v*.

**Proof of safeness.** Let $G$ denote the original graph and let $G'$ be the graph obtained from the application of the reduction rule. Since $|C| \ge 4$, $C$ is monochromatic in $G$ and $C-v$ is monochromatic in $G'$. This and the fact that $v$ has only neighbors in $C$ immediately implies that $G$ and $G'$ are equivalent. ◀

After application of Rule 5, every vertex in a cluster of size at least three has a neighbor in $U$. The next rule removes unnecessary edges between monochromatic parts and clusters.

**► Reduction Rule 6.** If there is a cluster *C* with at least three vertices and a monochromatic set $U_i$ such that $C \subseteq N^2(U_i)$, then remove all edges between *C* and $U_i$ from *G*, choose an arbitrary vertex $u \in U_i$ and two vertices $v_1, v_2 \in C$, and add two edges $\{u, v_1\}$ and $\{u, v_2\}$. If $|U_i| = 2$, then add an edge between $u' \in U_i \setminus \{u\}$ and $v_3 \in C \setminus \{v_1, v_2\}$. If $|U_i| > 2$, then make $U_i$ a clique.

**Proof of safeness.** Let $G$ denote the original graph and let $G'$ be the graph obtained from the application of the reduction rule. Since $C \subseteq N^2(U_i)$, we have, by Proposition 1, that $U_i \cup C$ is monochromatic. Thus, if $G$ has a matching cut $(A, B)$, then without loss of generality we have $U_i \cup C \subseteq A$. This implies that $(A, B)$ is a matching cut of $G'$ since $G'$ is obtained from $G$ by removing and adding certain edges between vertices in $U_i \cup C \subseteq A$.

Conversely, assume that $G'$ has a matching cut. In $G'$, $U_i$ is monochromatic and thus the cluster $C$ is contained in $N^2(U_i)$. By Proposition 1, $U_i \cup C$ is monochromatic in $G'$. As above, since $G$ can be obtained from $G'$ by removing and adding certain edges between vertices in $U_i \cup C$, $G$ also has a matching cut. ◀

After application of these rules, the size of the instance is, with exception of the edge clusters, already bounded by a polynomial function of $|U|$ as we show in the following.

**► Lemma 2.** Let $G$ be an instance of MATCHING CUT with cluster vertex deletion set $U$ that is reduced with respect to Reduction Rules 1–6. Then $G$ has

- $O(|U|^2)$ ambiguous vertices, and

- $O(|U|^2)$ nonedge clusters, each containing $O(|U|)$ vertices.

The proof of Lemma 2 is deferred to the full version of this work.

To obtain a first bound on the instance size, it remains to reduce the overall number of edge clusters. To this end, we consider for each edge cluster $\{u, v\}$ the neighborhoods of $u$ and $v$ in $U$. First, observe that, assuming $G$ is reduced with respect to Reduction Rule 1, $u$ and $v$ have neighbors in $U$. Now we call an edge cluster $\{u, v\}$ *simple* if $u$ has only neighbors in $U_i$ and $v$ has only neighbors in $U_j$ (possibly $i = j$). Observe that the number of non-simple edge clusters is already bounded: Each such cluster is ambiguous because at least one of its vertices is ambiguous. By Lemma 2, there are $O(|U|^2)$ such vertices and thus $O(|U|^2)$ clusters containing them. To obtain a bound on the overall number of edge clusters, we show that all simple edge clusters can be removed.

**► Reduction Rule 7.** If there is a simple edge cluster $\{u, v\}$, then remove $u$ and $v$ from $G$.

The proof of the safeness of this rule is deferred to the full version of this work.

Thus, with the above rules we obtain a kernel with $O(\mathrm{dc}(G)^3)$ vertices: a reduced instance has $O(|U|^2) = O(\mathrm{dc}(G)^2)$ clusters, each containing $O(|U|) = O(\mathrm{dc}(G))$ vertices. To obtain a kernel with an overall quadratic number of vertices, we observe first that after applications
of Reduction Rule 6, every vertex in cluster $C$, where $|C| \ge 3$ and $C \subseteq N^2(U_i)$ for some $i$, has at most one neighbor in $U_i$.

It remains to bound the number of vertices in $V \setminus U$ with only one neighbor in $U$. First, we find monochromatic parts of $U$ that can be merged not because they have many common neighbors but, instead, because they have common neighbors in several nonedge clusters.

**Reduction Rule 8.** If there are two vertices $u \in U_i$ and $u' \in U_j$, $i \neq j$, and three distinct nonedge clusters $C_1, C_2, C_3$ such that $u$ and $u'$ have at least one neighbor in each of them, then merge $U_i$ and $U_j$.

**Proof of safeness.** We show that $U_i \cup U_j$ is monochromatic; by definition this implies that merging $U_i$ and $U_j$ is safe. Let $(A, B)$ be any matching cut of $G$. Each of the three clusters is monochromatic because they are nonedge clusters. Hence, we can assume without loss of generality, that $A$ contains $C_1$ and $C_2$. Since $u$ has neighbors in $C_1$ and in $C_2$, it has two neighbors in $A$ and thus $U_i \subseteq A$. Similarly, $U_j \subseteq A$. Hence, $U_i \cup U_j$ is in the same part of the cut. This holds for all cuts, making $U_i \cup U_j$ monochromatic. ◀

**Lemma 3.** After exhaustive application of Reduction Rules 1–8, there are $O(|U^2|)$ vertices in $V \setminus U$ that are in nonedge clusters and have only one neighbor in $U$.

**Proof.** First, by Lemma 1, there are $O(|U|)$ fixed nonedge clusters. By Lemma 2, these clusters contain $O(|U|)$ vertices each. Thus, the number of vertices in fixed nonedge clusters that have only one neighbor in $U$ is $O(|U|^2)$.

Hence, it remains to bound the number of vertices that have only one neighbor in $U$ and are contained in a nonfixed cluster $C$. By Proposition 2, these clusters are ambiguous. Each ambiguous cluster $C$ contains an ambiguous vertex with neighbors in $U_i$ and $U_j$, where $i \neq j$. Thus, for each vertex of $C$ with only one neighbor $u \in U$, there is at least one other vertex $u' \in U$ such that $u'$ has at least one neighbor in $C$, and $u$ and $u'$ are not from the same monochromatic part $U_\ell$ (because $u$ is in at most one of $U_i$ and $U_j$). Now, for each $u \in U$ and $u' \in U$ that are in distinct monochromatic parts of $U$, let $N(u, u')$ denote the number of vertex pairs $\{v, v'\}$ such that there is an ambiguous cluster $C$ containing $v$ and $v'$, one of $v$ and $v'$ is adjacent to $u$, and the other is adjacent to $u'$. By the above discussion, any vertex in an ambiguous cluster $C$ with exactly one neighbor in $U$ increases the number $N(u, u')$ for at least one pair of vertices $u$ and $u'$. By pigeonhole principle, if there are more than $3 \cdot \binom{|U|}{2}$ vertices in ambiguous nonedge clusters that have only one neighbor in $U$, then there is some pair of vertices $u$ and $u'$ such that $N(u, u') \ge 3$. Since $u$ and $u'$ each have at most one neighbor in every ambiguous cluster, this means that there are three distinct clusters $C_1, C_2, C_3$ which contain neighbors of $u$ and $u'$. Because $u$ and $u'$ are from distinct monochromatic parts, Reduction Rule 8 applies, which contradicts the fact that $G$ is reduced with respect to this rule. Consequently, the number of vertices in ambiguous nonedge clusters that have only one neighbor in $U$ is $O(|U|^2)$. ◀

**Theorem 4.** MATCHING CUT admits a problem kernel with $O(\text{dc}(G)^2)$ vertices that can be computed in $O(\text{dc}(G)^3 \cdot (n^2 + nm))$ time.

**Proof.** Note that every instance contains $O(\text{dc}(G))$ vertices in $U$ because we may assume that $|U| \le 3\text{dc}(G)$. Furthermore, the number of special vertices is also $O(\text{dc}(G))$ since there is a constant number of them for every monochromatic part. To obtain the kernel, we need to reduce the size of $V \setminus U$. To this end, we first apply exhaustively Rules 1–8. Afterwards, $V \setminus U$ has $O(\text{dc}(G)^2)$ vertices: By Lemma 2, $V \setminus U$ has $O(\text{dc}(G)^2)$ ambiguous vertices. Moreover, since $G$ is reduced with respect to Rule 7, we have that every edge cluster
of Reduction Rule 6, every vertex in cluster $C$, where $|C| \ge 3$ and $C \subseteq N^2(U_i)$ for some $i$, has at most one neighbor in $U_i$.

It remains to bound the number of vertices in $V \setminus U$ with only one neighbor in $U$. First, we find monochromatic parts of $U$ that can be merged not because they have many common neighbors but, instead, because they have common neighbors in several nonedge clusters.

**Reduction Rule 8.** If there are two vertices $u \in U_i$ and $u' \in U_j$, $i \neq j$, and three distinct nonedge clusters $C_1, C_2, C_3$ such that $u$ and $u'$ have at least one neighbor in each of them, then merge $U_i$ and $U_j$.

**Proof of safeness.** We show that $U_i \cup U_j$ is monochromatic; by definition this implies that merging $U_i$ and $U_j$ is safe. Let $(A, B)$ be any matching cut of $G$. Each of the three clusters is monochromatic because they are nonedge clusters. Hence, we can assume without loss of generality, that $A$ contains $C_1$ and $C_2$. Since $u$ has neighbors in $C_1$ and in $C_2$, it has two neighbors in $A$ and thus $U_i \subseteq A$. Similarly, $U_j \subseteq A$. Hence, $U_i \cup U_j$ is in the same part of the cut. This holds for all cuts, making $U_i \cup U_j$ monochromatic. ◀

**Lemma 3.** After exhaustive application of Reduction Rules 1–8, there are $O(|U^2|)$ vertices in $V \setminus U$ that are in nonedge clusters and have only one neighbor in $U$.

**Proof.** First, by Lemma 1, there are $O(|U|)$ fixed nonedge clusters. By Lemma 2, these clusters contain $O(|U|)$ vertices each. Thus, the number of vertices in fixed nonedge clusters that have only one neighbor in $U$ is $O(|U|^2)$.

Hence, it remains to bound the number of vertices that have only one neighbor in $U$ and are contained in a nonfixed cluster $C$. By Proposition 2, these clusters are ambiguous. Each ambiguous cluster $C$ contains an ambiguous vertex with neighbors in $U_i$ and $U_j$, where $i \neq j$. Thus, for each vertex of $C$ with only one neighbor $u \in U$, there is at least one other vertex $u' \in U$ such that $u'$ has at least one neighbor in $C$, and $u$ and $u'$ are not from the same monochromatic part $U_\ell$ (because $u$ is in at most one of $U_i$ and $U_j$). Now, for each $u \in U$ and $u' \in U$ that are in distinct monochromatic parts of $U$, let $N(u, u')$ denote the number of vertex pairs $\{v, v'\}$ such that there is an ambiguous cluster $C$ containing $v$ and $v'$, one of $v$ and $v'$ is adjacent to $u$, and the other is adjacent to $u'$. By the above discussion, any vertex in an ambiguous cluster $C$ with exactly one neighbor in $U$ increases the number $N(u, u')$ for at least one pair of vertices $u$ and $u'$. By pigeonhole principle, if there are more than $3 \cdot \binom{|U|}{2}$ vertices in ambiguous nonedge clusters that have only one neighbor in $U$, then there is some pair of vertices $u$ and $u'$ such that $N(u, u') \ge 3$. Since $u$ and $u'$ each have at most one neighbor in every ambiguous cluster, this means that there are three distinct clusters $C_1, C_2, C_3$ which contain neighbors of $u$ and $u'$. Because $u$ and $u'$ are from distinct monochromatic parts, Reduction Rule 8 applies, which contradicts the fact that $G$ is reduced with respect to this rule. Consequently, the number of vertices in ambiguous nonedge clusters that have only one neighbor in $U$ is $O(|U|^2)$. ◀

**Theorem 4.** MATCHING CUT admits a problem kernel with $O(\mathrm{dc}(G)^2)$ vertices that can be computed in $O(\mathrm{dc}(G)^3 \cdot (n^2 + nm))$ time.

**Proof.** Note that every instance contains $O(\mathrm{dc}(G))$ vertices in $U$ because we may assume that $|U| \le 3\mathrm{dc}(G)$. Furthermore, the number of special vertices is also $O(\mathrm{dc}(G))$ since there is a constant number of them for every monochromatic part. To obtain the kernel, we need to reduce the size of $V \setminus U$. To this end, we first apply exhaustively Rules 1–8. Afterwards, $V \setminus U$ has $O(\mathrm{dc}(G)^2)$ vertices: By Lemma 2, $V \setminus U$ has $O(\mathrm{dc}(G)^2)$ ambiguous vertices. Moreover, since $G$ is reduced with respect to Rule 7, we have that every edge cluster
19:8 Matching Cut

contains an ambiguous vertex. Hence, the number of edge clusters, and therefore the number of vertices in edge clusters, is $O(\mathrm{dc}(G)^2)$. It remains to bound the number of vertices in nonedge clusters that are not ambiguous. Each of these vertices has only one neighbor in $U$ because $G$ is reduced with respect to Reduction Rule 6. By Lemma 3, $V \setminus U$ has $O(\mathrm{dc}(G)^2)$ vertices that are in nonedge clusters and have only one neighbor in $U$.

Finally, the number of vertices that have no neighbors in any set $U_i$ is $O(1)$ for each cluster because $G$ is reduced with respect to Rule 5 and thus $O(\mathrm{dc}(G)^2)$ overall.

It remains to bound the running time for the application of the rules. Rule 1 can be applied in time $O(n+m)$ and applies only once. For the remaining rules, we need to maintain the set $N^2(U_i)$ for each $U_i$. These sets can be computed in $O(\mathrm{dc}(G)(n+m))$ time. Afterwards, the applicability of each rule can be tested in $O(\mathrm{dc}(G)^2(n+m))$ with the bottleneck being Rule 8. Moreover, each rule can be applied in $O(n)$ time, with the exception of Rule 4 which may take $\Theta(n^2)$ time, because it may add $\Theta(n^2)$ many edges. To make this rule more efficient, we can however store the edges in each cluster only implicitly, giving a running time bound of $O(n)$ also for this rule; we omit the details. Thus, to obtain the claimed bound on the running time it is sufficient to bound the number of applications of the rules by $O(\mathrm{dc}(G) \cdot n)$: All rules that merge monochromatic parts can be performed $O(\mathrm{dc}(G))$ times overall. For the remaining rules, we have that Rule 4 can be performed $O(n)$ times, because it decreases the number of clusters in $G-U$ by one, Rules 5 and 7 can be performed $O(n)$ times, because they remove at least one vertex from $G$.

It is worth noting that if $G-U$ consists of only one cluster, i.e., $G-U$ is a clique $C$, Lemma 2 shows that $C$ can be reduced to contain $O(|U|)$ many vertices.

**Corollary 5.** *MATCHING CUT* admits a linear kernel when parameterized by $\mathrm{dq}(G)$, the distance to clique.

3 Single-exponential FPT Algorithms

In this section, we consider MATCHING CUT parameterized by the distance to cluster and by the distance to co-cluster. Recall that co-cluster graphs are precisely the complete multipartite graphs. We show that MATCHING CUT can be solved in time $2^{\mathrm{dc}(G)}O(n^2)$ and in time $2^{\mathrm{dc}(G)}O(nm)$. Recall that we may assume that all graphs considered are connected, have minimum degree at least two and that a clique $Q$ is monochromatic if $|Q| \neq 2$. Finally, observe that minimum distance to cluster sets and minimum distance to co-cluster sets can be computed in $O(1.92^{\mathrm{dc}(G)} \cdot n^2)$ time and $O(1.92^{\mathrm{dc}(G)} \cdot n^2)$ time, respectively [5].

**Distance to Cluster.** Next, we provide an FPT algorithm solving MATCHING CUT running in single-exponential time $2^{\mathrm{dc}(G)}O(n^2)$.

**Lemma 6.** *Let $U \subset V(G)$ such that $F = V(G) \setminus U$ induces a cluster graph. Given a partition $(A, B)$ of $G[U]$, it can be decided in time $O(n^2)$ if $G$ has a matching cut $(X, Y)$ such that $A \subseteq X$ and $B \subseteq Y$.*

**Proof.** We first consider the case $A$ or $B$ is empty, say $B = \emptyset$. Thus, $A = U$ and we are searching for a matching cut $(X, Y)$ such that $U \subseteq X$. If $G[F]$ has some connected component $Q$ such that $(Q, V(G) \setminus Q)$ is a matching cut, then we are done. Otherwise, consider some matching cut $(X, Y)$ such that $U \subseteq X$. For each connected component $Q$ of $G[F]$ we have $Q \subseteq X$ or $Q \subseteq Y$: This is obviously true for the connected components of size at least three and for those of size one because they are monochromatic in $G$. For each
19:8 Matching Cut

contains an ambiguous vertex. Hence, the number of edge clusters, and therefore the number of vertices in edge clusters, is $O(\mathrm{dc}(G)^2)$. It remains to bound the number of vertices in nonedge clusters that are not ambiguous. Each of these vertices has only one neighbor in $U$ because $G$ is reduced with respect to Reduction Rule 6. By Lemma 3, $V \setminus U$ has $O(\mathrm{dc}(G)^2)$ vertices that are in nonedge clusters and have only one neighbor in $U$.

Finally, the number of vertices that have no neighbors in any set $U_i$ is $O(1)$ for each cluster because $G$ is reduced with respect to Rule 5 and thus $O(\mathrm{dc}(G)^2)$ overall.

It remains to bound the running time for the application of the rules. Rule 1 can be applied in time $O(n+m)$ and applies only once. For the remaining rules, we need to maintain the set $N^2(U_i)$ for each $U_i$. These sets can be computed in $O(\mathrm{dc}(G)(n+m))$ time. Afterwards, the applicability of each rule can be tested in $O(\mathrm{dc}(G)^2(n+m))$ with the bottleneck being Rule 8. Moreover, each rule can be applied in $O(n)$ time, with the exception of Rule 4 which may take $\Theta(n^2)$ time, because it may add $\Theta(n^2)$ many edges. To make this rule more efficient, we can however store the edges in each cluster only implicitly, giving a running time bound of $O(n)$ also for this rule; we omit the details. Thus, to obtain the claimed bound on the running time it is sufficient to bound the number of applications of the rules by $O(\mathrm{dc}(G) \cdot n)$: All rules that merge monochromatic parts can be performed $O(\mathrm{dc}(G))$ times overall. For the remaining rules, we have that Rule 4 can be performed $O(n)$ times, because it decreases the number of clusters in $G-U$ by one, Rules 5 and 7 can be performed $O(n)$ times, because they remove at least one vertex from $G$.

It is worth noting that if $G-U$ consists of only one cluster, i.e., $G-U$ is a clique $C$, Lemma 2 shows that $C$ can be reduced to contain $O(|U|)$ many vertices.

**Corollary 5.** *MATCHING CUT* admits a linear kernel when parameterized by $\mathrm{dq}(G)$, the distance to clique.

3 Single-exponential FPT Algorithms

In this section, we consider MATCHING CUT parameterized by the distance to cluster and by the distance to co-cluster. Recall that co-cluster graphs are precisely the complete multipartite graphs. We show that MATCHING CUT can be solved in time $2^{\mathrm{dc}(G)}O(n^2)$ and in time $2^{\mathrm{dc}(G)}O(nm)$. Recall that we may assume that all graphs considered are connected, have minimum degree at least two and that a clique $Q$ is monochromatic if $|Q| \neq 2$. Finally, observe that minimum distance to cluster sets and minimum distance to co-cluster sets can be computed in $O(1.92^{\mathrm{dc}(G)} \cdot n^2)$ time and $O(1.92^{\mathrm{dc}(G)} \cdot n^2)$ time, respectively [5].

**Distance to Cluster.** Next, we provide an FPT algorithm solving MATCHING CUT running in single-exponential time $2^{\mathrm{dc}(G)}O(n^2)$.

**Lemma 6.** *Let $U \subset V(G)$ such that $F = V(G) \setminus U$ induces a cluster graph. Given a partition $(A, B)$ of $G[U]$, it can be decided in time $O(n^2)$ if $G$ has a matching cut $(X, Y)$ such that $A \subseteq X$ and $B \subseteq Y$.*

**Proof.** We first consider the case $A$ or $B$ is empty, say $B = \emptyset$. Thus, $A = U$ and we are searching for a matching cut $(X, Y)$ such that $U \subseteq X$. If $G[F]$ has some connected component $Q$ such that $(Q, V(G) \setminus Q)$ is a matching cut, then we are done. Otherwise, consider some matching cut $(X, Y)$ such that $U \subseteq X$. For each connected component $Q$ of $G[F]$ we have $Q \subseteq X$ or $Q \subseteq Y$: This is obviously true for the connected components of size at least three and for those of size one because they are monochromatic in $G$. For each
connected component $\{u, v\}$ of size two observe the following. Since $(V(G) \setminus \{u, v\}, \{u, v\})$ is not a matching cut, either

- $u$ and $v$ have a common neighbor in $U$, or

- $|N(u) \cap U| \ge 2$ or $|N(v) \cap U| \ge 2$.

In the first case, $\{u, v\}$ is monochromatic, in the second case $u$ and $v$ are in the same part of the cut as $U$, and thus we have $\{u, v\} \subseteq X$. Summarizing, $U \subseteq X$ and for each connected component $Q$ of $G[F]$ we have $Q \subseteq X$ or $Q \subseteq Y$. Since there is no matching cut between $U$ and a connected component $Q$ of $G[F]$, this implies $Q \subseteq X$. Hence, $F \cup U \subseteq X$ and thus $Y = \emptyset$. Therefore, $G$ has no matching cut $(X, Y)$ such that $U \subseteq X$.

Now assume that $A$ and $B$ are nonempty. Then the algorithm first applies Reduction Rules (R1) – (R4) given in [14]; the correctness of these rules is easy to see.

(R1) If an $A$-vertex has two $B$-neighbors, or a $B$-vertex has two $A$-neighbors then STOP: "$G$ has no matching cut separating $A, B$".

(R2) If $v \in F$, $|N(v) \cap A| \ge 2$ and $|N(v) \cap B| \ge 2$ then STOP: "$G$ has no matching cut separating $A, B$".

If $v \in F$ and $|N(v) \cap A| \ge 2$ then $A := A \cup \{v\}$.

If $v \in F$ and $|N(v) \cap B| \ge 2$ then $B := B \cup \{v\}$.

(R3) If $v \in A$ has two adjacent $F$-neighbors $w_1, w_2$ then $A := A \cup \{w_1, w_2\}$.

If $v \in B$ has two adjacent $F$-neighbors $w_3, w_4$ then $B := B \cup \{w_3, w_4\}$.

(R4) If there is an edge $xy$ in $G$ such that $x \in A$ and $y \in B$ and $N(x) \cap N(y) \cap F \ne \emptyset$ then STOP: "$G$ has no matching cut separating $A, B$".

If there is an edge $xy$ in $G$ such that $x \in A$ and $y \in B$ then add $N(x) \cap F$ to $A$, and add $N(y) \cap F$ to $B$.

If none of these reduction rules can be applied then

- the $A, B$-edges of $G$ form a matching cut in $G[A \cup B] = G - F$ due to (R1),

- every $F$-vertex is adjacent to at most one $A$- and at most one $B$-vertex due to (R2),

- the $F$-neighbors of any $A$-vertex and the $F$-neighbors of any $B$-vertex form an independent set due to (R3), and

- every $A$-vertex adjacent to a $B$-vertex has no $F$-neighbor and every $B$-vertex adjacent to an $A$-vertex has no $F$-neighbor.

Clearly these properties hold for the instance $(G, A, B)$ if none of the Rules (R1) – (R4) can be applied. Note that $G[F]$ is a cluster graph. Let $Q$ be the set of all monochromatic connected components in $G[F]$ and let $R := F \cup \bigcup_{Q \in Q} V(Q)$. That is, each member in $Q$ is a trivial clique or a clique with at least three vertices, and each vertex in $R$ belongs to a 2-vertex connected component in $G[F]$. Now, create a boolean formula $\phi$ as follows:

- For each $Q \in Q$ we have two boolean variables $Q_A$ and $Q_B$ (indicating all vertices of $Q$ should be added to $A$, respectively, to $B$).

- For each vertex $u \in R$ we have two boolean variables $u_A, u_B$ (indicating $u$ should be added to $A$, respectively, to $B$).

The clauses of $\phi$ are as follows:

(c1) For each $Q \in Q$: $(Q_A \lor Q_B), (\neg Q_A \lor \neg Q_B)$. These clauses ensure that $Q$ will be moved to $A$ or else to $B$.

(c2) For each vertex $u \in R$: $(u_A \lor u_B), (\neg u_A \lor \neg u_B)$. These clauses ensure that $u$ will be moved to $A$ or else to $B$.

(c3) For each two adjacent vertices $u, v \in R$:
connected component $\{u, v\}$ of size two observe the following. Since $(V(G) \setminus \{u, v\}, \{u, v\})$ is not a matching cut, either

- $u$ and $v$ have a common neighbor in $U$, or

- $|N(u) \cap U| \ge 2$ or $|N(v) \cap U| \ge 2$.

In the first case, $\{u, v\}$ is monochromatic, in the second case $u$ and $v$ are in the same part of the cut as $U$, and thus we have $\{u, v\} \subseteq X$. Summarizing, $U \subseteq X$ and for each connected component $Q$ of $G[F]$ we have $Q \subseteq X$ or $Q \subseteq Y$. Since there is no matching cut between $U$ and a connected component $Q$ of $G[F]$, this implies $Q \subseteq X$. Hence, $F \cup U \subseteq X$ and thus $Y = \emptyset$. Therefore, $G$ has no matching cut $(X, Y)$ such that $U \subseteq X$.

Now assume that $A$ and $B$ are nonempty. Then the algorithm first applies Reduction Rules (R1) – (R4) given in [14]; the correctness of these rules is easy to see.

(R1) If an $A$-vertex has two $B$-neighbors, or a $B$-vertex has two $A$-neighbors then STOP: "$G$ has no matching cut separating $A, B$".

(R2) If $v \in F$, $|N(v) \cap A| \ge 2$ and $|N(v) \cap B| \ge 2$ then STOP: "$G$ has no matching cut separating $A, B$".

If $v \in F$ and $|N(v) \cap A| \ge 2$ then $A := A \cup \{v\}$.

If $v \in F$ and $|N(v) \cap B| \ge 2$ then $B := B \cup \{v\}$.

(R3) If $v \in A$ has two adjacent $F$-neighbors $w_1, w_2$ then $A := A \cup \{w_1, w_2\}$.

If $v \in B$ has two adjacent $F$-neighbors $w_3, w_4$ then $B := B \cup \{w_3, w_4\}$.

(R4) If there is an edge $xy$ in $G$ such that $x \in A$ and $y \in B$ and $N(x) \cap N(y) \cap F \ne \emptyset$ then STOP: "$G$ has no matching cut separating $A, B$".

If there is an edge $xy$ in $G$ such that $x \in A$ and $y \in B$ then add $N(x) \cap F$ to $A$, and add $N(y) \cap F$ to $B$.

If none of these reduction rules can be applied then

- the $A, B$-edges of $G$ form a matching cut in $G[A \cup B] = G - F$ due to (R1),

- every $F$-vertex is adjacent to at most one $A$- and at most one $B$-vertex due to (R2),

- the $F$-neighbors of any $A$-vertex and the $F$-neighbors of any $B$-vertex form an independent set due to (R3), and

- every $A$-vertex adjacent to a $B$-vertex has no $F$-neighbor and every $B$-vertex adjacent to an $A$-vertex has no $F$-neighbor.

Clearly these properties hold for the instance $(G, A, B)$ if none of the Rules (R1) – (R4) can be applied. Note that $G[F]$ is a cluster graph. Let $Q$ be the set of all monochromatic connected components in $G[F]$ and let $R := F \cup \bigcup_{Q \in Q} V(Q)$. That is, each member in $Q$ is a trivial clique or a clique with at least three vertices, and each vertex in $R$ belongs to a 2-vertex connected component in $G[F]$. Now, create a boolean formula $\phi$ as follows:

- For each $Q \in Q$ we have two boolean variables $Q_A$ and $Q_B$ (indicating all vertices of $Q$ should be added to $A$, respectively, to $B$).

- For each vertex $u \in R$ we have two boolean variables $u_A, u_B$ (indicating $u$ should be added to $A$, respectively, to $B$).

The clauses of $\phi$ are as follows:

(c1) For each $Q \in Q$: $(Q_A \lor Q_B), (\neg Q_A \lor \neg Q_B)$. These clauses ensure that $Q$ will be moved to $A$ or else to $B$.

(c2) For each vertex $u \in R$: $(u_A \lor u_B), (\neg u_A \lor \neg u_B)$. These clauses ensure that $u$ will be moved to $A$ or else to $B$.

(c3) For each two adjacent vertices $u, v \in R$:
(c3.1) If $u$ has neighbors in $A$ and $B$, if $v$ has neighbors in $A$ and $B$, if $u$ and $v$ have neighbors in $A$, or if $u$ and $v$ have neighbors in $B$: $(u_A \leftrightarrow v_A)$, $(u_B \leftrightarrow v_B)$. These clauses ensure that either both $u$ and $v$ must be moved to $A$, or both must be moved to $B$.

(c3.2) If $|N(u) \cap A| = |N(v) \cap B| = 1$ and $N(u) \cap B = N(v) \cap A = \emptyset$: ($\neg u_B \lor \neg v_A$). This clause ensures that in case $u$ goes to $B$, $v$ must also go to $B$, and in case $v$ goes to $A$, $u$ must also go to $A$.

(c3.3) If $|N(u) \cap B| = |N(v) \cap A| = 1$ and $N(u) \cap A = N(v) \cap B = \emptyset$: ($\neg u_A \lor \neg v_B$). This clause ensures that in case $u$ goes to $A$, $v$ must also go to $A$, and in case $v$ goes to $B$, $u$ must also go to $B$.

(c4) For $z, z' \in Q \cup R$:

(c4.1) If $z, z'$ have a common neighbor in $A$: ($\neg z_B \lor \neg z'_B$). This clause ensures that in this case, $z$ or $z'$ must go to $A$.

(c4.2) If $z, z'$ have a common neighbor in $B$: ($\neg z_A \lor \neg z'_A$). This clause ensures that in this case, $z$ or $z'$ must go to $B$.

Then $\phi$ is the conjunction of all these clauses over all $Q \in \mathcal{Q}$ and all $u \in R$.

**Proposition 3.** *G has a matching cut (X, Y) with $A \subseteq X$ and $B \subseteq Y$ if and only if $\phi$ is satisfiable.*

The proof of Proposition 3 is deferred to the full version of this work.

Obviously, the length of the formula $\phi$ is $O(n^2)$. Since 2-Sat can be solved in linear time (cf. [3, 9, 10]), the above discussion yields an $O(n^2)$-time algorithm for deciding if $G$ has a matching cut $(X, Y)$ such that $A \subseteq X$ and $B \subseteq Y$. ◀

Running the algorithm of Lemma 6 for all partitions $(A, B)$ of $G[U]$, where $U$ is a minimum distance to cluster set of the input graph $G$, one obtains

**Theorem 7.** *MATCHING CUT can be solved in time $2^{dc(G)}O(n^2)$.*

**Distance to Co-cluster.** We now provide an FPT algorithm solving MATCHING CUT running in single-exponential time $2^{dc(G)}O(nm)$.

**Lemma 8.** *Let $U \subset V(G)$ such that $F = V(G) \setminus U$ induces a co-cluster graph. Given a partition $(A, B)$ of $G[U]$, it can be decided in time $O(nm)$ if $G$ has a matching cut $(X, Y)$ such that $A \subseteq X$ and $B \subseteq Y$.*

The proof of Lemma 8 is deferred to the full version of this work.

Running the algorithm of Lemma 8 for all partitions $(A, B)$ of $G[U]$, where $U$ is a minimum distance to co-cluster set of the input graph $G$, one obtains

**Theorem 9.** *MATCHING CUT can be solved in time $2^{dc(G)}O(nm)$.*

# 4 An Improved Exact Exponential Algorithm

Our algorithm takes as input a graph $G = (V, E)$ and decides whether or not there is an edge set $M \subseteq E$ such that $M$ is a matching cut of $G$. As above, we may assume that $G$ is connected and has minimum degree at least two. The idea is to compute a partition of the vertex set into subsets $A$ and $B$ such that $A$ and $B$ are nonempty unions of components of $G-M$ and all $M$-edges have one endvertex in $A$ and the other in $B$. Our algorithm consists of reduction rules and branching rules that label the vertices of the input graph by either $A$
(c3.1) If $u$ has neighbors in $A$ and $B$, if $v$ has neighbors in $A$ and $B$, if $u$ and $v$ have neighbors in $A$, or if $u$ and $v$ have neighbors in $B$: $(u_A \leftrightarrow v_A)$, $(u_B \leftrightarrow v_B)$. These clauses ensure that either both $u$ and $v$ must be moved to $A$, or both must be moved to $B$.

(c3.2) If $|N(u) \cap A| = |N(v) \cap B| = 1$ and $N(u) \cap B = N(v) \cap A = \emptyset$: ($\neg u_B \lor \neg v_A$). This clause ensures that in case $u$ goes to $B$, $v$ must also go to $B$, and in case $v$ goes to $A$, $u$ must also go to $A$.

(c3.3) If $|N(u) \cap B| = |N(v) \cap A| = 1$ and $N(u) \cap A = N(v) \cap B = \emptyset$: ($\neg u_A \lor \neg v_B$). This clause ensures that in case $u$ goes to $A$, $v$ must also go to $A$, and in case $v$ goes to $B$, $u$ must also go to $B$.

(c4) For $z, z' \in Q \cup R$:

(c4.1) If $z, z'$ have a common neighbor in $A$: ($\neg z_B \lor \neg z'_B$). This clause ensures that in this case, $z$ or $z'$ must go to $A$.

(c4.2) If $z, z'$ have a common neighbor in $B$: ($\neg z_A \lor \neg z'_A$). This clause ensures that in this case, $z$ or $z'$ must go to $B$.

Then $\phi$ is the conjunction of all these clauses over all $Q \in \mathcal{Q}$ and all $u \in R$.

**Proposition 3.** *G has a matching cut (X, Y) with $A \subseteq X$ and $B \subseteq Y$ if and only if $\phi$ is satisfiable.*

The proof of Proposition 3 is deferred to the full version of this work.

Obviously, the length of the formula $\phi$ is $O(n^2)$. Since 2-Sat can be solved in linear time (cf. [3, 9, 10]), the above discussion yields an $O(n^2)$-time algorithm for deciding if $G$ has a matching cut $(X, Y)$ such that $A \subseteq X$ and $B \subseteq Y$. ◀

Running the algorithm of Lemma 6 for all partitions $(A, B)$ of $G[U]$, where $U$ is a minimum distance to cluster set of the input graph $G$, one obtains

**Theorem 7.** *MATCHING CUT can be solved in time $2^{dc(G)}O(n^2)$.*

**Distance to Co-cluster.** We now provide an FPT algorithm solving MATCHING CUT running in single-exponential time $2^{dc(G)}O(nm)$.

**Lemma 8.** *Let $U \subset V(G)$ such that $F = V(G) \setminus U$ induces a co-cluster graph. Given a partition $(A, B)$ of $G[U]$, it can be decided in time $O(nm)$ if $G$ has a matching cut $(X, Y)$ such that $A \subseteq X$ and $B \subseteq Y$.*

The proof of Lemma 8 is deferred to the full version of this work.

Running the algorithm of Lemma 8 for all partitions $(A, B)$ of $G[U]$, where $U$ is a minimum distance to co-cluster set of the input graph $G$, one obtains

**Theorem 9.** *MATCHING CUT can be solved in time $2^{dc(G)}O(nm)$.*

# 4 An Improved Exact Exponential Algorithm

Our algorithm takes as input a graph $G = (V, E)$ and decides whether or not there is an edge set $M \subseteq E$ such that $M$ is a matching cut of $G$. As above, we may assume that $G$ is connected and has minimum degree at least two. The idea is to compute a partition of the vertex set into subsets $A$ and $B$ such that $A$ and $B$ are nonempty unions of components of $G-M$ and all $M$-edges have one endvertex in $A$ and the other in $B$. Our algorithm consists of reduction rules and branching rules that label the vertices of the input graph by either $A$
or *B* but never change the graph *G*. Finally we provide a termination lemma stating that if neither a reduction rule nor a branching rule can be applied then there is a matching cut in the graph *G*, respecting the current partial partition into *A* and *B*.

The branching algorithm below will be executed for all possible pairs $a, b \in V$, hence $O(n^2)$ times. To do this set $A := \{a\}$, $B := \{b\}$, and $F := V \setminus \{a, b\}$ and call the branching algorithm. At each stage of the algorithm, *A* and/or *B* will be extended or it will be determined that there is no matching cut that separates *A* from *B*.

We describe our algorithm by a list of reduction and branching rules given in preference order, i.e., in an execution of the algorithm on any instance of a subproblem one always applies the first rule applicable to the instance, which could be a reduction or a branching rule. A reduction rule produces one instance/subproblem while a branching rule results in at least two instances/subproblems, with different extensions of *A* and *B*. Note that *G* has a matching cut that separates *A* from *B* if and only if in at least one recursive branch, extensions *A'* of *A* and *B'* of *B* are obtained such that *G* has a matching cut that separates *A'* from *B'*. Typically a rule assigns one or more free vertices, vertices of *F*, either to *A* or to *B* and removes them from *F*, that is, we always have $F := V \setminus (A \cup B)$.

First our algorithm applies Reduction Rules (R1) – (R4) mentioned in Section 3 to the current instance (in the order of the rules). In addition, we need two new reduction rules.

(R5) If there are vertices $u, v \in F$ such that $N(u) = N(v) = \{x, y\}$ with $x \in A, y \in B$, then $A := A \cup \{u\}, B := B \cup \{v\}$.

► **Proposition 4.** *Reduction Rule (R5) is safe: G has a matching cut separating A and B if and only if G has a matching cut separating A ∪ {u} and B ∪ {v}.*

The proof of Proposition 4 is deferred to the full version of this work.

(R6) If there are vertices $u, v \in F$ such that $N(u) = N(v) = \{x, y\}$ with $x \in A, y \in F$ then
$A := A \cup \{u\}$.

If there are vertices $u, v \in F$ such that $N(u) = N(v) = \{x, y\}$ with $x \in F, y \in B$ then
$B := B \cup \{v\}$.

► **Proposition 5.** *Reduction Rule (R6) is safe:*

(i) Let $x \in A$ and $y \in F$. Then *G* has a matching cut separating *A* and *B* if and only if *G* has a matching cut separating *A* $\cup$ $\{u\}$ and *B*.

(ii) Let $x \in F$ and $y \in B$. Then *G* has a matching cut separating *A* and *B* if and only if *G* has a matching cut separating *A* and *B* $\cup$ $\{v\}$.

The proof of Proposition 5 is deferred to the full version of this work.

Our algorithm consists of six branching rules dealing with small configurations (connected subgraphs with at most eight vertices some of them may already belong to *A* or *B*.) See Fig. 2. The Branching Rules (B1) and (B2) are new, the last four have been used in [14]. Moreover, compared to [14] we do a better branching on configuration (B5).

To determine the branching vectors which correspond to our branching rules, we set the size of an instance (*G*, *A*, *B*) as its number of free vertices, i.e., |*V*(*G*)| − |*A*| − |*B*|.

(B1) We branch into two subproblems. First, add $v_1$ to *B*. Then $v_2$ has to be added to *B* and $v_3$ has to be added to *A*. Second, add $v_1$ to *A*. Then $v_2$ has to be added to *A* too. Hence the branching vector is (3, 2).

(B2) We branch into two subproblems. First, add $v_2$ to *B*. Then $v_1$ has to be added to *A* and $v_3$ has to be added to *B*. Second, add $v_2$ to *A*. Then $v_3$ has to be added to *A* too. Hence the branching vector is (3, 2).
or *B* but never change the graph *G*. Finally we provide a termination lemma stating that if neither a reduction rule nor a branching rule can be applied then there is a matching cut in the graph *G*, respecting the current partial partition into *A* and *B*.

The branching algorithm below will be executed for all possible pairs $a, b \in V$, hence $O(n^2)$ times. To do this set $A := \{a\}$, $B := \{b\}$, and $F := V \setminus \{a, b\}$ and call the branching algorithm. At each stage of the algorithm, *A* and/or *B* will be extended or it will be determined that there is no matching cut that separates *A* from *B*.

We describe our algorithm by a list of reduction and branching rules given in preference order, i.e., in an execution of the algorithm on any instance of a subproblem one always applies the first rule applicable to the instance, which could be a reduction or a branching rule. A reduction rule produces one instance/subproblem while a branching rule results in at least two instances/subproblems, with different extensions of *A* and *B*. Note that *G* has a matching cut that separates *A* from *B* if and only if in at least one recursive branch, extensions *A'* of *A* and *B'* of *B* are obtained such that *G* has a matching cut that separates *A'* from *B'*. Typically a rule assigns one or more free vertices, vertices of *F*, either to *A* or to *B* and removes them from *F*, that is, we always have $F := V \setminus (A \cup B)$.

First our algorithm applies Reduction Rules (R1) – (R4) mentioned in Section 3 to the current instance (in the order of the rules). In addition, we need two new reduction rules.

(R5) If there are vertices $u, v \in F$ such that $N(u) = N(v) = \{x, y\}$ with $x \in A, y \in B$, then $A := A \cup \{u\}, B := B \cup \{v\}$.

**► Proposition 4.** *Reduction Rule (R5) is safe: G has a matching cut separating A and B if and only if G has a matching cut separating A $\cup$ $\{u\}$ and B $\cup$ $\{v\}$.*

The proof of Proposition 4 is deferred to the full version of this work.

(R6) If there are vertices $u, v \in F$ such that $N(u) = N(v) = \{x, y\}$ with $x \in A, y \in F$ then $A := A \cup \{u\}$.

If there are vertices $u, v \in F$ such that $N(u) = N(v) = \{x, y\}$ with $x \in F, y \in B$ then $B := B \cup \{v\}$.

**► Proposition 5.** *Reduction Rule (R6) is safe:*

(i) Let $x \in A$ and $y \in F$. Then *G* has a matching cut separating *A* and *B* if and only if *G* has a matching cut separating *A* $\cup$ $\{u\}$ and *B*.

(ii) Let $x \in F$ and $y \in B$. Then *G* has a matching cut separating *A* and *B* if and only if *G* has a matching cut separating *A* and *B* $\cup \{v\}$.

The proof of Proposition 5 is deferred to the full version of this work.

Our algorithm consists of six branching rules dealing with small configurations (connected subgraphs with at most eight vertices some of them may already belong to *A* or *B*.) See Fig. 2. The Branching Rules (B1) and (B2) are new, the last four have been used in [14]. Moreover, compared to [14] we do a better branching on configuration (B5).

To determine the branching vectors which correspond to our branching rules, we set the size of an instance (*G*, *A*, *B*) as its number of free vertices, i.e., |*V*(*G*)| − |*A*| − |*B*|.

(B1) We branch into two subproblems. First, add $v_1$ to *B*. Then $v_2$ has to be added to *B* and $v_3$ has to be added to *A*. Second, add $v_1$ to *A*. Then $v_2$ has to be added to *A* too. Hence the branching vector is (3, 2).

(B2) We branch into two subproblems. First, add $v_2$ to *B*. Then $v_1$ has to be added to *A* and $v_3$ has to be added to *B*. Second, add $v_2$ to *A*. Then $v_3$ has to be added to *A* too. Hence the branching vector is (3, 2).
<figure><img src="image_104.png" /><figcaption>Figure 2 Branching configurations: Vertices with label A and B belong to A, respectively, to B; vertices with labels $v_i$ are in F.</figcaption></figure>

(B3) First, add $v_2$ to B. This implies that $v_1$ has to be added to A, and that $v_3$ and $v_4$ have to be added to B. Second, add $v_2$ to A. Hence the branching vector is (4, 1).

(B4) On this configuration we branch into two subproblems, similar to (B3). First, add $v_3$ to A. This implies that $v_4$ has to be added to B, and that $v_1$ and $v_2$ have to be added to A. Second, add $v_3$ to B. Hence the branching vector is (4, 1).

(B5) We branch into two subproblems. First, add $v_2$ to A. This implies that $v_3$ has to be added to B and then $v_4$ has to be added to A. Second, add $v_2$ to B. Then $v_1$ must be added to A. Hence the branching vector is (3, 2).

(B6) We branch into four subproblems. First, add $v_5$ to A. This implies that $v_2$ and $v_3$ have to be added to A. Next, add $v_5$ to B. There are three choices to label $v_2$ and $v_3$: AB, BA, BB. In the first two choices, $v_6$ has to be added to B and $v_1$ or $v_4$ has to be added to A. In the last choice, $v_1$ and $v_4$ have to be added to A. Hence the branching vector is (3, 5, 5, 5).

The branching numbers of the branching vectors of our algorithm are 1.3803 (B3, B4), 1.3734 (B6) and 1.3248 (B1, B2, B5). Consequently, the running time of our algorithm is $O^*(1.3803^n)$.

It remains to show that if none of the reduction and branching rules is applicable to $(G, A, B)$ then $G$ has a matching cut $(X, Y)$ with $A \subseteq X$ and $B \subseteq Y$. The proof of this fact is deferred to the full version of this work. In summary, we obtain the following result.

**▶ Theorem 10.** MATCHING CUT can be solved in time $O^*(1.3803^n)$.

## 5 Conclusions

We provided three algorithms for MATCHING CUT: an exact exponential algorithm of running time $O^*(1.3803^n)$, a fixed-parameter algorithm of running time $2^{dc(G)}O(n^2)$ where $dc(G)$ is the distance to cluster number, and a fixed-parameter algorithm of running time $2^{d\bar{c}(G)}O(nm)$ where $d\bar{c}(G)$ is the distance to co-cluster number. Our results improved the $O^*(1.4143^n)$ time exact algorithm and the $2^{\tau(G)}O(n^2)$ time algorithm previously given in [14], where $\tau(G) \ge \max\{dc(G), d\bar{c}(G)\}$ is the vertex cover number. Moreover, we found a quadratic vertex-kernel for MATCHING CUT for the distance to cluster, and a linear vertex-kernel for the distance to clique.

There are many possible directions for future research. Does MATCHING CUT admit a linear vertex-kernel for the distance to cluster? Even a linear vertex-kernel for the parameter vertex cover number $\tau(G)$ is open. Moreover, it is open whether the problem admits a polynomial kernel for the feedback vertex set number of $G$. Finally, it is natural to ask whether the running time of our $O^*(1.3803^n)$ branching algorithm can be improved.
<figure><img src="image_106.png" /><figcaption>■ **Figure 2** Branching configurations: Vertices with label *A* and *B* belong to *A*, respectively, to *B*; vertices with labels $v_i$ are in *F*.</figcaption></figure>

(B3) First, add $v_2$ to $B$. This implies that $v_1$ has to be added to $A$, and that $v_3$ and $v_4$ have to be added to $B$. Second, add $v_2$ to $A$. Hence the branching vector is (4, 1).

(B4) On this configuration we branch into two subproblems, similar to (B3). First, add $v_3$ to $A$. This implies that $v_4$ has to be added to $B$, and that $v_1$ and $v_2$ have to be added to $A$. Second, add $v_3$ to $B$. Hence the branching vector is (4, 1).

(B5) We branch into two subproblems. First, add $v_2$ to $A$. This implies that $v_3$ has to be added to $B$ and then $v_4$ has to be added to $A$. Second, add $v_2$ to $B$. Then $v_1$ must be added to $A$. Hence the branching vector is (3, 2).

(B6) We branch into four subproblems. First, add $v_5$ to $A$. This implies that $v_2$ and $v_3$ have to be added to $A$. Next, add $v_5$ to $B$. There are three choices to label $v_2$ and $v_3$: AB, BA, BB. In the first two choices, $v_6$ has to be added to $B$ and $v_1$ or $v_4$ has to be added to $A$. In the last choice, $v_1$ and $v_4$ have to be added to $A$. Hence the branching vector is (3, 5, 5, 5).

The branching numbers of the branching vectors of our algorithm are 1.3803 (B3, B4), 1.3734 (B6) and 1.3248 (B1, B2, B5). Consequently, the running time of our algorithm is $O^*(1.3803^n)$.

It remains to show that if none of the reduction and branching rules is applicable to $(G, A, B)$ then $G$ has a matching cut $(X, Y)$ with $A \subseteq X$ and $B \subseteq Y$. The proof of this fact is deferred to the full version of this work. In summary, we obtain the following result.

► **Theorem 10.** MATCHING CUT can be solved in time $O^*(1.3803^n)$.

## 5 Conclusions

We provided three algorithms for MATCHING CUT: an exact exponential algorithm of running time $O^*(1.3803^n)$, a fixed-parameter algorithm of running time $2^{dc(G)}O(n^2)$ where $dc(G)$ is the distance to cluster number, and a fixed-parameter algorithm of running time $2^{d\bar{c}(G)}O(nm)$ where $d\bar{c}(G)$ is the distance to co-cluster number. Our results improved the $O^*(1.4143^n)$ time exact algorithm and the $2^{\tau(G)}O(n^2)$ time algorithm previously given in [14], where $\tau(G) \ge \max\{dc(G), d\bar{c}(G)\}$ is the vertex cover number. Moreover, we found a quadratic vertex-kernel for MATCHING CUT for the distance to cluster, and a linear vertex-kernel for the distance to clique.

There are many possible directions for future research. Does MATCHING CUT admit a linear vertex-kernel for the distance to cluster? Even a linear vertex-kernel for the parameter vertex cover number $\tau(G)$ is open. Moreover, it is open whether the problem admits a polynomial kernel for the feedback vertex set number of $G$. Finally, it is natural to ask whether the running time of our $O^*(1.3803^n)$ branching algorithm can be improved.
References

1 Júlio Araújo, Nathann Cohen, Frédéric Giroire, and Frédéric Havet. Good edge-labelling of graphs. *Discr. Appl. Math.*, 160(18):2502–2513, 2012.

2 N. R. Aravind, Subrahmanyam Kalyanasundaram, and Anjeneya Swami Kare. On Structural Parameterizations of the Matching Cut Problem. In *Proceedings of the 11th International Conference on Combinatorial Optimization and Applications (COCOA '17)*, volume 10628 of LNCS, pages 475–482. Springer, 2017.

3 Bengt Aspvall, Michael F. Plass, and Robert Endre Tarjan. A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean Formulas. *Inf. Process. Lett.*, 8(3):121–123, 1979.

4 Paul S. Bonsma. The complexity of the matching-cut problem for planar graphs and other graph classes. *J. Graph Theory*, 62(2):109–126, 2009.

5 Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, and Marcin Pilipczuk. A Fast Branching Algorithm for Cluster Vertex Deletion. *Theory Comput. Syst.*, 58(2):357–376, 2016.

6 Mieczysław Borowiecki and Katarzyna Jesse-Józefczyk. Matching cutsets in graphs of diameter 2. *Theor. Comput. Sci.*, 407(1-3):574–582, 2008.

7 Vasek Chvátal. Recognizing decomposable graphs. *J. Graph Theory*, 8(1):51–53, 1984.

8 Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. *Parameterized Algorithms*. Springer, 2015.

9 Martin Davis and Hilary Putnam. A Computing Procedure for Quantification Theory. *J. ACM*, 7(3):201–215, 1960.

10 Shimon Even, Alon Itai, and Adi Shamir. On the Complexity of Timetable and Multicommodity Flow Problems. *SIAM J. Comput.*, 5(4):691–703, 1976.

11 Arthur M. Farley and Andrzej Proskurowski. Networks immune to isolated line failures. *Networks*, 12(4):393–403, 1982.

12 Fedor V. Fomin and Dieter Kratsch. *Exact Exponential Algorithms*. Springer, 2010.

13 Ron L. Graham. On primitive graphs and optimal vertex assignments. *Ann. N. Y. Acad. Sci.*, 175(1):170–186, 1970.

14 Dieter Kratsch and Van Bang Le. Algorithms solving the Matching Cut problem. *Theor. Comput. Sci.*, 609:328–335, 2016.

15 Hoàng-Oanh Le and Van Bang Le. On the Complexity of Matching Cut in Graphs of Fixed Diameter. In *Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC '16)*, volume 64 of LIPIcs, pages 50:1–50:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016.

16 Van Bang Le and Bert Randerath. On stable cutsets in line graphs. *Theor. Comput. Sci.*, 301(1-3):463–475, 2003.

17 Augustine M. Moshi. Matching cutsets in graphs. *J. Graph Theory*, 13(5):527–536, 1989.

18 Maurizio Patrignani and Maurizio Pizzonia. The Complexity of the Matching-Cut Problem. In *Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '01)*, volume 2204 of LNCS, pages 284–295. Springer, 2001.
References

1 Júlio Araújo, Nathann Cohen, Frédéric Giroire, and Frédéric Havet. Good edge-labelling of graphs. *Discr. Appl. Math.*, 160(18):2502–2513, 2012.

2 N. R. Aravind, Subrahmanyam Kalyanasundaram, and Anjeneya Swami Kare. On Structural Parameterizations of the Matching Cut Problem. In *Proceedings of the 11th International Conference on Combinatorial Optimization and Applications (COCOA '17)*, volume 10628 of LNCS, pages 475–482. Springer, 2017.

3 Bengt Aspvall, Michael F. Plass, and Robert Endre Tarjan. A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean Formulas. *Inf. Process. Lett.*, 8(3):121–123, 1979.

4 Paul S. Bonsma. The complexity of the matching-cut problem for planar graphs and other graph classes. *J. Graph Theory*, 62(2):109–126, 2009.

5 Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, and Marcin Pilipczuk. A Fast Branching Algorithm for Cluster Vertex Deletion. *Theory Comput. Syst.*, 58(2):357–376, 2016.

6 Mieczysław Borowiecki and Katarzyna Jesse-Józefczyk. Matching cutsets in graphs of diameter 2. *Theor. Comput. Sci.*, 407(1-3):574–582, 2008.

7 Vasek Chvátal. Recognizing decomposable graphs. *J. Graph Theory*, 8(1):51–53, 1984.

8 Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. *Parameterized Algorithms*. Springer, 2015.

9 Martin Davis and Hilary Putnam. A Computing Procedure for Quantification Theory. *J. ACM*, 7(3):201–215, 1960.

10 Shimon Even, Alon Itai, and Adi Shamir. On the Complexity of Timetable and Multicommodity Flow Problems. *SIAM J. Comput.*, 5(4):691–703, 1976.

11 Arthur M. Farley and Andrzej Proskurowski. Networks immune to isolated line failures. *Networks*, 12(4):393–403, 1982.

12 Fedor V. Fomin and Dieter Kratsch. *Exact Exponential Algorithms*. Springer, 2010.

13 Ron L. Graham. On primitive graphs and optimal vertex assignments. *Ann. N. Y. Acad. Sci.*, 175(1):170–186, 1970.

14 Dieter Kratsch and Van Bang Le. Algorithms solving the Matching Cut problem. *Theor. Comput. Sci.*, 609:328–335, 2016.

15 Hoàng-Oanh Le and Van Bang Le. On the Complexity of Matching Cut in Graphs of Fixed Diameter. In *Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC '16)*, volume 64 of LIPIcs, pages 50:1–50:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016.

16 Van Bang Le and Bert Randerath. On stable cutsets in line graphs. *Theor. Comput. Sci.*, 301(1-3):463–475, 2003.

17 Augustine M. Moshi. Matching cutsets in graphs. *J. Graph Theory*, 13(5):527–536, 1989.

18 Maurizio Patrignani and Maurizio Pizzonia. The Complexity of the Matching-Cut Problem. In *Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '01)*, volume 2204 of LNCS, pages 284–295. Springer, 2001.
<figure><img src="image_105.png" /></figure>
<figure><img src="image_107.png" /></figure>
# Subset Feedback Vertex Set on Graphs of Bounded Independent Set Size

Charis Papadopoulos

Department of Mathematics, University of Ioannina, Greece
charis@cs.uoi.gr

Spyridon Tzimas

Department of Mathematics, University of Ioannina, Greece
roytzimas@hotmail.com

## Abstract

The (WEIGHTED) SUBSET FEEDBACK VERTEX SET problem is a generalization of the classical FEEDBACK VERTEX SET problem and asks for a vertex set of minimum (weight) size that intersects all cycles containing a vertex of a predescribed set of vertices. Although the two problems exhibit different computational complexity on split graphs, no similar characterization is known on other classes of graphs. Towards the understanding of the complexity difference between the two problems, it is natural to study the importance of a structural graph parameter. Here we consider graphs of bounded independent set number for which it is known that WEIGHTED FEEDBACK VERTEX SET can be solved in polynomial time. We provide a dichotomy result with respect to the size of a maximum independent set. In particular we show that WEIGHTED SUBSET FEEDBACK VERTEX SET can be solved in polynomial time for graphs of independent set number at most three, whereas we prove that the problem remains NP-hard for graphs of independent set number four. Moreover, we show that the (unweighted) SUBSET FEEDBACK VERTEX SET problem can be solved in polynomial time on graphs of bounded independent set number by giving an algorithm with running time $n^{O(d)}$, where $d$ is the size of a maximum independent set of the input graph. To complement our results, we demonstrate how our ideas can be extended to other terminal set problems on graphs of bounded independent set size. Based on our findings for SUBSET FEEDBACK VERTEX SET, we settle the complexity of NODE MULTIWAY CUT, a terminal set problem that asks for a vertex set of minimum size that intersects all paths connecting any two terminals, as well as its variants where nodes are weighted and/or the terminals are deletable, for every value of the given independent set number.

2012 ACM Subject Classification Mathematics of computing → Graph algorithms

**Keywords and phrases** Subset Feedback Vertex Set, Node Multiway Cut, Terminal Set problem, polynomial-time algorithm, NP-completeness, W[1]-hardness, graphs of bounded independent set size

Digital Object Identifier 10.4230/LIPIcs.IPEC.2018.20

**Related Version** A full version of the paper is available at https://arxiv.org/abs/1805.07141, [32].

**Funding** This research has been financially supported by General Secretariat for Research and Technology (GSRT) and the Hellenic Foundation for Research and Innovation (HFRI) (Scholarship Code: 82220).

<figure><img src="image_106.png" /></figure>

© Charis Papadopoulos and Spyridon Tzimas; licensed under Creative Commons License CC-BY

13th International Symposium on Parameterized and Exact Computation (IPEC 2018).

Editors: Christophe Paul and Michal Pilipczuk; Article No. 20; pp. 20:1–20:14

Leibniz International Proceedings in Informatics

<figure><img src="image_107.png" /></figure>

LIPICS Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
# Subset Feedback Vertex Set on Graphs of Bounded Independent Set Size

Charis Papadopoulos

Department of Mathematics, University of Ioannina, Greece
charis@cs.uoi.gr

Spyridon Tzimas

Department of Mathematics, University of Ioannina, Greece
roytzimas@hotmail.com

## Abstract

The (WEIGHTED) SUBSET FEEDBACK VERTEX SET problem is a generalization of the classical FEEDBACK VERTEX SET problem and asks for a vertex set of minimum (weight) size that intersects all cycles containing a vertex of a predescribed set of vertices. Although the two problems exhibit different computational complexity on split graphs, no similar characterization is known on other classes of graphs. Towards the understanding of the complexity difference between the two problems, it is natural to study the importance of a structural graph parameter. Here we consider graphs of bounded independent set number for which it is known that WEIGHTED FEEDBACK VERTEX SET can be solved in polynomial time. We provide a dichotomy result with respect to the size of a maximum independent set. In particular we show that WEIGHTED SUBSET FEEDBACK VERTEX SET can be solved in polynomial time for graphs of independent set number at most three, whereas we prove that the problem remains NP-hard for graphs of independent set number four. Moreover, we show that the (unweighted) SUBSET FEEDBACK VERTEX SET problem can be solved in polynomial time on graphs of bounded independent set number by giving an algorithm with running time $n^{O(d)}$, where $d$ is the size of a maximum independent set of the input graph. To complement our results, we demonstrate how our ideas can be extended to other terminal set problems on graphs of bounded independent set size. Based on our findings for SUBSET FEEDBACK VERTEX SET, we settle the complexity of NODE MULTIWAY CUT, a terminal set problem that asks for a vertex set of minimum size that intersects all paths connecting any two terminals, as well as its variants where nodes are weighted and/or the terminals are deletable, for every value of the given independent set number.

2012 ACM Subject Classification Mathematics of computing → Graph algorithms

**Keywords and phrases** Subset Feedback Vertex Set, Node Multiway Cut, Terminal Set problem, polynomial-time algorithm, NP-completeness, W[1]-hardness, graphs of bounded independent set size

Digital Object Identifier 10.4230/LIPIcs.IPEC.2018.20

**Related Version** A full version of the paper is available at https://arxiv.org/abs/1805.07141, [32].

**Funding** This research has been financially supported by General Secretariat for Research and Technology (GSRT) and the Hellenic Foundation for Research and Innovation (HFRI) (Scholarship Code: 82220).

<figure><img src="image_108.png" /></figure>

© Charis Papadopoulos and Spyridon Tzimas; licensed under Creative Commons License CC-BY

13th International Symposium on Parameterized and Exact Computation (IPEC 2018).

Editors: Christophe Paul and Michal Pilipczuk; Article No. 20; pp. 20:1–20:14

Leibniz International Proceedings in Informatics

<figure><img src="image_109.png" /></figure>

LIPICS

Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
# 1 Introduction

Given a (vertex-weighted) graph $G = (V, E)$ and a set $S \subseteq V$, the (WEIGHTED) SUBSET FEEDBACK VERTEX SET problem, introduced by Even et al. [13], asks for a vertex set of minimum (weight) size that intersects all cycles containing a vertex of $S$. Cygan et al. [10] and Kawarabayashi and Kobayashi [25] independently showed that SUBSET FEEDBACK VERTEX SET is fixed-parameter tractable (FPT) parameterized by the solution size, while Hols and Kratsch provided a randomized polynomial kernel for the problem [21]. There has been a considerable amount of work to obtain faster, still exponential-time, algorithms even when restricted to particular graph classes [5, 16, 15, 19]. As a generalization of the classical FEEDBACK VERTEX SET for which $S = V$, the problem remains NP-hard on bipartite graphs [36] and planar graphs [17]. On the positive side, WEIGHTED SUBSET FEEDBACK VERTEX SET can be solved in polynomial time on interval graphs, permutation graphs, and cobipartite graphs [31], the latter being a subclass of graphs of independent set size at most two. However a notable difference between the two problems regarding their complexity status is the class of split graphs: FEEDBACK VERTEX SET is known to be polynomial-time solvable on split graphs [7, 34], whereas SUBSET FEEDBACK VERTEX SET remains NP-hard on split graphs [16].

In order to obtain further (in)tractability results for SUBSET FEEDBACK VERTEX SET, it is reasonable to consider structural parameters of graphs that may lend themselves to provide a unified approach. In terms of parameterized complexity FEEDBACK VERTEX SET is known to be FPT, when parameterized by tree-width [8] and clique-width [2] which implies that FEEDBACK VERTEX SET can be solved in polynomial time on graphs of bounded such parameters. Although FEEDBACK VERTEX SET is $W[1]$-hard parameterized by the size of the independent set, it can be solved in polynomial time on graphs of bounded maximum induced matching (i.e., FEEDBACK VERTEX SET belongs in $XP$ parameterized by the size of a maximum induced matching) [24]. Only very recently, Jaffke et al. proposed an algorithm that solves WEIGHTED FEEDBACK VERTEX SET in time $n^{O(w)}$ where $w$ is the maximum induced matching width of the given graph [23]. Despite their relevant name, graphs of bounded maximum induced matching (or graphs of bounded independent set number) are not related to graphs of bounded maximum induced matching width as indicated in [35].

The approach of [23] provides a powerful mechanism, as it unifies polynomial-time algorithms for WEIGHTED FEEDBACK VERTEX SET on several graph classes such as interval graphs, permutation graphs, circular-arc graphs, and Dilworth-$k$ graphs for fixed $k$, among others. Such a mechanism raises the question of whether the algorithm given in [23] can be extended to the more general setting of WEIGHTED SUBSET FEEDBACK VERTEX SET. However the proposed algorithm is based on the crucial fact that the forest of a solution has bounded number of internal nodes which is not necessarily true for the $S$-forest of WEIGHTED SUBSET FEEDBACK VERTEX SET. Thus it seems difficult to control the size of the solution whenever $S \subset V$. As this observation does not rule out any positive answer, here we develop the first step towards such an approach by considering graphs of bounded independent set number which form candidate relevant graphs. Although WEIGHTED FEEDBACK VERTEX SET can be solved in time $n^{O(p)}$ on graphs of maximum induced matching at most $p$ [24], SUBSET FEEDBACK VERTEX SET is already NP-complete on graphs of maximum induced matching equal to one (i.e., split graphs) [16].

In this work we show that the complexity behaviour of the weighted version of the problem is completely different from the behaviour of the unweighted variant on graphs with bounded $\alpha(G)$, where $\alpha(G)$ is the size of a maximum independent set in a graph $G$.
# 1 Introduction

Given a (vertex-weighted) graph $G = (V, E)$ and a set $S \subseteq V$, the (WEIGHTED) SUBSET FEEDBACK VERTEX SET problem, introduced by Even et al. [13], asks for a vertex set of minimum (weight) size that intersects all cycles containing a vertex of $S$. Cygan et al. [10] and Kawarabayashi and Kobayashi [25] independently showed that SUBSET FEEDBACK VERTEX SET is fixed-parameter tractable (FPT) parameterized by the solution size, while Hols and Kratsch provided a randomized polynomial kernel for the problem [21]. There has been a considerable amount of work to obtain faster, still exponential-time, algorithms even when restricted to particular graph classes [5, 16, 15, 19]. As a generalization of the classical FEEDBACK VERTEX SET for which $S = V$, the problem remains NP-hard on bipartite graphs [36] and planar graphs [17]. On the positive side, WEIGHTED SUBSET FEEDBACK VERTEX SET can be solved in polynomial time on interval graphs, permutation graphs, and cobipartite graphs [31], the latter being a subclass of graphs of independent set size at most two. However a notable difference between the two problems regarding their complexity status is the class of split graphs: FEEDBACK VERTEX SET is known to be polynomial-time solvable on split graphs [7, 34], whereas SUBSET FEEDBACK VERTEX SET remains NP-hard on split graphs [16].

In order to obtain further (in)tractability results for SUBSET FEEDBACK VERTEX SET, it is reasonable to consider structural parameters of graphs that may lend themselves to provide a unified approach. In terms of parameterized complexity FEEDBACK VERTEX SET is known to be FPT, when parameterized by tree-width [8] and clique-width [2] which implies that FEEDBACK VERTEX SET can be solved in polynomial time on graphs of bounded such parameters. Although FEEDBACK VERTEX SET is $W[1]$-hard parameterized by the size of the independent set, it can be solved in polynomial time on graphs of bounded maximum induced matching (i.e., FEEDBACK VERTEX SET belongs in $XP$ parameterized by the size of a maximum induced matching) [24]. Only very recently, Jaffke et al. proposed an algorithm that solves WEIGHTED FEEDBACK VERTEX SET in time $n^{O(w)}$ where $w$ is the maximum induced matching width of the given graph [23]. Despite their relevant name, graphs of bounded maximum induced matching (or graphs of bounded independent set number) are not related to graphs of bounded maximum induced matching width as indicated in [35].

The approach of [23] provides a powerful mechanism, as it unifies polynomial-time algorithms for WEIGHTED FEEDBACK VERTEX SET on several graph classes such as interval graphs, permutation graphs, circular-arc graphs, and Dilworth-$k$ graphs for fixed $k$, among others. Such a mechanism raises the question of whether the algorithm given in [23] can be extended to the more general setting of WEIGHTED SUBSET FEEDBACK VERTEX SET. However the proposed algorithm is based on the crucial fact that the forest of a solution has bounded number of internal nodes which is not necessarily true for the $S$-forest of WEIGHTED SUBSET FEEDBACK VERTEX SET. Thus it seems difficult to control the size of the solution whenever $S \subset V$. As this observation does not rule out any positive answer, here we develop the first step towards such an approach by considering graphs of bounded independent set number which form candidate relevant graphs. Although WEIGHTED FEEDBACK VERTEX SET can be solved in time $n^{O(p)}$ on graphs of maximum induced matching at most $p$ [24], SUBSET FEEDBACK VERTEX SET is already NP-complete on graphs of maximum induced matching equal to one (i.e., split graphs) [16].

In this work we show that the complexity behaviour of the weighted version of the problem is completely different from the behaviour of the unweighted variant on graphs with bounded $\alpha(G)$, where $\alpha(G)$ is the size of a maximum independent set in a graph $G$.
- We show that WEIGHTED SUBSET FEEDBACK VERTEX SET can be solved in polynomial time on graphs with $\alpha(G) \le 3$.

Such graphs consist of the complements of triangle-free graphs; recall that for triangle-free graphs FEEDBACK VERTEX SET remains NP-hard [36]. We solve WEIGHTED SUBSET FEEDBACK VERTEX SET on such graphs, by exploiting a structural characterization of the solution with respect to the vertices that are *close* to S.

- We further provide a dichotomy result showing that WEIGHTED SUBSET FEEDBACK VERTEX SET remains NP-complete on graphs with $\alpha(G) = 4$.

Thus we enlarge our knowledge on the complexity difference of the two problems with respect to a structural graph parameter.

- In order to complement our results we show that SUBSET FEEDBACK VERTEX SET can be solved in time $n^{O(d)}$, where $\alpha(G) \le d$.

Our findings concerning SUBSET FEEDBACK VERTEX SET are summarized in Table 1.

Moreover, we demonstrate how our ideas can be extended to other *terminal set* problems on graphs of bounded independent set size. In the (unweighted) NODE MULTIWAY CUT problem, we are given a graph $G = (V, E)$, a terminal set $T \subseteq V$, and a nonnegative integer $k$ and the goal is to find a set $X \subseteq V \setminus T$ of size at most $k$ such that any path between two different terminals intersects $X$. NODE MULTIWAY CUT is known to be in FPT parameterized by the solution size [4, 29] and even above guaranteed value [9]. For further results on variants of NODE MULTIWAY CUT we refer to [3, 18, 27]. We completely characterize the complexity of NODE MULTIWAY CUT with respect to the size of the maximum independent set.

- In particular, we show that for $\alpha(G) \le 2$ NODE MULTIWAY CUT can be solved in polynomial time, whereas for $\alpha(G) = 3$ it remains NP-complete by adopting the reduction for WEIGHTED SUBSET FEEDBACK VERTEX SET with $\alpha(G) = 4$.

We further consider a relaxed variation of NODE MULTIWAY CUT in which we are allowed to remove terminal vertices, called NODE MULTIWAY CUT WITH DELETABLE TERMINALS (also known as UNRESTRICTED NODE MULTIWAY CUT).

- We show that the (unweighted) NODE MULTIWAY CUT WITH DELETABLE TERMINALS problem can be solved in polynomial time on graphs of bounded independent set number, using an idea similar to the polynomial-time algorithm for the SUBSET FEEDBACK VERTEX SET problem.

- Regarding its node-weighted variation, we provide a complexity dichotomy result showing that WEIGHTED NODE MULTIWAY CUT WITH DELETABLE TERMINALS can be solved in polynomial time on graphs with $\alpha(G) \le 2$, whereas it becomes NP-complete on graphs with $\alpha(G) = 3$.

We note that the polynomial-time algorithm for the weighted variation is obtained by invoking our algorithm for WEIGHTED SUBSET FEEDBACK VERTEX SET on graphs with $\alpha(G) \le 3$.

## 2 Preliminaries

We refer to [1, 11, 20] for our standard graph terminology. For $X \subseteq V$, $N_G(X) = \bigcup_{v \in X} N_G(v) \setminus X$ and $N_G[X] = N_G(X) \cup X$. A *weighted graph* $G = (V, E)$ is a graph, where each vertex $v \in V$ is assigned a *weight* that is a positive integer number. We denote by $w(v)$ the weight of each vertex $v \in V$. For a vertex set $A \subset V$, the weight of $A$, denoted by $w(A)$, is $\sum_{v \in A} w(v)$.

Given a graph $G$, the *independent set number*, denoted by $\alpha(G)$, is the size of the maximum independent set in $G$. In terms of forbidden subgraph characterization, note that $\alpha(G) \le d$ if and only if $G$ does not contain $(d+1)K_1$ as an induced subgraph. We say that
- We show that WEIGHTED SUBSET FEEDBACK VERTEX SET can be solved in polynomial time on graphs with $\alpha(G) \le 3$.

Such graphs consist of the complements of triangle-free graphs; recall that for triangle-free graphs FEEDBACK VERTEX SET remains NP-hard [36]. We solve WEIGHTED SUBSET FEEDBACK VERTEX SET on such graphs, by exploiting a structural characterization of the solution with respect to the vertices that are close to S.

- We further provide a dichotomy result showing that WEIGHTED SUBSET FEEDBACK VERTEX SET remains NP-complete on graphs with $\alpha(G) = 4$.

Thus we enlarge our knowledge on the complexity difference of the two problems with respect to a structural graph parameter.

- In order to complement our results we show that SUBSET FEEDBACK VERTEX SET can be solved in time $n^{O(d)}$, where $\alpha(G) \le d$.

Our findings concerning SUBSET FEEDBACK VERTEX SET are summarized in Table 1.

Moreover, we demonstrate how our ideas can be extended to other terminal set problems on graphs of bounded independent set size. In the (unweighted) NODE MULTIWAY CUT problem, we are given a graph $G = (V, E)$, a terminal set $T \subseteq V$, and a nonnegative integer $k$ and the goal is to find a set $X \subseteq V \setminus T$ of size at most $k$ such that any path between two different terminals intersects $X$. NODE MULTIWAY CUT is known to be in FPT parameterized by the solution size [4, 29] and even above guaranteed value [9]. For further results on variants of NODE MULTIWAY CUT we refer to [3, 18, 27]. We completely characterize the complexity of NODE MULTIWAY CUT with respect to the size of the maximum independent set.

- In particular, we show that for $\alpha(G) \le 2$ NODE MULTIWAY CUT can be solved in polynomial time, whereas for $\alpha(G) = 3$ it remains NP-complete by adopting the reduction for WEIGHTED SUBSET FEEDBACK VERTEX SET with $\alpha(G) = 4$.

We further consider a relaxed variation of NODE MULTIWAY CUT in which we are allowed to remove terminal vertices, called NODE MULTIWAY CUT WITH DELETABLE TERMINALS (also known as UNRESTRICTED NODE MULTIWAY CUT).

- We show that the (unweighted) NODE MULTIWAY CUT WITH DELETABLE TERMINALS problem can be solved in polynomial time on graphs of bounded independent set number, using an idea similar to the polynomial-time algorithm for the SUBSET FEEDBACK VERTEX SET problem.

- Regarding its node-weighted variation, we provide a complexity dichotomy result showing that WEIGHTED NODE MULTIWAY CUT WITH DELETABLE TERMINALS can be solved in polynomial time on graphs with $\alpha(G) \le 2$, whereas it becomes NP-complete on graphs with $\alpha(G) = 3$.

We note that the polynomial-time algorithm for the weighted variation is obtained by invoking our algorithm for WEIGHTED SUBSET FEEDBACK VERTEX SET on graphs with $\alpha(G) \le 3$.

## 2 Preliminaries

We refer to [1, 11, 20] for our standard graph terminology. For $X \subseteq V$, $N_G(X) = \bigcup_{v \in X} N_G(v) \setminus X$ and $N_G[X] = N_G(X) \cup X$. A weighted graph $G = (V, E)$ is a graph, where each vertex $v \in V$ is assigned a weight that is a positive integer number. We denote by $w(v)$ the weight of each vertex $v \in V$. For a vertex set $A \subset V$, the weight of $A$, denoted by $w(A)$, is $\sum_{v \in A} w(v)$.

Given a graph $G$, the *independent set number*, denoted by $\alpha(G)$, is the size of the maximum independent set in $G$. In terms of forbidden subgraph characterization, note that $\alpha(G) \le d$ if and only if $G$ does not contain $(d+1)K_1$ as an induced subgraph. We say that
<table><caption>**Table 1** Computational complexity results for FEEDBACK VERTEX SET (FVS) and SUBSET FEEDBACK VERTEX SET (SFVS) on graphs of bounded independent set number and graphs of bounded maximum induced matching. Note that every graph of independent set number *d* has maximum induced matching of size at most *d*, while the converse is not necessarily true.</caption><thead><tr><th colspan="3">Bounded Structural Parameter</th></tr><tr><th></th><th>Max. Independent Set (d)</th><th>Max. Induced Matching (p)</th></tr></thead><tbody><tr><th>Weighted FVS</th><td colspan="2">n<sup>O(p)</sup> [24]</td></tr><tr><th>Weighted SFVS</th><td>d &le; 3 &nbsp;&nbsp;&nbsp;&nbsp; n<sup>O(1)</sup> &nbsp;&nbsp;&nbsp;&nbsp; Theorem 6<br/>d = 4 &nbsp;&nbsp;&nbsp;&nbsp; NP-complete &nbsp;&nbsp;&nbsp;&nbsp; Theorem 7</td><td></td></tr><tr><th>Unweighted SFVS</th><td>n<sup>O(d)</sup> &nbsp;&nbsp;&nbsp;&nbsp; Theorem 8</td><td>NP-complete [16]</td></tr></tbody></table>

a graph *G* has *bounded independent set size* if there exists a positive integer *d* such that $\alpha(G) \le d$. The *clique cover number* of *G*, denoted by $\kappa(G)$, is the smallest number of cliques needed to partition $V(G)$ into $S_1, \dots, S_k$ such that $G[S_i]$ is a clique. A *vertex cover* is a set of vertices such that every edge of *G* is incident to at least one vertex of the set. A *matching* is a set of edges having no common endpoint. An *induced matching*, denoted by $pK_2$, is a matching *M* of *p* edges such that $G[V(M)]$ is isomorphic to $pK_2$. The *maximum induced matching* number, denoted by $p(G)$, is the largest number of edges in any induced matching of *G*. It is not difficult to see that for any graph *G*, $\kappa(G) \ge \alpha(G) \ge p(G)$ holds.

The (WEIGHTED) SUBSET FEEDBACK VERTEX SET (SFVS) problem asks for a given (vertex-weighted) graph $G = (V, E)$, a set $S \subseteq V$, and an integer $k$, whether there exists a set $X$ with $|X| \le k$ ($w(X) \le k$) such that no cycle in $G - X$ contains a vertex of *S*. As remarked, we distinguish between the weighted and the unweighted version of the problem. In the unweighted version of the problem note that all weights are equal and positive. The classical FEEDBACK VERTEX SET (FVS) problem is a special case of SUBSET FEEDBACK VERTEX SET with $S = V$. A vertex of *S* is simply called *S-vertex*. An induced cycle of *G* is called *S-cycle* if an *S-vertex* is contained in the cycle. We define an *S-forest* $F = (V_F, E_F)$ to be the subgraph of *G* induced by the vertex set $V_F \subseteq V$ for which no cycle in $G[V_F]$ is an *S-cycle*. It is not difficult to see that the problem of computing a minimum weighted subset feedback vertex set is equivalent to the problem of computing a maximum weighted *S-forest*.

Let us give a couple of observations on the nature of SUBSET FEEDBACK VERTEX SET on graphs of bounded independent set size. Let *G* be a graph and let *d* be a positive integer such that every independent set of *G* has at most *d* vertices. Firstly note that the bounded-size independent set is a hereditary property, meaning that for every induced subgraph *H* of *G*, we have $\alpha(H) \le d$. Moreover for any clique *C* of *G*, any *S-forest* of *G* contains at most two vertices of $S \cap C$.

► **Observation 1.** Let *G* be a graph with $\alpha(G) \le d$ and let $S \subseteq V$.

(1) For any set $X$ of $2d + 1$ vertices, there is a cycle in $G[X]$.

(2) Any *S-forest* of *G* has at most $2d$ vertices from *S*.

We note that Observation 1 directly implies that any $2d + 1$ vertices of $G[S]$ induce an *S-cycle*, which allows us to construct by brute force all possible subsets of *S* belonging to any *S-forest* in time $n^{O(d)}$.
<table><caption>Table 1 Computational complexity results for FEEDBACK VERTEX SET (FVS) and SUBSET FEEDBACK VERTEX SET (SFVS) on graphs of bounded independent set number and graphs of bounded maximum induced matching. Note that every graph of independent set number *d* has maximum induced matching of size at most *d*, while the converse is not necessarily true.</caption><thead><tr><th colspan="3">Bounded Structural Parameter</th></tr><tr><th></th><th>Max. Independent Set (d)</th><th>Max. Induced Matching (p)</th></tr></thead><tbody><tr><th>Weighted FVS</th><td colspan="2" style="text-align: center;">n<sup>O(p)</sup> [24]</td></tr><tr><th>Weighted SFVS</th><td>d &le; 3 &nbsp;&nbsp;&nbsp;&nbsp; n<sup>O(1)</sup> &nbsp;&nbsp;&nbsp;&nbsp; Theorem 6<br/>d = 4 &nbsp;&nbsp;&nbsp;&nbsp; NP-complete &nbsp;&nbsp;&nbsp;&nbsp; Theorem 7</td><td></td></tr><tr><th>Unweighted SFVS</th><td>n<sup>O(d)</sup> &nbsp;&nbsp;&nbsp;&nbsp; Theorem 8</td><td>NP-complete [16]</td></tr></tbody></table>

a graph $G$ has *bounded independent set size* if there exists a positive integer $d$ such that $\alpha(G) \le d$. The *clique cover number* of $G$, denoted by $\kappa(G)$, is the smallest number of cliques needed to partition $V(G)$ into $S_1, \dots, S_k$ such that $G[S_i]$ is a clique. A *vertex cover* is a set of vertices such that every edge of $G$ is incident to at least one vertex of the set. A *matching* is a set of edges having no common endpoint. An *induced matching*, denoted by $pK_2$, is a matching $M$ of $p$ edges such that $G[V(M)]$ is isomorphic to $pK_2$. The *maximum induced matching* number, denoted by $p(G)$, is the largest number of edges in any induced matching of $G$. It is not difficult to see that for any graph $G$, $\kappa(G) \ge \alpha(G) \ge p(G)$ holds.

The (WEIGHTED) SUBSET FEEDBACK VERTEX SET (SFVS) problem asks for a given (vertex-weighted) graph $G = (V, E)$, a set $S \subseteq V$, and an integer $k$, whether there exists a set $X$ with $|X| \le k$ ($w(X) \le k$) such that no cycle in $G - X$ contains a vertex of $S$. As remarked, we distinguish between the weighted and the unweighted version of the problem. In the unweighted version of the problem note that all weights are equal and positive. The classical FEEDBACK VERTEX SET (FVS) problem is a special case of SUBSET FEEDBACK VERTEX SET with $S = V$. A vertex of $S$ is simply called *S-vertex*. An induced cycle of $G$ is called *S-cycle* if an *S-vertex* is contained in the cycle. We define an *S-forest* $F = (V_F, E_F)$ to be the subgraph of $G$ induced by the vertex set $V_F \subseteq V$ for which no cycle in $G[V_F]$ is an *S-cycle*. It is not difficult to see that the problem of computing a minimum weighted subset feedback vertex set is equivalent to the problem of computing a maximum weighted *S-forest*.

Let us give a couple of observations on the nature of SUBSET FEEDBACK VERTEX SET on graphs of bounded independent set size. Let $G$ be a graph and let $d$ be a positive integer such that every independent set of $G$ has at most $d$ vertices. Firstly note that the bounded-size independent set is a hereditary property, meaning that for every induced subgraph $H$ of $G$, we have $\alpha(H) \le d$. Moreover for any clique $C$ of $G$, any *S-forest* of $G$ contains at most two vertices of $S \cap C$.

► **Observation 1.** Let $G$ be a graph with $\alpha(G) \le d$ and let $S \subseteq V$.

(1) For any set $X$ of $2d + 1$ vertices, there is a cycle in $G[X]$.

(2) Any *S-forest* of $G$ has at most $2d$ vertices from $S$.

We note that Observation 1 directly implies that any $2d + 1$ vertices of $G[S]$ induce an *S-cycle*, which allows us to construct by brute force all possible subsets of $S$ belonging to any *S-forest* in time $n^{O(d)}$.
<figure><img src="image_108.png" /><figcaption>Figure 1 Illustrating an *S*-distance partition ($F_{\le 1}, F_{>1}$) of an *S*-forest *F* with $S = \{s_1, s_2, s_3\}$ that shows the connected components $C_1, C_2, C_3$ of $F_{>1}$. The edges inside $F_{>1}$ are not drawn in order to highlight that the cut satisfies the given tuple $(A_1, A_2, A_3)$.</figcaption></figure>

### 3 Weighted SFVS on Graphs of Bounded Independent Set

Here we consider the WEIGHTED SUBSET FEEDBACK VERTEX SET and we show a dichotomy result with respect to the size of the maximum independent set. We first provide a polynomial-time algorithm on graphs of independent set size at most three and then we show that WEIGHTED SUBSET FEEDBACK VERTEX SET is NP-complete on graphs of independent set size equal to four.

Let $(G, S, k)$ be an instance of WEIGHTED SUBSET FEEDBACK VERTEX SET for which $G$ is a graph of independent set size at most $d$. In the forthcoming arguments, instead of directly computing a solution for WEIGHTED SUBSET FEEDBACK VERTEX SET, we consider the equivalent problem of computing an *S*-forest of $G$ having weight at least $w(V) - k$.

Let $F = (V_F, E_F)$ be an induced subgraph of $G$. Recall that an *S*-forest is an induced subgraph of $G$. We partition the graph $F$ into two induced subgraphs $F_{\le 1}$ and $F_{>1}$ as follows:

- $F_{\le 1}$ is the subgraph of $F$ induced by the vertices of $N[S \cap V_F]$; the vertices of $F_{\le 1}$ are at distance at most one from $S \cap V_F$ and are denoted by $S_{\le 1}$.

- $F_{>1}$ is the graph $F - S_{\le 1}$ and contains vertices that are at distance at least two from $S \cap V_F$.

Such a partition is called the *S*-distance partition of $F$, denoted by $(F_{\le 1}, F_{>1})$. The set of edges of $F$ having one endpoint in $F_{\le 1}$ and the other in $F_{>1}$ are called the *cut* with respect to $F_{\le 1}$ and $F_{>1}$. Notice that a vertex of $F_{\le 1}$ that is adjacent to a vertex of $F_{>1}$ belongs to $S_{\le 1} \setminus S$.

Let $\{C_1, \dots, C_{d'}\}$ be the partition of the vertices of $F_{>1}$ such that each $C_i$, $1 \le i \le d'$, induces a connected component in $F_{>1}$. Because $F_{>1}$ is an induced subgraph of $G$, it is clear that $d' \le d$. Let $(A_1, \dots, A_{d'})$ be a tuple of $d'$ subsets of $S_{\le 1} \setminus S$, i.e., each $A_i \subseteq (S_{\le 1} \setminus S)$ holds. We say that the cut satisfies the tuple $(A_1, \dots, A_{d'})$ if for any vertex $v \in C_i$, we have $(N_G(v) \cap S_{\le 1}) \subseteq A_i$. The notion of an *S*-distance partition of $F$ with the corresponding cut is illustrated in Figure 1.

We now utilize the *S*-distance partition of $F$ in order to construct an algorithm that solves WEIGHTED SUBSET FEEDBACK VERTEX SET on graphs of independent set size at most $d$ and subsequently show that this algorithm is efficient for $d \le 3$. Our general approach relies on the following facts:

- By Observation 1 (2) we try all subsets $S'$ of $S$ with at most $2d$ vertices and keep those sets that induce a forest. This step is used in constructing the graph $F_{\le 1}$. In particular,
<figure><img src="image_110.png" /><figcaption>Figure 1 Illustrating an *S*-distance partition ($F_{\le 1}, F_{>1}$) of an *S*-forest *F* with $S = \{s_1, s_2, s_3\}$ that shows the connected components $C_1, C_2, C_3$ of $F_{>1}$. The edges inside $F_{>1}$ are not drawn in order to highlight that the cut satisfies the given tuple $(A_1, A_2, A_3)$.</figcaption></figure>

3 Weighted SFVS on Graphs of Bounded Independent Set

Here we consider the WEIGHTED SUBSET FEEDBACK VERTEX SET and we show a dichotomy
result with respect to the size of the maximum independent set. We first provide a polynomial-
time algorithm on graphs of independent set size at most three and then we show that
WEIGHTED SUBSET FEEDBACK VERTEX SET is NP-complete on graphs of independent set
size equal to four.

Let $(G, S, k)$ be an instance of WEIGHTED SUBSET FEEDBACK VERTEX SET for which $G$ is a graph of independent set size at most $d$. In the forthcoming arguments, instead of directly computing a solution for WEIGHTED SUBSET FEEDBACK VERTEX SET, we consider the equivalent problem of computing an $S$-forest of $G$ having weight at least $w(V) - k$.

Let $F = (V_F, E_F)$ be an induced subgraph of $G$. Recall that an $S$-forest is an induced subgraph of $G$. We partition the graph $F$ into two induced subgraphs $F_{\le 1}$ and $F_{>1}$ as follows:

- $F_{\le 1}$ is the subgraph of $F$ induced by the vertices of $N[S \cap V_F]$; the vertices of $F_{\le 1}$ are at distance at most one from $S \cap V_F$ and are denoted by $S_{\le 1}$.

- $F_{>1}$ is the graph $F - S_{\le 1}$ and contains vertices that are at distance at least two from $S \cap V_F$.

Such a partition is called the *S-distance partition of* *F*, denoted by (*F*<sub>≤1</sub>, *F*<sub>>1</sub>). The set of edges of *F* having one endpoint in *F*<sub>≤1</sub> and the other in *F*<sub>>1</sub> are called *the cut* with respect to *F*<sub>≤1</sub> and *F*<sub>>1</sub>. Notice that a vertex of *F*<sub>≤1</sub> that is adjacent to a vertex of *F*<sub>>1</sub> belongs to *S*<sub>≤1</sub> \ *S*.

Let {$C_1, \dots, C_{d'}$} be the partition of the vertices of $F_{>1}$ such that each $C_i$, $1 \le i \le d'$, induces a connected component in $F_{>1}$. Because $F_{>1}$ is an induced subgraph of $G$, it is clear that $d' \le d$. Let $(A_1, \dots, A_{d'})$ be a tuple of $d'$ subsets of $S_{\le 1} \setminus S$, i.e., each $A_i \subseteq (S_{\le 1} \setminus S)$ holds. We say that *the cut satisfies* the tuple $(A_1, \dots, A_{d'})$ if for any vertex $v \in C_i$, we have $(N_G(v) \cap S_{\le 1}) \subseteq A_i$. The notion of an *S*-distance partition of *F* with the corresponding cut is illustrated in Figure 1.

We now utilize the *S*-distance partition of *F* in order to construct an algorithm that solves WEIGHTED SUBSET FEEDBACK VERTEX SET on graphs of independent set size at most *d* and subsequently show that this algorithm is efficient for *d* ≤ 3. Our general approach relies on the following facts:

- By Observation 1 (2) we try all subsets $S'$ of $S$ with at most $2d$ vertices and keep those sets that induce a forest. This step is used in constructing the graph $F_{\le 1}$. In particular,
for each such set $S'$, we construct all $F_{\le 1}$ such that $S \cap V(F_{\le 1}) = S'$. We will show that the number of such subsets produced is bounded by $n^{O(d)}$.

- For each of the potential subsets $S'$ constructed in the previous step, and for each $d' \le d$, we determine all possible tuples $(A_1, \dots, A_{d'})$ in $F_{\le 1}$ with $A_i \subseteq (N[S'] \setminus S)$ that are satisfied by cuts of $S$-distance partitions. We show why considering only these tuples is sufficient in Lemma 2.

- Up to that point we can show that all steps can be executed in polynomial time regardless of $d \le 3$. However for the next and final step we can only achieve polynomial running time if we restrict ourselves to $d \le 3$ due to the number of connected components of $F_{>1}$. For each tuple computed in the previous step, we find connected components $C_1, \dots, C_{d'}$ of maximum weight such that the cut of $(G[S'], G[C_1 \cup \dots \cup C_{d'}])$ satisfies the tuple. For doing so, we take advantage of the small number of connected components ($d' < 3$) and an efficient way of computing a vertex-cut between such components.

We begin by showing that the $S$-distance partition of $F$ provides a useful tool towards computing a maximum $S$-forest. Given a set of vertices $X \subseteq N[S]$ and $d'$ subsets $A_i$ of $X \setminus S$, we construct the graph $\hat{G}$ that is obtained from $G[X]$ by adding $d'$ vertices $w_1, \dots, w_{d'}$ such that every vertex $w_i$ is adjacent to all the vertices of $A_i$. In what follows, we always assume that $G$ is a graph having independent set size at most $d$.

**Lemma 2.** Let $F$ be an $S$-forest of $G$ with $S$-distance partition $(F_{\le 1}, F_{>1})$ such that $S_{\le 1} \cap S \ne \emptyset$. Then for $d' \le d$, there is a tuple $(A_1, \dots, A_{d'})$ with $A_i \subseteq (S_{\le 1} \setminus S)$ such that
(i) the cut of $(F_{\le 1}, F_{>1})$ satisfies $(A_1, \dots, A_{d'})$ and
(ii) every induced subgraph $H$ of $G$ with $S$-distance partition $(H[S_{\le 1}], H-S_{\le 1})$ that satisfies $(A_1, \dots, A_{d'})$ is an $S$-forest.

**Proof.** Let $\{C_1, \dots, C_{d'}\}$ be the partition of the vertices of $F_{>1}$ such that every $C_i$ induces a connected component in $F_{>1}$. We define a tuple $(A_1, \dots, A_{d'})$ in which every $A_i = N(C_i) \cap S_{\le 1}$, for $1 \le i \le d'$. Clearly $A_i \subseteq (S_{\le 1} \setminus S)$ since every vertex $F_{>1}$ is at distance at least two from $S_{\le 1} \cap S$. Thus, by construction, the cut of $(F_{\le 1}, F_{>1})$ satisfies the tuple $(A_1, \dots, A_{d'})$.

For the next claim, we first show that $\hat{G}$ with respect to $S_{\le 1}$ and the tuple $(A_1, \dots, A_{d'})$ is an $S$-forest. Assume for contradiction that there is an $S$-cycle $\hat{C}$ in $\hat{G}$. Since $F_{\le 1}$ does not contain any $S$-cycle, $\hat{C}$ contains a vertex $w_i$ and at least two vertices $u_i, v_i$ from $A_i$, $1 \le i \le d'$. By the fact that $A_i = N(C_i) \cap S_{\le 1}$, there is a vertex $x$ in $C_i$ of $F_{>1}$ that is adjacent to $u_i$ and there is a vertex $y$ in $C_i$ of $F_{>1}$ that is adjacent to $v_i$. Together with a path between $x$ and $y$ in the connected component $C_i$, we construct a path in $G$ with endvertices $u_i$ and $v_i$ that is completely contained in $C_i$. This means that if we replace every vertex $w_i$ of $\hat{C}$ by a path with internal vertices of $C_i$ then we obtain an $S$-cycle in $F$, leading to a contradiction. Thus, $\hat{G}$ is an $S$-forest.

Let $H$ be an induced subgraph of $G$ with $S$-distance partition $(H[S_{\le 1}], H - S_{\le 1})$ that satisfies $(A_1, \dots, A_{d'})$. Observe that $H[S_{\le 1}] = F_{\le 1}$ as they are induced subgraphs of the same vertex set of $G$. Thus $H[S_{\le 1}]$ does not contain any $S$-cycle, because $F$ is an $S$-forest. Since the cut of $(H[S_{\le 1}], H - S_{\le 1})$ satisfies $(A_1, \dots, A_{d'})$, there is a partition $\{T_1, \dots, T_{d'}\}$ in $H - S_{\le 1}$ such that $T_i$ is a connected component of $H - S_{\le 1}$ and $N(T_i) \subseteq A_i$, for $1 \le i \le d'$. We show that $H$ is indeed an $S$-forest. For contradiction, assume an $S$-cycle $C$ in $H$. There are no $S$-cycles in $H[S_{\le 1}]$ which implies that $C \cap T_i \ne \emptyset$ for some $1 \le i \le d'$. For every such set we replace the part $C \cap T_i$ by a vertex $w'_i$. Denote by $H'$ the resulting graph. Notice that $H'[C]$ is a subgraph of $\hat{G}[C]$ because $N_{H'}(w'_i) \subseteq N_{\hat{G}}(w_i)$. This, however, implies an $S$-cycle in $\hat{G}$ which gives the desired contradiction. Therefore, $H$ is an $S$-forest. $\quad$
for each such set $S'$, we construct all $F_{\le 1}$ such that $S \cap V(F_{\le 1}) = S'$. We will show that the number of such subsets produced is bounded by $n^{O(d)}$.

- For each of the potential subsets $S'$ constructed in the previous step, and for each $d' \le d$, we determine all possible tuples $(A_1, \dots, A_{d'})$ in $F_{\le 1}$ with $A_i \subseteq (N[S'] \setminus S)$ that are satisfied by cuts of $S$-distance partitions. We show why considering only these tuples is sufficient in Lemma 2.

- Up to that point we can show that all steps can be executed in polynomial time regardless of $d \le 3$. However for the next and final step we can only achieve polynomial running time if we restrict ourselves to $d \le 3$ due to the number of connected components of $F_{>1}$. For each tuple computed in the previous step, we find connected components $C_1, \dots, C_{d'}$ of maximum weight such that the cut of $(G[S'], G[C_1 \cup \dots \cup C_{d'}])$ satisfies the tuple. For doing so, we take advantage of the small number of connected components ($d' < 3$) and an efficient way of computing a vertex-cut between such components.

We begin by showing that the $S$-distance partition of $F$ provides a useful tool towards computing a maximum $S$-forest. Given a set of vertices $X \subseteq N[S]$ and $d'$ subsets $A_i$ of $X \setminus S$, we construct the graph $\hat{G}$ that is obtained from $G[X]$ by adding $d'$ vertices $w_1, \dots, w_{d'}$ such that every vertex $w_i$ is adjacent to all the vertices of $A_i$. In what follows, we always assume that $G$ is a graph having independent set size at most $d$.

**Lemma 2.** Let $F$ be an $S$-forest of $G$ with $S$-distance partition $(F_{\le 1}, F_{>1})$ such that $S_{\le 1} \cap S \ne \emptyset$. Then for $d' \le d$, there is a tuple $(A_1, \dots, A_{d'})$ with $A_i \subseteq (S_{\le 1} \setminus S)$ such that
(i) the cut of $(F_{\le 1}, F_{>1})$ satisfies $(A_1, \dots, A_{d'})$ and
(ii) every induced subgraph $H$ of $G$ with $S$-distance partition $(H[S_{\le 1}], H-S_{\le 1})$ that satisfies $(A_1, \dots, A_{d'})$ is an $S$-forest.

**Proof.** Let $\{C_1, \dots, C_{d'}\}$ be the partition of the vertices of $F_{>1}$ such that every $C_i$ induces a connected component in $F_{>1}$. We define a tuple $(A_1, \dots, A_{d'})$ in which every $A_i = N(C_i) \cap S_{\le 1}$, for $1 \le i \le d'$. Clearly $A_i \subseteq (S_{\le 1} \setminus S)$ since every vertex $F_{>1}$ is at distance at least two from $S_{\le 1} \cap S$. Thus, by construction, the cut of $(F_{\le 1}, F_{>1})$ satisfies the tuple $(A_1, \dots, A_{d'})$.

For the next claim, we first show that $\hat{G}$ with respect to $S_{\le 1}$ and the tuple $(A_1, \dots, A_{d'})$ is an $S$-forest. Assume for contradiction that there is an $S$-cycle $\hat{C}$ in $\hat{G}$. Since $F_{\le 1}$ does not contain any $S$-cycle, $\hat{C}$ contains a vertex $w_i$ and at least two vertices $u_i, v_i$ from $A_i$, $1 \le i \le d'$. By the fact that $A_i = N(C_i) \cap S_{\le 1}$, there is a vertex $x$ in $C_i$ of $F_{>1}$ that is adjacent to $u_i$ and there is a vertex $y$ in $C_i$ of $F_{>1}$ that is adjacent to $v_i$. Together with a path between $x$ and $y$ in the connected component $C_i$, we construct a path in $G$ with endvertices $u_i$ and $v_i$ that is completely contained in $C_i$. This means that if we replace every vertex $w_i$ of $\hat{C}$ by a path with internal vertices of $C_i$ then we obtain an $S$-cycle in $F$, leading to a contradiction. Thus, $\hat{G}$ is an $S$-forest.

Let $H$ be an induced subgraph of $G$ with $S$-distance partition $(H[S_{\le 1}], H - S_{\le 1})$ that satisfies $(A_1, \dots, A_{d'})$. Observe that $H[S_{\le 1}] = F_{\le 1}$ as they are induced subgraphs of the same vertex set of $G$. Thus $H[S_{\le 1}]$ does not contain any $S$-cycle, because $F$ is an $S$-forest. Since the cut of $(H[S_{\le 1}], H - S_{\le 1})$ satisfies $(A_1, \dots, A_{d'})$, there is a partition $\{T_1, \dots, T_{d'}\}$ in $H - S_{\le 1}$ such that $T_i$ is a connected component of $H - S_{\le 1}$ and $N(T_i) \subseteq A_i$, for $1 \le i \le d'$. We show that $H$ is indeed an $S$-forest. For contradiction, assume an $S$-cycle $C$ in $H$. There are no $S$-cycles in $H[S_{\le 1}]$ which implies that $C \cap T_i \ne \emptyset$ for some $1 \le i \le d'$. For every such set we replace the part $C \cap T_i$ by a vertex $w'_i$. Denote by $H'$ the resulting graph. Notice that $H'[C]$ is a subgraph of $\hat{G}[C]$ because $N_{H'}(w'_i) \subseteq N_{\hat{G}}(w_i)$. This, however, implies an $S$-cycle in $\hat{G}$ which gives the desired contradiction. Therefore, $H$ is an $S$-forest. $\quad$
Notice that $G-S$ is trivially an $S$-forest of $G$. Thus, if $F$ is an $S$-forest of $G$ such that $S_{\le 1} \cap S = \emptyset$ then $F$ does not contain any vertex of $S$ and $F = G-S$. Next, we assume that $S_{\le 1} \cap S \ne \emptyset$ and show how to bound the vertex set $S_{\le 1}$ of $F_{\le 1}$.

**Lemma 3.** Let $F$ be an $S$-forest of $G$ with $S$-distance partition $(F_{\le 1}, F_{>1})$ such that $S_{\le 1} \cap S \ne \emptyset$.

1. If $|S_{\le 1} \cap S| \le 2d-2$ then $|S_{\le 1}| \le 4d-2$.

2. If $|S_{\le 1} \cap S| \ge 2d-1$ then $|S_{\le 1}| \le 2d$.

**Proof.** Let $F$ be such an $S$-forest of $G$ with $|S_{\le 1} \cap S| \ge 1$. By Observation 1 (2), we know that $|S_{\le 1} \cap S| \le 2d$. To ease the presentation, we let $S' = S_{\le 1} \setminus S$. We consider separately the two cases of the claim.

**Case 1.** Let $1 \le |S_{\le 1} \cap S| \le 2d-2$. Assume for contradiction that $|S'| > 4d - |S_{\le 1} \cap S| - 2$. We show that $F[S']$ contains a matching with at least $d$ edges. Observe that $|S'| + |S_{\le 1} \cap S| > 4d - 2$. Applying Observation 1 (1) shows that there is a cycle $C$ in $F[S_{\le 1}]$. Since $F$ is an $S$-forest, this is not an $S$-cycle, so all vertices contained in $C$ are vertices of $S'$. Iteratively removing the two endpoints of an edge from $C$, as long as $|S'| + |S_{\le 1} \cap S| > 2d$, constructs $d$ edges of $S'$ having no common endpoints by Observation 1 (1). Thus, $F[S']$ contains a matching $M$ with at least $d$ edges.

Let $C_1, \dots, C_d'$ be the connected components of $F[S_{\le 1} \cap S]$. Notice that $d' \le d$ because $F[S_{\le 1} \cap S]$ is an induced subgraph of a graph with maximum independent set size at most $d$. By construction, every vertex of $S'$ is adjacent to at least one vertex of $S_{\le 1} \cap S$. If the endpoints of an edge of $M$ in $S'$ are adjacent to vertices of the same component $C_i$, $1 \le i \le d'$, then there is an $S$-cycle in $F$ since every vertex of $C_i$ belongs to $S$. Thus the endpoints of every edge of $M$ are adjacent to different connected components of $F[S_{\le 1} \cap S]$. Now obtain a bipartite graph by contracting every component $C_i$ into a single vertex and every edge of $M$ into a single vertex and keep only the adjacencies between the components and the edges of $M$. Let $(A, B)$ be the bipartition of the resulting bipartite graph such that $A$ contains the components of $F[S_{\le 1} \cap S]$ and $B$ contains the edges of $M$. Since $|A| \le |B|$ and every vertex of $B$ is adjacent to at least two vertices of $A$, there is a cycle in the bipartite graph. Then, it is not difficult to see that the cycle of the contracted vertices corresponds to an $S$-cycle in $F$. Therefore there is an $S$-cycle in an $S$-forest, leading to a contradiction.

**Case 2.** Let $2d-1 \le |S_{\le 1} \cap S| \le 2d$. Assume for contradiction that $|S'| > 2d - |S_{\le 1} \cap S|$. This means that $S'$ contains at least one vertex. We pick a nonempty subset $W$ of $S'$ as follows. If $|S_{\le 1} \cap S| = 2d-1$ then $W$ consists of any two vertices of $S'$. If $|S_{\le 1} \cap S| = 2d$ then $W$ consists of an arbitrary vertex of $S'$. In both cases, notice that $|S_{\le 1} \cap S| + |W| > 2d$ by the fact $2d-1 \le |S_{\le 1} \cap S|$. Then Observation 1 (1) implies that there is a cycle in $F[(S_{\le 1} \cap S) \cup W]$. Since $W$ has at most two vertices, we conclude that the induced cycle of $F[(S_{\le 1} \cap S) \cup W]$ has at least one vertex from $S$, hence it is an $S$-cycle in $F$. Therefore we reach a contradiction which implies that $|S'| \le 2d - |S_{\le 1} \cap S|$. ◀

Lemma 3 shows that we can compute all possible candidates for $S_{\le 1}$ in polynomial time as follows.

- We first try, by brute force, all subsets $S'$ of $S$ having at most $2d$ vertices, according to Observation 1 (2).

- Then, for each such subset $S'$, we incorporate a set $X' \subseteq N(S')$ for which either $|X'| + |S'| \le 4d-2$, or $|X'| + |S'| \le 2d$, according to Lemma 3.

- Given the described sets $S'$ and $X'$, we check if $G[S' \cup X']$ induces an $S$-forest and, if so, we include them into a list $L_1$ containing all candidates for $S_{\le 1}$.
Notice that $G-S$ is trivially an $S$-forest of $G$. Thus, if $F$ is an $S$-forest of $G$ such that $S_{\le 1} \cap S = \emptyset$ then $F$ does not contain any vertex of $S$ and $F = G-S$. Next, we assume that $S_{\le 1} \cap S \ne \emptyset$ and show how to bound the vertex set $S_{\le 1}$ of $F_{\le 1}$.

**Lemma 3.** Let $F$ be an $S$-forest of $G$ with $S$-distance partition $(F_{\le 1}, F_{>1})$ such that $S_{\le 1} \cap S \ne \emptyset$.

1. If $|S_{\le 1} \cap S| \le 2d-2$ then $|S_{\le 1}| \le 4d-2$.

2. If $|S_{\le 1} \cap S| \ge 2d-1$ then $|S_{\le 1}| \le 2d$.

**Proof.** Let $F$ be such an $S$-forest of $G$ with $|S_{\le 1} \cap S| \ge 1$. By Observation 1 (2), we know that $|S_{\le 1} \cap S| \le 2d$. To ease the presentation, we let $S' = S_{\le 1} \setminus S$. We consider separately the two cases of the claim.

**Case 1.** Let $1 \le |S_{\le 1} \cap S| \le 2d-2$. Assume for contradiction that $|S'| > 4d - |S_{\le 1} \cap S| - 2$. We show that $F[S']$ contains a matching with at least $d$ edges. Observe that $|S'| + |S_{\le 1} \cap S| > 4d - 2$. Applying Observation 1 (1) shows that there is a cycle $C$ in $F[S_{\le 1}]$. Since $F$ is an $S$-forest, this is not an $S$-cycle, so all vertices contained in $C$ are vertices of $S'$. Iteratively removing the two endpoints of an edge from $C$, as long as $|S'| + |S_{\le 1} \cap S| > 2d$, constructs $d$ edges of $S'$ having no common endpoints by Observation 1 (1). Thus, $F[S']$ contains a matching $M$ with at least $d$ edges.

Let $C_1, \dots, C_d'$ be the connected components of $F[S_{\le 1} \cap S]$. Notice that $d' \le d$ because $F[S_{\le 1} \cap S]$ is an induced subgraph of a graph with maximum independent set size at most $d$. By construction, every vertex of $S'$ is adjacent to at least one vertex of $S_{\le 1} \cap S$. If the endpoints of an edge of $M$ in $S'$ are adjacent to vertices of the same component $C_i$, $1 \le i \le d'$, then there is an $S$-cycle in $F$ since every vertex of $C_i$ belongs to $S$. Thus the endpoints of every edge of $M$ are adjacent to different connected components of $F[S_{\le 1} \cap S]$. Now obtain a bipartite graph by contracting every component $C_i$ into a single vertex and every edge of $M$ into a single vertex and keep only the adjacencies between the components and the edges of $M$. Let $(A, B)$ be the bipartition of the resulting bipartite graph such that $A$ contains the components of $F[S_{\le 1} \cap S]$ and $B$ contains the edges of $M$. Since $|A| \le |B|$ and every vertex of $B$ is adjacent to at least two vertices of $A$, there is a cycle in the bipartite graph. Then, it is not difficult to see that the cycle of the contracted vertices corresponds to an $S$-cycle in $F$. Therefore there is an $S$-cycle in an $S$-forest, leading to a contradiction.

**Case 2.** Let $2d-1 \le |S_{\le 1} \cap S| \le 2d$. Assume for contradiction that $|S'| > 2d - |S_{\le 1} \cap S|$. This means that $S'$ contains at least one vertex. We pick a nonempty subset $W$ of $S'$ as follows. If $|S_{\le 1} \cap S| = 2d-1$ then $W$ consists of any two vertices of $S'$. If $|S_{\le 1} \cap S| = 2d$ then $W$ consists of an arbitrary vertex of $S'$. In both cases, notice that $|S_{\le 1} \cap S| + |W| > 2d$ by the fact $2d-1 \le |S_{\le 1} \cap S|$. Then Observation 1 (1) implies that there is a cycle in $F[(S_{\le 1} \cap S) \cup W]$. Since $W$ has at most two vertices, we conclude that the induced cycle of $F[(S_{\le 1} \cap S) \cup W]$ has at least one vertex from $S$, hence it is an $S$-cycle in $F$. Therefore we reach a contradiction which implies that $|S'| \le 2d - |S_{\le 1} \cap S|$. ◀

Lemma 3 shows that we can compute all possible candidates for $S_{\le 1}$ in polynomial time as follows.

- We first try, by brute force, all subsets $S'$ of $S$ having at most $2d$ vertices, according to Observation 1 (2).

- Then, for each such subset $S'$, we incorporate a set $X' \subseteq N(S')$ for which either $|X'| + |S'| \le 4d-2$, or $|X'| + |S'| \le 2d$, according to Lemma 3.

- Given the described sets $S'$ and $X'$, we check if $G[S' \cup X']$ induces an $S$-forest and, if so, we include them into a list $L_1$ containing all candidates for $S_{\le 1}$.
The correctness follows from Observation 1 and Lemma 3. Regarding the running time, notice that we create at most $n^{O(d)}$ subsets for each of $S'$ and $X' \subseteq N(S')$. Thus, in time $n^{O(d)}$ we can compute a list $L_1$ that contains all possible subsets of the vertices corresponding to $S_{\le 1}$. Notice that such vertices are enough to build the part $F_{\le 1}$.

Let $S_{\le 1}$ be a set of $L_1$. We now focus on the graph $G' = G - (S_{\le 1} \cup S)$ that contains the vertices that are at distance of at least two from $S_{\le 1} \cap S$. Observe that for any $S$-forest $F$, the set of all vertices in $F$ which are at distance of at most one from the vertices of $S \cap V(F)$, are present as an element of $L_1$. Let $d'$ be the number of connected components of $G'$. It is clear that $d' \le d$. In fact, if $S_{\le 1} \cap S$ contains at least one vertex then $d' < d$, since the vertices of $G'$ are at distance of at least two from $S_{\le 1} \cap S$. Moreover, observe that if $S_{\le 1} \cap S = \emptyset$ then $G - S$ is a trivial solution, since we try all subsets of $S$, having at most $2d$ vertices, for the set $S_{\le 1}$. From now on, we assume that $|S_{\le 1} \cap S| \ge 1$ so that $d' < d$.

By brute force, we find all tuples $(A_1, \dots, A_{d'})$ such that the following hold:

(i) $A_i \subseteq (S_{\le 1} \setminus S)$, for every $1 \le i \le d'$, and

(ii) the graph $\hat{G}$ with respect to $S_{\le 1}$ and $(A_1, \dots, A_{d'})$ is an $S$-forest.

Notice that by Lemma 2 (ii) it is sufficient to consider only such tuples. Since $A_i \subseteq S_{\le 1}$, $d' < d$, and $|S_{\le 1}| \le 4d$, the number of tuples is $d^{O(d)}$, so that we can obtain the desired set of tuples that satisfy both conditions in polynomial time.

In what follows, we consider the case for $d \le 3$. By the previous arguments, we are given a set $S_{\le 1} \subseteq N[S]$ and tuples of the form $A_1$ or $(A_1, A_2)$ which are subsets of $S_{\le 1} \setminus S$. Our task is to compute a subset $V'$ of the vertices of $G'$ such that the vertices of $S_{\le 1} \cup V'$ induce a maximum $S$-forest and the cut $(G[S_{\le 1}], G[V'])$ satisfies $A_1$ or $(A_1, A_2)$, respectively. We distinguish the two cases with the following two lemmas.

**Lemma 4.** Let $X \subseteq N[S]$ and let $A_1$ be a subset of $X \setminus S$ such that both $F_{\le 1} = G[X]$ and $\hat{G}$ with respect to $X$ and $A_1$ are $S$-forests. There exists a polynomial-time algorithm that computes a maximum $S$-forest $F$ with an $S$-distance partition $(F_{\le 1}, F_{>1})$ having a cut satisfying $A_1$.

**Proof.** Since $F_{\le 1}$ is a fixed $S$-forest of $F$, we need to determine the vertices of $V \setminus (X \cup S)$ that are included in $F_{>1}$. By the desired cut of $(F_{\le 1}, F_{>1})$, we are restricted to the vertices of $V \setminus (X \cup S)$ that have neighbors in $F_{\le 1}$ only to $A_1$. Those vertices can be described as follows:

$$B_1 = (V \setminus (X \cup S)) \setminus \{w \in V : N(w) \cap (X \setminus (S \cup A_1)) \neq \emptyset\}.$$

Notice that $B_1$ contains vertices that are at distance at least two from the $S$-vertices of $X \cap S$. Since the cut satisfies a single subset $A_1$, we have at most one connected component of $G[B_1]$ in $F_{>1}$. In order to choose the correct connected component of $G[B_1]$, we try to include each of them in $F_{>1}$ and select the one having the maximum total weight. Notice that adding any component of $G[B_1]$ into $F_{>1}$ cannot create any $S$-cycle, because $\hat{G}$ with respect to $X$ and $A_1$ is an $S$-forest. Thus, by Lemma 2, we correctly compute a maximum $S$-forest with the desired properties. Clearly the set $B_1$ can be constructed in polynomial time. Since the number of connected components $G[B_1]$ is at most two, all steps can be executed in polynomial time. $\blacksquare$

**Lemma 5.** Let $X \subseteq N[S]$ and let $A_1, A_2$ be subsets of $X \setminus S$ such that both $F_{\le 1} = G[X]$ and $\hat{G}$ with respect to $X$ and $(A_1, A_2)$ are $S$-forests. There exists a polynomial-time algorithm that computes a maximum $S$-forest $F$ with an $S$-distance partition $(F_{\le 1}, F_{>1})$ having a cut satisfying $(A_1, A_2)$.
The correctness follows from Observation 1 and Lemma 3. Regarding the running time, notice that we create at most $n^{O(d)}$ subsets for each of $S'$ and $X' \subseteq N(S')$. Thus, in time $n^{O(d)}$ we can compute a list $L_1$ that contains all possible subsets of the vertices corresponding to $S_{\le 1}$. Notice that such vertices are enough to build the part $F_{\le 1}$.

Let $S_{\le 1}$ be a set of $L_1$. We now focus on the graph $G' = G - (S_{\le 1} \cup S)$ that contains the vertices that are at distance of at least two from $S_{\le 1} \cap S$. Observe that for any $S$-forest $F$, the set of all vertices in $F$ which are at distance of at most one from the vertices of $S \cap V(F)$, are present as an element of $L_1$. Let $d'$ be the number of connected components of $G'$. It is clear that $d' \le d$. In fact, if $S_{\le 1} \cap S$ contains at least one vertex then $d' < d$, since the vertices of $G'$ are at distance of at least two from $S_{\le 1} \cap S$. Moreover, observe that if $S_{\le 1} \cap S = \emptyset$ then $G - S$ is a trivial solution, since we try all subsets of $S$, having at most $2d$ vertices, for the set $S_{\le 1}$. From now on, we assume that $|S_{\le 1} \cap S| \ge 1$ so that $d' < d$.

By brute force, we find all tuples $(A_1, \dots, A_{d'})$ such that the following hold:

(i) $A_i \subseteq (S_{\le 1} \setminus S)$, for every $1 \le i \le d'$, and

(ii) the graph $\hat{G}$ with respect to $S_{\le 1}$ and $(A_1, \dots, A_{d'})$ is an $S$-forest.

Notice that by Lemma 2 (ii) it is sufficient to consider only such tuples. Since $A_i \subseteq S_{\le 1}$, $d' < d$, and $|S_{\le 1}| \le 4d$, the number of tuples is $d^{O(d)}$, so that we can obtain the desired set of tuples that satisfy both conditions in polynomial time.

In what follows, we consider the case for $d \le 3$. By the previous arguments, we are given a set $S_{\le 1} \subseteq N[S]$ and tuples of the form $A_1$ or $(A_1, A_2)$ which are subsets of $S_{\le 1} \setminus S$. Our task is to compute a subset $V'$ of the vertices of $G'$ such that the vertices of $S_{\le 1} \cup V'$ induce a maximum $S$-forest and the cut $(G[S_{\le 1}], G[V'])$ satisfies $A_1$ or $(A_1, A_2)$, respectively. We distinguish the two cases with the following two lemmas.

**Lemma 4.** Let $X \subseteq N[S]$ and let $A_1$ be a subset of $X \setminus S$ such that both $F_{\le 1} = G[X]$ and $\hat{G}$ with respect to $X$ and $A_1$ are $S$-forests. There exists a polynomial-time algorithm that computes a maximum $S$-forest $F$ with an $S$-distance partition $(F_{\le 1}, F_{>1})$ having a cut satisfying $A_1$.

**Proof.** Since $F_{\le 1}$ is a fixed $S$-forest of $F$, we need to determine the vertices of $V \setminus (X \cup S)$ that are included in $F_{>1}$. By the desired cut of $(F_{\le 1}, F_{>1})$, we are restricted to the vertices of $V \setminus (X \cup S)$ that have neighbors in $F_{\le 1}$ only to $A_1$. Those vertices can be described as follows:

$$B_1 = (V \setminus (X \cup S)) \setminus \{w \in V : N(w) \cap (X \setminus (S \cup A_1)) \neq \emptyset\}.$$

Notice that $B_1$ contains vertices that are at distance at least two from the $S$-vertices of $X \cap S$. Since the cut satisfies a single subset $A_1$, we have at most one connected component of $G[B_1]$ in $F_{>1}$. In order to choose the correct connected component of $G[B_1]$, we try to include each of them in $F_{>1}$ and select the one having the maximum total weight. Notice that adding any component of $G[B_1]$ into $F_{>1}$ cannot create any $S$-cycle, because $\hat{G}$ with respect to $X$ and $A_1$ is an $S$-forest. Thus, by Lemma 2, we correctly compute a maximum $S$-forest with the desired properties. Clearly the set $B_1$ can be constructed in polynomial time. Since the number of connected components $G[B_1]$ is at most two, all steps can be executed in polynomial time. ◀

**Lemma 5.** Let $X \subseteq N[S]$ and let $A_1, A_2$ be subsets of $X \setminus S$ such that both $F_{\le 1} = G[X]$ and $\hat{G}$ with respect to $X$ and $(A_1, A_2)$ are $S$-forests. There exists a polynomial-time algorithm that computes a maximum $S$-forest $F$ with an $S$-distance partition $(F_{\le 1}, F_{>1})$ having a cut satisfying $(A_1, A_2)$.
**Proof.** Similar to the proof of Lemma 4, we first construct the sets $B_1, B_2$ that contain vertices of $V \setminus (X \cup S)$ and satisfy the cut obtained from $X$:

$$B_1 = (V \setminus (X \cup S)) \setminus \{w \in V : N(w) \cap (X \setminus (S \cup A_1)) \neq \emptyset\} \text{ and}$$

$$B_2 = (V \setminus (X \cup S)) \setminus \{w \in V : N(w) \cap (X \setminus (S \cup A_2)) \neq \emptyset\}.$$

As the desired cut of $(F_{\leq 1}, F_{>1})$ satisfies $(A_1, A_2)$, there are two connected components of $F_{>1}$ which are subsets of the two sets $B_1$ and $B_2$, respectively. Let $C_1$ and $C_2$ be the connected components of $F_{>1}$ such that $C_1 \subseteq B_1$ and $C_2 \subseteq B_2$. Now observe that there should be two non-adjacent vertices $w_1 \in B_1$ and $w_2 \in B_2$ that belong to $C_1$ and $C_2$, respectively. We iterate over all possible pairs of non-adjacent vertices $w_1 \in B_1 \cap C_1$ and $w_2 \in B_2 \cap C_2$ in $O(n^2)$ time. Assuming a given choice for $w_1$ and $w_2$, observe the following:

- Since $w_1$ and $w_2$ are vertices of different connected components of $F_{>1}$, the components themselves are further restricted to be subsets of $B_1 \setminus N[w_2]$ and $B_2 \setminus N[w_1]$, respectively. That is, $C_1 \subseteq (B_1 \setminus N[w_2])$ and $C_2 \subseteq (B_2 \setminus N[w_1])$.

- Since $F$ has at least one vertex of $S$, $w_1, w_2 \in V \setminus (X \cup S)$ are non-adjacent, and by the fact $d \leq 3$, we have that $B_1 \setminus N[w_2]$ and $B_2 \setminus N[w_1]$ induce cliques in $G$. Thus $B_1 \setminus N[w_2] \subseteq N[w_1]$ and $B_2 \setminus N[w_1] \subseteq N[w_2]$, respectively.

Then by the second statement it is not difficult to see that $B_1 \setminus N[w_2]$ and $B_2 \setminus N[w_1]$ are disjoint. Let $B'_1 = (B_1 \setminus N[w_2]) \setminus \{w_1\}$ and $B'_2 = (B_2 \setminus N[w_1]) \setminus \{w_2\}$. Now in order to find the maximum induced $S$-forest under the stated conditions and our assumption that $w_1$ and $w_2$ belong to the two connected components of $F_{>1}$, it suffices to find the maximum subset $C_1 \cup C_2$ of $B'_1 \cup B'_2$ such that there are no edges between the vertices of $C_1 \cap B'_1$ and the vertices of $C_2 \cap B'_2$. This boils down to compute a minimum weighted vertex cover on the bipartite graph $G'$ obtained from $G[B'_1 \cup B'_2]$ and removing the edges inside $G[B'_1]$ and $G[B'_2]$. By maximum flow standard techniques, we compute a minimum weighted vertex cover $U$ on $G'$ in polynomial time [30]. Therefore, $G[B'_1 \cup B'_2] - U$ contains the connected components $C_1 \setminus \{w_1\}$ and $C_1 \setminus \{w_2\}$, as required. ◀

Now we are equipped with our necessary tools in order to obtain our main result, namely a polynomial-time algorithm that solves WEIGHTED SUBSET FEEDBACK VERTEX SET on graphs of independent set of size at most 3.

**Theorem 6.** WEIGHTED SUBSET FEEDBACK VERTEX SET on graphs of independent set of size at most 3 can be solved on time $n^{O(1)}$.

**Proof.** Let us briefly explain such an algorithm for computing a maximum $S$-forest $F$ of a graph $G$ having independent set size at most three. Let $d = 3$. Initially we set $F^* = G - S$. Then, for every set $X \subseteq N[S]$ with $|X| \leq 4d$ such that $G[X]$ is an $S$-forest, we try by brute force all subsets $A_1$ and $(A_1, A_2)$ with $A_i \subseteq (X \setminus S)$ such that $\hat{G}$ with respect to $X$ and $A_1$ or $(A_1, A_2)$ is an $S$-forest. For each of such subsets, we find a maximum $S$-forest $F$ with an $S$-distance partition $(G[X], F_{>1})$ having a cut satisfying $A_1$ or $(A_1, A_2)$, respectively, by applying the algorithms described in Lemma 4 and Lemma 5. At each step, we maintain the maximum weighted $S$-forest $F^*$ by comparing $F$ with $F^*$. Finally we provide the vertices $V \setminus V(F^*)$ as the set with the minimum total weight that are removed from $G$.

By Lemma 3, it is sufficient to consider the described subsets $X$. Since every induced subgraph of $G - X$ contains at most two connected components, Lemma 2 implies that all possible subsets $A_1$ or $(A_1, A_2)$ with the described properties are enough to consider. Thus, the correctness follows from Lemmata 3–5. Regarding the running time, notice that whether a graph contains an $S$-cycle can be tested in linear time. Thus we can construct all
**Proof.** Similar to the proof of Lemma 4, we first construct the sets $B_1, B_2$ that contain vertices of $V \setminus (X \cup S)$ and satisfy the cut obtained from $X$:

$$B_1 = (V \setminus (X \cup S)) \setminus \{w \in V : N(w) \cap (X \setminus (S \cup A_1)) \neq \emptyset\} \text{ and}$$

$$B_2 = (V \setminus (X \cup S)) \setminus \{w \in V : N(w) \cap (X \setminus (S \cup A_2)) \neq \emptyset\}.$$

As the desired cut of $(F_{\leq 1}, F_{>1})$ satisfies $(A_1, A_2)$, there are two connected components of $F_{>1}$ which are subsets of the two sets $B_1$ and $B_2$, respectively. Let $C_1$ and $C_2$ be the connected components of $F_{>1}$ such that $C_1 \subseteq B_1$ and $C_2 \subseteq B_2$. Now observe that there should be two non-adjacent vertices $w_1 \in B_1$ and $w_2 \in B_2$ that belong to $C_1$ and $C_2$, respectively. We iterate over all possible pairs of non-adjacent vertices $w_1 \in B_1 \cap C_1$ and $w_2 \in B_2 \cap C_2$ in $O(n^2)$ time. Assuming a given choice for $w_1$ and $w_2$, observe the following:

- Since $w_1$ and $w_2$ are vertices of different connected components of $F_{>1}$, the components themselves are further restricted to be subsets of $B_1 \setminus N[w_2]$ and $B_2 \setminus N[w_1]$, respectively. That is, $C_1 \subseteq (B_1 \setminus N[w_2])$ and $C_2 \subseteq (B_2 \setminus N[w_1])$.

- Since $F$ has at least one vertex of $S$, $w_1, w_2 \in V \setminus (X \cup S)$ are non-adjacent, and by the fact $d \leq 3$, we have that $B_1 \setminus N[w_2]$ and $B_2 \setminus N[w_1]$ induce cliques in $G$. Thus $B_1 \setminus N[w_2] \subseteq N[w_1]$ and $B_2 \setminus N[w_1] \subseteq N[w_2]$, respectively.

Then by the second statement it is not difficult to see that $B_1 \setminus N[w_2]$ and $B_2 \setminus N[w_1]$ are disjoint. Let $B'_1 = (B_1 \setminus N[w_2]) \setminus \{w_1\}$ and $B'_2 = (B_2 \setminus N[w_1]) \setminus \{w_2\}$. Now in order to find the maximum induced $S$-forest under the stated conditions and our assumption that $w_1$ and $w_2$ belong to the two connected components of $F_{>1}$, it suffices to find the maximum subset $C_1 \cup C_2$ of $B'_1 \cup B'_2$ such that there are no edges between the vertices of $C_1 \cap B'_1$ and the vertices of $C_2 \cap B'_2$. This boils down to compute a minimum weighted vertex cover on the bipartite graph $G'$ obtained from $G[B'_1 \cup B'_2]$ and removing the edges inside $G[B'_1]$ and $G[B'_2]$. By maximum flow standard techniques, we compute a minimum weighted vertex cover $U$ on $G'$ in polynomial time [30]. Therefore, $G[B'_1 \cup B'_2] - U$ contains the connected components $C_1 \setminus \{w_1\}$ and $C_1 \setminus \{w_2\}$, as required. ◀

Now we are equipped with our necessary tools in order to obtain our main result, namely a polynomial-time algorithm that solves WEIGHTED SUBSET FEEDBACK VERTEX SET on graphs of independent set of size at most 3.

**Theorem 6.** WEIGHTED SUBSET FEEDBACK VERTEX SET on graphs of independent set of size at most 3 can be solved on time $n^{O(1)}$.

**Proof.** Let us briefly explain such an algorithm for computing a maximum $S$-forest $F$ of a graph $G$ having independent set size at most three. Let $d = 3$. Initially we set $F^* = G - S$. Then, for every set $X \subseteq N[S]$ with $|X| \leq 4d$ such that $G[X]$ is an $S$-forest, we try by brute force all subsets $A_1$ and $(A_1, A_2)$ with $A_i \subseteq (X \setminus S)$ such that $\hat{G}$ with respect to $X$ and $A_1$ or $(A_1, A_2)$ is an $S$-forest. For each of such subsets, we find a maximum $S$-forest $F$ with an $S$-distance partition $(G[X], F_{>1})$ having a cut satisfying $A_1$ or $(A_1, A_2)$, respectively, by applying the algorithms described in Lemma 4 and Lemma 5. At each step, we maintain the maximum weighted $S$-forest $F^*$ by comparing $F$ with $F^*$. Finally we provide the vertices $V \setminus V(F^*)$ as the set with the minimum total weight that are removed from $G$.

By Lemma 3, it is sufficient to consider the described subsets $X$. Since every induced subgraph of $G - X$ contains at most two connected components, Lemma 2 implies that all possible subsets $A_1$ or $(A_1, A_2)$ with the described properties are enough to consider. Thus, the correctness follows from Lemmata 3–5. Regarding the running time, notice that whether a graph contains an $S$-cycle can be tested in linear time. Thus we can construct all
described and valid subsets in $n^{\mathcal{O}(1)}$ time. Therefore the total running time of the algorithm is $n^{\mathcal{O}(1)}$, since each of the algorithms given in Lemma 4 and Lemma 5, respectively, requires polynomial time. ◀

Let us now show that extending Theorem 6 to graphs of larger independent sets is not possible. More precisely, with the following result we show that WEIGHTED SUBSET FEEDBACK VERTEX SET is para-NP-complete parameterized by $\alpha(G)$.

**▶ Theorem 7.** WEIGHTED SUBSET FEEDBACK VERTEX SET is NP-complete on graphs of independent set of size at most 4.

**Proof.** We will provide a polynomial reduction from the VERTEX COVER problem on tripartite graphs which is NP-complete [17] and asks whether a tripartite graph $G$ contains a vertex cover of weight at most $k$. Let $G = (A, B, C, E)$ be a tripartite graph on $n$ vertices, where $(A, B, C)$ is the partition of $V(G)$. We construct a weighted graph $G'$ from $G$ in polynomial time as follows.

- We turn the three independent sets $A, B$ and $C$ into cliques by adding all necessary edges and we give all vertices unary weight.

- We add a vertex $r_A$ that is adjacent to all of the vertices of $A$ and we assign weight $n$ to $r_A$. In a completely symmetric way, we add vertices $r_B$ and $r_C$ with respect to the sets $B$ and $C$, respectively.

- We add a vertex $s$ that is adjacent to all three vertices $r_A, r_B, r_C$ having weight $n$. This completes the construction of $G'$. Observe that all vertices of $V(G') \setminus \{s, r_A, r_B, r_C\}$ have weight equal to one. It is not difficult to verify that the constructed graph $G'$ is a graph having an independent set at most 4, since the vertex set of $G' - \{s\}$ can be partitioned into three cliques.

Next we claim that $G$ has a vertex cover $U$ of weight at most $k < n$ if and only if $G'$ with $S = \{s\}$ has a subset feedback vertex set of weight at most $k$. Assume a vertex cover $U$ of $G$. By definition, $U$ covers all edges of $G$, so that $G[(A \cup B \cup C) \setminus U]$ is an independent set. This means that $G'[(A \cup B \cup C) \setminus U]$ is a vertex-disjoint union of cliques. Since $s$ is non-adjacent to any vertex of $G$ and $G'[r_A, r_B, r_C]$ is an independent set, every cycle of $G' - U$ contains a vertex of $r_A, r_B$ and $r_C$ with at least two vertices from $A, B$ and $C$, respectively. Thus, $G' - U$ is a connected $S$-forest. Therefore, $U$ is a subset feedback vertex set of $(G', \{s\})$ of size at most $k$.

For the opposite direction, assume a subset feedback vertex set $F$ of $(G', \{s\})$. If $F$ is not a subset of $A \cup B \cup C$, then its sum of weights is greater or equal to $n$. Then $F$ is not a minimum subset feedback vertex set of $(G', \{s\})$, since $A \cup B \cup C$ minus a single vertex is trivially a subset feedback vertex set of $(G', \{s\})$ of total weight $n-1$. Thus $F$ is indeed a subset of $A \cup B \cup C$. Assume that $F$ is not a vertex cover of $G$. By definition, there is an edge of $G$ that remains uncovered. Without loss of generality, assume that this edge has its endpoints on the vertices $x \in A$ and $y \in B$. Then $\langle s, r_A, x, y, r_B \rangle$ is an induced cycle of $G'$, which contradicts the fact that $F$ is a subset feedback vertex set of $(G', \{s\})$. Therefore $F$ is a vertex cover of $G$. ◀

We stress that Theorem 7 further implies that the NP-completeness result carries along to graphs of clique cover number at most four, since the constructed graph given in the proof can be partitioned into four disjoint cliques.
described and valid subsets in $n^{\mathcal{O}(1)}$ time. Therefore the total running time of the algorithm is $n^{\mathcal{O}(1)}$, since each of the algorithms given in Lemma 4 and Lemma 5, respectively, requires polynomial time. ◀

Let us now show that extending Theorem 6 to graphs of larger independent sets is not possible. More precisely, with the following result we show that WEIGHTED SUBSET FEEDBACK VERTEX SET is para-NP-complete parameterized by $\alpha(G)$.

**▶ Theorem 7.** WEIGHTED SUBSET FEEDBACK VERTEX SET is NP-complete on graphs of independent set of size at most 4.

**Proof.** We will provide a polynomial reduction from the VERTEX COVER problem on tripartite graphs which is NP-complete [17] and asks whether a tripartite graph $G$ contains a vertex cover of weight at most $k$. Let $G = (A, B, C, E)$ be a tripartite graph on $n$ vertices, where $(A, B, C)$ is the partition of $V(G)$. We construct a weighted graph $G'$ from $G$ in polynomial time as follows.

- We turn the three independent sets $A, B$ and $C$ into cliques by adding all necessary edges and we give all vertices unary weight.

- We add a vertex $r_A$ that is adjacent to all of the vertices of $A$ and we assign weight $n$ to $r_A$. In a completely symmetric way, we add vertices $r_B$ and $r_C$ with respect to the sets $B$ and $C$, respectively.

- We add a vertex $s$ that is adjacent to all three vertices $r_A, r_B, r_C$ having weight $n$. This completes the construction of $G'$. Observe that all vertices of $V(G') \setminus \{s, r_A, r_B, r_C\}$ have weight equal to one. It is not difficult to verify that the constructed graph $G'$ is a graph having an independent set at most 4, since the vertex set of $G' - \{s\}$ can be partitioned into three cliques.

Next we claim that $G$ has a vertex cover $U$ of weight at most $k < n$ if and only if $G'$ with $S = \{s\}$ has a subset feedback vertex set of weight at most $k$. Assume a vertex cover $U$ of $G$. By definition, $U$ covers all edges of $G$, so that $G[(A \cup B \cup C) \setminus U]$ is an independent set. This means that $G'[(A \cup B \cup C) \setminus U]$ is a vertex-disjoint union of cliques. Since $s$ is non-adjacent to any vertex of $G$ and $G'[r_A, r_B, r_C]$ is an independent set, every cycle of $G' - U$ contains a vertex of $r_A, r_B$ and $r_C$ with at least two vertices from $A, B$ and $C$, respectively. Thus, $G' - U$ is a connected $S$-forest. Therefore, $U$ is a subset feedback vertex set of $(G', \{s\})$ of size at most $k$.

For the opposite direction, assume a subset feedback vertex set $F$ of $(G', \{s\})$. If $F$ is not a subset of $A \cup B \cup C$, then its sum of weights is greater or equal to $n$. Then $F$ is not a minimum subset feedback vertex set of $(G', \{s\})$, since $A \cup B \cup C$ minus a single vertex is trivially a subset feedback vertex set of $(G', \{s\})$ of total weight $n-1$. Thus $F$ is indeed a subset of $A \cup B \cup C$. Assume that $F$ is not a vertex cover of $G$. By definition, there is an edge of $G$ that remains uncovered. Without loss of generality, assume that this edge has its endpoints on the vertices $x \in A$ and $y \in B$. Then $\langle s, r_A, x, y, r_B \rangle$ is an induced cycle of $G'$, which contradicts the fact that $F$ is a subset feedback vertex set of $(G', \{s\})$. Therefore $F$ is a vertex cover of $G$. ◀

We stress that Theorem 7 further implies that the NP-completeness result carries along to graphs of clique cover number at most four, since the constructed graph given in the proof can be partitioned into four disjoint cliques.