**Lemma 5.** There exists an $MSO_2$ formula that is modeled by a graph $G \boxtimes C_k$ and its set HORIZONTAL of horizontal edges exactly when $G \boxtimes C_k$ meets the conditions of Lemma 2.

*Proof.* The formula is

$$ \exists S : (ACYCLIC(S) \land REPRESENTED(S) \land \mathrm{ROOT}_k(S)). $$

A subgraph defined by a set $S$ of its edges meets the first condition of the lemma if $ACYCLIC(S)$ is true, it meets the second condition of the lemma if $REPRESENTED(S)$ is true, and it meets the third condition of the lemma if $\mathrm{ROOT}_k(S)$ is true. ◀

**Corollary 6.** The property of a graph $G$ being $k$-leaf power can be expressed as an $MSO_2$ formula of $G \boxtimes C_k$ and of the set HORIZONTAL of horizontal edges of this product graph.

# 5 Fixed-Parameter Tractability of Leaf Powers

In order to apply Courcelle's theorem to the product graph $G \boxtimes C_k$ we need to bound its treewidth.

**Lemma 7.** If $G$ has treewidth $t$ and $H$ has a bounded number of vertices $s$ then $G \boxtimes H$ has treewidth at most $s(t+1) - 1$.

*Proof.* Given any tree-decomposition of $G$ with width $t$, we can form a decomposition of $G \boxtimes H$ by using the same tree, and placing each vertex $(v, w)$ of $G \boxtimes H$ (where $v$ and $w$ are vertices of $G$ and $H$ respectively) into the same bag as vertex $v$ of $G$. The size of the largest bag of the tree-decomposition of $G$ is $t+1$, so the size of the largest bag of the resulting tree-decomposition of the product graph is $s(t+1)$. The treewidth is one less than the size of the largest bag. ◀

**Corollary 8.** If $G$ has a bounded treewidth and $k$ is bounded, then $G \boxtimes C_k$ also has bounded treewidth.

This gives us our main theorem:

**Theorem 9.** For fixed constants $k$ and $d$, it is possible to recognize in linear time (with fixed-parameter tractable dependence on $k$ and $d$) whether a graph of degeneracy at most $d$ is a $k$-leaf power.

*Proof.* If we consider the class of graphs with bounded degeneracy $d$, trivially these graphs do not contain the complete bipartite graph $K_{d+1,d+1}$ as a subgraph. Gurski and Wanke proved that $k$-leaf powers with fixed $k$ have bounded clique-width [24]. In separate work, they also proved that every class of graphs with bounded clique-width and no $K_{a,a}$ subgraph has bounded treewidth [23]. These results immediately imply that $k$-leaf powers with bounded degeneracy have bounded treewidth, and it follows from Corollary 8 that $G \boxtimes C_k$ also has bounded treewidth. Therefore, by applying Courcelle's theorem to the $MSO_2$ formula of Corollary 6 we obtain the result. ◀

# 6 Conclusion

We have provided a fixed-parameter algorithm to recognize $k$-leaf powers for graphs of bounded degeneracy. Our method embeds a $k$-leaf root of a $k$-leaf power graph in the product graph of the input graph and a $k$-vertex cycle $C_k$, finds a logical characterization of the
**Lemma 5.** There exists an $\text{MSO}_2$ formula that is modeled by a graph $G \boxtimes C_k$ and its set HORIZONTAL of horizontal edges exactly when $G \boxtimes C_k$ meets the conditions of Lemma 2.

*Proof.* The formula is

$$ \exists S : (\text{ACYCLIC}(S) \land \text{REPRESENTED}(S) \land \text{ROOT}_k(S)). $$

A subgraph defined by a set $S$ of its edges meets the first condition of the lemma if $\text{ACYCLIC}(S)$ is true, it meets the second condition of the lemma if $\text{REPRESENTED}(S)$ is true, and it meets the third condition of the lemma if $\text{ROOT}_k(S)$ is true. ◀

**Corollary 6.** The property of a graph $G$ being $k$-leaf power can be expressed as an $\text{MSO}_2$ formula of $G \boxtimes C_k$ and of the set HORIZONTAL of horizontal edges of this product graph.

# 5 Fixed-Parameter Tractability of Leaf Powers

In order to apply Courcelle's theorem to the product graph $G \boxtimes C_k$ we need to bound its treewidth.

**Lemma 7.** If $G$ has treewidth $t$ and $H$ has a bounded number of vertices $s$ then $G \boxtimes H$ has treewidth at most $s(t+1) - 1$.

*Proof.* Given any tree-decomposition of $G$ with width $t$, we can form a decomposition of $G \boxtimes H$ by using the same tree, and placing each vertex $(v, w)$ of $G \boxtimes H$ (where $v$ and $w$ are vertices of $G$ and $H$ respectively) into the same bag as vertex $v$ of $G$. The size of the largest bag of the tree-decomposition of $G$ is $t+1$, so the size of the largest bag of the resulting tree-decomposition of the product graph is $s(t+1)$. The treewidth is one less than the size of the largest bag. ◀

**Corollary 8.** If $G$ has a bounded treewidth and $k$ is bounded, then $G \boxtimes C_k$ also has bounded treewidth.

This gives us our main theorem:

**Theorem 9.** For fixed constants $k$ and $d$, it is possible to recognize in linear time (with fixed-parameter tractable dependence on $k$ and $d$) whether a graph of degeneracy at most $d$ is a $k$-leaf power.

*Proof.* If we consider the class of graphs with bounded degeneracy $d$, trivially these graphs do not contain the complete bipartite graph $K_{d+1,d+1}$ as a subgraph. Gurski and Wanke proved that $k$-leaf powers with fixed $k$ have bounded clique-width [24]. In separate work, they also proved that every class of graphs with bounded clique-width and no $K_{a,a}$ subgraph has bounded treewidth [23]. These results immediately imply that $k$-leaf powers with bounded degeneracy have bounded treewidth, and it follows from Corollary 8 that $G \boxtimes C_k$ also has bounded treewidth. Therefore, by applying Courcelle's theorem to the $\text{MSO}_2$ formula of Corollary 6 we obtain the result. ◀

# 6 Conclusion

We have provided a fixed-parameter algorithm to recognize $k$-leaf powers for graphs of bounded degeneracy. Our method embeds a $k$-leaf root of a $k$-leaf power graph in the product graph of the input graph and a $k$-vertex cycle $C_k$, finds a logical characterization of the
16:12 Parameterized Leaf Power Recognition

leaf roots that are embedded in this way, and applies Courcelle's theorem to determine the
existence of a subgraph of the product graph that meets our characterization.

It is perhaps of interest to observe that, although ACYCLIC and ALIGNED involve quantification over vertex sets, the only quantification over edge sets that we use is in the formula of Lemma 5. If we could eliminate all edge sets from our formula (including HORIZONTAL), and obtain an MSO₁ formula for *k*-leaf powers in place of the MSO₂ formula that we use, it might be possible to eliminate the dependence on degeneracy from our parameterized analysis.

Our methods of using low-treewidth supergraphs to represent vertices and edges that are
not part of the input graph, and of using graph products to find these supergraphs, may
be useful in other graph problems. For instance, this method would have greatly simplified
the application of Courcelle's theorem in our recent work on planar split thickness [20]: a
graph *G* has planar split thickness *k* if and only if *G* ⋉ *K*<sub>*k*</sub> has a planar subgraph *S* such
that, for each non-horizontal edge of the product, the endpoints of the edge are aligned with
the endpoints of an edge in *S*. In reducing the logical complexity of problems such as these,
our method also makes it more likely that faster model checkers for restricted fragments
of MSO logic [1] can be applied to our problem. Additionally, and more speculatively, the
reduced logical complexity of our method may help guide future efforts to solve the problem
directly using dynamic programming rather than by applying Courcelle's theorem.

References

1 Max Bannach and Sebastian Berndt. Practical Access to Dynamic Programming on Tree Decompositions. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, *26th Annual European Symposium on Algorithms (ESA 2018)*, volume 112 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 6:1–6:13, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. doi:10.4230/LIPIcs.ESA.2018.6.

2 Michael J Bannister and David Eppstein. Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth. In *International Symposium on Graph Drawing*, pages 210–221. Springer, 2014.

3 Umberto Bertelé and Francesco Brioschi. *Nonserial Dynamic Programming*. Academic Press, 1972.

4 Hans L. Bodlaender. A tourist guide through treewidth. *Acta Cybernet.*, 11(1-2):1-21, 1993.

5 Andreas Brandstädt and Christian Hundt. Ptolemaic graphs and interval graphs are leaf powers. In *Latin American Symposium on Theoretical Informatics*, pages 479–491. Springer, 2008.

6 Andreas Brandstädt, Christian Hundt, Federico Mancini, and Peter Wagner. Rooted directed path graphs are leaf powers. *Discrete Math.*, 310(4):897–910, 2010. doi:10.1016/j.disc.2009.10.006.

7 Andreas Brandstädt and Van Bang Le. Structure and linear time recognition of 3-leaf powers. *Inform. Process. Lett.*, 98(4):133–138, 2006. doi:10.1016/j.ipl.2006.01.004.

8 Andreas Brandstädt, Van Bang Le, and Dieter Rautenbach. A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers. *Discrete Math.*, 309(12):3843–3852, 2009. doi:10.1016/j.disc.2008.10.025.

9 Andreas Brandstädt, Van Bang Le, and R. Sritharan. Structure and linear-time recognition of 4-leaf powers. *ACM Trans. Algorithms*, 5(1):A11:1–A11:22, 2009. doi:10.1145/1435375.1435386.
16:12 Parameterized Leaf Power Recognition

leaf roots that are embedded in this way, and applies Courcelle's theorem to determine the
existence of a subgraph of the product graph that meets our characterization.

It is perhaps of interest to observe that, although ACYCLIC and ALIGNED involve quantification over vertex sets, the only quantification over edge sets that we use is in the formula of Lemma 5. If we could eliminate all edge sets from our formula (including HORIZONTAL), and obtain an MSO₁ formula for *k*-leaf powers in place of the MSO₂ formula that we use, it might be possible to eliminate the dependence on degeneracy from our parameterized analysis.

Our methods of using low-treewidth supergraphs to represent vertices and edges that are
not part of the input graph, and of using graph products to find these supergraphs, may
be useful in other graph problems. For instance, this method would have greatly simplified
the application of Courcelle's theorem in our recent work on planar split thickness [20]: a
graph *G* has planar split thickness *k* if and only if *G* ⋄ *K*<sub>*k*</sub> has a planar subgraph *S* such
that, for each non-horizontal edge of the product, the endpoints of the edge are aligned with
the endpoints of an edge in *S*. In reducing the logical complexity of problems such as these,
our method also makes it more likely that faster model checkers for restricted fragments
of MSO logic [1] can be applied to our problem. Additionally, and more speculatively, the
reduced logical complexity of our method may help guide future efforts to solve the problem
directly using dynamic programming rather than by applying Courcelle's theorem.

References

1 Max Bannach and Sebastian Berndt. Practical Access to Dynamic Programming on Tree Decompositions. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, *26th Annual European Symposium on Algorithms (ESA 2018)*, volume 112 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 6:1–6:13, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. doi:10.4230/LIPIcs.ESA.2018.6.

2 Michael J Bannister and David Eppstein. Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth. In *International Symposium on Graph Drawing*, pages 210–221. Springer, 2014.

3 Umberto Bertelé and Francesco Brioschi. *Nonserial Dynamic Programming*. Academic Press, 1972.

4 Hans L. Bodlaender. A tourist guide through treewidth. *Acta Cybernet.*, 11(1-2):1-21, 1993.

5 Andreas Brandstädt and Christian Hundt. Ptolemaic graphs and interval graphs are leaf powers. In *Latin American Symposium on Theoretical Informatics*, pages 479–491. Springer, 2008.

6 Andreas Brandstädt, Christian Hundt, Federico Mancini, and Peter Wagner. Rooted directed path graphs are leaf powers. *Discrete Math.*, 310(4):897–910, 2010. doi:10.1016/j.disc.2009.10.006.

7 Andreas Brandstädt and Van Bang Le. Structure and linear time recognition of 3-leaf powers. *Inform. Process. Lett.*, 98(4):133–138, 2006. doi:10.1016/j.ipl.2006.01.004.

8 Andreas Brandstädt, Van Bang Le, and Dieter Rautenbach. A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers. *Discrete Math.*, 309(12):3843–3852, 2009. doi:10.1016/j.disc.2008.10.025.

9 Andreas Brandstädt, Van Bang Le, and R. Sritharan. Structure and linear-time recognition of 4-leaf powers. *ACM Trans. Algorithms*, 5(1):A11:1–A11:22, 2009. doi:10.1145/1435375.1435386.
10 Andreas Brandstädt and Peter Wagner. On k-versus (k+ 1)-leaf powers. In *International Conference on Combinatorial Optimization and Applications*, pages 171–179. Springer, 2008.

11 Maw-Shang Chang and Ming-Tat Ko. The 3-Steiner root problem. In *International Workshop on Graph-Theoretic Concepts in Computer Science*, pages 109–120. Springer, 2007.

12 Zhi-Zhong Chen, Tao Jiang, and Guohui Lin. Computing phylogenetic roots with bounded degrees and errors. *SIAM J. Comput.*, 32(4):864–879, 2003. doi:10.1137/S0097539701389154.

13 Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. *Inform. and Comput.*, 85(1):12–75, 1990. doi:10.1016/0890-5401(90)90043-H.

14 Bruno Courcelle. On the expression of graph properties in some fragments of monadic second-order logic. In Neil Immerman and Phokion G. Kolaitis, editors, *Descriptive Complexity and Finite Models: Proceedings of a DIMACS Workshop, January 14–17, 1996, Princeton University, volume 31 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci.*, pages 33–62. American Mathematical Society, Providence, RI, 1997.

15 Bruno Courcelle. The expression of graph properties and graph transformations in monadic second-order logic. In *Handbook of graph grammars and computing by graph transformation, Vol. 1*, pages 313–400. World Scientific, River Edge, NJ, 1997. doi:10.1142/9789812384720_0005.

16 Bruno Courcelle, Joost Engelfriet, and Grzegorz Rozenberg. Handle-rewriting hypergraph grammars. *J. Comput. System Sci.*, 46(2):218–270, 1993. doi:10.1016/0022-0000(93) 90004-G.

17 Bruno Courcelle, J. A. Makowsky, and U. Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. *Theory Comput. Syst.*, 33(2):125–150, 2000. doi:10.1007/s002249910009.

18 Michael Dom, Jiong Guo, Falk Hüffner, and Rolf Niedermeier. Error compensation in leaf root problems. In *International Symposium on Algorithms and Computation*, pages 389–401. Springer, 2004.

19 Michael Dom, Jiong Guo, Falk Hüffner, and Rolf Niedermeier. Extending the tractability border for closest leaf powers. In *International Workshop on Graph-Theoretic Concepts in Computer Science*, pages 397–408. Springer, 2005.

20 David Eppstein, Philipp Kindermann, Stephen Kobourov, Giuseppe Liotta, Anna Lubiw, Aude Maignan, Debajyoti Mondal, Hamideh Vosoughpour, Sue Whitesides, and Stephen Wismath. On the planar split thickness of graphs. *Algorithmica*, 80(3):977–994, 2018. doi:10.1007/s00453-017-0328-y.

21 Walter M. Fitch and Emanuel Margoliash. Construction of phylogenetic trees. *Science*, 155(3760):279–284, 1967. doi:10.1126/science.155.3760.279.

22 Martin Grohe. Computing crossing numbers in quadratic time. In *Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing*, pages 231–236, New York, 2001. ACM. doi:10.1145/380752.380805.

23 Frank Gurski and Egon Wanke. The tree-width of clique-width bounded graphs without $K_{n,n}$. In *International Workshop on Graph-Theoretic Concepts in Computer Science*, pages 196–205. Springer, 2000.

24 Frank Gurski and Egon Wanke. The clique-width of tree-power and leaf-power graphs. In *International Workshop on Graph-Theoretic Concepts in Computer Science*, pages 76–85. Springer, 2007.

25 Rudolf Halin. S-functions for graphs. *J. Geometry*, 8(1-2):171–186, 1976. doi:10.1007/BF01917434.

26 Petr Hliněný. Branch-width, parse trees, and monadic second-order logic for matroids. *J. Combin. Theory Ser. B*, 96(3):325–351, 2006. doi:10.1016/j.jctb.2005.08.005.
10 Andreas Brandstädt and Peter Wagner. On k-versus (k+ 1)-leaf powers. In *International Conference on Combinatorial Optimization and Applications*, pages 171–179. Springer, 2008.

11 Maw-Shang Chang and Ming-Tat Ko. The 3-Steiner root problem. In *International Workshop on Graph-Theoretic Concepts in Computer Science*, pages 109–120. Springer, 2007.

12 Zhi-Zhong Chen, Tao Jiang, and Guohui Lin. Computing phylogenetic roots with bounded degrees and errors. *SIAM J. Comput.*, 32(4):864–879, 2003. doi:10.1137/S0097539701389154.

13 Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. *Inform. and Comput.*, 85(1):12–75, 1990. doi:10.1016/0890-5401(90)90043-H.

14 Bruno Courcelle. On the expression of graph properties in some fragments of monadic second-order logic. In Neil Immerman and Phokion G. Kolaitis, editors, *Descriptive Complexity and Finite Models: Proceedings of a DIMACS Workshop, January 14–17, 1996, Princeton University, volume 31 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci.*, pages 33–62. American Mathematical Society, Providence, RI, 1997.

15 Bruno Courcelle. The expression of graph properties and graph transformations in monadic second-order logic. In *Handbook of graph grammars and computing by graph transformation, Vol. 1*, pages 313–400. World Scientific, River Edge, NJ, 1997. doi:10.1142/9789812384720_0005.

16 Bruno Courcelle, Joost Engelfriet, and Grzegorz Rozenberg. Handle-rewriting hypergraph grammars. *J. Comput. System Sci.*, 46(2):218–270, 1993. doi:10.1016/0022-0000(93) 90004-G.

17 Bruno Courcelle, J. A. Makowsky, and U. Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. *Theory Comput. Syst.*, 33(2):125–150, 2000. doi:10.1007/s002249910009.

18 Michael Dom, Jiong Guo, Falk Hüffner, and Rolf Niedermeier. Error compensation in leaf root problems. In *International Symposium on Algorithms and Computation*, pages 389–401. Springer, 2004.

19 Michael Dom, Jiong Guo, Falk Hüffner, and Rolf Niedermeier. Extending the tractability border for closest leaf powers. In *International Workshop on Graph-Theoretic Concepts in Computer Science*, pages 397–408. Springer, 2005.

20 David Eppstein, Philipp Kindermann, Stephen Kobourov, Giuseppe Liotta, Anna Lubiw, Aude Maignan, Debajyoti Mondal, Hamideh Vosoughpour, Sue Whitesides, and Stephen Wismath. On the planar split thickness of graphs. *Algorithmica*, 80(3):977–994, 2018. doi:10.1007/s00453-017-0328-y.

21 Walter M. Fitch and Emanuel Margoliash. Construction of phylogenetic trees. *Science*, 155(3760):279–284, 1967. doi:10.1126/science.155.3760.279.

22 Martin Grohe. Computing crossing numbers in quadratic time. In *Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing*, pages 231–236, New York, 2001. ACM. doi:10.1145/380752.380805.

23 Frank Gurski and Egon Wanke. The tree-width of clique-width bounded graphs without $K_{n,n}$. In *International Workshop on Graph-Theoretic Concepts in Computer Science*, pages 196–205. Springer, 2000.

24 Frank Gurski and Egon Wanke. The clique-width of tree-power and leaf-power graphs. In *International Workshop on Graph-Theoretic Concepts in Computer Science*, pages 76–85. Springer, 2007.

25 Rudolf Halin. *S*-functions for graphs. *J. Geometry*, 8(1-2):171–186, 1976. doi:10.1007/BF01917434.

26 Petr Hliněný. Branch-width, parse trees, and monadic second-order logic for matroids. *J. Combin. Theory Ser. B*, 96(3):325–351, 2006. doi:10.1016/j.jctb.2005.08.005.
16:14 Parameterized Leaf Power Recognition

27 William Kennedy, Guohui Lin, and Guiying Yan. Strictly chordal graphs are leaf powers. *J. Discrete Algorithms*, 4(4):511-525, 2006. doi:10.1016/j.jda.2005.06.005.

28 David W. Matula and Leland L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. *J. ACM*, 30(3):417-427, 1983. doi:10.1145/2402.322385.

29 Naomi Nishimura, Prabhakar Ragde, and Dimitrios M. Thilikos. On graph powers for leaf-labeled trees. *J. Algorithms*, 42(1):69-108, 2002. doi:10.1006/jagm.2001.1195.

30 Dieter Rautenbach. Some remarks about leaf roots. *Discrete Math.*, 306(13):1456-1461, 2006. doi:10.1016/j.disc.2006.03.030.

31 Neil Robertson and P. D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. *J. Algorithms*, 7(3):309-322, 1986. doi:10.1016/0196-6774(86)90023-4.
16:14 Parameterized Leaf Power Recognition

27 William Kennedy, Guohui Lin, and Guiying Yan. Strictly chordal graphs are leaf powers. *J. Discrete Algorithms*, 4(4):511-525, 2006. doi:10.1016/j.jda.2005.06.005.

28 David W. Matula and Leland L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. *J. ACM*, 30(3):417-427, 1983. doi:10.1145/2402.322385.

29 Naomi Nishimura, Prabhakar Ragde, and Dimitrios M. Thilikos. On graph powers for leaf-labeled trees. *J. Algorithms*, 42(1):69-108, 2002. doi:10.1006/jagm.2001.1195.

30 Dieter Rautenbach. Some remarks about leaf roots. *Discrete Math.*, 306(13):1456-1461, 2006. doi:10.1016/j.disc.2006.03.030.

31 Neil Robertson and P. D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. *J. Algorithms*, 7(3):309-322, 1986. doi:10.1016/0196-6774(86)90023-4.
# Parameterized Complexity of Independent Set in H-Free Graphs

Édouard Bonnet

Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France

Nicolas Bousquet

CNRS, G-SCOP laboratory, Grenoble-INP, France

Pierre Charbit

Université Paris Diderot, IRIF, France

Stéphan Thomassé

Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France
Institut Universitaire de France

Rémi Watrigant

Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France

**Abstract**

In this paper, we investigate the complexity of MAXIMUM INDEPENDENT SET (MIS) in the class of H-free graphs, that is, graphs excluding a fixed graph as an induced subgraph. Given that the problem remains *NP*-hard for most graphs *H*, we study its fixed-parameter tractability and make progress towards a dichotomy between *FPT* and *W*[1]-hard cases. We first show that MIS remains *W*[1]-hard in graphs forbidding simultaneously *K*₁,₄, any finite set of cycles of length at least 4, and any finite set of trees with at least two branching vertices. In particular, this answers an open question of Dabrowski *et al*. concerning *C*₄-free graphs. Then we extend the polynomial algorithm of Alekseev when *H* is a disjoint union of edges to an *FPT* algorithm when *H* is a disjoint union of cliques. We also provide a framework for solving several other cases, which is a generalization of the concept of *iterative expansion* accompanied by the extraction of a particular structure using Ramsey's theorem. Iterative expansion is a maximization version of the so-called *iterative compression*. We believe that our framework can be of independent interest for solving other similar graph problems. Finally, we present positive and negative results on the existence of polynomial (Turing) kernels for several graphs *H*.

**2012 ACM Subject Classification** Theory of computation → Fixed parameter tractability

**Keywords and phrases** Parameterized Algorithms, Independent Set, H-Free Graphs

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

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

**Funding** É. B. is supported by the LABEX MILYON (ANR-10- LABX-0070) of Université de Lyon, within the program "Investissements d'Avenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR). N. B. and P. C. are supported by the ANR Project DISTANCIA (ANR-17-CE40-0015) operated by the French National Research Agency (ANR).

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

© É. Bonnet, N. Bousquet, P. Charbit, S. Thomassé, and R. Watrigant;

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. 17; pp. 17:1–17:13

Leibniz International Proceedings in Informatics

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

LIPICS

Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
# Parameterized Complexity of Independent Set in H-Free Graphs

Édouard Bonnet

Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France

Nicolas Bousquet

CNRS, G-SCOP laboratory, Grenoble-INP, France

Pierre Charbit

Université Paris Diderot, IRIF, France

Stéphan Thomassé

Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France
Institut Universitaire de France

Rémi Watrigant

Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France

## Abstract

In this paper, we investigate the complexity of MAXIMUM INDEPENDENT SET (MIS) in the class of H-free graphs, that is, graphs excluding a fixed graph as an induced subgraph. Given that the problem remains *NP*-hard for most graphs *H*, we study its fixed-parameter tractability and make progress towards a dichotomy between *FPT* and *W*[1]-hard cases. We first show that MIS remains *W*[1]-hard in graphs forbidding simultaneously *K*₁,₄, any finite set of cycles of length at least 4, and any finite set of trees with at least two branching vertices. In particular, this answers an open question of Dabrowski *et al*. concerning *C*₄-free graphs. Then we extend the polynomial algorithm of Alekseev when *H* is a disjoint union of edges to an *FPT* algorithm when *H* is a disjoint union of cliques. We also provide a framework for solving several other cases, which is a generalization of the concept of *iterative expansion* accompanied by the extraction of a particular structure using Ramsey's theorem. Iterative expansion is a maximization version of the so-called *iterative compression*. We believe that our framework can be of independent interest for solving other similar graph problems. Finally, we present positive and negative results on the existence of polynomial (Turing) kernels for several graphs *H*.

**2012 ACM Subject Classification** Theory of computation → Fixed parameter tractability

**Keywords and phrases** Parameterized Algorithms, Independent Set, H-Free Graphs

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

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

**Funding** É. B. is supported by the LABEX MILYON (ANR-10- LABX-0070) of Université de Lyon, within the program "Investissements d'Avenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR). N. B. and P. C. are supported by the ANR Project DISTANCIA (ANR-17-CE40-0015) operated by the French National Research Agency (ANR).

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

© É. Bonnet, N. Bousquet, P. Charbit, S. Thomassé, and R. Watrigant;

licensed under Creative Commons License CC-BY

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

Editors: Christophe Paul and Michał Pilipczuk; Article No. 17; pp. 17:1–17:13

Leibniz International Proceedings in Informatics

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

LIPICS

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

Given a simple graph $G$, a set of vertices $S \subseteq V(G)$ is an *independent set* if the vertices of this set are all pairwise non-adjacent. Finding an independent set with maximum cardinality is a fundamental problem in algorithmic graph theory, and is known as the MIS problem (MIS, for short) [12]. In general graphs, it is not only $NP$-hard, but also not approximable within $O(n^{1-\epsilon})$ for any $\epsilon > 0$ unless $P = NP$ [20], and $W[1]$-hard [10] (unless otherwise stated, $n$ always denotes the number of vertices of the input graph). Thus, it seems natural to study the complexity of MIS in restricted graph classes. One natural way to obtain such a restricted graph class is to forbid some given pattern to appear in the input. For a fixed graph $H$, we say that a graph is *$H$-free* if it does not contain $H$ as an induced subgraph. Unfortunately, it turns out that for most graphs $H$, MIS in $H$-free graphs remains $NP$-hard, as shown by a very simple reduction first observed by Alekseev:

**Theorem 1 ([1]).** Let $H$ be a connected graph which is neither a path nor a subdivision of the claw. Then MIS is $NP$-hard in $H$-free graphs.

On the positive side, the case of $P_t$-free graphs has attracted a lot of attention during the last decade. While it is still open whether there exists $t \in \mathbb{N}$ for which MIS is $NP$-hard in $P_t$-free graphs, quite involved polynomial-time algorithms were discovered for $P_5$-free graphs [17], and very recently for $P_6$-free graphs [13]. In addition, we can also mention the recent following result: MIS admits a subexponential algorithm running in time $2^{O(\sqrt{\ln \ln n})}$ in $P_t$-free graphs for every $t \in \mathbb{N}$ [3]. The second open question concerns the subdivision of the claw. Let $S_{i,j,j}$ be a tree with exactly three vertices of degree one, being at distance $i$, $j$ and $k$ from the unique vertex of degree three. The complexity of MIS is still open in $S_{1,2,2}$-free graphs and $S_{1,1,3}$-free graphs. In this direction, the only positive results concern some subcases: it is polynomial-time solvable in $(S_{1,2,2}, S_{1,1,3}, \mathit{dart})$-free graphs [15], $(S_{1,1,3}, \mathit{banner})$-free graphs and $(S_{1,1,3}, \mathit{bull})$-free graphs [16], where $\mathit{dart}$, $\mathit{banner}$ and $\mathit{bull}$ are particular graphs on five vertices. Given the large number of graphs $H$ for which the problem remains $NP$-hard, it seems natural to investigate the existence of parameterized algorithms<fnref n="1" />, that is, determining the existence of an independent set of size $k$ in a graph with $n$ vertices in time $O(f(k)n^c)$ for some computable function $f$ and constant $c$. A very simple case concerns $K_r$-free graphs, that is, graphs excluding a clique of size $r$. In that case, Ramsey’s theorem implies that every such graph $G$ admits an independent set of size $\Omega(n^{\frac{1}{r-1}})$, where $n = |V(G)|$. In the $FPT$ vocabulary, it implies that MIS in $K_r$-free graphs has a kernel with $O(k^{r-1})$ vertices.

To the best of our knowledge, the first step towards an extension of this observation within the $FPT$ framework is the work of Dabrowski *et al.* [8] (see also Dabrowski’s PhD manuscript [7]) who showed, among others, that for any positive integer $r$, MAX WEIGHTED INDEPENDENT SET is FPT in $H$-free graphs when $H$ is a clique of size $r$ minus an edge. In the same paper, they settle the parameterized complexity of MIS on almost all the remaining cases of $H$-free graphs when $H$ has at most four vertices. The conclusion is that the problem is $FPT$ on those classes, except for $H = C_4$ which is left open. We answer this question by showing that MIS remains $W[1]$-hard in a subclass of $C_4$-free graphs. On the negative side, it was proved that MIS remains $W[1]$-hard in $K_{1,4}$-free graphs [14].

Finally, we can also mention the case where $H$ is the *bull* graph, which is a triangle with a pending vertex attached to two different vertices. For that case, a polynomial Turing kernel was obtained [19] then improved [11].

<footnote n="1">¹ For the sake of simplicity, “MIS” will denote the optimisation, decision and parameterized version of the problem (in the latter case, the parameter is the size of the solution), the correct use being clear from the context.</footnote>
1 Introduction

Given a simple graph $G$, a set of vertices $S \subseteq V(G)$ is an *independent set* if the vertices of this set are all pairwise non-adjacent. Finding an independent set with maximum cardinality is a fundamental problem in algorithmic graph theory, and is known as the MIS problem (MIS, for short) [12]. In general graphs, it is not only NP-hard, but also not approximable within $O(n^{1-\epsilon})$ for any $\epsilon > 0$ unless $P = NP$ [20], and $W[1]$-hard [10] (unless otherwise stated, $n$ always denotes the number of vertices of the input graph). Thus, it seems natural to study the complexity of MIS in restricted graph classes. One natural way to obtain such a restricted graph class is to forbid some given pattern to appear in the input. For a fixed graph $H$, we say that a graph is *H-free* if it does not contain $H$ as an induced subgraph. Unfortunately, it turns out that for most graphs $H$, MIS in $H$-free graphs remains NP-hard, as shown by a very simple reduction first observed by Alekseev:

**Theorem 1 ([1]).** Let $H$ be a connected graph which is neither a path nor a subdivision of the claw. Then MIS is NP-hard in $H$-free graphs.

On the positive side, the case of $P_t$-free graphs has attracted a lot of attention during the last decade. While it is still open whether there exists $t \in \mathbb{N}$ for which MIS is NP-hard in $P_t$-free graphs, quite involved polynomial-time algorithms were discovered for $P_5$-free graphs [17], and very recently for $P_6$-free graphs [13]. In addition, we can also mention the recent following result: MIS admits a subexponential algorithm running in time $2^{O(\sqrt{\ln \ln n})}$ in $P_t$-free graphs for every $t \in \mathbb{N}$ [3]. The second open question concerns the subdivision of the claw. Let $S_{i,j,j}$ be a tree with exactly three vertices of degree one, being at distance $i$, $j$ and $k$ from the unique vertex of degree three. The complexity of MIS is still open in $S_{1,2,2}$-free graphs and $S_{1,1,3}$-free graphs. In this direction, the only positive results concern some subcases: it is polynomial-time solvable in $(S_{1,2,2}, S_{1,1,3}, \mathit{dart})$-free graphs [15], $(S_{1,1,3}, \mathit{banner})$-free graphs and $(S_{1,1,3}, \mathit{bull})$-free graphs [16], where $\mathit{dart}$, $\mathit{banner}$ and $\mathit{bull}$ are particular graphs on five vertices. Given the large number of graphs $H$ for which the problem remains NP-hard, it seems natural to investigate the existence of parameterized algorithms<fnref n="1" />, that is, determining the existence of an independent set of size $k$ in a graph with $n$ vertices in time $O(f(k)n^c)$ for some computable function $f$ and constant $c$. A very simple case concerns $K_r$-free graphs, that is, graphs excluding a clique of size $r$. In that case, Ramsey’s theorem implies that every such graph $G$ admits an independent set of size $\Omega(n^{\frac{1}{r-1}})$, where $n = |V(G)|$. In the $\mathit{FPT}$ vocabulary, it implies that MIS in $K_r$-free graphs has a kernel with $O(k^{r-1})$ vertices.

To the best of our knowledge, the first step towards an extension of this observation within the $\mathit{FPT}$ framework is the work of Dabrowski et al. [8] (see also Dabrowski’s PhD manuscript [7]) who showed, among others, that for any positive integer $r$, MAX WEIGHTED INDEPENDENT SET is FPT in $H$-free graphs when $H$ is a clique of size $r$ minus an edge. In the same paper, they settle the parameterized complexity of MIS on almost all the remaining cases of $H$-free graphs when $H$ has at most four vertices. The conclusion is that the problem is $\mathit{FPT}$ on those classes, except for $H = C_4$ which is left open. We answer this question by showing that MIS remains $W[1]$-hard in a subclass of $C_4$-free graphs. On the negative side, it was proved that MIS remains $W[1]$-hard in $K_{1,4}$-free graphs [14].

Finally, we can also mention the case where $H$ is the *bull* graph, which is a triangle with a pending vertex attached to two different vertices. For that case, a polynomial Turing kernel was obtained [19] then improved [11].

<footnote n="1">¹ For the sake of simplicity, “MIS” will denote the optimisation, decision and parameterized version of the problem (in the latter case, the parameter is the size of the solution), the correct use being clear from the context.</footnote>
## 1.1 Our results

In Section 2, we present three reductions proving $W[1]$-hardness of MIS in graph excluding several graphs as induced subgraphs, such as $K_{1,4}$, any fixed cycle of length at least four, and any fixed tree with two branching vertices. In Section 3, we extend the polynomial algorithm of Alekseev when $H$ is a disjoint union of edges to an $FPT$ algorithm when $H$ is a disjoint union of cliques. In Section 4, we present a general framework extending the technique of *iterative expansion*, which itself is the maximization version of the well-known iterative compression technique. We apply this framework to provide $FPT$ algorithms when $H$ is a clique minus a complete bipartite graph, or when $H$ is a clique minus a triangle. Finally, in Section 5, we focus on the existence of polynomial (Turing) kernels. We first strenghten some results of the previous section by providing polynomial (Turing) kernels in the case where $H$ is a clique minus a claw. Then, we prove that for many $H$, MIS on $H$-free graphs does not admit a polynomial kernel, unless $NP \subseteq coNP/poly$. Our results allows to obtain the complete dichotomy polynomial/polynomial kernel (PK)/no PK but polynomial Turing kernel/$W[1]$-hard for all possible graphs on four vertices, while only five graphs on five vertices remain open for the $FPT/W[1]$-hard dichotomy.

Due to space restrictions, proofs marked with a (⋆) were omitted, and can be found in the long version of the paper [4]. This long version also contains additional figures, and two variants of the reduction presented in the next section, together with a discussion.

## 1.2 Notation

For classical notation related to graph theory or fixed-parameter tractable algorithms, we refer the reader to the monographs [9] and [10], respectively. For an integer $r \ge 2$ and a graph $H$ with vertex set $V(H) = \{v_1, \dots, v_{n_H}\}$ with $n_H \le r$, we denote by $K_r \setminus H$ the graph with vertex set $\{1, \dots, r\}$ and edge set $\{ab : 1 \le a, b \le r \text{ such that } v avb \notin E(H)\}$. For $X \subseteq V(G)$, we write $G \setminus X$ to denote $G[V(G) \setminus X]$. For two graphs $G$ and $H$, we denote by $G \uplus H$ the *disjoint union* operation, that is, the graph with vertex set $V(G) \cup V(H)$ and edge set $E(G) \cup E(H)$. We denote by $G + H$ the *join* operation of $G$ and $H$, that is, the graph with vertex set $V(G) \cup V(H)$ and edge set $E(G) \cup E(H) \cup \{uv : u \in V(G), v \in V(H)\}$. For two integers $r, k$, we denote by $Ram(r, k)$ the Ramsey number of $r$ and $k$, i.e. the minimum order of a graph to contain either a clique of size $r$ or an independent set of size $k$. We write for short $Ram(k) = Ram(k, k)$. Finally, for $\ell, k > 0$, we denote by $Ram_\ell(k)$ the minimum order of a complete graph whose edges are colored with $\ell$ colors to contain a monochromatic clique of size $k$.

## 2 W[1]-hardness

**▶ Theorem 2.** For any $p_1 \ge 4$ and $p_2 \ge 1$, MIS remains $W[1]$-hard in graphs excluding simultaneously the following graphs as induced subgraphs: $K_{1,4}$, $C_4$, ..., $C_{p_1}$ and any tree $T$ with two branching vertices<fnref n="2" /> at distance at most $p_2$.

**Proof.** Let $p = \max\{p_1, p_2\}$. We reduce from GRID TILING, where the input is composed of $k^2$ sets $S_{i,j} \subseteq [m] \times [m]$ ($0 \le i, j \le k-1$), called *tiles*, each composed of $n$ elements. The objective of GRID TILING is to find an element $s_{i,j}^* \in S_{i,j}$ for each $0 \le i, j \le k-1$, such that $s_{i,j}^*$ agrees in the first coordinate with $s_{i,j+1}^*$, and agrees in the second coordinate with $s_{i+1,j}^*$,

<footnote n="2">² A branching vertex in a tree is a vertex of degree at least 3.</footnote>
## 1.1 Our results

In Section 2, we present three reductions proving $W[1]$-hardness of MIS in graph excluding several graphs as induced subgraphs, such as $K_{1,4}$, any fixed cycle of length at least four, and any fixed tree with two branching vertices. In Section 3, we extend the polynomial algorithm of Alekseev when $H$ is a disjoint union of edges to an $FPT$ algorithm when $H$ is a disjoint union of cliques. In Section 4, we present a general framework extending the technique of *iterative expansion*, which itself is the maximization version of the well-known iterative compression technique. We apply this framework to provide $FPT$ algorithms when $H$ is a clique minus a complete bipartite graph, or when $H$ is a clique minus a triangle. Finally, in Section 5, we focus on the existence of polynomial (Turing) kernels. We first strenghten some results of the previous section by providing polynomial (Turing) kernels in the case where $H$ is a clique minus a claw. Then, we prove that for many $H$, MIS on $H$-free graphs does not admit a polynomial kernel, unless $NP \subseteq coNP/poly$. Our results allows to obtain the complete dichotomy polynomial/polynomial kernel (PK)/no PK but polynomial Turing kernel/$W[1]$-hard for all possible graphs on four vertices, while only five graphs on five vertices remain open for the $FPT/W[1]$-hard dichotomy.

Due to space restrictions, proofs marked with a (⋆) were omitted, and can be found in the long version of the paper [4]. This long version also contains additional figures, and two variants of the reduction presented in the next section, together with a discussion.

## 1.2 Notation

For classical notation related to graph theory or fixed-parameter tractable algorithms, we refer the reader to the monographs [9] and [10], respectively. For an integer $r \ge 2$ and a graph $H$ with vertex set $V(H) = \{v_1, \dots, v_{n_H}\}$ with $n_H \le r$, we denote by $K_r \setminus H$ the graph with vertex set $\{1, \dots, r\}$ and edge set $\{ab : 1 \le a, b \le r \text{ such that } v avb \notin E(H)\}$. For $X \subseteq V(G)$, we write $G \setminus X$ to denote $G[V(G) \setminus X]$. For two graphs $G$ and $H$, we denote by $G \uplus H$ the *disjoint union* operation, that is, the graph with vertex set $V(G) \cup V(H)$ and edge set $E(G) \cup E(H)$. We denote by $G + H$ the *join* operation of $G$ and $H$, that is, the graph with vertex set $V(G) \cup V(H)$ and edge set $E(G) \cup E(H) \cup \{uv : u \in V(G), v \in V(H)\}$. For two integers $r, k$, we denote by $Ram(r, k)$ the Ramsey number of $r$ and $k$, i.e. the minimum order of a graph to contain either a clique of size $r$ or an independent set of size $k$. We write for short $Ram(k) = Ram(k, k)$. Finally, for $\ell, k > 0$, we denote by $Ram_\ell(k)$ the minimum order of a complete graph whose edges are colored with $\ell$ colors to contain a monochromatic clique of size $k$.

## 2 W[1]-hardness

**Theorem 2.** For any $p_1 \ge 4$ and $p_2 \ge 1$, MIS remains $W[1]$-hard in graphs excluding simultaneously the following graphs as induced subgraphs: $K_{1,4}$, $C_4$, ..., $C_{p_1}$ and any tree $T$ with two branching vertices<fnref n="2" /> at distance at most $p_2$.

*Proof.* Let $p = \max\{p_1, p_2\}$. We reduce from GRID TILING, where the input is composed of $k^2$ sets $S_{i,j} \subseteq [m] \times [m]$ ($0 \le i, j \le k-1$), called *tiles*, each composed of $n$ elements. The objective of GRID TILING is to find an element $s_{i,j}^* \in S_{i,j}$ for each $0 \le i, j \le k-1$, such that $s_{i,j}^*$ agrees in the first coordinate with $s_{i,j+1}^*$, and agrees in the second coordinate with $s_{i+1,j}^*$,

<footnote n="2">² A branching vertex in a tree is a vertex of degree at least 3.</footnote>
<figure><img src="image_93.png" /><figcaption>■ **Figure 1** Gadget $TG^{i,j}$ representing a tile and its adjacencies with $TG_{i,j-1}$ and $TG_{i,j+1}$, for $p=1$. Each circle is a clique on $n$ vertices (dashed cliques are the cycle cliques). Black, blue and red arrows represent respectively type $T_h$, $T_r$ and $T_c$ edges (bold arrows are between two gadgets).</figcaption></figure>

for every $0 \le i, j \le k-1$ (incrementations of $i$ and $j$ are done modulo $k$). In such case, we say that $\{s_{i,j}^*, 0 \le i, j \le k-1\}$ is a feasible solution of the instance. It is known that GRID TILING is $W[1]$-hard parameterized by $k$ [6].

Before describing formally the reduction, let us give some definitions and ideas. Given $s = (a, b)$ and $s' = (a', b')$, we say that $s$ is row-compatible (resp. column-compatible) with $s'$ if $a \ge a'$ (resp. $b \ge b')^3$. Observe that a solution $\{s_{i,j}^*, 0 \le i, j \le k-1\}$ is feasible if and only if $s_{i,j}^*$ is row-compatible with $s_{i,j+1}^*$ and column-compatible with $s_{i+1,j}^*$ for every $0 \le i, j \le k-1$ (incrementations of $i$ and $j$ are done modulo $k$). Informally, the main idea of the reduction is that, when representing a tile by a clique, the row-compatibility (resp. column-compatibility) relation (as well at its complement) forms a $C_4$-free graph when considering two consecutive tiles, and a claw-free graph when considering three consecutive tiles. The main difficulty is to forbid the desired graphs to appear in the “branchings” of tiles. We now describe the reduction.

For every tile $S_{i,j} = \{s_1^{i,j}, \dots, s_n^{i,j}\}$, we construct a tile gadget $TG_{i,j}$, depicted in Figure 1. Notice that this gadget shares some ideas with the $W[1]$-hardness of the problem in $K_{1,4}$-free graphs by Hermelin et al. [14]. To define this gadget, we first describe an oriented graph with three types of arcs (type $T_h$, $T_r$ and $T_c$, which respectively stands for *half graph*, *row* and *column*, this meaning will become clearer later), and then explain how to represent the vertices and arcs of this graph to get the concrete gadget. Consider first a directed cycle on $4p+4$ vertices $c_1, \dots, c_{4p+4}$ with arcs of type $T_h$. Then consider four oriented paths on $p+1$ vertices: $P_1, P_2, P_3$ and $P_4$. $P_1$ and $P_3$ are composed of arcs of type $T_c$, while $P_2$ and $P_4$ are composed of arcs of type $T_r$. Put an arc of type $T_c$ between the last vertex of $P_1$ and $c_1$, an arc of type $T_c$ between $c_{2p+3}$ and the first vertex of $P_3$, an arc of type $T_r$ between $c_{p+2}$ and the first vertex of $P_2$, and an arc of type $T_r$ between the last vertex of $P_4$ and $c_{3p+4}$.

<footnote n="3">³ Notice that the row-compatibility (resp. column-compatibility) relation is not symmetrical.</footnote>
<figure><img src="image_96.png" /><figcaption>■ **Figure 1** Gadget $TG^{i,j}$ representing a tile and its adjacencies with $TG_{i,j-1}$ and $TG_{i,j+1}$, for $p=1$. Each circle is a clique on $n$ vertices (dashed cliques are the cycle cliques). Black, blue and red arrows represent respectively type $T_h$, $T_r$ and $T_c$ edges (bold arrows are between two gadgets).</figcaption></figure>

for every $0 \le i, j \le k-1$ (incrementations of $i$ and $j$ are done modulo $k$). In such case, we say that $\{s_{i,j}^*, 0 \le i, j \le k-1\}$ is a feasible solution of the instance. It is known that GRID TILING is $W[1]$-hard parameterized by $k$ [6].

Before describing formally the reduction, let us give some definitions and ideas. Given $s = (a, b)$ and $s' = (a', b')$, we say that $s$ is row-compatible (resp. column-compatible) with $s'$ if $a \ge a'$ (resp. $b \ge b')^3$. Observe that a solution $\{s_{i,j}^*, 0 \le i, j \le k-1\}$ is feasible if and only if $s_{i,j}^*$ is row-compatible with $s_{i,j+1}^*$ and column-compatible with $s_{i+1,j}^*$ for every $0 \le i, j \le k-1$ (incrementations of $i$ and $j$ are done modulo $k$). Informally, the main idea of the reduction is that, when representing a tile by a clique, the row-compatibility (resp. column-compatibility) relation (as well at its complement) forms a $C_4$-free graph when considering two consecutive tiles, and a claw-free graph when considering three consecutive tiles. The main difficulty is to forbid the desired graphs to appear in the “branchings” of tiles. We now describe the reduction.

For every tile $S_{i,j} = \{s_1^{i,j}, \dots, s_n^{i,j}\}$, we construct a tile gadget $TG_{i,j}$, depicted in Figure 1. Notice that this gadget shares some ideas with the $W[1]$-hardness of the problem in $K_{1,4}$-free graphs by Hermelin et al. [14]. To define this gadget, we first describe an oriented graph with three types of arcs (type $T_h$, $T_r$ and $T_c$, which respectively stands for *half graph*, *row* and *column*, this meaning will become clearer later), and then explain how to represent the vertices and arcs of this graph to get the concrete gadget. Consider first a directed cycle on $4p+4$ vertices $c_1, \dots, c_{4p+4}$ with arcs of type $T_h$. Then consider four oriented paths on $p+1$ vertices: $P_1, P_2, P_3$ and $P_4$. $P_1$ and $P_3$ are composed of arcs of type $T_c$, while $P_2$ and $P_4$ are composed of arcs of type $T_r$. Put an arc of type $T_c$ between the last vertex of $P_1$ and $c_1$, an arc of type $T_c$ between $c_{2p+3}$ and the first vertex of $P_3$, an arc of type $T_r$ between $c_{p+2}$ and the first vertex of $P_2$, and an arc of type $T_r$ between the last vertex of $P_4$ and $c_{3p+4}$.

<footnote n="3">³ Notice that the row-compatibility (resp. column-compatibility) relation is not symmetrical.</footnote>
Now, replace every vertex of this oriented graph by a clique on $n$ vertices, and fix an arbitrary ordering on the vertices of each clique. For each arc of type $T_h$ between $c$ and $c'$, add a half graph$^4$ between the corresponding cliques: connect the $a^{th}$ vertex of the clique representing $c$ with the $b^{th}$ vertex of the clique representing $c'$ iff $a > b$. For every arc of type $T_r$ from a vertex $c$ to a vertex $c'$, connect the $a^{th}$ vertex of the clique representing $c$ with the $b^{th}$ vertex of the clique representing $c'$ iff $s_a^{i,j}$ is not row-compatible with $s_b^{i,j}$. Similarly, for every arc of type $T_c$ from a vertex $c$ to a vertex $c'$, connect the $a^{th}$ vertex of the clique representing $C$ with the $b^{th}$ vertex of the clique representing $c'$ iff $s_a^{i,j}$ is not column-compatible with $s_b^{i,j}$. The cliques corresponding to vertices of this gadget are called the main cliques of $TG_{i,j}$, and the cliques corresponding to the central cycle on $4p+4$ vertices are called the cycle cliques. The main cliques which are not cycle cliques are called path cliques. The cycle cliques adjacent to one path clique are called branching cliques. Finally, the clique corresponding to the vertex of degree one in the path attached to $c_1$ (resp. $c_{p+2}$, $c_{2p+3}$, $c_{3p+4}$) is called the top (resp. right, bottom, left) clique of $TG_{i,j}$, denoted by $T_{i,j}$ (resp. $R_{i,j}$, $B_{i,j}$, $L_{i,j}$). Let $T_{i,j} = \{t_1^{i,j}, \dots, t_1^{i,j}\}$, $R_{i,j} = \{r_1^{i,j}, \dots, r_1^{i,j}\}$, $B_{i,j} = \{b_1^{i,j}, \dots, b_1^{i,j}\}$, and $L_{i,j} = \{\ell_1^{i,j}, \dots, \ell_n^{i,j}\}$. For the sake of readability, we might omit the superscripts $i,j$ when it is clear from the context.

**Lemma 3.** (⋆) Let $K$ be an independent set of size $8(p+1)$ in $TG_{i,j}$. Then:

(a) $K$ intersects all the cycle cliques on the same index $x$;

(b) if $K \cap T_{i,j} = \{t_{x_t}\}$, $K \cap R_{i,j} = \{r_{x_r}\}$, $K \cap B_{i,j} = \{b_{x_b}\}$, and $K \cap L_{i,j} = \{\ell_{x_\ell}\}$. Then:

- $s_{x_\ell}^{i,j}$ is row-compatible with $s_x^{i,j}$ which is row-compatible with $s_{x_r}^{i,j}$, and

- $s_{x_t}^{i,j}$ is column-compatible with $s_x^{i,j}$ which is column-compatible with $s_{x_b}^{i,j}$.

For $i,j \in \{0, \dots, k-1\}$, we connect the right clique of $TG_{i,j}$ with the left clique of $TG_{i,j+1}$ in a “type $T_r$ spirit”: for every $x, y \in [n]$, connect $r_x^{i,j} \in R_{i,j}$ with $\ell_y^{i,j+1} \in L_{i,j+1}$ iff $s_x^{i,j}$ is not row-compatible with $s_y^{i,j+1}$. Similarly, we connect the bottom clique of $TG_{i,j}$ with the top clique of $TG_{i+1,j}$ in a “type $T_c$ spirit”: for every $x, y \in [n]$, connect $b_x^{i,j} \in B_{i,j}$ with $t_y^{i+1,j} \in T_{i+1,j}$ iff $s_x^{i,j}$ is not column-compatible with $s_y^{i+1,j}$ (all incrementations of $i$ and $j$ are done modulo $k$). This terminates the construction of the graph $G$.

**Lemma 4.** (⋆) The input instance of GRID TILING is positive if and only if $G$ has an independent set of size $k' = 8(p+1)k^2$.

Let us now prove that $G$ does not contain the graphs mentioned in the statement as an induced subgraph:

(i) $K_{1,4}$: we first prove that for every $0 \le i, j \le k-1$, the graph induced by the cycle cliques of $TG_{i,j}$ is claw-free. For the sake of contradiction, suppose that there exist three consecutive cycle cliques $A, B$ and $C$ containing a claw. W.l.o.g. we may assume that $b_x \in B$ is the center of the claw, and $a_\alpha \in A$, $b_\beta \in B$ and $c_\gamma \in C$ are the three endpoints. By construction of the gadgets (there is a half graph between $A$ and $B$ and between $B$ and $C$), we must have $\alpha < x < \gamma$. Now, observe that if $x < \beta$ then $a_\alpha$ must be adjacent to $b_\beta$, and if $\beta < x$, then $b_\beta$ must be adjacent to $c_\gamma$, but both case are impossible since $\{a_\alpha, b_\beta, c_\gamma\}$ is supposed to be an independent set. Similarly, we can prove that the graph induced by each path of size $2(p+1)$ linking two consecutive gadgets is claw-free. Hence, the only way for $K_{1,4}$ to appear in $G$ would be that

<footnote>$^4$ Notice that our definition of half graph slightly differs from the usual one, in the sense that we do not put edges relying two vertices of the same index. Hence, our construction can actually be seen as the complement of a half graph (which is consistent with the fact that usually, both parts of a half graph are independent sets, while they are cliques in our gadgets).</footnote>
Now, replace every vertex of this oriented graph by a clique on $n$ vertices, and fix an arbitrary ordering on the vertices of each clique. For each arc of type $T_h$ between $c$ and $c'$, add a half graph$^4$ between the corresponding cliques: connect the $a^{th}$ vertex of the clique representing $c$ with the $b^{th}$ vertex of the clique representing $c'$ iff $a > b$. For every arc of type $T_r$ from a vertex $c$ to a vertex $c'$, connect the $a^{th}$ vertex of the clique representing $c$ with the $b^{th}$ vertex of the clique representing $c'$ iff $s_a^{i,j}$ is not row-compatible with $s_b^{i,j}$. Similarly, for every arc of type $T_c$ from a vertex $c$ to a vertex $c'$, connect the $a^{th}$ vertex of the clique representing $C$ with the $b^{th}$ vertex of the clique representing $c'$ iff $s_a^{i,j}$ is not column-compatible with $s_b^{i,j}$. The cliques corresponding to vertices of this gadget are called the main cliques of $TG_{i,j}$, and the cliques corresponding to the central cycle on $4p+4$ vertices are called the cycle cliques. The main cliques which are not cycle cliques are called path cliques. The cycle cliques adjacent to one path clique are called branching cliques. Finally, the clique corresponding to the vertex of degree one in the path attached to $c_1$ (resp. $c_{p+2}$, $c_{2p+3}$, $c_{3p+4}$) is called the top (resp. right, bottom, left) clique of $TG_{i,j}$, denoted by $T_{i,j}$ (resp. $R_{i,j}$, $B_{i,j}$, $L_{i,j}$). Let $T_{i,j} = \{t_1^{i,j}, \dots, t_1^{i,j}\}$, $R_{i,j} = \{r_1^{i,j}, \dots, r_1^{i,j}\}$, $B_{i,j} = \{b_1^{i,j}, \dots, b_1^{i,j}\}$, and $L_{i,j} = \{\ell_1^{i,j}, \dots, \ell_n^{i,j}\}$. For the sake of readability, we might omit the superscripts $i,j$ when it is clear from the context.

**Lemma 3.** (⋆) Let $K$ be an independent set of size $8(p+1)$ in $TG_{i,j}$. Then:

(a) $K$ intersects all the cycle cliques on the same index $x$;

(b) if $K \cap T_{i,j} = \{t_{x_t}\}$, $K \cap R_{i,j} = \{r_{x_r}\}$, $K \cap B_{i,j} = \{b_{x_b}\}$, and $K \cap L_{i,j} = \{\ell_{x_\ell}\}$. Then:

- $s_{x_\ell}^{i,j}$ is row-compatible with $s_x^{i,j}$ which is row-compatible with $s_{x_r}^{i,j}$, and

- $s_{x_t}^{i,j}$ is column-compatible with $s_x^{i,j}$ which is column-compatible with $s_{x_b}^{i,j}$.

For $i,j \in \{0, \dots, k-1\}$, we connect the right clique of $TG_{i,j}$ with the left clique of $TG_{i,j+1}$ in a “type $T_r$ spirit”: for every $x, y \in [n]$, connect $r_x^{i,j} \in R_{i,j}$ with $\ell_y^{i,j+1} \in L_{i,j+1}$ iff $s_x^{i,j}$ is not row-compatible with $s_y^{i,j+1}$. Similarly, we connect the bottom clique of $TG_{i,j}$ with the top clique of $TG_{i+1,j}$ in a “type $T_c$ spirit”: for every $x, y \in [n]$, connect $b_x^{i,j} \in B_{i,j}$ with $t_y^{i+1,j} \in T_{i+1,j}$ iff $s_x^{i,j}$ is not column-compatible with $s_y^{i+1,j}$ (all incrementations of $i$ and $j$ are done modulo $k$). This terminates the construction of the graph $G$.

**Lemma 4.** (⋆) The input instance of GRID TILING is positive if and only if $G$ has an independent set of size $k' = 8(p+1)k^2$.

Let us now prove that $G$ does not contain the graphs mentioned in the statement as an induced subgraph:

(i) $K_{1,4}$: we first prove that for every $0 \le i, j \le k-1$, the graph induced by the cycle cliques of $TG_{i,j}$ is claw-free. For the sake of contradiction, suppose that there exist three consecutive cycle cliques $A, B$ and $C$ containing a claw. W.l.o.g. we may assume that $b_x \in B$ is the center of the claw, and $a_\alpha \in A$, $b_\beta \in B$ and $c_\gamma \in C$ are the three endpoints. By construction of the gadgets (there is a half graph between $A$ and $B$ and between $B$ and $C$), we must have $\alpha < x < \gamma$. Now, observe that if $x < \beta$ then $a_\alpha$ must be adjacent to $b_\beta$, and if $\beta < x$, then $b_\beta$ must be adjacent to $c_\gamma$, but both case are impossible since $\{a_\alpha, b_\beta, c_\gamma\}$ is supposed to be an independent set. Similarly, we can prove that the graph induced by each path of size $2(p+1)$ linking two consecutive gadgets is claw-free. Hence, the only way for $K_{1,4}$ to appear in $G$ would be that

<footnote>$^4$ Notice that our definition of half graph slightly differs from the usual one, in the sense that we do not put edges relying two vertices of the same index. Hence, our construction can actually be seen as the complement of a half graph (which is consistent with the fact that usually, both parts of a half graph are independent sets, while they are cliques in our gadgets).</footnote>
the center appears in the cycle clique attached to a path, for instance in the clique represented by the vertex $c_1$ in the cycle. However, it can easily be seen that in this case, a claw must lie either in the graph induced by the cycle cliques of the gadget, or in the path linking $TG_{i,j}$ with $TG_{i-1,j}$, which is impossible.

(ii) $C_4, \dots, C_{p_1}$. The main argument is that the graph induced by any two main cliques does not contain any of these cycles. Then, we show that such a cycle cannot lie entirely in the cycle cliques of a single gadget $TG_{i,j}$. Indeed, if this cycle uses at most one vertex per main clique, then it must be of length at least $4p+4$. If it intersects a clique $C$ on two vertices, then either it also intersect all the cycle cliques of the gadget, in which case it is of length $4p+5$, or it intersects an adjacent clique of $C$ on two vertices, in which case these two cliques induce a $C_4$, which is impossible. Similarly, such a cycle cannot lie entirely in a path between the main cliques of two gadgets. Finally, the main cliques of two gadgets are at distance $2(p+1)$, hence such a cycle cannot intersect the main cliques of two gadgets.

(iii) any tree $T$ with two branching vertices at distance at most $p_2$. Using the same argument as for the $K_{1,4}$ case, observe that the claws contained in $G$ can only appear in the cycle cliques where the paths are attached. However, observe that these cliques are at distance $2(p+1) > p_2$, thus, such a tree $T$ cannot appear in $G$. ◀

3 Positive results I: disjoint union of cliques

For $r, q \ge 1$, let $K_r^q$ be the disjoint union of $q$ copies of $K_r$. The following proof is inspired by the case $r=2$ by Alekseev [2].

► **Theorem 5.** MAXIMUM INDEPENDENT SET is FPT in $K_r^q$-free graphs.

**Proof.** We will prove by induction on $q$ that a $K_r^q$-free graph has an independent set of size $k$ or has at most $(Ram(r,k)+1)^{qk}n^{qr}$ independent sets. This will give the desired FPT-algorithm, as the proof shows how to construct this collection of independent sets. Note that the case $q=1$ is trivial by Ramsey's theorem.

Let $G$ be a $K_r^q$-free graph and let $<$ be any fixed total ordering of $V(G)$ such that the largest vertex in this ordering belongs to a clique of size $r$ (the case where $G$ is $K_r$-free is trivial by Ramsey's theorem). For any vertex $x$, define $x^+ = \{y, x < y\}$ and $x^- = V(G) \setminus x^+$ (hence, $x \in x^-$).

Let $C$ be a fixed clique of size $r$ in $G$ and let $c$ be the largest vertex of $C$ with respect to $<$. Let $V_1$ be the set of vertices of $c^+$ which have no neighbor in $C$. Note that $V_1$ induces a $K_r^{q-1}$-free graph, so by induction either it contains an independent set of size $k$, and so does $G$, or it has at most $(Ram(r,k)+1)^{(q-1)k}n^{(q-1)r}$ independent sets. In the latter case, let $S_1$ be the set of all independent sets of $G[V_1]$.

Now in a second phase we define an initially empty set $S_C$ and do the following. For each independent set $S_1$ in $S_1$ (including the empty set), we denote by $V_2$ the set of vertices in $c^-$ that have no neighbor in $S_1$ (notice that $c \in V_2$). For every choice of a vertex $x$ amongst the largest $(Ram(r,k)+1)$ vertices of $V_2$ in the order, we add $x$ to $S_1$ and modify $V_2$ in order to keep only vertices that are smaller than $x$ (with respect to $<$) and not adjacent to $x$. We repeat this operation $k$ times (or less if $V_2$ becomes empty) and, at the end, we either find an independent set of size $k$ or add $S_1$ to $S_C$. By doing so we construct a family of at most $(Ram(r,k)+1)^k$ independent sets for each $S_1$, so in total we get indeed at most $(Ram(r,k)+1)^{kq}n^{(q-1)r}$ independent sets for each clique $C$. Finally we define $S$ as the union over all $r$-cliques $C$ of the sets $S_C$, so that $S$ has size at most the desired number.
the center appears in the cycle clique attached to a path, for instance in the clique represented by the vertex $c_1$ in the cycle. However, it can easily be seen that in this case, a claw must lie either in the graph induced by the cycle cliques of the gadget, or in the path linking $TG_{i,j}$ with $TG_{i-1,j}$, which is impossible.

(ii) $C_4, \dots, C_{p_1}$. The main argument is that the graph induced by any two main cliques does not contain any of these cycles. Then, we show that such a cycle cannot lie entirely in the cycle cliques of a single gadget $TG_{i,j}$. Indeed, if this cycle uses at most one vertex per main clique, then it must be of length at least $4p+4$. If it intersects a clique $C$ on two vertices, then either it also intersect all the cycle cliques of the gadget, in which case it is of length $4p+5$, or it intersects an adjacent clique of $C$ on two vertices, in which case these two cliques induce a $C_4$, which is impossible. Similarly, such a cycle cannot lie entirely in a path between the main cliques of two gadgets. Finally, the main cliques of two gadgets are at distance $2(p+1)$, hence such a cycle cannot intersect the main cliques of two gadgets.

(iii) any tree $T$ with two branching vertices at distance at most $p_2$. Using the same argument as for the $K_{1,4}$ case, observe that the claws contained in $G$ can only appear in the cycle cliques where the paths are attached. However, observe that these cliques are at distance $2(p+1) > p_2$, thus, such a tree $T$ cannot appear in $G$. ◀

3 Positive results I: disjoint union of cliques

For $r, q \ge 1$, let $K_r^q$ be the disjoint union of $q$ copies of $K_r$. The following proof is inspired by the case $r=2$ by Alekseev [2].

► **Theorem 5.** MAXIMUM INDEPENDENT SET is FPT in $K_r^q$-free graphs.

**Proof.** We will prove by induction on $q$ that a $K_r^q$-free graph has an independent set of size $k$ or has at most $(Ram(r,k)+1)^{qk}n^{qr}$ independent sets. This will give the desired FPT-algorithm, as the proof shows how to construct this collection of independent sets. Note that the case $q=1$ is trivial by Ramsey's theorem.

Let $G$ be a $K_r^q$-free graph and let $<$ be any fixed total ordering of $V(G)$ such that the largest vertex in this ordering belongs to a clique of size $r$ (the case where $G$ is $K_r$-free is trivial by Ramsey's theorem). For any vertex $x$, define $x^+ = \{y, x < y\}$ and $x^- = V(G) \setminus x^+$ (hence, $x \in x^-$).

Let $C$ be a fixed clique of size $r$ in $G$ and let $c$ be the largest vertex of $C$ with respect to $<$. Let $V_1$ be the set of vertices of $c^+$ which have no neighbor in $C$. Note that $V_1$ induces a $K_r^{q-1}$-free graph, so by induction either it contains an independent set of size $k$, and so does $G$, or it has at most $(Ram(r,k)+1)^{(q-1)k}n^{(q-1)r}$ independent sets. In the latter case, let $S_1$ be the set of all independent sets of $G[V_1]$.

Now in a second phase we define an initially empty set $S_C$ and do the following. For each independent set $S_1$ in $S_1$ (including the empty set), we denote by $V_2$ the set of vertices in $c^-$ that have no neighbor in $S_1$ (notice that $c \in V_2$). For every choice of a vertex $x$ amongst the largest $(Ram(r,k)+1)$ vertices of $V_2$ in the order, we add $x$ to $S_1$ and modify $V_2$ in order to keep only vertices that are smaller than $x$ (with respect to $<$) and not adjacent to $x$. We repeat this operation $k$ times (or less if $V_2$ becomes empty) and, at the end, we either find an independent set of size $k$ or add $S_1$ to $S_C$. By doing so we construct a family of at most $(Ram(r,k)+1)^k$ independent sets for each $S_1$, so in total we get indeed at most $(Ram(r,k)+1)^{kq}n^{(q-1)r}$ independent sets for each clique $C$. Finally we define $S$ as the union over all $r$-cliques $C$ of the sets $S_C$, so that $S$ has size at most the desired number.
We claim that if $\mathcal{G}$ does not contain an independent set of size $k$, then $\mathcal{S}$ contains all independent sets of $\mathcal{G}$. It suffices to prove that for every independent set $\mathcal{S}$, there exists a clique $\mathcal{C}$ for which $\mathcal{S} \in \mathcal{S}_{\mathcal{C}}$. Let $\mathcal{S}$ be an independent set, and define $\mathcal{C}$ to be a clique of size $r$ such that its largest vertex $c$ (with respect to $<$) satisfies the conditions:

- no vertex of $\mathcal{C}$ is adjacent to a vertex of $\mathcal{S} \cap c^+$, and

- $c$ is the smallest vertex such that a clique $\mathcal{C}$ satisfying the first item exists.

First remark that such a clique always exist, since we assumed that the largest vertex $c_{\text{last}}$ of $< \mathcal{S}$ is contained in a clique of size $r$, which means that $\mathcal{S} \cap c_{\text{last}}^+$ is empty and thus the first item is vacuously satisfied. Secondly, note that several cliques $\mathcal{C}$ might satisfy the two previous conditions. In that case, pick one such clique arbitrarily. This definition of $\mathcal{C}$ and $c$ ensures that $\mathcal{S} \cap c^+$ is an independent set in the set $V_1$ defined in the construction above (it might be empty, but we also consider this case). Thus, it will be picked in the second phase as some $S_1 \in S_1$ and for this choice, each time $V_2$ is considered, the fact that $\mathcal{C}$ is chosen to minimize its largest element $c$ guarantees that there must be a vertex of $\mathcal{S}$ in the $(\text{Ram}(r, k) + 1)$ largest vertices in $V_2$: either $c \in \mathcal{S}$ and we are done, or $\mathcal{S}$ must intersect one of the $\text{Ram}(r, k)$ largest elements of $V_2 \setminus \{c\}$, otherwise there would be an $r$-clique contradicting the choice of $\mathcal{C}$. This shows that $\mathcal{S} \in \mathcal{S}_{\mathcal{C}}$, which concludes our proof. ◀

# 4 Positive results II

## 4.1 Key ingredient: Iterative expansion and Ramsey extraction

In this section, we present the main idea of our algorithms. It is a generalization of iterative expansion, which itself is the maximization version of the well-known iterative compression technique. Iterative compression is a useful tool for designing parameterized algorithms for subset problems (i.e. problems where a solution is a subset of some set of elements: vertices of a graph, variables of a logic formula...etc.) [6, 18]. Although it has been mainly used for minimization problems, iterative compression has been successfully applied for maximization problems as well, under the name *iterative expansion* [5]. Roughly speaking, when the problem consists in finding a solution of size at least $k$, the iterative expansion technique consists in solving the problem where a solution $\mathcal{S}$ of size $k-1$ is given in the input, in the hope that this solution will imply some structure in the instance. In the following, we consider an extension of this approach where, instead of a single smaller solution, one is given a set of $f(k)$ smaller solutions $S_1, \dots, S_{f(k)}$. As we will see later, we can further add more constraints on the sets $S_1, \dots, S_{f(k)}$. Notice that all the results presented in this sub-section (Lemmas 7 and 10 in particular) hold for any hereditary graph class (including the class of all graphs). The use of properties inherited from particular graphs (namely, $H$-free graphs in our case) will only appear in Sections 4.2 and 4.3.

**Definition 6.** For a function $f: \mathbb{N} \to \mathbb{N}$, the $f$-ITERATIVE EXPANSION MIS takes as input a graph $\mathcal{G}$, an integer $k$, and a set of $f(k)$ independent sets $S_1, \dots, S_{f(k)}$, each of size $k-1$. The objective is to find an independent set of size $k$ in $\mathcal{G}$, or to decide that such an independent set does not exist.

**Lemma 7.** $(\star)$ Let $\mathcal{G}$ be a hereditary graph class. MIS is FPT in $\mathcal{G}$ iff $f$-ITERATIVE EXPANSION MIS is FPT in $\mathcal{G}$ for some computable function $f: \mathbb{N} \to \mathbb{N}$.

We will actually prove a stronger version of this result, by adding more constraints on the input sets $S_1, \dots, S_{f(k)}$, and show that solving the expansion version on this particular kind of input is enough to obtain the result for MIS.
We claim that if $\mathcal{G}$ does not contain an independent set of size $k$, then $\mathcal{S}$ contains all independent sets of $\mathcal{G}$. It suffices to prove that for every independent set $\mathcal{S}$, there exists a clique $\mathcal{C}$ for which $\mathcal{S} \in \mathcal{S}_{\mathcal{C}}$. Let $\mathcal{S}$ be an independent set, and define $\mathcal{C}$ to be a clique of size $r$ such that its largest vertex $c$ (with respect to $<$) satisfies the conditions:

- no vertex of $\mathcal{C}$ is adjacent to a vertex of $\mathcal{S} \cap c^+$, and

- $c$ is the smallest vertex such that a clique $\mathcal{C}$ satisfying the first item exists.

First remark that such a clique always exist, since we assumed that the largest vertex $c_{\text{last}}$ of $< \mathcal{S}$ is contained in a clique of size $r$, which means that $\mathcal{S} \cap c_{\text{last}}^+$ is empty and thus the first item is vacuously satisfied. Secondly, note that several cliques $\mathcal{C}$ might satisfy the two previous conditions. In that case, pick one such clique arbitrarily. This definition of $\mathcal{C}$ and $c$ ensures that $\mathcal{S} \cap c^+$ is an independent set in the set $V_1$ defined in the construction above (it might be empty, but we also consider this case). Thus, it will be picked in the second phase as some $S_1 \in S_1$ and for this choice, each time $V_2$ is considered, the fact that $\mathcal{C}$ is chosen to minimize its largest element $c$ guarantees that there must be a vertex of $\mathcal{S}$ in the $(\text{Ram}(r, k) + 1)$ largest vertices in $V_2$: either $c \in \mathcal{S}$ and we are done, or $\mathcal{S}$ must intersect one of the $\text{Ram}(r, k)$ largest elements of $V_2 \setminus \{c\}$, otherwise there would be an $r$-clique contradicting the choice of $\mathcal{C}$. This shows that $\mathcal{S} \in \mathcal{S}_{\mathcal{C}}$, which concludes our proof. ◀

# 4 Positive results II

## 4.1 Key ingredient: Iterative expansion and Ramsey extraction

In this section, we present the main idea of our algorithms. It is a generalization of iterative expansion, which itself is the maximization version of the well-known iterative compression technique. Iterative compression is a useful tool for designing parameterized algorithms for subset problems (i.e. problems where a solution is a subset of some set of elements: vertices of a graph, variables of a logic formula...etc.) [6, 18]. Although it has been mainly used for minimization problems, iterative compression has been successfully applied for maximization problems as well, under the name *iterative expansion* [5]. Roughly speaking, when the problem consists in finding a solution of size at least $k$, the iterative expansion technique consists in solving the problem where a solution $\mathcal{S}$ of size $k-1$ is given in the input, in the hope that this solution will imply some structure in the instance. In the following, we consider an extension of this approach where, instead of a single smaller solution, one is given a set of $f(k)$ smaller solutions $S_1, \dots, S_{f(k)}$. As we will see later, we can further add more constraints on the sets $S_1, \dots, S_{f(k)}$. Notice that all the results presented in this sub-section (Lemmas 7 and 10 in particular) hold for any hereditary graph class (including the class of all graphs). The use of properties inherited from particular graphs (namely, $H$-free graphs in our case) will only appear in Sections 4.2 and 4.3.

**Definition 6.** For a function $f: \mathbb{N} \to \mathbb{N}$, the $f$-ITERATIVE EXPANSION MIS takes as input a graph $\mathcal{G}$, an integer $k$, and a set of $f(k)$ independent sets $S_1, \dots, S_{f(k)}$, each of size $k-1$. The objective is to find an independent set of size $k$ in $\mathcal{G}$, or to decide that such an independent set does not exist.

**Lemma 7.** (*) Let $\mathcal{G}$ be a hereditary graph class. MIS is FPT in $\mathcal{G}$ iff $f$-ITERATIVE EXPANSION MIS is FPT in $\mathcal{G}$ for some computable function $f: \mathbb{N} \to \mathbb{N}$.

We will actually prove a stronger version of this result, by adding more constraints on the input sets $S_1, \dots, S_{f(k)}$, and show that solving the expansion version on this particular kind of input is enough to obtain the result for MIS.
17:8 Parameterized Complexity of Independent Set in H-Free Graphs

**Definition 8.** Given a graph $G$ and a set of $k-1$ vertex-disjoint cliques of $G$, $\mathcal{C} = \{C_1, \dots, C_{k-1}\}$, each of size $q$, we say that $\mathcal{C}$ is a set of *Ramsey-extracted cliques of size* $q$ if the conditions below hold. Let $C_r = \{c_j^r : j \in \{1, \dots, q\}\}$ for every $r \in \{1, \dots, k-1\}$.

For every $j \in [q]$, the set $\{c_j^r : r \in \{1, \dots, k-1\}\}$ is an independent set of $G$ of size $k-1$.

For any $r \neq r' \in \{1, \dots, k-1\}$, one of the four following case can happen:

(i) for every $j, j' \in [q]$, $c_j^r c_{j'}^{r'} \notin E(G)$

(ii) for every $j, j' \in [q]$, $c_j^r c_{j'}^{r'} \in E(G)$ iff $j \neq j'$

(iii) for every $j, j' \in [q]$, $c_j^r c_{j'}^{r'} \in E(G)$ iff $j < j'$

(iv) for every $j, j' \in [q]$, $c_j^r c_{j'}^{r'} \in E(G)$ iff $j > j'$

In the case (i) (resp. (ii)), we say that the relation between $C_r$ and $C_{r'}$ is empty (resp. full$^5$). In case (iii) or (iv), we say the relation is semi-full.

Observe, in particular, that a set $\mathcal{C}$ of $k-1$ Ramsey-extracted cliques of size $q$ can be partitionned into $q$ independent sets of size $k-1$. As we will see later, these cliques will allow us to obtain more structure with the remaining vertices if the graph is $H$-free. Roughly speaking, if $q$ is large, we will be able to extract from $\mathcal{C}$ another set $\mathcal{C}'$ of $k-1$ Ramsey-extracted cliques of size $q' < q$, such that every clique is a module$^6$ with respect to the solution $x_1^*, \dots, x_k^*$ we are looking for. Then, by guessing the structure of the adjacencies between $\mathcal{C}'$ and the solution, we will be able to identify from the remaining vertices $k$ sets $X_1, \dots, X_k$, where each $X_i$ has the same neighborhood as $x_i^*$ w.r.t. $\mathcal{C}'$, and plays the role of "candidates" for this vertex. For a function $f: \mathbb{N} \to \mathbb{N}$, we define the following problem:

**Definition 9.** The $f$-RAMSEY-EXTRACTED ITERATIVE EXPANSION MIS problem takes as input an integer $k$ and a graph $G$ whose vertices are partitionned into non-empty sets $X_1 \cup \dots \cup X_k \cup C_1 \cup \dots \cup C_{k-1}$, where:

$\{C_1, \dots, C_{k-1}\}$ is a set of $k-1$ Ramsey-extracted cliques of size $f(k)$

any independent set of size $k$ in $G$ is contained in $X_1 \cup \dots \cup X_k$

$\forall i \in \{1, \dots, k\}, \forall v, w \in X_i$ and $\forall j \in \{1, \dots, k-1\}, N(v) \cap C_j = N(w) \cap C_j = \emptyset$ or $N(v) \cap C_j = N(w) \cap C_j = C_j$

the following bipartite graph $\mathcal{B}$ is connected: $V(\mathcal{B}) = B_1 \cup B_2$, $B_1 = \{b_1^1, \dots, b_k^1\}$, $B_2 = \{b_1^2, \dots, b_{k-1}^2\}$ and $b_j^1 b_r^2 \in E(\mathcal{B})$ iff $X_j$ and $C_r$ are adjacent.

The objective is to find an independent set $S$ in $G$ of size at least $k$, or to decide that $G$ does not contain an independent set $S$ such that $S \cap X_i \neq \emptyset$ for all $i \in \{1, \dots, k\}$.

**Lemma 10.** Let $\mathcal{G}$ be a hereditary graph class. If there exists a computable function $f: \mathbb{N} \to \mathbb{N}$ such that $f$-RAMSEY-EXTRACTED ITERATIVE EXPANSION MIS is FPT in $\mathcal{G}$, then $g$-ITERATIVE EXPANSION MIS is FPT in $\mathcal{G}$, where $g(x) = \text{Ram}_\ell(f(x)2^{x(x-1)}) \ \forall x \in \mathbb{N}$, with $\ell_x = 2^{(x-1)^2}$.

**Proof.** Let $f: \mathbb{N} \to \mathbb{N}$ be such a function, and let $G$, $k$ and $S = \{S_1, \dots, S_{g(k)}\}$ be an input of $g$-ITERATIVE EXPANSION MIS. Recall that the objective is to find an independent set of size $k$ in $G$, or to decide that such an independent set does not exist. If $G$ contains an independent set of size $k$, then either there is one intersecting some set of $S$, or every independent set of size $k$ avoids the sets in $S$. In order to capture the first case, we branch on every vertex $v$ of the sets in $S$, and make a recursive call with parameter $G \setminus N[v]$, $k-1$.

<footnote n="5">5 Remark that in this case, the graph induced by $C_r \cup C_{r'}$ is the complement of a perfect matching.</footnote>

<footnote n="6">6 A set of vertices $M$ is a module if every vertex $v \notin M$ is adjacent to either all vertices of $M$, or none.</footnote>
17:8 Parameterized Complexity of Independent Set in H-Free Graphs

**Definition 8.** Given a graph $G$ and a set of $k-1$ vertex-disjoint cliques of $G$, $\mathcal{C} = \{C_1, \dots, C_{k-1}\}$, each of size $q$, we say that $\mathcal{C}$ is a set of *Ramsey-extracted cliques of size* $q$ if the conditions below hold. Let $C_r = \{c_j^r : j \in \{1, \dots, q\}\}$ for every $r \in \{1, \dots, k-1\}$.

For every $j \in [q]$, the set $\{c_j^r : r \in \{1, \dots, k-1\}\}$ is an independent set of $G$ of size $k-1$.

For any $r \neq r' \in \{1, \dots, k-1\}$, one of the four following case can happen:

(i) for every $j, j' \in [q]$, $c_j^r c_{j'}^{r'} \notin E(G)$

(ii) for every $j, j' \in [q]$, $c_j^r c_{j'}^{r'} \in E(G)$ iff $j \neq j'$

(iii) for every $j, j' \in [q]$, $c_j^r c_{j'}^{r'} \in E(G)$ iff $j < j'$

(iv) for every $j, j' \in [q]$, $c_j^r c_{j'}^{r'} \in E(G)$ iff $j > j'$

In the case (i) (resp. (ii)), we say that the relation between $C_r$ and $C_{r'}$ is empty (resp. full$^5$). In case (iii) or (iv), we say the relation is semi-full.

Observe, in particular, that a set $\mathcal{C}$ of $k-1$ Ramsey-extracted cliques of size $q$ can be partitionned into $q$ independent sets of size $k-1$. As we will see later, these cliques will allow us to obtain more structure with the remaining vertices if the graph is $H$-free. Roughly speaking, if $q$ is large, we will be able to extract from $\mathcal{C}$ another set $\mathcal{C}'$ of $k-1$ Ramsey-extracted cliques of size $q' < q$, such that every clique is a module$^6$ with respect to the solution $x_1^*, \dots, x_k^*$ we are looking for. Then, by guessing the structure of the adjacencies between $\mathcal{C}'$ and the solution, we will be able to identify from the remaining vertices $k$ sets $X_1, \dots, X_k$, where each $X_i$ has the same neighborhood as $x_i^*$ w.r.t. $\mathcal{C}'$, and plays the role of "candidates" for this vertex. For a function $f: \mathbb{N} \to \mathbb{N}$, we define the following problem:

**Definition 9.** The $f$-RAMSEY-EXTRACTED ITERATIVE EXPANSION MIS problem takes as input an integer $k$ and a graph $G$ whose vertices are partitionned into non-empty sets $X_1 \cup \dots \cup X_k \cup C_1 \cup \dots \cup C_{k-1}$, where:

$\{C_1, \dots, C_{k-1}\}$ is a set of $k-1$ Ramsey-extracted cliques of size $f(k)$

any independent set of size $k$ in $G$ is contained in $X_1 \cup \dots \cup X_k$

$\forall i \in \{1, \dots, k\}, \forall v, w \in X_i$ and $\forall j \in \{1, \dots, k-1\}, N(v) \cap C_j = N(w) \cap C_j = \emptyset$ or $N(v) \cap C_j = N(w) \cap C_j = C_j$

the following bipartite graph $\mathcal{B}$ is connected: $V(\mathcal{B}) = B_1 \cup B_2$, $B_1 = \{b_1^1, \dots, b_k^1\}$, $B_2 = \{b_1^2, \dots, b_{k-1}^2\}$ and $b_j^1 b_r^2 \in E(\mathcal{B})$ iff $X_j$ and $C_r$ are adjacent.

The objective is to find an independent set $S$ in $G$ of size at least $k$, or to decide that $G$ does not contain an independent set $S$ such that $S \cap X_i \neq \emptyset$ for all $i \in \{1, \dots, k\}$.

**Lemma 10.** Let $\mathcal{G}$ be a hereditary graph class. If there exists a computable function $f: \mathbb{N} \to \mathbb{N}$ such that $f$-RAMSEY-EXTRACTED ITERATIVE EXPANSION MIS is FPT in $\mathcal{G}$, then $g$-ITERATIVE EXPANSION MIS is FPT in $\mathcal{G}$, where $g(x) = \text{Ram}_\ell(f(x)2^{x(x-1)}) \ \forall x \in \mathbb{N}$, with $\ell_x = 2^{(x-1)^2}$.

**Proof.** Let $f: \mathbb{N} \to \mathbb{N}$ be such a function, and let $G$, $k$ and $S = \{S_1, \dots, S_{g(k)}\}$ be an input of $g$-ITERATIVE EXPANSION MIS. Recall that the objective is to find an independent set of size $k$ in $G$, or to decide that such an independent set does not exist. If $G$ contains an independent set of size $k$, then either there is one intersecting some set of $S$, or every independent set of size $k$ avoids the sets in $S$. In order to capture the first case, we branch on every vertex $v$ of the sets in $S$, and make a recursive call with parameter $G \setminus N[v]$, $k-1$.

<footnote>$^5$Remark that in this case, the graph induced by $C_r \cup C_{r'}$ is the complement of a perfect matching.</footnote>

<footnote>$^6$A set of vertices $M$ is a module if every vertex $v \notin M$ is adjacent to either all vertices of $M$, or none.</footnote>
In the remainder of the algorithm, we thus assume that any independent set of size $k$ in $G$ avoids every set of $S$.

We choose an arbitrary ordering of the vertices of each $S_j$. Let us denote by $s_j^r$ the $r^{th}$ vertex of $S_j$. Notice that given an ordered pair of sets of $k-1$ vertices $(A, B)$, there are $\ell_k = 2^{(k-1)^2}$ possible sets of edges between these two sets. Let us denote by $c_1, \dots, c_{2^{(k-1)^2}}$ the possible sets of edges, called *types*. We define an auxiliary edge-colored graph $H$ whose vertices are in one-to-one correspondence with $S_1, \dots, S_{g(k)}$, and, for $i < j$, there is an edge between $S_i$ and $S_j$ of color $\gamma$ iff the type of $(S_i, S_j)$ is $\gamma$. By Ramsey's theorem, since $H$ has $Ram_{\ell_k}(f(k)2^{k(k-1)})$ vertices, it must admit a monochromatic clique of size at least $h(k) = f(k)2^{k(k-1)}$. W.l.o.g., the vertex set of this clique corresponds to $S_1, \dots, S_{h(k)}$. For $p \in \{1, \dots, k-1\}$, let $C_p = \{s_j^p : \dots, s_{h(k)}^p\}$. Observe that the Ramsey extraction ensures that each $C_p$ is either a clique or an independent set. If $C_p$ is an independent set for some $r$, then we can immediately conclude, since $h(k) \ge k$. Hence, we suppose that $C_p$ is a clique for every $p \in \{1, \dots, k-1\}$. We now prove that $C_1, \dots, C_{k-1}$ are Ramsey-extracted cliques of size $h(k)$. First, by construction, for every $j \in \{1, \dots, h(k)\}$, the set $\{s_j^p : p = 1, \dots, k-1\}$ is an independent set. Then, let $c$ be the type of the clique obtained previously, represented by the adjacencies between two sets $(A, B)$, each of size $k-1$. For every $p \in \{1, \dots, k-1\}$, let $a_p$ (resp. $b_p$) be the $a^{th}$ vertex of $A$ (resp. $B$). Let $p, q \in \{1, \dots, t\}$, $p \ne q$. If any of $a_p b_q$ and $a_q b_p$ are edges in type $c$, then there is no edge between $C_p$ and $C_q$, and their relation is thus empty. If both edges $a_p b_q$ and $a_q b_p$ exist in $c$, then the relation between $C_p$ and $C_q$ is full. Finally if exactly one edge among $a_p b_q$ and $a_q b_p$ exists in $c$, then the relation between $C_p$ and $C_q$ is semi-full. This concludes the fact that $C = \{C_1, \dots, C_{k-1}\}$ are Ramsey-extracted cliques of size $h(k)$.

Suppose that $G$ has an independent set $X^* = \{x_1^*, \dots, x_k^*\}$. Recall that we assumed previously that $X^*$ is contained in $V(G) \setminus (C_1 \cup \dots \cup C_{k-1})$. The next step of the algorithm consists in branching on every subset of $f(k)$ indices $J \subseteq \{1, \dots, h(k)\}$, and restrict every set $C_p$ to $\{s_j^p : j \in J\}$. For the sake of readability, we keep the notation $C_p$ to denote $\{s_j^p : j \in J\}$ (the non-selected vertices are put back in the set of remaining vertices of the graph, i.e. we do not delete them). Since $h(k) = f(k)2^{k(k-1)}$, there must exist a branching where the chosen indices are such that for every $i \in \{1, \dots, k\}$ and every $p \in \{1, \dots, k-1\}$, $x_i^*$ is either adjacent to all vertices of $C_p$ or none of them. In the remainder, we may thus assume that such a branching has been made, with respect to the considered solution $X^* = \{x_1^*, \dots, x_k^*\}$. Now, for every $v \in V(G) \setminus (C_1, \dots, C_{k-1})$, if there exists $p \in \{1, \dots, k-1\}$ such that $N(v) \cap C_p \ne \emptyset$ and $N(v) \cap C_p \ne C_p$, then we can remove this vertex, as we know that it cannot correspond to any $x_i^*$. Thus, we know that all the remaining vertices $v$ are such that for every $p \in \{1, \dots, k-1\}$, $v$ is either adjacent to all vertices of $C_p$, or none of them.

In the following, we perform a color coding-based step on the remaining vertices. Informally, this color coding will allow us to identify, for every vertex $x_i^*$ of the optimal solution, a set $X_i$ of candidates, with the property that all vertices in $X_i$ have the same neighborhood with respect to sets $C_1, \dots, C_{k-1}$. We thus color uniformly at random the remaining vertices $V(G) \setminus (C_1, \dots, C_{k-1})$ using $k$ colors. The probability that the elements of $X^*$ are colored with pairwise distinct colors is at least $e^{-k}$. We are thus reduced to the case of finding a *colorful*<fnref n="7" /> independent set of size $k$. For every $i \in \{1, \dots, k\}$, let $X_i$ be the vertices of $V(G) \setminus (C_1, \dots, C_{k-1})$ colored with color $i$. We now partition every set $X_i$ into at most $2^{k-1}$ subsets $X_i^1, \dots, X_i^{2^{k-1}}$, such that for every $j \in \{1, \dots, 2^{k-1}\}$, all vertices of $X_i^j$ have the same neighborhood with respect to the sets $C_1, \dots, C_{k-1}$ (recall that every vertex of

<footnote n="7">⁷ A set of vertices is called *colorful* if it is colored with pairwise distinct colors.</footnote>
In the remainder of the algorithm, we thus assume that any independent set of size $k$ in $G$ avoids every set of $S$.

We choose an arbitrary ordering of the vertices of each $S_j$. Let us denote by $s_j^r$ the $r^{th}$ vertex of $S_j$. Notice that given an ordered pair of sets of $k-1$ vertices $(A, B)$, there are $\ell_k = 2^{(k-1)^2}$ possible sets of edges between these two sets. Let us denote by $c_1, \dots, c_{2^{(k-1)^2}}$ the possible sets of edges, called *types*. We define an auxiliary edge-colored graph $H$ whose vertices are in one-to-one correspondence with $S_1, \dots, S_{g(k)}$, and, for $i < j$, there is an edge between $S_i$ and $S_j$ of color $\gamma$ iff the type of $(S_i, S_j)$ is $\gamma$. By Ramsey's theorem, since $H$ has $Ram_{\ell_k}(f(k)2^{k(k-1)})$ vertices, it must admit a monochromatic clique of size at least $h(k) = f(k)2^{k(k-1)}$. W.l.o.g., the vertex set of this clique corresponds to $S_1, \dots, S_{h(k)}$. For $p \in \{1, \dots, k-1\}$, let $C_p = \{s_j^p : \dots, s_{h(k)}^p\}$. Observe that the Ramsey extraction ensures that each $C_p$ is either a clique or an independent set. If $C_p$ is an independent set for some $r$, then we can immediately conclude, since $h(k) \ge k$. Hence, we suppose that $C_p$ is a clique for every $p \in \{1, \dots, k-1\}$. We now prove that $C_1, \dots, C_{k-1}$ are Ramsey-extracted cliques of size $h(k)$. First, by construction, for every $j \in \{1, \dots, h(k)\}$, the set $\{s_j^p : p = 1, \dots, k-1\}$ is an independent set. Then, let $c$ be the type of the clique obtained previously, represented by the adjacencies between two sets $(A, B)$, each of size $k-1$. For every $p \in \{1, \dots, k-1\}$, let $a_p$ (resp. $b_p$) be the $a^{th}$ vertex of $A$ (resp. $B$). Let $p, q \in \{1, \dots, t\}$, $p \ne q$. If any of $a_p b_q$ and $a_q b_p$ are edges in type $c$, then there is no edge between $C_p$ and $C_q$, and their relation is thus empty. If both edges $a_p b_q$ and $a_q b_p$ exist in $c$, then the relation between $C_p$ and $C_q$ is full. Finally if exactly one edge among $a_p b_q$ and $a_q b_p$ exists in $c$, then the relation between $C_p$ and $C_q$ is semi-full. This concludes the fact that $C = \{C_1, \dots, C_{k-1}\}$ are Ramsey-extracted cliques of size $h(k)$.

Suppose that $G$ has an independent set $X^* = \{x_1^*, \dots, x_k^*\}$. Recall that we assumed previously that $X^*$ is contained in $V(G) \setminus (C_1 \cup \dots \cup C_{k-1})$. The next step of the algorithm consists in branching on every subset of $f(k)$ indices $J \subseteq \{1, \dots, h(k)\}$, and restrict every set $C_p$ to $\{s_j^p : j \in J\}$. For the sake of readability, we keep the notation $C_p$ to denote $\{s_j^p : j \in J\}$ (the non-selected vertices are put back in the set of remaining vertices of the graph, i.e. we do not delete them). Since $h(k) = f(k)2^{k(k-1)}$, there must exist a branching where the chosen indices are such that for every $i \in \{1, \dots, k\}$ and every $p \in \{1, \dots, k-1\}$, $x_i^*$ is either adjacent to all vertices of $C_p$ or none of them. In the remainder, we may thus assume that such a branching has been made, with respect to the considered solution $X^* = \{x_1^*, \dots, x_k^*\}$. Now, for every $v \in V(G) \setminus (C_1, \dots, C_{k-1})$, if there exists $p \in \{1, \dots, k-1\}$ such that $N(v) \cap C_p \ne \emptyset$ and $N(v) \cap C_p \ne C_p$, then we can remove this vertex, as we know that it cannot correspond to any $x_i^*$. Thus, we know that all the remaining vertices $v$ are such that for every $p \in \{1, \dots, k-1\}$, $v$ is either adjacent to all vertices of $C_p$, or none of them.

In the following, we perform a color coding-based step on the remaining vertices. Informally, this color coding will allow us to identify, for every vertex $x_i^*$ of the optimal solution, a set $X_i$ of candidates, with the property that all vertices in $X_i$ have the same neighborhood with respect to sets $C_1, \dots, C_{k-1}$. We thus color uniformly at random the remaining vertices $V(G) \setminus (C_1, \dots, C_{k-1})$ using $k$ colors. The probability that the elements of $X^*$ are colored with pairwise distinct colors is at least $e^{-k}$. We are thus reduced to the case of finding a *colorful*<fnref n="7" /> independent set of size $k$. For every $i \in \{1, \dots, k\}$, let $X_i$ be the vertices of $V(G) \setminus (C_1, \dots, C_{k-1})$ colored with color $i$. We now partition every set $X_i$ into at most $2^{k-1}$ subsets $X_i^1, \dots, X_i^{2^{k-1}}$, such that for every $j \in \{1, \dots, 2^{k-1}\}$, all vertices of $X_i^j$ have the same neighborhood with respect to the sets $C_1, \dots, C_{k-1}$ (recall that every vertex of

<footnote n="7">⁷ A set of vertices is called *colorful* if it is colored with pairwise distinct colors.</footnote>
17:10 Parameterized Complexity of Independent Set in H-Free Graphs

$V(G) \setminus (C_1, \dots, C_{k-1})$ is adjacent to all vertices of $C_p$ or none, for each $p \in \{1, \dots, k-1\}$.
We branch on every tuple $(j_1, \dots, j_k) \in \{1, \dots, 2^{k-1}\}$. Clearly the number of branchings
is bounded by a function of $k$ only and, moreover, one branching $(j_1, \dots, j_k)$ is such that
$x_i^*$ has the same neighborhood in $C_1 \cup \dots \cup C_{k-1}$ as vertices of $X_i^{j_i}$ for every $i \in \{1, \dots, k\}$.
We assume in the following that such a branching has been made. For every $i \in \{1, \dots, k\}$,
we can thus remove vertices of $X_i^{j_i}$ for every $j \neq j_i$. For the sake of readability, we rename
$X_i^{j_i}$ as $X_i$. Let $\mathcal{B}$ be the bipartite graph with vertex bipartition $(B_1, B_2)$, $B_1 = \{b_1^1, \dots, b_k^1\}$,
$B_2 = \{b_1^2, \dots, b_{k-1}^2\}$, and $b_i^1 b_p^2 \in \mathcal{E}(\mathcal{B})$ iff $x_i^*$ is adjacent to $C_p$. Since every $x_i^*$ has the same
neighborhood as $X_i$ with respect to $C_1, \dots, C_{k-1}$, this bipartite graph actually corresponds
to the one described in Definition 9 representing the adjacencies between $X_i$'s and $C_p$'s. We
now prove that it is connected. Suppose it is not. Then, since $|B_1| = k$ and $|B_2| = k-1$,
there must be a component with as many vertices from $B_1$ as vertices from $B_2$. However,
in this case, using the fixed solution $X^*$ on one side and an independent set of size $k-1$
in $C_1 \cup \dots \cup C_{k-1}$ on the other side, it implies that there is an independent set of size $k$
intersecting $\cup_{p=1}^{k-1} C_p$, a contradiction.

Hence, all conditions of Definition 9 are now fulfilled. It now remains to find an independent
set of size *k* disjoint from the sets *C*, and having a non-empty intersection with *X*<sub>*i*</sub>, for
every *i* ∈ {1, ..., *k*}. We thus run an algorithm solving *f*-RAMSEY-EXTRACTED ITERATIVE
EXPANSION MIS on this input, which concludes the algorithm.

◀

The proof of the following result is immediate, by using successively Lemmas 7 and 10.

**Theorem 11.** Let $\mathcal{G}$ be a hereditary graph class. If $f$-RAMSEY-EXTRACTED ITERATIVE EXPANSION MIS is FPT in $\mathcal{G}$ for some computable function $f$, then MIS is FPT in $\mathcal{G}$.

We now apply this framework to two families of graphs *H*.

4.2 Clique minus a smaller clique

**Theorem 12.** (⋆) For any $r \ge 2$ and $s < r$, MIS in $(K_r \setminus K_s)$-free graphs is FPT if $s \le 3$, and $W[1]$-hard otherwise.

4.3 Clique minus a complete bipartite graph

For every three positive integers $r$, $s_1$, $s_2$ with $s_1 + s_2 < r$, we consider the graph $K_r \setminus K_{s_1, s_2}$.
Another way to see $K_r \setminus K_{s_1, s_2}$ is as a $P_3$ of cliques of size $s_1$, $r - s_1 - s_2$, and $s_2$. More
formally, every graph $K_r \setminus K_{s_1, s_2}$ can be obtained from a $P_3$ by adding $s_1 - 1$ false twins of
the first vertex, $r - s_1 - s_2 - 1$, for the second, and $s_2 - 1$, for the third.

**Theorem 13.** $\forall r \ge 2 \text{ and } s_1 \le s_2 \text{ s.t. } s_1 + s_2 < r$, MIS in $K_r \setminus K_{s_1, s_2}$-free graphs is FPT.

**Proof.** It is more convenient to prove the result for $K_{3r} \setminus K_{r,r}$-free graphs, for any positive integer $r$. It implies the theorem by choosing this new $r$ to be larger than $s_1$, $s_2$, and $r - s_1 - s_2$. We will show that for $f(x) := 3r$ for every $x \in \mathbb{N}$, f-RAMSEY-EXTRACTED ITERATIVE EXPANSION MIS in $K_{3r} \setminus K_{r,r}$-free graphs is FPT. By Theorem 11, this implies that MIS is FPT in this class. Let $C_1, \dots, C_{k-1}$ (whose union is denoted by $\mathcal{C}$) be the Ramsey-extracted cliques of size $3r$, which can be partitionned, as in Definition 9, into $3r$ independent sets $S_1, \dots, S_{3r}$, each of size $k-1$. Let $\mathcal{X} = \bigcup_{i=1}^k X_i$ be the set in which we are looking for an independent set of size $k$. We recall that between any $X_i$ and any $C_j$ there are either all the edges or none. Hence, the whole interaction between $\mathcal{X}$ and $\mathcal{C}$ can be described by the bipartite graph $\mathcal{B}$ described in Definition 9. Firstly, we can assume that each $X_i$ is of
17:10 Parameterized Complexity of Independent Set in H-Free Graphs

$V(G) \setminus (C_1, \dots, C_{k-1})$ is adjacent to all vertices of $C_p$ or none, for each $p \in \{1, \dots, k-1\}$.
We branch on every tuple $(j_1, \dots, j_k) \in \{1, \dots, 2^{k-1}\}$. Clearly the number of branchings
is bounded by a function of $k$ only and, moreover, one branching $(j_1, \dots, j_k)$ is such that
$x_i^*$ has the same neighborhood in $C_1 \cup \dots \cup C_{k-1}$ as vertices of $X_i^{j_i}$ for every $i \in \{1, \dots, k\}$.
We assume in the following that such a branching has been made. For every $i \in \{1, \dots, k\}$,
we can thus remove vertices of $X_i^{j_i}$ for every $j \neq j_i$. For the sake of readability, we rename
$X_i^{j_i}$ as $X_i$. Let $\mathcal{B}$ be the bipartite graph with vertex bipartition $(B_1, B_2)$, $B_1 = \{b_1^1, \dots, b_k^1\}$,
$B_2 = \{b_1^2, \dots, b_{k-1}^2\}$, and $b_i^1b_p^2 \in \mathcal{E}(\mathcal{B})$ iff $x_i^*$ is adjacent to $C_p$. Since every $x_i^*$ has the same
neighborhood as $X_i$ with respect to $C_1, \dots, C_{k-1}$, this bipartite graph actually corresponds
to the one described in Definition 9 representing the adjacencies between $X_i$'s and $C_p$'s. We
now prove that it is connected. Suppose it is not. Then, since $|B_1| = k$ and $|B_2| = k-1$,
there must be a component with as many vertices from $B_1$ as vertices from $B_2$. However,
in this case, using the fixed solution $X^*$ on one side and an independent set of size $k-1$
in $C_1 \cup \dots \cup C_{k-1}$ on the other side, it implies that there is an independent set of size $k$
intersecting $\cup_{p=1}^{k-1} C_p$, a contradiction.

Hence, all conditions of Definition 9 are now fulfilled. It now remains to find an independent
set of size *k* disjoint from the sets *C*, and having a non-empty intersection with *X*<sub>*i*</sub>, for
every *i* ∈ {1, ..., *k*}. We thus run an algorithm solving *f*-RAMSEY-EXTRACTED ITERATIVE
EXPANSION MIS on this input, which concludes the algorithm.

◀

The proof of the following result is immediate, by using successively Lemmas 7 and 10.

**Theorem 11.** Let $\mathcal{G}$ be a hereditary graph class. If $f$-RAMSEY-EXTRACTED ITERATIVE EXPANSION MIS is FPT in $\mathcal{G}$ for some computable function $f$, then MIS is FPT in $\mathcal{G}$.

We now apply this framework to two families of graphs *H*.

4.2 Clique minus a smaller clique

**Theorem 12.** (⋆) For any $r \ge 2$ and $s < r$, MIS in $(K_r \setminus K_s)$-free graphs is FPT if $s \le 3$, and $W[1]$-hard otherwise.

4.3 Clique minus a complete bipartite graph

For every three positive integers $r$, $s_1$, $s_2$ with $s_1 + s_2 < r$, we consider the graph $K_r \setminus K_{s_1, s_2}$.
Another way to see $K_r \setminus K_{s_1, s_2}$ is as a $P_3$ of cliques of size $s_1$, $r - s_1 - s_2$, and $s_2$. More
formally, every graph $K_r \setminus K_{s_1, s_2}$ can be obtained from a $P_3$ by adding $s_1 - 1$ false twins of
the first vertex, $r - s_1 - s_2 - 1$, for the second, and $s_2 - 1$, for the third.

**Theorem 13.** $\forall r \ge 2 \text{ and } s_1 \le s_2 \text{ s.t. } s_1 + s_2 < r$, MIS in $K_r \setminus K_{s_1, s_2}$-free graphs is FPT.

**Proof.** It is more convenient to prove the result for $K_{3r} \setminus K_{r,r}$-free graphs, for any positive integer $r$. It implies the theorem by choosing this new $r$ to be larger than $s_1$, $s_2$, and $r - s_1 - s_2$. We will show that for $f(x) := 3r$ for every $x \in \mathbb{N}$, f-RAMSEY-EXTRACTED ITERATIVE EXPANSION MIS in $K_{3r} \setminus K_{r,r}$-free graphs is FPT. By Theorem 11, this implies that MIS is FPT in this class. Let $C_1, \dots, C_{k-1}$ (whose union is denoted by $\mathcal{C}$) be the Ramsey-extracted cliques of size $3r$, which can be partitionned, as in Definition 9, into $3r$ independent sets $S_1, \dots, S_{3r}$, each of size $k-1$. Let $\mathcal{X} = \bigcup_{i=1}^k X_i$ be the set in which we are looking for an independent set of size $k$. We recall that between any $X_i$ and any $C_j$ there are either all the edges or none. Hence, the whole interaction between $\mathcal{X}$ and $\mathcal{C}$ can be described by the bipartite graph $\mathcal{B}$ described in Definition 9. Firstly, we can assume that each $X_i$ is of
size at least $Ram(r,k)$, otherwise we can branch on $Ram(r,k)$ choices to find one vertex in an optimum solution. By Ramsey's theorem, we can assume that each $X_i$ contains a clique of size $r$ (if it contains an independent set of size $k$, we are done). Our general strategy is to leverage the fact that the input graph is $(K_{3r} \setminus K_{r,r})$-free to describe the structure of $\mathcal{X}$. Hopefully, this structure will be sufficient to solve our problem in FPT time.

We define an auxiliary graph $Y$ with $k-1$ vertices. The vertices $y_1, \dots, y_{k-1}$ of $Y$ represent the Ramsey-extracted cliques of $\mathcal{C}$ and two vertices $y_i$ and $y_j$ are adjacent iff the relation between $C_i$ and $C_j$ is not empty (equivalently the relation is full or semi-full). It might seem peculiar that we concentrate the structure of $\mathcal{C}$, when we will eventually discard it from the graph. It is an indirect move: the simple structure of $\mathcal{C}$ will imply that the interaction between $\mathcal{X}$ and $\mathcal{C}$ is simple, which in turn, will severely restrict the subgraph induced by $\mathcal{X}$. More concretely, in the rest of the proof, we will (1) show that $Y$ is a clique, (2) deduce that $\mathcal{B}$ is a complete bipartite graph, (3) conclude that $\mathcal{X}$ cannot contain an induced $K_r^2 = K_r \uplus K_r$ and run the algorithm of Theorem 5.

Suppose that there is $y_{i_1}y_{i_2}y_{i_3}$ an induced $P_3$ in $Y$, and consider $C_{i_1}, C_{i_2}, C_{i_3}$ the corresponding Ramsey-extracted cliques. For $s < t \in [3r]$, let $C_i^{s \to t} := C_i \cap \bigcup_{s \le j \le t} S_j$. In other words, $C_i^{s \to t}$ contains the elements of $C_i$ having indices between $s$ and $t$. Since $|C_i| = 3r$, each $C_i$ can be partitionned into three sets, of $r$ elements each: $C_i^{1 \to r}$, $C_i^{r+1 \to 2r}$ and $C_i^{2r+1 \to 3r}$. Recall that the relation between $C_{i_1}$ and $C_{i_2}$ (resp. $C_{i_2}$ and $C_{i_3}$) is either full or semi-full, while the relation between $C_{i_1}$ and $C_{i_3}$ is empty. This implies that at least one of the four following sets induces a graph isomorphic to $K_{3r} \setminus K_{r,r}$:

- $C_{i_1}^{1 \to r} \cup C_{i_2}^{r+1 \to 2r} \cup C_{i_3}^{1 \to r}$

- $C_{i_1}^{1 \to r} \cup C_{i_2}^{r+1 \to 2r} \cup C_{i_3}^{2r+1 \to 3r}$

- $C_{i_1}^{2r+1 \to 3r} \cup C_{i_2}^{r+1 \to 2r} \cup C_{i_3}^{1 \to r}$

- $C_{i_1}^{2r+1 \to 3r} \cup C_{i_2}^{r+1 \to 2r} \cup C_{i_3}^{2r+1 \to 3r}$

Hence, $Y$ is a disjoint union of cliques. Let us assume that $Y$ is the union of at least two (maximal) cliques.

Recall that the bipartite graph $\mathcal{B}$ is connected. Thus there is $b_h^1 \in B_1$ (corresponding to $X_h$) adjacent to $b_i^2 \in B_2$ and $b_j^2 \in B_2$ (corresponding to $C_i$ and $C_j$, respectively), such that $y_i$ and $y_j$ lie in two different connected components of $Y$ (in particular, the relation between $C_i$ and $C_j$ is empty). Recall that $X_h$ contains a clique of size at least $r$. This clique induces, together with any $r$ vertices in $C_i$ and any $r$ vertices in $C_j$, a graph isomorphic to $K_{3r} \setminus K_{r,r}$; a contradiction. Hence, $Y$ is a clique.

Now, we can show that $\mathcal{B}$ is a complete bipartite graph. Each $X_h$ has to be adjacent to at least one $C_i$ (otherwise this trivially contradicts the connectedness of $\mathcal{B}$). If $X_h$ is not linked to $C_j$ for some $j \in \{1, \dots, k-1\}$, then a clique of size $r$ in $X_h$ (which always exists) induces, together with $C_i^{1 \to r} \cup C_j^{2r+1 \to 3r}$ or with $C_i^{2r+1 \to 3r} \cup C_j^{1 \to r}$, a graph isomorphic to $K_{3r} \setminus K_{r,r}$.

Since $\mathcal{B}$ is a complete bipartite graph, every vertex of $C_1$ dominates all vertices of $\mathcal{X}$ In particular, $\mathcal{X}$ is in the intersection of the neighborhood of the vertices of some clique of size $r$. This implies that the subgraph induced by $\mathcal{X}$ is $(K_r \uplus K_r)$-free. Hence, we can run the FPT algorithm of Theorem 5 on this graph. ◀

# 5 Polynomial (Turing) kernels

In this section we investigate some special cases of Section 4.3, in particular when $H$ is a clique of size $r$ minus a claw with $s$ branches, for $s < r$. Although Theorem 13 proves that MIS is FPT for every possible values of $r$ and $s$, we show that when $s \ge r-2$, the problem
size at least $Ram(r, k)$, otherwise we can branch on $Ram(r, k)$ choices to find one vertex in an optimum solution. By Ramsey's theorem, we can assume that each $X_i$ contains a clique of size $r$ (if it contains an independent set of size $k$, we are done). Our general strategy is to leverage the fact that the input graph is $(K_{3r} \setminus K_{r,r})$-free to describe the structure of $\mathcal{X}$. Hopefully, this structure will be sufficient to solve our problem in FPT time.

We define an auxiliary graph $Y$ with $k-1$ vertices. The vertices $y_1, \dots, y_{k-1}$ of $Y$ represent the Ramsey-extracted cliques of $\mathcal{C}$ and two vertices $y_i$ and $y_j$ are adjacent iff the relation between $C_i$ and $C_j$ is not empty (equivalently the relation is full or semi-full). It might seem peculiar that we concentrate the structure of $\mathcal{C}$, when we will eventually discard it from the graph. It is an indirect move: the simple structure of $\mathcal{C}$ will imply that the interaction between $\mathcal{X}$ and $\mathcal{C}$ is simple, which in turn, will severely restrict the subgraph induced by $\mathcal{X}$. More concretely, in the rest of the proof, we will (1) show that $Y$ is a clique, (2) deduce that $\mathcal{B}$ is a complete bipartite graph, (3) conclude that $\mathcal{X}$ cannot contain an induced $K_r^2 = K_r \uplus K_r$ and run the algorithm of Theorem 5.

Suppose that there is $y_{i_1}y_{i_2}y_{i_3}$ an induced $P_3$ in $Y$, and consider $C_{i_1}, C_{i_2}, C_{i_3}$ the corresponding Ramsey-extracted cliques. For $s < t \in [3r]$, let $C_i^{s \to t} := C_i \cap \bigcup_{s \le j \le t} S_j$. In other words, $C_i^{s \to t}$ contains the elements of $C_i$ having indices between $s$ and $t$. Since $|C_i| = 3r$, each $C_i$ can be partitionned into three sets, of $r$ elements each: $C_i^{1 \to r}, C_i^{r+1 \to 2r}$ and $C_i^{2r+1 \to 3r}$. Recall that the relation between $C_{i_1}$ and $C_{i_2}$ (resp. $C_{i_2}$ and $C_{i_3}$) is either full or semi-full, while the relation between $C_{i_1}$ and $C_{i_3}$ is empty. This implies that at least one of the four following sets induces a graph isomorphic to $K_{3r} \setminus K_{r,r}$:

- $C_{i_1}^{1 \to r} \cup C_{i_2}^{r+1 \to 2r} \cup C_{i_3}^{1 \to r}$

- $C_{i_1}^{1 \to r} \cup C_{i_2}^{r+1 \to 2r} \cup C_{i_3}^{2r+1 \to 3r}$

- $C_{i_1}^{2r+1 \to 3r} \cup C_{i_2}^{r+1 \to 2r} \cup C_{i_3}^{1 \to r}$

- $C_{i_1}^{2r+1 \to 3r} \cup C_{i_2}^{r+1 \to 2r} \cup C_{i_3}^{2r+1 \to 3r}$

Hence, $Y$ is a disjoint union of cliques. Let us assume that $Y$ is the union of at least two (maximal) cliques.

Recall that the bipartite graph $\mathcal{B}$ is connected. Thus there is $b_h^1 \in B_1$ (corresponding to $X_h$) adjacent to $b_i^2 \in B_2$ and $b_j^2 \in B_2$ (corresponding to $C_i$ and $C_j$, respectively), such that $y_i$ and $y_j$ lie in two different connected components of $Y$ (in particular, the relation between $C_i$ and $C_j$ is empty). Recall that $X_h$ contains a clique of size at least $r$. This clique induces, together with any $r$ vertices in $C_i$ and any $r$ vertices in $C_j$, a graph isomorphic to $K_{3r} \setminus K_{r,r}$; a contradiction. Hence, $Y$ is a clique.

Now, we can show that $\mathcal{B}$ is a complete bipartite graph. Each $X_h$ has to be adjacent to at least one $C_i$ (otherwise this trivially contradicts the connectedness of $\mathcal{B}$). If $X_h$ is not linked to $C_j$ for some $j \in \{1, \dots, k-1\}$, then a clique of size $r$ in $X_h$ (which always exists) induces, together with $C_i^{1 \to r} \cup C_j^{2r+1 \to 3r}$ or with $C_i^{2r+1 \to 3r} \cup C_j^{1 \to r}$, a graph isomorphic to $K_{3r} \setminus K_{r,r}$.

Since $\mathcal{B}$ is a complete bipartite graph, every vertex of $C_1$ dominates all vertices of $\mathcal{X}$ In particular, $\mathcal{X}$ is in the intersection of the neighborhood of the vertices of some clique of size $r$. This implies that the subgraph induced by $\mathcal{X}$ is $(K_r \uplus K_r)$-free. Hence, we can run the FPT algorithm of Theorem 5 on this graph. ◀

# 5 Polynomial (Turing) kernels

In this section we investigate some special cases of Section 4.3, in particular when $H$ is a clique of size $r$ minus a claw with $s$ branches, for $s < r$. Although Theorem 13 proves that MIS is FPT for every possible values of $r$ and $s$, we show that when $s \ge r-2$, the problem
References

1. V. Alekseev. The Effect of Local Constraints on the Complexity of Determination of the Graph Independence Number. *Combinatorial-Algebraic Methods in Applied Mathematics*, pages 3–13, 1982. in Russian.

2. V. E. Alekseev. On the number of maximal independent sets in graphs from hereditary classes. *Combinatorial-Algebraic Methods in Discrete Optimization*, pages 5–8, 1991. (In Russian).

3. G. Bacsó, D. Lokshtanov, D. Marx, M. Pilipczuk, Z. Tuza, and E. Jan van Leeuwen. Subexponential-time Algorithms for Maximum Independent Set in $P_t$-free and Broom-free Graphs. *CoRR*, abs/1804.04077, 2018.

4. É. Bonnet, N. Bousquet, P. Charbit, S. Thomassé, and R. Watrigant. Parameterized Complexity of Independent Set in H-Free Graphs. *CoRR*, 2018. arXiv:1810.04620.

5. J. Chen, Y. L., S. Lu, S. S., and F. Zhang. Iterative Expansion and Color Coding: An Improved Algorithm for 3D-Matching. *ACM Trans. Algorithms*, 8(1):6:1–6:22, 2012.

6. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. *Parameterized Algorithms*. Springer, 2015.

7. K. Dabrowski. *Structural Solutions to Maximum Independent Set and Related Problems*. PhD thesis, University of Warwick, 2012.

8. K. Dabrowski, V. V. Lozin, H. Müller, and D. Rautenbach. Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number. *J. Discrete Algorithms*, 14:207–213, 2012.

9. R. Diestel. *Graph Theory, 4th Edition*, volume 173 of *Graduate texts in mathematics*. Springer, 2012.

10. R. G. Downey and M. R. Fellows. *Fundamentals of Parameterized Complexity*. Texts in Computer Science. Springer, 2013.

11. H. Perret du Cray and I. Sau. Improved FPT algorithms for weighted independent set in bull-free graphs. *Discrete Mathematics*, 341(2):451–462, 2018.

12. M. R. Garey and D. S. Johnson. *Computers and Intractability: A Guide to the Theory of NP-Completeness*. W. H. Freeman, 1979.

13. A. Grzesik, T. Klimosova, M. Pilipczuk, and M. Pilipczuk. Polynomial-time algorithm for Maximum Weight Independent Set on $P_6$-free graphs. *CoRR*, abs/1707.05491, 2017.

14. D. Hermelin, M. Mnich, and E. J. van Leeuwen. Parameterized Complexity of Induced Graph Matching on Claw-Free Graphs. *Algorithmica*, 70(3):513–560, 2014.

15. T. Karthick. Independent Sets in Some Classes of $S_{i,j,k}$-free Graphs. *J. Comb. Optim.*, 34(2):612–630, August 2017.

16. T. Karthick and F. Maffray. Maximum weight independent sets in classes related to claw-free graphs. *Discrete Applied Mathematics*, 216:233–239, 2017.

17. D. Lokshtanov, M. Vatshelle, and Y. Villanger. Independent Set in $P_5$-Free Graphs in Polynomial Time. In *Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014*, pages 570–581, 2014.

18. B. Reed, K. Smith, and A. Vetta. Finding odd cycle transversals. *Operations Research Letters*, 32(4):299–301, 2004.

19. S. Thomassé, N. Trotignon, and K. Vuskovic. A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs. *Algorithmica*, 77(3):619–641, 2017.

20. D. Zuckerman. Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. *Theory of Computing*, 3(1):103–128, 2007.
References

1 V. Alekseev. The Effect of Local Constraints on the Complexity of Determination of the Graph Independence Number. *Combinatorial-Algebraic Methods in Applied Mathematics*, pages 3–13, 1982. in Russian.

2 V. E. Alekseev. On the number of maximal independent sets in graphs from hereditary classes. *Combinatorial-Algebraic Methods in Discrete Optimization*, pages 5–8, 1991. (In Russian).

3 G. Bacsó, D. Lokshtanov, D. Marx, M. Pilipczuk, Z. Tuza, and E. Jan van Leeuwen. Subexponential-time Algorithms for Maximum Independent Set in $P_t$-free and Broom-free Graphs. *CoRR*, abs/1804.04077, 2018.

4 É. Bonnet, N. Bousquet, P. Charbit, S. Thomassé, and R. Watrigant. Parameterized Complexity of Independent Set in H-Free Graphs. *CoRR*, 2018. arXiv:1810.04620.

5 J. Chen, Y. L., S. Lu, S. S., and F. Zhang. Iterative Expansion and Color Coding: An Improved Algorithm for 3D-Matching. *ACM Trans. Algorithms*, 8(1):6:1–6:22, 2012.

6 M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. *Parameterized Algorithms*. Springer, 2015.

7 K. Dabrowski. *Structural Solutions to Maximum Independent Set and Related Problems*. PhD thesis, University of Warwick, 2012.

8 K. Dabrowski, V. V. Lozin, H. Müller, and D. Rautenbach. Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number. *J. Discrete Algorithms*, 14:207–213, 2012.

9 R. Diestel. *Graph Theory, 4th Edition*, volume 173 of *Graduate texts in mathematics*. Springer, 2012.

10 R. G. Downey and M. R. Fellows. *Fundamentals of Parameterized Complexity*. Texts in Computer Science. Springer, 2013.

11 H. Perret du Cray and I. Sau. Improved FPT algorithms for weighted independent set in bull-free graphs. *Discrete Mathematics*, 341(2):451–462, 2018.

12 M. R. Garey and D. S. Johnson. *Computers and Intractability: A Guide to the Theory of NP-Completeness*. W. H. Freeman, 1979.

13 A. Grzesik, T. Klimosova, M. Pilipczuk, and M. Pilipczuk. Polynomial-time algorithm for Maximum Weight Independent Set on $P_6$-free graphs. *CoRR*, abs/1707.05491, 2017.

14 D. Hermelin, M. Mnich, and E. J. van Leeuwen. Parameterized Complexity of Induced Graph Matching on Claw-Free Graphs. *Algorithmica*, 70(3):513–560, 2014.

15 T. Karthick. Independent Sets in Some Classes of $S_{i,j,k}$-free Graphs. *J. Comb. Optim.*, 34(2):612–630, August 2017.

16 T. Karthick and F. Maffray. Maximum weight independent sets in classes related to claw-free graphs. *Discrete Applied Mathematics*, 216:233–239, 2017.

17 D. Lokshtanov, M. Vatshelle, and Y. Villanger. Independent Set in $P_5$-Free Graphs in Polynomial Time. In *Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014*, pages 570–581, 2014.

18 B. Reed, K. Smith, and A. Vetta. Finding odd cycle transversals. *Operations Research Letters*, 32(4):299–301, 2004.

19 S. Thomassé, N. Trotignon, and K. Vuskovic. A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs. *Algorithmica*, 77(3):619–641, 2017.

20 D. Zuckerman. Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. *Theory of Computing*, 3(1):103–128, 2007.
<figure><img src="image_94.png" /></figure>
<figure><img src="image_97.png" /></figure>
# Multi-Budgeted Directed Cuts

**Stefan Kratsch**

Institut für Informatik, Humboldt-Universität zu Berlin
kratsch@informatik.hu-berlin.de

**Shaohua Li**

Institute of Informatics, University of Warsaw
Shaohua.Li@mimuw.edu.pl

**Dániel Marx**

Institute for Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI)
dmarx@cs.bme.hu

**Marcin Pilipczuk**

Institute of Informatics, University of Warsaw
malcin@mimuw.edu.pl

**Magnus Wahlström<fnref n="1" />**

Royal Holloway, University of London
Magnus.Wahlstrom@rhul.ac.uk

**Abstract**

In this paper, we study multi-budgeted variants of the classic minimum cut problem and graph separation problems that turned out to be important in parameterized complexity: SKEW MULTICUT and DIRECTED FEEDBACK ARC SET. In our generalization, we assign colors 1, 2, ..., $\ell$ to some edges and give separate budgets $k_1, k_2, ..., k_\ell$ for colors 1, 2, ..., $\ell$. For every color $i \in \{1, ..., \ell\}$, let $E_i$ be the set of edges of color $i$. The solution $C$ for the multi-budgeted variant of a graph separation problem not only needs to satisfy the usual separation requirements (i.e., be a cut, a skew multicut, or a directed feedback arc set, respectively), but also needs to satisfy that $|C \cap E_i| \le k_i$ for every $i \in \{1, ..., \ell\}$.

Contrary to the classic minimum cut problem, the multi-budgeted variant turns out to be NP-hard even for $\ell = 2$. We propose FPT algorithms parameterized by $k = k_1 + ... + k_\ell$ for all three problems. To this end, we develop a branching procedure for the multi-budgeted minimum cut problem that measures the progress of the algorithm not by reducing $k$ as usual, but by elevating the capacity of some edges and thus increasing the size of maximum source-to-sink flow. Using the fact that a similar strategy is used to enumerate all important separators of a given size, we merge this process with the flow-guided branching and show an FPT bound on the number of (appropriately defined) important multi-budgeted separators. This allows us to extend our algorithm to the SKEW MULTICUT and DIRECTED FEEDBACK ARC SET problems.

Furthermore, we show connections of the multi-budgeted variants with weighted variants of the directed cut problems and the CHAIN $\ell$-SAT problem, whose parameterized complexity remains an open problem. We show that these problems admit a bounded-in-parameter number of "maximally pushed" solutions (in a similar spirit as important separators are maximally pushed), giving somewhat weak evidence towards their tractability.

**2012 ACM Subject Classification** Theory of computation → Fixed parameter tractability

**Keywords and phrases** important separators, multi-budgeted cuts, Directed Feedback Vertex Set, fixed-parameter tractability, minimum cut

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

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

erc
European Research Council
Co-funded by the European Union's Research and Innovation Programme

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

© Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, and Magnus Wahlström; 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. 18; pp. 18:1–18:14

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

LIPICS

Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

<footnote n="1">¹ Supported by EPSRC grant EP/P007228/1</footnote>
# Multi-Budgeted Directed Cuts

## Stefan Kratsch

Institut für Informatik, Humboldt-Universität zu Berlin
kratsch@informatik.hu-berlin.de

## Shaohua Li

Institute of Informatics, University of Warsaw
Shaohua.Li@mimuw.edu.pl

## Dániel Marx

Institute for Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI)
dmarx@cs.bme.hu

## Marcin Pilipczuk

Institute of Informatics, University of Warsaw
malcin@mimuw.edu.pl

## Magnus Wahlström<fnref n="1" />

Royal Holloway, University of London
Magnus.Wahlstrom@rhul.ac.uk

### Abstract

In this paper, we study multi-budgeted variants of the classic minimum cut problem and graph separation problems that turned out to be important in parameterized complexity: SKEW MULTICUT and DIRECTED FEEDBACK ARC SET. In our generalization, we assign colors 1, 2, ..., $\ell$ to some edges and give separate budgets $k_1, k_2, ..., k_\ell$ for colors 1, 2, ..., $\ell$. For every color $i \in \{1, ..., \ell\}$, let $E_i$ be the set of edges of color $i$. The solution $C$ for the multi-budgeted variant of a graph separation problem not only needs to satisfy the usual separation requirements (i.e., be a cut, a skew multicut, or a directed feedback arc set, respectively), but also needs to satisfy that $|C \cap E_i| \le k_i$ for every $i \in \{1, ..., \ell\}$.

Contrary to the classic minimum cut problem, the multi-budgeted variant turns out to be NP-hard even for $\ell = 2$. We propose FPT algorithms parameterized by $k = k_1 + ... + k_\ell$ for all three problems. To this end, we develop a branching procedure for the multi-budgeted minimum cut problem that measures the progress of the algorithm not by reducing $k$ as usual, but by elevating the capacity of some edges and thus increasing the size of maximum source-to-sink flow. Using the fact that a similar strategy is used to enumerate all important separators of a given size, we merge this process with the flow-guided branching and show an FPT bound on the number of (appropriately defined) important multi-budgeted separators. This allows us to extend our algorithm to the SKEW MULTICUT and DIRECTED FEEDBACK ARC SET problems.

Furthermore, we show connections of the multi-budgeted variants with weighted variants of the directed cut problems and the CHAIN $\ell$-SAT problem, whose parameterized complexity remains an open problem. We show that these problems admit a bounded-in-parameter number of "maximally pushed" solutions (in a similar spirit as important separators are maximally pushed), giving somewhat weak evidence towards their tractability.

**2012 ACM Subject Classification** Theory of computation → Fixed parameter tractability

**Keywords and phrases** important separators, multi-budgeted cuts, Directed Feedback Vertex Set, fixed-parameter tractability, minimum cut

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

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

erc
European Research Council
Co-funded by the European Union's Research and Innovation Programme

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

© Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, and Magnus Wahlström; 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. 18; pp. 18:1–18:14

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

LIPICS

Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

<footnote n="1">¹ Supported by EPSRC grant EP/P007228/1</footnote>
18:2 Multi-Budgeted Directed Cuts

**Related Version** A full version of the paper is available at https://arxiv.org/abs/1810.06848.

**Funding** This research is a part of projects that have received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme under grant agreements No 714704 (S. Li and M. Pilipczuk), 280152 (D. Marx), and 725978 (D. Marx).

# 1 Introduction

Graph separation problems are important topics in both theoretical area and applications. Although the famous minimum cut problem is known to be polynomial-time solvable, many well-known variants are NP-hard, which are intensively studied from the point of view of approximation [1, 2, 11, 13, 14, 18] and, what is more relevant for this work, parameterized complexity.

The notion of important separators, introduced by Marx [22], turned out to be fundamental for a number of graph separation problems such as MULTIWAY CUT [22], DIRECTED FEEDBACK VERTEX SET [4], or ALMOST 2-CNF SAT [27]. Further work, concerning mostly undirected graphs, resulted in a wide range of involved algorithmic techniques: applications of matroid techniques [19, 20], shadow removal [8, 25], randomized contractions [5], LP-guided branching [10, 15, 16, 17], and treewidth reduction [24], among others.

From the above techniques, only the notion of important separators and the related technique of shadow removal generalizes to directed graphs, giving FPT algorithms for DIRECTED FEEDBACK ARC SET [4], DIRECTED MULTIWAY CUT [8], and DIRECTED SUBSET FEEDBACK VERTEX SET [7]. As a result, the parameterized complexity of a number of important graph separation problems in directed graphs remains open, and the quest to investigate them has been put on by the third author in a survey from 2012 [23]. Since the publication of this survey, two negative answers have been obtained. Two authors of this work showed that DIRECTED MULTICUT is W[1]-hard even for four terminal pairs (leaving the case of three terminal pairs open) [26], while Lokshtanov et al. [21] showed intractability of DIRECTED ODD CYCLE TRANSVERSAL.

During an open problem session at Recent Advancements in Parameterized Complexity school (December 2017) [12], Saurabh posed the question of parameterized complexity of a weighted variant of DIRECTED FEEDBACK ARC SET, where given a directed edge-weighted graph $G$, an integer $k$, and a target weight $w$, the goal is to find a set $X \subseteq E(G)$ such that $G-X$ is acyclic and $X$ is of cardinality at most $k$ and weight at most $w$. Consider a similar problem WEIGHTED st-CUT: given a directed graph $G$ with positive edge weights and two distinguished vertices $s, t \in V(G)$, an integer $k$, and a target weight $w$, decide if $G$ admits an st-cut of cardinality at most $k$ and weight at most $w$. The parameterized complexity of this problem parameterized by $k$ is open even if $G$ is restricted to be acyclic, while with this restriction the problem can easily be reduced to DIRECTED FEEDBACK ARC SET (add an arc $(t,s)$ of prohibitively large weight).

The WEIGHTED st-CUT problem becomes similar to another directed graph cut problem, identified in [6], namely CHAIN $\ell$-SAT. While this problem is originally formulated in CSP language, the graph formulation is as follows: given a directed graph $G$ with a partition of edge set $E(G) = P_1 \uplus P_2 \uplus \dots \uplus P_m$ such that each $P_i$ is an edge set of a simple path of length at most $\ell$ (the input paths could have common nodes), an integer $k$, and two vertices $s, t \in V(G)$, find an st-cut $C \subseteq E(G)$ such that $|\{i | C \cap P_i \neq \emptyset\}| \leq k$. This problem can easily be seen to be equivalent to minimum st-cut problem (and thus polynomial-time solvable) for $\ell \leq 2$, but is NP-hard for $\ell \geq 3$ and its parameterized complexity (with $k$ as a parameter) remains an open problem.
18:2 Multi-Budgeted Directed Cuts

**Related Version** A full version of the paper is available at https://arxiv.org/abs/1810.06848.

**Funding** This research is a part of projects that have received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme under grant agreements No 714704 (S. Li and M. Pilipczuk), 280152 (D. Marx), and 725978 (D. Marx).

# 1 Introduction

Graph separation problems are important topics in both theoretical area and applications. Although the famous minimum cut problem is known to be polynomial-time solvable, many well-known variants are NP-hard, which are intensively studied from the point of view of approximation [1, 2, 11, 13, 14, 18] and, what is more relevant for this work, parameterized complexity.

The notion of important separators, introduced by Marx [22], turned out to be fundamental for a number of graph separation problems such as MULTIWAY CUT [22], DIRECTED FEEDBACK VERTEX SET [4], or ALMOST 2-CNF SAT [27]. Further work, concerning mostly undirected graphs, resulted in a wide range of involved algorithmic techniques: applications of matroid techniques [19, 20], shadow removal [8, 25], randomized contractions [5], LP-guided branching [10, 15, 16, 17], and treewidth reduction [24], among others.

From the above techniques, only the notion of important separators and the related technique of shadow removal generalizes to directed graphs, giving FPT algorithms for DIRECTED FEEDBACK ARC SET [4], DIRECTED MULTIWAY CUT [8], and DIRECTED SUBSET FEEDBACK VERTEX SET [7]. As a result, the parameterized complexity of a number of important graph separation problems in directed graphs remains open, and the quest to investigate them has been put on by the third author in a survey from 2012 [23]. Since the publication of this survey, two negative answers have been obtained. Two authors of this work showed that DIRECTED MULTICUT is W[1]-hard even for four terminal pairs (leaving the case of three terminal pairs open) [26], while Lokshtanov et al. [21] showed intractability of DIRECTED ODD CYCLE TRANSVERSAL.

During an open problem session at Recent Advancements in Parameterized Complexity school (December 2017) [12], Saurabh posed the question of parameterized complexity of a weighted variant of DIRECTED FEEDBACK ARC SET, where given a directed edge-weighted graph $G$, an integer $k$, and a target weight $w$, the goal is to find a set $X \subseteq E(G)$ such that $G-X$ is acyclic and $X$ is of cardinality at most $k$ and weight at most $w$. Consider a similar problem WEIGHTED st-CUT: given a directed graph $G$ with positive edge weights and two distinguished vertices $s, t \in V(G)$, an integer $k$, and a target weight $w$, decide if $G$ admits an st-cut of cardinality at most $k$ and weight at most $w$. The parameterized complexity of this problem parameterized by $k$ is open even if $G$ is restricted to be acyclic, while with this restriction the problem can easily be reduced to DIRECTED FEEDBACK ARC SET (add an arc $(t,s)$ of prohibitively large weight).

The WEIGHTED st-CUT problem becomes similar to another directed graph cut problem, identified in [6], namely CHAIN $\ell$-SAT. While this problem is originally formulated in CSP language, the graph formulation is as follows: given a directed graph $G$ with a partition of edge set $E(G) = P_1 \uplus P_2 \uplus \dots \uplus P_m$ such that each $P_i$ is an edge set of a simple path of length at most $\ell$ (the input paths could have common nodes), an integer $k$, and two vertices $s, t \in V(G)$, find an st-cut $C \subseteq E(G)$ such that $|\{i | C \cap P_i \neq \emptyset\}| \leq k$. This problem can easily be seen to be equivalent to minimum st-cut problem (and thus polynomial-time solvable) for $\ell \leq 2$, but is NP-hard for $\ell \geq 3$ and its parameterized complexity (with $k$ as a parameter) remains an open problem.
In this paper we make progress towards resolving the question of parameterized complexity of the two aforementioned problems: weighted *st*-cut problem (in general digraphs, not necessary acyclic ones) and *CHAIN* $\ell$-SAT. Our contribution is twofold.

## Multi-budgeted variant

We define a *multi-budgeted* variant of a number of cut problems (including the minimum cut problem) and show its fixed-parameter tractability. In this variant, the edges of the graph are colored with $\ell$ colors, and the input specifies separate budgets for each color. More formally, we primarily consider the following problem.

### MULTI-BUDGETED CUT

**Input:** A directed graph $G$, two disjoint sets of vertices $X, Y \subseteq V(G)$, an integer $\ell$, and for every $i \in \{1, 2, \dots, \ell\}$ a set $E_i \subseteq E(G)$ and an integer $k_i \ge 1$.

**Question:** Is there a set of arcs $C \subseteq \bigcup_{i=1}^{\ell} E_i$ such that there is no directed $X-Y$ path in $G \setminus C$ and for every $i \in [\ell]$, $|C \cap E_i| \le k_i$.

Similarly we can define multi-budgeted variants of DIRECTED FEEDBACK ARC SET and SKEW MULTICUT.

We observe that MULTI-BUDGETED CUT for $\ell = 2$ reduces to WEIGHTED st-CUT as follows. Let $(G, X, Y, E_1, E_2, k_1, k_2)$ be a MULTI-BUDGETED CUT instance for $\ell = 2$. First, observe that we may assume that $E_1 \cap E_2 = \emptyset$, as we can replace every edge $e \in E_1 \cap E_2$ with two copies $e_1 \in E_1 \setminus E_2$ and $e_2 \in E_2 \setminus E_1$. Second, construct an equivalent WEIGHTED st-CUT instance $(G', s, t, k, w)$ as follows. To construct $G'$, first add two vertices $s, t$ to $G$ and edges $\{(s, x)|x \in X\}$ and $\{(y, t)|y \in Y\}$ of prohibitively large weight. Assign also prohibitively large weight to every edge $e \in E(G) \setminus (E_1 \cup E_2)$. Assign weight $(k_1 + 1)k_2 + 1$ to every edge $e \in E_1$. For every edge $e \in E_2$, add $k_1 + 1$ copies of $e$ to $G'$ of weight 1 each. Finally, set $k := (k_1 + 1) \cdot k_2 + k_1$ as the cardinality bound and $w := k_1((k_1 + 1)k_2 + 1) + (k_1 + 1)k_2$ as the target weight. The equivalence of the instances follows from the fact that the cardinality bound allows to pick in the solution at most $k_2$ bundles of $k_1 + 1$ copies of an edge of $E_2$, while the weight bound allows to pick only $k_1$ edges of $E_1$.

Thus, MULTI-BUDGETED CUT for $\ell = 2$ corresponds to the case of WEIGHTED st-CUT where the weights are integral and both target cardinality and weight are bounded in parameter.<fnref n="2" /> This connection was our primary motivation to study the multi-budgeted variants of the cut problems.

Contrary to the classic minimum cut problem, we note that MULTI-BUDGETED CUT becomes NP-hard for $\ell \ge 2$ by a simple reduction from constrained minimum vertex cover problem on bipartite graphs [3].<fnref n="3" /> We show that MULTI-BUDGETED CUT is FPT when parameterized by $k = k_1 + \dots + k_\ell$. For this problem, our branching strategy is as follows. First, note that in the problem definition we assume that each $k_i$ is positive, and thus $\ell \le k$. A standard application of the Ford-Fulkerson algorithm gives a minimum *XY*-cut *C* of size $\lambda$ and $\lambda$ edge-disjoint *X*–*Y* paths $P_1, P_2, \dots, P_\lambda$. If *C* is a solution, then we are done. Similarly, if $\lambda > k$, then there is no solution. Otherwise, we branch which colors of the sought

<footnote n="2">² For a reduction in the other direction, replace every arc $e$ of weight $\omega(e)$ with one copy of color 1 and $\omega(e)$ copies of color 2, and set budgets $k_1 = k$ and $k_2 = w$.</footnote>

<footnote n="3">³ We believe this problem must have been formulated already before and proven to be NP-hard. However, we were not able to find it in the literature. Our own reduction will be available in the full version of the paper.</footnote>
In this paper we make progress towards resolving the question of parameterized complexity of the two aforementioned problems: weighted st-cut problem (in general digraphs, not necessary acyclic ones) and CHAIN $\ell$-SAT. Our contribution is twofold.

## Multi-budgeted variant

We define a multi-budgeted variant of a number of cut problems (including the minimum cut problem) and show its fixed-parameter tractability. In this variant, the edges of the graph are colored with $\ell$ colors, and the input specifies separate budgets for each color. More formally, we primarily consider the following problem.

### MULTI-BUDGETED CUT

**Input:** A directed graph $G$, two disjoint sets of vertices $X, Y \subseteq V(G)$, an integer $\ell$, and for every $i \in \{1, 2, \dots, \ell\}$ a set $E_i \subseteq E(G)$ and an integer $k_i \ge 1$.

**Question:** Is there a set of arcs $C \subseteq \bigcup_{i=1}^{\ell} E_i$ such that there is no directed $X-Y$ path in $G \setminus C$ and for every $i \in [\ell]$, $|C \cap E_i| \le k_i$.

Similarly we can define multi-budgeted variants of DIRECTED FEEDBACK ARC SET and SKEW MULTICUT.

We observe that MULTI-BUDGETED CUT for $\ell = 2$ reduces to WEIGHTED st-CUT as follows. Let $(G, X, Y, E_1, E_2, k_1, k_2)$ be a MULTI-BUDGETED CUT instance for $\ell = 2$. First, observe that we may assume that $E_1 \cap E_2 = \emptyset$, as we can replace every edge $e \in E_1 \cap E_2$ with two copies $e_1 \in E_1 \setminus E_2$ and $e_2 \in E_2 \setminus E_1$. Second, construct an equivalent WEIGHTED st-CUT instance $(G', s, t, k, w)$ as follows. To construct $G'$, first add two vertices $s, t$ to $G$ and edges $\{(s, x)|x \in X\}$ and $\{(y, t)|y \in Y\}$ of prohibitively large weight. Assign also prohibitively large weight to every edge $e \in E(G) \setminus (E_1 \cup E_2)$. Assign weight $(k_1 + 1)k_2 + 1$ to every edge $e \in E_1$. For every edge $e \in E_2$, add $k_1 + 1$ copies of $e$ to $G'$ of weight 1 each. Finally, set $k := (k_1 + 1) \cdot k_2 + k_1$ as the cardinality bound and $w := k_1((k_1 + 1)k_2 + 1) + (k_1 + 1)k_2$ as the target weight. The equivalence of the instances follows from the fact that the cardinality bound allows to pick in the solution at most $k_2$ bundles of $k_1 + 1$ copies of an edge of $E_2$, while the weight bound allows to pick only $k_1$ edges of $E_1$.

Thus, MULTI-BUDGETED CUT for $\ell = 2$ corresponds to the case of WEIGHTED st-CUT where the weights are integral and both target cardinality and weight are bounded in parameter.<fnref n="2" /> This connection was our primary motivation to study the multi-budgeted variants of the cut problems.

Contrary to the classic minimum cut problem, we note that MULTI-BUDGETED CUT becomes NP-hard for $\ell \ge 2$ by a simple reduction from constrained minimum vertex cover problem on bipartite graphs [3].<fnref n="3" /> We show that MULTI-BUDGETED CUT is FPT when parameterized by $k = k_1 + \dots + k_\ell$. For this problem, our branching strategy is as follows. First, note that in the problem definition we assume that each $k_i$ is positive, and thus $\ell \le k$. A standard application of the Ford-Fulkerson algorithm gives a minimum $XY$-cut $C$ of size $\lambda$ and $\lambda$ edge-disjoint $X-Y$ paths $P_1, P_2, \dots, P_\lambda$. If $C$ is a solution, then we are done. Similarly, if $\lambda > k$, then there is no solution. Otherwise, we branch which colors of the sought

<footnote n="2">² For a reduction in the other direction, replace every arc $e$ of weight $\omega(e)$ with one copy of color 1 and $\omega(e)$ copies of color 2, and set budgets $k_1 = k$ and $k_2 = w$.</footnote>

<footnote n="3">³ We believe this problem must have been formulated already before and proven to be NP-hard. However, we were not able to find it in the literature. Our own reduction will be available in the full version of the paper.</footnote>
18:4 Multi-Budgeted Directed Cuts

solution should appear on each paths $P_j$; that is, for every $i \in [\ell]$ and $j \in [\lambda]$, we guess if $P_j \cap E_i$ contains an edge of the sought solution, and in each guess assign infinite capacities to the edges of wrong color. If this change increased the size of a maximum flow from $X$ to $Y$, then we can charge the branching step to this increase, as the size of the flow cannot exceed $k$. The critical insight is that if the size of the minimum flow does not increase (i.e., $P_1, \dots, P_\lambda$ remains a maximum flow), then a corresponding minimum cut is necessarily a solution. As a result, we obtain the following.

**Theorem 1.** MULTI-BUDGETED CUT admits an FPT algorithm with running time bound $O(2^{k^2\ell} \cdot k \cdot (|V(G)| + |E(G)|))$ where $k = \sum_{i=1}^{\ell} k_i$.

The charging of the branching step to a flow increase appears also in the classic argument for bound of the number of important separators [4] (see also [9, Chapter 8]). We observe that our branching algorithm can be merged with this procedure, yielding a bound (as a function of $k$) and enumeration procedure of naturally defined multi-budgeted important separators. This in turn allows us to generalize our FPT algorithm to MULTI-BUDGETED SKEW MULTICUT and MULTI-BUDGETED DIRECTED FEEDBACK ARC SET.

**Theorem 2.** MULTI-BUDGETED SKEW MULTICUT and MULTI-BUDGETED DIRECTED FEEDBACK ARC SET admit FPT algorithms with running time bound $2^{O(k^3 \log k)} (|V(G)| + |E(G)|)$ where $k = \sum_{i=1}^{\ell} k_i$.

Bound on the number of pushed solutions

While we are not able to establish fixed-parameter tractability of the weighted variant of the minimum cut problem (even in acyclic graphs) nor of CHAIN $\ell$-SAT, we show the following graph-theoretic statement. Consider a directed graph $G$ with two distinguished vertices $s, t \in V(G)$. For two (inclusion-wise) minimal st-cuts $C_1, C_2$ we say that $C_1$ is closer to $t$ than $C_2$ if every vertex reachable from $s$ in $G - C_2$ is also reachable from $s$ in $G - C_1$. A classic submodularity argument implies that there is exactly one closest to $t$ minimum st-cut, while the essence of the notion of important separators is the observation that there is bounded-in-$k$ number of minimal separators of cardinality at most $k$ that are closest to $t$. In Section 5 we show a similar existential statement for the two discussed problems.

**Theorem 3.** For every integer $k$ there exists an integer $g$ such that the following holds. Let $G$ be a directed graph with positive edge weights and two distinguished vertices $s, t \in V(G)$. Let $\mathcal{F}$ be a family of all st-cuts that are of minimum weight among all (inclusion-wise) minimal st-cuts of cardinality at most $k$. Let $\mathcal{G} \subseteq \mathcal{F}$ be the family of those cuts $C$ such that no other cut of $\mathcal{F}$ is closer to $t$. Then $|\mathcal{G}| \le g$.

**Theorem 4.** For every integers $k, \ell$ there exists an integer $g'$ such that the following holds. Let $I := (G, s, t, (P_i)_{i=1}^m, k)$ be a CHAIN $\ell$-SAT instance that is a yes-instance but $(G, s, t, (P_i)_{i=1}^m, k-1)$ is a no-instance. Let $\mathcal{F}$ be a family of all (inclusion-wise) minimal solutions to $I$ and let $\mathcal{G} \subseteq \mathcal{F}$ be the family of those cuts $C$ such that no other cut of $\mathcal{F}$ is closer to $t$. Then $|\mathcal{G}| \le g'$.

Unfortunately, our proof is purely existential, and does not yield an enumeration procedure of the "closest to $t$" solutions.

Organization

In this extended abstract, we prove Theorem 1 in Section 3, present the multi-budgeted extension of the notion of important separators (needed for Theorem 2) in Section 4, and sketch the proofs of Theorems 3 and 4 in Section 5.
18:4 Multi-Budgeted Directed Cuts

solution should appear on each paths $P_j$; that is, for every $i \in [\ell]$ and $j \in [\lambda]$, we guess if $P_j \cap E_i$ contains an edge of the sought solution, and in each guess assign infinite capacities to the edges of wrong color. If this change increased the size of a maximum flow from $X$ to $Y$, then we can charge the branching step to this increase, as the size of the flow cannot exceed $k$. The critical insight is that if the size of the minimum flow does not increase (i.e., $P_1, \dots, P_\lambda$ remains a maximum flow), then a corresponding minimum cut is necessarily a solution. As a result, we obtain the following.

**Theorem 1.** *MULTI-BUDGETED CUT* admits an FPT algorithm with running time bound $O(2^{k^2\ell} \cdot k \cdot (|V(G)| + |E(G)|))$ where $k = \sum_{i=1}^{\ell} k_i$.

The charging of the branching step to a flow increase appears also in the classic argument for bound of the number of important separators [4] (see also [9, Chapter 8]). We observe that our branching algorithm can be merged with this procedure, yielding a bound (as a function of $k$) and enumeration procedure of naturally defined multi-budgeted important separators. This in turn allows us to generalize our FPT algorithm to MULTI-BUDGETED SKEW MULTICUT and MULTI-BUDGETED DIRECTED FEEDBACK ARC SET.

**Theorem 2.** *MULTI-BUDGETED SKEW MULTICUT and MULTI-BUDGETED DIRECTED FEEDBACK ARC SET* admit FPT algorithms with running time bound $2^{O(k^3 \log k)} (|V(G)| + |E(G)|)$ where $k = \sum_{i=1}^{\ell} k_i$.

Bound on the number of pushed solutions

While we are not able to establish fixed-parameter tractability of the weighted variant of the minimum cut problem (even in acyclic graphs) nor of CHAIN $\ell$-SAT, we show the following graph-theoretic statement. Consider a directed graph $G$ with two distinguished vertices $s, t \in V(G)$. For two (inclusion-wise) minimal st-cuts $C_1, C_2$ we say that $C_1$ is closer to $t$ than $C_2$ if every vertex reachable from $s$ in $G - C_2$ is also reachable from $s$ in $G - C_1$. A classic submodularity argument implies that there is exactly one closest to $t$ minimum st-cut, while the essence of the notion of important separators is the observation that there is bounded-in-$k$ number of minimal separators of cardinality at most $k$ that are closest to $t$. In Section 5 we show a similar existential statement for the two discussed problems.

**Theorem 3.** For every integer $k$ there exists an integer $g$ such that the following holds. Let $G$ be a directed graph with positive edge weights and two distinguished vertices $s, t \in V(G)$. Let $\mathcal{F}$ be a family of all st-cuts that are of minimum weight among all (inclusion-wise) minimal st-cuts of cardinality at most $k$. Let $\mathcal{G} \subseteq \mathcal{F}$ be the family of those cuts $C$ such that no other cut of $\mathcal{F}$ is closer to $t$. Then $|\mathcal{G}| \le g$.

**Theorem 4.** For every integers $k, \ell$ there exists an integer $g'$ such that the following holds. Let $I := (G, s, t, (P_i)_{i=1}^m, k)$ be a CHAIN $\ell$-SAT instance that is a yes-instance but $(G, s, t, (P_i)_{i=1}^m, k-1)$ is a no-instance. Let $\mathcal{F}$ be a family of all (inclusion-wise) minimal solutions to $I$ and let $\mathcal{G} \subseteq \mathcal{F}$ be the family of those cuts $C$ such that no other cut of $\mathcal{F}$ is closer to $t$. Then $|\mathcal{G}| \le g'$.

Unfortunately, our proof is purely existential, and does not yield an enumeration procedure of the "closest to $t$" solutions.

Organization

In this extended abstract, we prove Theorem 1 in Section 3, present the multi-budgeted extension of the notion of important separators (needed for Theorem 2) in Section 4, and sketch the proofs of Theorems 3 and 4 in Section 5.
## 2 Preliminaries

For an integer $n$, we denote $[n] = \{1, 2, \dots, n\}$. For a directed graph $G$, we use $V(G)$ to represent the set of vertices of $G$ and $E(G)$ to represent the set of directed edges of $G$. In all multi-budgeted problems, the directed graph $G$ comes with sets $E_i \subseteq E(G)$ for $i \in [\ell]$ which we refer as *colors*. That is, an edge $e$ is *of color* $i$ if $e \in E_i$, and of *no color* if $e \notin E(G) \setminus \bigcup_{i=1}^{\ell} E_i$. Note that an edge may have many colors, as we do not insist on the sets $E_i$ being pairwise disjoint.

Let $X$ and $Y$ be two disjoint vertex sets in a directed graph $G$, an *XY-cut* of $G$ is a set of edges $C$ such that every directed path from a vertex in $X$ to a vertex in $Y$ contains an edge of $C$. A cut $C$ is *minimal* if no proper subset of $C$ is an *XY-cut*, and *minimum* if $C$ is of minimum possible cardinality. Let $C$ be an *XY-cut* and let $R$ be the set of vertices reachable from $X$ in $G \setminus C$. We define $\delta^+(R) = \{(u, v) \in E(G) | u \in R \text{ and } v \notin R\}$ and note that if $C$ is minimal, then $\delta^+(R) = C$.

Let $(G, X, Y, \ell, (E_i, k_i))_{i=1}^\ell$ be a MULTI-BUDGETED CUT instance and let $C$ be an *XY-cut*. We say that $C$ is *budget-respecting* if $C \subseteq \bigcup_{i=1}^\ell E_i$ and $|C \cap E_i| \le k_i$ for every $i \in [\ell]$. For a set $Z \subseteq E(G)$ we say that $C$ is *Z-respecting* if $C \subseteq Z$. In such contexts, we often call $Z$ the set of deletable edges. An *XY-cut* $C$ is a *minimum Z-respecting cut* if it is a *Z-respecting XY-cut* of minimum possible cardinality among all *Z-respecting XY-cuts*.

Our FPT algorithms start with $Z = \bigcup_{i=1}^\ell E_i$ and in branching steps shrink the set $Z$ to reduce the search space. We encapsulate our use of the classic Ford-Fulkerson algorithm in the following statement.

**► Theorem 5.** Given a directed graph $G$, two disjoint sets $X, Y \subseteq V(G)$, a set $Z \subseteq E(G)$, and an integer $k$, one can in $O(k(|V(G)| + |E(G)|))$ time either find the following objects:

- $\lambda$ paths $P_1, P_2, \dots, P_\lambda$ such that every $P_i$ starts in $X$ and ends in $Y$, and every edge $e \in Z$ appears on at most one path $P_i$;

- a set $B \subseteq Z$ consisting of all edges of $G$ that participate in some minimum Z-respecting XY-cut;

- a minimum Z-respecting XY-cut $C$ of size $\lambda$ that is closest to $Y$ among all minimum Z-respecting XY-cuts; or correctly conclude that there is no Z-respecting XY-cut of cardinality at most $k$.

## 3 Multi-budgeted cut

We now give an FPT algorithm parameterized by $k = \sum_{i=1}^\ell k_i$ for the MULTI-BUDGETED CUT problem. We follow a branching strategy that recursively reduces a set $Z$ of deletable edges. That is, we start with $Z = \bigcup_{i=1}^\ell E_i$ (so that every solution is initially Z-respecting) and in each recursive step, we look for a Z-respecting solution and reduce the set $Z$ in a branching step.

Consider a recursive call where we look for a Z-respecting solution to the input MULTI-BUDGETED CUT instance $(G, X, Y, \ell, (E_i, k_i))_{i=1}^\ell$. That is, we look for a Z-respecting budget-respecting cut. We apply Theorem 5 to it. If it returns that there is no Z-respecting XY-cut of size at most $k$, we terminate the current branch, as there is no solution. Otherwise, we obtain the paths $P_1, P_2, \dots, P_\lambda$, the set $B$ (which we will not use in this section), and the cut $C$.

If $C$ is budget-respecting, then it is a solution and we can return it. Otherwise, we perform the following branching step. We iterate over all tuples $(A_1, \dots, A_\ell)$ such that for every $i \in [\ell]$, $A_i \subseteq [\lambda]$ and $|A_i| \le k_i$. $A_i$ represents the subset of paths $P_1, \dots, P_\lambda$ on which at
## 2 Preliminaries

For an integer $n$, we denote $[n] = \{1, 2, \dots, n\}$. For a directed graph $G$, we use $V(G)$ to represent the set of vertices of $G$ and $E(G)$ to represent the set of directed edges of $G$. In all multi-budgeted problems, the directed graph $G$ comes with sets $E_i \subseteq E(G)$ for $i \in [\ell]$ which we refer as *colors*. That is, an edge $e$ is *of color* $i$ if $e \in E_i$, and of *no color* if $e \in E(G) \setminus \bigcup_{i=1}^{\ell} E_i$. Note that an edge may have many colors, as we do not insist on the sets $E_i$ being pairwise disjoint.

Let $X$ and $Y$ be two disjoint vertex sets in a directed graph $G$, an *XY-cut* of $G$ is a set of edges $C$ such that every directed path from a vertex in $X$ to a vertex in $Y$ contains an edge of $C$. A cut $C$ is *minimal* if no proper subset of $C$ is an *XY-cut*, and *minimum* if $C$ is of minimum possible cardinality. Let $C$ be an *XY-cut* and let $R$ be the set of vertices reachable from $X$ in $G \setminus C$. We define $\delta^+(R) = \{(u, v) \in E(G) | u \in R \text{ and } v \notin R\}$ and note that if $C$ is minimal, then $\delta^+(R) = C$.

Let $(G, X, Y, \ell, (E_i, k_i))_{i=1}^\ell$ be a MULTI-BUDGETED CUT instance and let $C$ be an *XY-cut*. We say that $C$ is *budget-respecting* if $C \subseteq \bigcup_{i=1}^\ell E_i$ and $|C \cap E_i| \le k_i$ for every $i \in [\ell]$. For a set $Z \subseteq E(G)$ we say that $C$ is *Z-respecting* if $C \subseteq Z$. In such contexts, we often call $Z$ the set of deletable edges. An *XY-cut* $C$ is a *minimum Z-respecting cut* if it is a *Z-respecting XY-cut* of minimum possible cardinality among all *Z-respecting XY-cuts*.

Our FPT algorithms start with $Z = \bigcup_{i=1}^\ell E_i$ and in branching steps shrink the set $Z$ to reduce the search space. We encapsulate our use of the classic Ford-Fulkerson algorithm in the following statement.

**► Theorem 5.** Given a directed graph $G$, two disjoint sets $X, Y \subseteq V(G)$, a set $Z \subseteq E(G)$, and an integer $k$, one can in $O(k(|V(G)| + |E(G)|))$ time either find the following objects:

- $\lambda$ paths $P_1, P_2, \dots, P_\lambda$ such that every $P_i$ starts in $X$ and ends in $Y$, and every edge $e \in Z$ appears on at most one path $P_i$;

- a set $B \subseteq Z$ consisting of all edges of $G$ that participate in some minimum Z-respecting XY-cut;

- a minimum Z-respecting XY-cut $C$ of size $\lambda$ that is closest to $Y$ among all minimum Z-respecting XY-cuts; or correctly conclude that there is no Z-respecting XY-cut of cardinality at most $k$.

## 3 Multi-budgeted cut

We now give an FPT algorithm parameterized by $k = \sum_{i=1}^\ell k_i$ for the MULTI-BUDGETED CUT problem. We follow a branching strategy that recursively reduces a set $Z$ of deletable edges. That is, we start with $Z = \bigcup_{i=1}^\ell E_i$ (so that every solution is initially Z-respecting) and in each recursive step, we look for a Z-respecting solution and reduce the set $Z$ in a branching step.

Consider a recursive call where we look for a Z-respecting solution to the input MULTI-BUDGETED CUT instance $(G, X, Y, \ell, (E_i, k_i))_{i=1}^\ell$. That is, we look for a Z-respecting budget-respecting cut. We apply Theorem 5 to it. If it returns that there is no Z-respecting XY-cut of size at most $k$, we terminate the current branch, as there is no solution. Otherwise, we obtain the paths $P_1, P_2, \dots, P_\lambda$, the set $B$ (which we will not use in this section), and the cut $C$.

If $C$ is budget-respecting, then it is a solution and we can return it. Otherwise, we perform the following branching step. We iterate over all tuples $(A_1, \dots, A_\ell)$ such that for every $i \in [\ell]$, $A_i \subseteq [\lambda]$ and $|A_i| \le k_i$. $A_i$ represents the subset of paths $P_1, \dots, P_\lambda$ on which at
**18:6 Multi-Budgeted Directed Cuts**

MultiBudgetedCut(G, X, Y, ℓ, (Eᵢ, kᵢ)ᵢ=₁)

Input: A directed graph G, two disjoint set of vertices X, Y ⊆ V(G), an integer ℓ, for every i ∈ [ℓ]
a set Eᵢ ⊆ E(G) and an integer k.

Output: an XY cut C ⊆ ⋃ℓᵢ=₁ Eᵢ such that for every i ∈ [ℓ], |C ∩ Eᵢ| ≤ kᵢ if it exists, otherwise return NO.

1. $Z := \bigcup_{i=1}^{l} E_i;$

2. **return Solve(Z);**

Solve(Z)

a. apply Theorem 5 to (G, X, Y, k, Z) where k = ∑ℓᵢ=₁ kᵢ, obtaining objects (Pᵢ)λᵢ=₁, B, and C,
or an answer NO;

b. **if** the answer NO is obtained, **then return** NO;

c. if C is budget-respecting, **then return** C;

d. **for each** (A₁, ..., Aℓ) such that for every i in [ℓ], Aᵢ ⊆ [λ] and |Aᵢ| ≤ kᵢ **do**

d.1 $\hat{Z} := Z;$

d.2 **for each** i ∈ [ℓ] **do**
    **for each** j ∈ [λ] \ Aᵢ **do**
        $\hat{Z} := \hat{Z} \setminus (Eᵢ ∩ E(Pⱼ));$

d.3 $D = \text{Solve}(\hat{Z});$

d.4 if $D \neq \text{NO}$ then return $D$;

e. **return** NO;

Figure 1 FPT algorithm for MULTI-BUDGETED CUT.

least one edge of color *i* is in the solution for each *i* ∈ [ℓ]. For those edges of color *i* which
are on the paths not indicated by *A*ᵢ, they are not in the solution. Thus we can safely delete
them from *Z*. More formally, for every *i* ∈ [ℓ] and *j* ∈ [λ] \ *A*ᵢ, we remove from *Z* all edges
of *E*(*P*ⱼ) ∩ *E*ᵢ. We recurse on the reduced set *Z*. A pseudocode is available in Figure 1.

**Theorem 6.** The algorithm in Figure 1 for MULTI-BUDGETED CUT is correct and runs in time $O(2^{\ell k^2} \cdot k \cdot (|V(G)| + |E(G)|))$ where $k = \sum_{i=1}^{\ell} k_i$.

**Proof.** We prove the correctness of the algorithm by showing that it returns a solution if and only if the input instance is a yes-instance. The "only if" direction is obvious, as the algorithm returns only Z-respecting budget-respecting XY-cuts and $Z \subseteq \cup_{i=1}^{\ell} E_i$ in each recursive call.

We prove the correctness for the "if" direction. Let $C_0$ be a solution, that is, a budget-
respecting *XY*-cut. In the initial call to **Solve**, $C_0$ is *Z*-respecting. It suffices to inductively
show that in each call to **Solve** such that $C_0$ is *Z*-respecting, either the call returns a
solution, or $C_0$ is $\hat{Z}$-respecting for at least one of the subcalls. Since $C_0$ is *Z*-respecting, the
application of Theorem 5 returns objects $(P_i)_{i=1}^\lambda, B$, and $C$. If $C$ is budget-respecting, then
the algorithm returns it and we are done. Otherwise, consider the branch $(A_1, A_2, \dots, A_\ell)$
where $A_i = \{j | E(P_j) \cap C_0 \neq \emptyset\}$. Since $C_0$ is budget-respecting, $C_0 \subseteq Z$, and no edge of $Z$
appears on more than one path $P_j$, we have $|A_i| \le k_i$ for every $i \in [\ell]$. Thus, $(A_1, A_2, \dots, A_\ell)$
is a branch considered by the algorithm. In this branch, the algorithm refines the set $Z$ to
$\hat{Z}$. By the definition of $A_i$, for every $i \in [\ell]$ and $j \in [\lambda] \setminus A_i$, we have $C_0 \cap E_i \cap E(P_j) = \emptyset$.
Consequently, $C_0$ is $\hat{Z}$-respecting and we are done.

For the time bound, the following observation is crucial.

**Claim 7.** Consider one recursive call **Solve**(Z) where the application of Theorem 5 in line (a) returned objects $(P_i)_{i=1}^\lambda$, B and C. Assume that in some recursive subcall **Solve**($\hat{Z}$) invoked in line (d.3) (Figure 1), the subsequent application of Theorem 5 in line (a) of the
18:6 Multi-Budgeted Directed Cuts

MultiBudgetedCut(G, X, Y, ℓ, (Eᵢ, kᵢ)ᵢ=₁)

Input: A directed graph G, two disjoint set of vertices X, Y ⊆ V(G), an integer ℓ, for every i ∈ [ℓ]
a set Eᵢ ⊆ E(G) and an integer k.

Output: an XY cut C ⊆ ⋃ℓᵢ=₁ Eᵢ such that for every i ∈ [ℓ], |C ∩ Eᵢ| ≤ kᵢ if it exists, otherwise
return NO.

1. $Z := \bigcup_{i=1}^{l} E_i;$

2. **return Solve(Z);**

Solve(Z)

a. apply Theorem 5 to (G, X, Y, k, Z) where k = ∑ℓᵢ=₁ kᵢ, obtaining objects (Pᵢ)λᵢ=₁, B, and C,
or an answer NO;

b. **if** the answer NO is obtained, **then return** NO;

c. if C is budget-respecting, **then return** C;

d. **for each** (A₁, ..., Aℓ) such that for every i in [ℓ], Aᵢ ⊆ [λ] and |Aᵢ| ≤ kᵢ **do**

d.1 $\hat{Z} := Z;$

d.2 **for each** $i \in [\ell]$ **do**
    **for each** $j \in [\lambda] \setminus A_i$ **do**
        $\hat{Z} := \hat{Z} \setminus (E_i \cap E(j))$;

d.3 $D = \text{Solve}(\hat{Z});$

d.4 if $D \neq \text{NO}$ then return $D$;

e. return NO;

Figure 1 FPT algorithm for MULTI-BUDGETED CUT.

least one edge of color *i* is in the solution for each *i* ∈ [ℓ]. For those edges of color *i* which
are on the paths not indicated by *A*ᵢ, they are not in the solution. Thus we can safely delete
them from *Z*. More formally, for every *i* ∈ [ℓ] and *j* ∈ [λ] \ *A*ᵢ, we remove from *Z* all edges
of *E*(*P*ⱼ) ∩ *E*ᵢ. We recurse on the reduced set *Z*. A pseudocode is available in Figure 1.

**Theorem 6.** *The algorithm in Figure 1 for MULTI-BUDGETED CUT is correct and runs in time O(2^k^2 · k · (|V(G)| + |E(G)|)) where k = Σ_{i=1}^ℓ k_i.*

**Proof.** We prove the correctness of the algorithm by showing that it returns a solution if and only if the input instance is a yes-instance. The "only if" direction is obvious, as the algorithm returns only Z-respecting budget-respecting XY-cuts and $Z \subseteq \cup_{i=1}^l E_i$ in each recursive call.

We prove the correctness for the "if" direction. Let $C_0$ be a solution, that is, a budget-respecting XY-cut. In the initial call to **Solve**, $C_0$ is Z-respecting. It suffices to inductively show that in each call to **Solve** such that $C_0$ is Z-respecting, either the call returns a solution, or $C_0$ is $\hat{Z}$-respecting for at least one of the subcalls. Since $C_0$ is Z-respecting, the application of Theorem 5 returns objects $(P_i)_{i=1}^\lambda$, $B$, and $C$. If $C$ is budget-respecting, then the algorithm returns it and we are done. Otherwise, consider the branch $(A_1, A_2, \dots, A_\ell)$ where $A_i = \{j | E(P_j) \cap C_0 \neq \emptyset\}$. Since $C_0$ is budget-respecting, $C_0 \subseteq Z$, and no edge of $Z$ appears on more than one path $P_j$, we have $|A_i| \le k_i$ for every $i \in [\ell]$. Thus, $(A_1, A_2, \dots, A_\ell)$ is a branch considered by the algorithm. In this branch, the algorithm refines the set $Z$ to $\hat{Z}$. By the definition of $A_i$, for every $i \in [\ell]$ and $j \in [\lambda] \setminus A_i$, we have $C_0 \cap E_i \cap E(P_j) = \emptyset$. Consequently, $C_0$ is $\hat{Z}$-respecting and we are done.

For the time bound, the following observation is crucial.

**Claim 7.** *Consider one recursive call *Solve*(Z) where the application of Theorem 5 in line (a) returned objects $(P_i)_{i=1}^\lambda$, B and C. Assume that in some recursive subcall **Solve**($\hat{Z}$) invoked in line (d.3) (Figure 1), the subsequent application of Theorem 5 in line (a) of the*
subcall returned a cut of the same size, that is, the algorithm of Theorem 5 returned a cut $\tilde{C}$ of size $\tilde{\lambda} = \lambda$. Then the cut $\tilde{C}$ is budget-respecting and, consequently, is returned in line (c) of the subcall.

**Proof.** Since $|\tilde{C}| = \lambda$ is a $\tilde{Z}$-respecting $XY$-cut, $\tilde{Z} \subseteq Z$, and every edge $e \in Z$ appears on at most one path $P_i$, we have that $\tilde{C}$ consists of exactly one edge of $\tilde{Z}$ on every path $P_i$, that is, $\tilde{C} = \{e_1, e_2, \dots, e_\lambda\}$ and $e_j \in E(P_j) \cap \tilde{Z}$ for every $j \in [\lambda]$. In other words, the paths $(P_j)_{j=1}^\lambda$ still correspond to a maximum flow from $X$ to $Y$ with edges of $\tilde{Z}$ being of unit capacity and edges outside $\tilde{Z}$ of infinite capacity because $(P_j)_{j=1}^\lambda$ are paths satisfying that any two of them are disjoint on $\tilde{Z} \subseteq Z$ and $\lambda$ is still equal to the size of the maximum flow. If $e_j \in E_i$ for some $j \in [\lambda]$ and $i \in [\ell]$, then by the construction of set $\tilde{Z}$, we have $j \in A_i$. Consequently, $|\{j|e_j \in E_i\}| \le |A_i| \le k_i$ for every $i \in [\ell]$, and thus $\tilde{C}$ is budget-respecting. ▼

Claim 7 implies that the depth of the search tree is bounded by $k$, as the algorithm terminates when $\lambda$ exceeds $k$. At every step, there are at most $(2^\lambda)^\ell \le (2^k)^\ell$ different tuples $(A_1, \dots, A_\ell)$ to consider. Consequently, there are $\mathcal{O}(2^{(k-1)k\ell})$ nodes of the search tree that enter the loop in line (d) and $\mathcal{O}(2^{k^2\ell})$ nodes that invoke the algorithm of Theorem 5. As a result, the running time of the algorithm is $\mathcal{O}(2^{\ell k^2} \cdot k \cdot (|V(G)| + |E(G)|))$. ◀

# 4 Multi-budgeted important separators with applications

Similar to the concept of important separators proposed by Marx [22] (see also [9, Chapter 8]), we define *multi-budgeted important separators* as follows.

**► Definition 8.** Let $(G, X, Y, \ell, (E_i, k_i)_{i=1}^\ell)$ be a MULTI-BUDGETED CUT instance and let $Z \subseteq \bigcup_{i=1}^\ell E_i$ be a set of deletable edges. Let $C_1, C_2$ be two minimal Z-respecting budget-respecting XY-cuts. We say that $C_1$ dominates $C_2$ if

1. every vertex reachable from $X$ in $G - C_2$ is also reachable from $X$ in $G - C_1$;

2. for every $i \in [\ell]$, $|C_1 \cap E_i| \le |C_2 \cap E_i|$.

We say that $\tilde{C}$ is an *important Z-respecting budget-respecting XY-cut* if $\tilde{C}$ is a minimal Z-respecting budget-respecting XY-cut and no other minimal Z-respecting budget-respecting XY-cut dominates $\tilde{C}$. $\tilde{C}$ is an *important budget-respecting XY-cut* if it is an *important Z-respecting budget-respecting XY-cut* for $Z = \bigcup_{i=1}^\ell E_i$.

Chen et al. [4] showed an enumeration procedure for (classic) important separators using similar charging scheme as the one of the previous section. Our main result in this section is a merge of the arguments from the previous section with the arguments of Chen et al. Theorem 2 follows from Theorem 9 via an analogous arguments as in [4].

**► Theorem 9.** Let $(G, X, Y, \ell, (E_i, k_i)_{i=1}^\ell)$ be a MULTI-BUDGETED CUT instance, let $Z \subseteq \bigcup_{i=1}^\ell E_i$ be a set of deletable edges, and denote $k = \sum_{i=1}^\ell k_i$. Then one can in $2^{\mathcal{O}(k^2 \log k)} (|V(G)| + |E(G)|)$ time enumerate a family of minimal Z-respecting budget-respecting XY-cuts of size $2^{\mathcal{O}(k^2 \log k)}$ that contains all important ones.

**Proof.** Consider the recursive algorithm presented in Figure 2. The recursive procedure **ImportantCut** takes as an input a MULTI-BUDGETED CUT instance $I = (G, X, Y, \ell, (E_i, k_i)_{i=1}^\ell)$ and a set $Z \subseteq \bigcup_{i=1}^\ell E_i$, with the goal to enumerate all important Z-respecting budget-respecting XY-cuts. Note that the procedure may output some more Z-respecting budget-respecting XY-cuts; we need only to ensure that

1. it outputs all important ones,

2. it outputs $2^{\mathcal{O}(k^2 \ell \log k)}$ cuts, and

3. it runs within the desired time.
subcall returned a cut of the same size, that is, the algorithm of Theorem 5 returned a cut $\tilde{C}$ of size $\tilde{\lambda} = \lambda$. Then the cut $\tilde{C}$ is budget-respecting and, consequently, is returned in line (c) of the subcall.

**Proof.** Since $|\tilde{C}| = \lambda$ is a $\tilde{Z}$-respecting $XY$-cut, $\tilde{Z} \subseteq Z$, and every edge $e \in Z$ appears on at most one path $P_i$, we have that $\tilde{C}$ consists of exactly one edge of $\tilde{Z}$ on every path $P_i$, that is, $\tilde{C} = \{e_1, e_2, \dots, e_\lambda\}$ and $e_j \in E(P_j) \cap \tilde{Z}$ for every $j \in [\lambda]$. In other words, the paths $(P_j)_{j=1}^\lambda$ still correspond to a maximum flow from $X$ to $Y$ with edges of $\tilde{Z}$ being of unit capacity and edges outside $\tilde{Z}$ of infinite capacity because $(P_j)_{j=1}^\lambda$ are paths satisfying that any two of them are disjoint on $\tilde{Z} \subseteq Z$ and $\lambda$ is still equal to the size of the maximum flow. If $e_j \in E_i$ for some $j \in [\lambda]$ and $i \in [\ell]$, then by the construction of set $\tilde{Z}$, we have $j \in A_i$. Consequently, $|\{j|e_j \in E_i\}| \le |A_i| \le k_i$ for every $i \in [\ell]$, and thus $\tilde{C}$ is budget-respecting. ▼

Claim 7 implies that the depth of the search tree is bounded by $k$, as the algorithm terminates when $\lambda$ exceeds $k$. At every step, there are at most $(2^\lambda)^\ell \le (2^k)^\ell$ different tuples $(A_1, \dots, A_\ell)$ to consider. Consequently, there are $\mathcal{O}(2^{(k-1)k\ell})$ nodes of the search tree that enter the loop in line (d) and $\mathcal{O}(2^{k^2\ell})$ nodes that invoke the algorithm of Theorem 5. As a result, the running time of the algorithm is $\mathcal{O}(2^{\ell k^2} \cdot k \cdot (|V(G)| + |E(G)|))$. ◀

# 4 Multi-budgeted important separators with applications

Similar to the concept of important separators proposed by Marx [22] (see also [9, Chapter 8]), we define *multi-budgeted important separators* as follows.

**► Definition 8.** Let $(G, X, Y, \ell, (E_i, k_i)_{i=1}^\ell)$ be a MULTI-BUDGETED CUT instance and let $Z \subseteq \bigcup_{i=1}^\ell E_i$ be a set of deletable edges. Let $C_1, C_2$ be two minimal Z-respecting budget-respecting XY-cuts. We say that $C_1$ dominates $C_2$ if

1. every vertex reachable from $X$ in $G - C_2$ is also reachable from $X$ in $G - C_1$;

2. for every $i \in [\ell]$, $|C_1 \cap E_i| \le |C_2 \cap E_i|$.

We say that $\tilde{C}$ is an *important Z-respecting budget-respecting XY-cut* if $\tilde{C}$ is a minimal Z-respecting budget-respecting XY-cut and no other minimal Z-respecting budget-respecting XY-cut dominates $\tilde{C}$. $\tilde{C}$ is an *important budget-respecting XY-cut* if it is an *important Z-respecting budget-respecting XY-cut* for $Z = \bigcup_{i=1}^\ell E_i$.

Chen et al. [4] showed an enumeration procedure for (classic) important separators using similar charging scheme as the one of the previous section. Our main result in this section is a merge of the arguments from the previous section with the arguments of Chen et al. Theorem 2 follows from Theorem 9 via an analogous arguments as in [4].

**► Theorem 9.** Let $(G, X, Y, \ell, (E_i, k_i)_{i=1}^\ell)$ be a MULTI-BUDGETED CUT instance, let $Z \subseteq \bigcup_{i=1}^\ell E_i$ be a set of deletable edges, and denote $k = \sum_{i=1}^\ell k_i$. Then one can in $2^{\mathcal{O}(k^2 \log k)} (|V(G)| + |E(G)|)$ time enumerate a family of minimal Z-respecting budget-respecting XY-cuts of size $2^{\mathcal{O}(k^2 \log k)}$ that contains all important ones.

**Proof.** Consider the recursive algorithm presented in Figure 2. The recursive procedure **ImportantCut** takes as an input a MULTI-BUDGETED CUT instance $I = (G, X, Y, \ell, (E_i, k_i)_{i=1}^\ell)$ and a set $Z \subseteq \bigcup_{i=1}^\ell E_i$, with the goal to enumerate all important Z-respecting budget-respecting XY-cuts. Note that the procedure may output some more Z-respecting budget-respecting XY-cuts; we need only to ensure that

1. it outputs all important ones,

2. it outputs $2^{\mathcal{O}(k^2 \ell \log k)}$ cuts, and

3. it runs within the desired time.
The procedure first invokes the algorithm of Theorem 5 on $(G, X, Y, k, Z)$, where $k = \sum_{i=1}^{\ell} k_i$. If the call returned that there is no $Z$-respecting $XY$-cut of size at most $k$, we can return an empty set. Otherwise, let $(P_j)_{j=1}^{\lambda}$, $B$, and $C$ be the computed objects. We perform a branching step, with each branch labeled with a tuple $(A_1, A_2, \dots, A_\ell)$ where $A_i \subseteq [\lambda]$ and $|A_i| \le k_i$ for every $i \in [\ell]$. A branch $(A_1, A_2, \dots, A_\ell)$ is supposed to capture important cuts $C_0$ with $\{j|C_0 \cap B \cap E(P_j) \cap E_i \neq \emptyset\} \subseteq A_i$ for every $i \in [\ell]$; that is, for every $i \in [\ell]$ and $j \in [\lambda]$ we guess if $C_0$ contains a bottleneck edge of color $i$ on path $P_j$. All this information (i.e., paths $P_j$, the set $B$, the cut $C$, and the sets $A_i$) are passed to an auxiliary procedure ** Enum.**

The procedure ** Enum.** shrinks the set $Z$ according to sets $A_i$. More formally, for every $i \in [\ell]$ and $j \in [\lambda] \setminus A_i$ we delete from $Z$ all edges from $B \cap E_i \cap E(P_j)$, obtaining a set $\tilde{Z} \subseteq Z$. At this point, we check if the reduction of the set $Z$ to $\tilde{Z}$ increased the size of minimum $Z$-respecting $XY$-cut by invoking Theorem 5 on $(G, X, Y, k, \tilde{Z})$ and obtaining objects $(\hat{P}_j)_{j=1}^{\lambda}, \hat{B}, \hat{C}$ or a negative answer. If the size of the minimum cut increased, that is, $\tilde{\lambda} > \lambda$, we recurse with the original procedure **ImportantCut**. Otherwise, we add one cut to $S$, namely $\hat{C}$. Furthermore, we try to shrink one of the sets $A_i$ by one and recurse; that is, for every $i \in [\ell]$ and every $j \in A_i$, we recurse with the procedure ** Enum.** on sets $A_i'$ where $A_i' = A_i \setminus \{j\}$ and $A_{i'}' = A_{i'}$ for every $i' \in [\ell] \setminus \{i\}$.

Let us first analyze the size of the search tree. A call to **ImportantCut** invokes at most $\left(\sum_{\le k}^{\lambda} \right) \le (k\ell + 1)^k$ calls to ** Enum.** Each call to ** Enum.** either falls back to **ImportantCut** if $\tilde{\lambda} > \lambda$ or branches into $\sum_{i=1}^{\ell} |A_i| \le k\ell$ recursive calls to itself. In each recursive call, the sum $\sum_{i=1}^{\ell} |A_i|$ decreases by one. Consequently, the initial call to ** Enum.** results in at most $(k\ell)^k$ recursive calls, each potentially falling back to **ImportantCut**. Since each recursive call to **ImportantCut** uses strictly larger value of $\lambda$, which cannot grow larger than $k$, and $\ell \le k$, the total size of the recursion tree is $2^{O(k^2 \log k)}$. Each recursive call to ** Enum.** adds at most one set to $S$, while each recursive call to **ImportantCut** and ** Enum.** runs in time $O(2^{k\ell} \cdot k \cdot (|V(G)| + |E(G)|))$. The promised size of the family $S$ and the running time bound follows. It remains to show correctness, that is, that every important $Z$-respecting budget-respecting $XY$-cut is contained in $S$ returned by a call to **ImportantCut**(I, Z).

We prove by induction on the size of the recursion tree that (1) every call to **ImportantCut**(I, Z) enumerates all important $Z$-respecting budget-respecting $XY$-cuts, and (2) every call to ** Enum.**(I, Z, $(P_j)_{j=1}^{\lambda}$, B, C, $(A_i)_{i=1}^{\ell}$) enumerates all important $Z$-respecting budget-respecting $XY$-cuts $C_0$ with the property that $\{j|E_i \cap E(P_j) \cap B \cap C_0 \neq \emptyset\} \subseteq A_i$ for every $i \in [\ell]$.

The inductive step for a call **ImportantCut**(I, Z) is straightforward. Let us fix an arbitrary important $Z$-respecting budget-respecting $XY$-cut $C_0$. Since $C_0$ is budget-respecting, $C_0$ is a $Z$-respecting cut of size at most $k$, and thus the initial call to Theorem 5 cannot return NO. Consider the tuple $(A_1, A_2, \dots, A_\ell)$ where for every $i \in [\ell]$, $\{j|E(P_j) \cap E_i \cap B \cap C_0\} = A_i$. Since $C_0$ is budget-respecting and the paths $P_j$ do not share an edge of $Z$, we have that $|A_i| \le k_i$ for every $i \in [\ell]$ and the algorithm considers this tuple in one of the branches. Then, from the inductive hypothesis, the corresponding call to ** Enum.** returns a set containing $C_0$.

Consider now a call to ** Enum.**(I, Z, $(P_j)_{j=1}^{\lambda}$, B, C, $(A_i)_{i=1}^{\ell}$) and an important $Z$-respecting budget-respecting $XY$-cuts $C_0$ with the property that $\{j|E_i \cap E(P_j) \cap B \cap C_0 \neq \emptyset\} \subseteq A_i$ for every $i \in [\ell]$. By the construction of $\tilde{Z}$ and the above assumption, $C_0$ is $\tilde{Z}$-respecting. In particular, the call to the algorithm of Theorem 5 cannot return NO. Hence, in the case when $\tilde{\lambda} > \lambda$, $C_0$ is enumerated by the recursive call to **ImportantCut** and we are done. Assume then $\tilde{\lambda} = \lambda$.
The procedure first invokes the algorithm of Theorem 5 on $(G, X, Y, k, Z)$, where $k = \sum_{i=1}^{\ell} k_i$. If the call returned that there is no $Z$-respecting $XY$-cut of size at most $k$, we can return an empty set. Otherwise, let $(P_j)_{j=1}^{\lambda}$, $B$, and $C$ be the computed objects. We perform a branching step, with each branch labeled with a tuple $(A_1, A_2, \dots, A_\ell)$ where $A_i \subseteq [\lambda]$ and $|A_i| \le k_i$ for every $i \in [\ell]$. A branch $(A_1, A_2, \dots, A_\ell)$ is supposed to capture important cuts $C_0$ with $\{j|C_0 \cap B \cap E(P_j) \cap E_i \neq \emptyset\} \subseteq A_i$ for every $i \in [\ell]$; that is, for every $i \in [\ell]$ and $j \in [\lambda]$ we guess if $C_0$ contains a bottleneck edge of color $i$ on path $P_j$. All this information (i.e., paths $P_j$, the set $B$, the cut $C$, and the sets $A_i$) are passed to an auxiliary procedure **Enum**.

The procedure **Enum** shrinks the set $Z$ according to sets $A_i$. More formally, for every $i \in [\ell]$ and $j \in [\lambda] \setminus A_i$ we delete from $Z$ all edges from $B \cap E_i \cap E(P_j)$, obtaining a set $\tilde{Z} \subseteq Z$. At this point, we check if the reduction of the set $Z$ to $\tilde{Z}$ increased the size of minimum $Z$-respecting $XY$-cut by invoking Theorem 5 on $(G, X, Y, k, \tilde{Z})$ and obtaining objects $(\hat{P}_j)_{j=1}^{\lambda}, \hat{B}, \hat{C}$ or a negative answer. If the size of the minimum cut increased, that is, $\tilde{\lambda} > \lambda$, we recurse with the original procedure **ImportantCut**. Otherwise, we add one cut to $S$, namely $\hat{C}$. Furthermore, we try to shrink one of the sets $A_i$ by one and recurse; that is, for every $i \in [\ell]$ and every $j \in A_i$, we recurse with the procedure **Enum** on sets $A_i'$ where $A_i' = A_i \setminus \{j\}$ and $A_{i'}' = A_{i'}$ for every $i' \in [\ell] \setminus \{i\}$.

Let us first analyze the size of the search tree. A call to **ImportantCut** invokes at most $\binom{\lambda}{\le k} \le (k\ell + 1)^k$ calls to **Enum**. Each call to **Enum** either falls back to **ImportantCut** if $\tilde{\lambda} > \lambda$ or branches into $\sum_{i=1}^{\ell} |A_i| \le k\ell$ recursive calls to itself. In each recursive call, the sum $\sum_{i=1}^{\ell} |A_i|$ decreases by one. Consequently, the initial call to **Enum** results in at most $(k\ell)^k$ recursive calls, each potentially falling back to **ImportantCut**. Since each recursive call to **ImportantCut** uses strictly larger value of $\lambda$, which cannot grow larger than $k$, and $\ell \le k$, the total size of the recursion tree is $2^{O(k^2 \log k)}$. Each recursive call to **Enum** adds at most one set to $S$, while each recursive call to **ImportantCut** and **Enum** runs in time $O(2^{k\ell} \cdot k \cdot (|V(G)| + |E(G)|))$. The promised size of the family $S$ and the running time bound follows. It remains to show correctness, that is, that every important $Z$-respecting budget-respecting $XY$-cut is contained in $S$ returned by a call to **ImportantCut**(I, Z).

We prove by induction on the size of the recursion tree that (1) every call to **ImportantCut**(I, Z) enumerates all important $Z$-respecting budget-respecting $XY$-cuts, and (2) every call to **Enum**(I, Z, $(P_j)_{j=1}^{\lambda}, B, C, (A_i)_{i=1}^{\ell}$) enumerates all important $Z$-respecting budget-respecting $XY$-cuts $C_0$ with the property that $\{j|E_i \cap E(P_j) \cap B \cap C_0 \neq \emptyset\} \subseteq A_i$ for every $i \in [\ell]$.

The inductive step for a call **ImportantCut**(I, Z) is straightforward. Let us fix an arbitrary important $Z$-respecting budget-respecting $XY$-cut $C_0$. Since $C_0$ is budget-respecting, $C_0$ is a $Z$-respecting cut of size at most $k$, and thus the initial call to Theorem 5 cannot return NO. Consider the tuple $(A_1, A_2, \dots, A_\ell)$ where for every $i \in [\ell]$, $\{j|E(P_j) \cap E_i \cap B \cap C_0\} = A_i$. Since $C_0$ is budget-respecting and the paths $P_j$ do not share an edge of $Z$, we have that $|A_i| \le k_i$ for every $i \in [\ell]$ and the algorithm considers this tuple in one of the branches. Then, from the inductive hypothesis, the corresponding call to **Enum** returns a set containing $C_0$.

Consider now a call to **Enum**(I, Z, $(P_j)_{j=1}^{\lambda}, B, C, (A_i)_{i=1}^{\ell}$) and an important $Z$-respecting budget-respecting $XY$-cuts $C_0$ with the property that $\{j|E_i \cap E(P_j) \cap B \cap C_0 \neq \emptyset\} \subseteq A_i$ for every $i \in [\ell]$. By the construction of $\tilde{Z}$ and the above assumption, $C_0$ is $\tilde{Z}$-respecting. In particular, the call to the algorithm of Theorem 5 cannot return NO. Hence, in the case when $\tilde{\lambda} > \lambda$, $C_0$ is enumerated by the recursive call to **ImportantCut** and we are done. Assume then $\tilde{\lambda} = \lambda$.
**ImportantCut(I, Z)**

Input: A MULTI-BUDGETED CUT instance $I = (G, X, Y, \ell, (E_i, k_i)_{i=1}^\ell)$ and a set $Z \subseteq \bigcup_{i=1}^\ell E_i$.

Output: a family $\mathcal{S}$ of minimal Z-respecting budget-respecting XY-cuts that contains all important ones.

1. $\mathcal{S} := \emptyset$;

2. apply the algorithm of Theorem 5 to $(G, X, Y, k, Z)$ with $k = \sum_{i=1}^\ell k_i$, obtaining either objects $(P_i)_{i=1}^\lambda, B$, and $C$, or an answer NO;

3. if an answer NO is obtained, **then return** $\mathcal{S}$;

4. **for each** $(A_1, \dots, A_\ell)$ such that for every $i$ in $[\ell]$, $A_i \subseteq [\lambda]$ and $|A_i| \le k_i$ **do**

4.1 $\mathcal{S} := \mathcal{S} \cup \text{Enum}(I, Z, (P_j)_{j=1}^\lambda, B, C, (A_i)_{i=1}^\ell)$

5. **return** $\mathcal{S}$

**Enum(I, Z, (P_j)_{j=1}^\lambda, B, C, (A_i)_{i=1}^\ell)**

Input: A MULTI-BUDGETED CUT instance $I = (G, X, Y, \ell, (E_i, k_i)_{i=1}^\ell)$, a set $Z \subseteq \bigcup_{i=1}^\ell E_i$, a family $(P_j)_{j=1}^\lambda$ of paths from $X$ to $Y$ such that every edge of $Z$ appears on at most one path $P_j$, a set $B$ consisting of all edges that participate in some minimum Z-respecting XY-cut, a minimum Z-respecting XY-cut $C$ closest to $Y$, and sets $A_i \subseteq [\lambda]$ of size at most $k_i$ for every $i \in [\ell]$

Output: a family $\mathcal{S}$ of minimal Z-respecting budget-respecting XY-cuts that contains all cuts $C_0$ that are important Z-respecting budget respecting XY-cuts and satisfy $\{j|E(P_j) \cap B \cap C_0 \cap E_i \neq \emptyset\} \subseteq A_i$ for every $i \in [\ell]$.

a. $\hat{Z} := Z$;

b. **for each** $i \in [\ell]$ **do**
   for each $j \in [\lambda] \setminus A_i$ **do**

$$ \hat{Z} := \hat{Z} \setminus (B \cap E_i \cap E(P_j)); $$

c. apply the algorithm of Theorem 5 to $(G, X, Y, k, \hat{Z})$, obtaining either objects $(\hat{P}_i)_{i=1}^\lambda, \hat{B}$, and $\hat{C}$ or an answer NO;

d. if $\hat{\lambda}$ exists and $\hat{\lambda} > \lambda$, **then**

d.1 $\mathcal{S} := \mathcal{S} \cup \text{ImportantCut}(I, \hat{Z})$;

e. **else if** $\hat{\lambda}$ exists and equals $\lambda$, **then**

e.1 $\mathcal{S} := \mathcal{S} \cup \{\hat{C}\}$;

e.2 **for each** $i \in [\ell]$ **do**
   **for each** $j \in A_i$ **do**

$$ A'_i := A_i \setminus \{j\} \text{ and } A'_{i'} := A_{i'} \text{ for every } i' \in [\ell] \setminus \{i\} $$

$$ \mathcal{S} := \mathcal{S} \cup \text{Enum}(I, \hat{Z}, (P_j)_{j=1}^\lambda, \hat{B}, \hat{C}, (A'_i)_{i=1}^\ell). $$

f. **return** $\mathcal{S}$

Figure 2 FPT algorithm for enumerating important multi-budgeted Z-respecting XY-cuts.

For $i \in [\ell]$, let $\hat{A}_i = \{j|E_i \cap E(P_j) \cap \hat{B} \cap C_0 \neq \emptyset\}$. Since $\hat{Z} \subseteq Z$ but the sizes of minimum Z-respecting and $\hat{Z}$-respecting XY-cuts are the same, we have $\hat{B} \subseteq B$. Consequently, $\hat{A}_i \subseteq A_i$ for every $i \in [\ell]$.

Assume there exists $i \in [\ell]$ such that $\hat{A}_i \subsetneq A_i$ and let $j \in A_i \setminus \hat{A}_i$. Consider then the branch $(i, j)$ of the **Enum** procedure, that is, the recursive call with $A'_i = A_i \setminus \{j\}$ and $A'_{i'} = A_{i'}$ for $i' \in [\ell] \setminus \{i\}$. Observe that we have $\{j|E_{i'} \cap E(P_j) \cap \hat{B} \cap C_0 \neq \emptyset\} \subseteq A'_{i'}$ for every $i' \in [\ell]$ and, by the inductive hypothesis, the corresponding call to **Enum** enumerates $C_0$. Hence, we are left only with the case $\hat{A}_i = A_i$, that is, $A_i = \{j|E_i \cap E(P_j) \cap \hat{B} \cap C_0 \neq \emptyset\}$ for every $i \in [\ell]$.

We claim that in this case $C_0 = \hat{C}$. Assume otherwise. Since $|\hat{C}| = \hat{\lambda} = \lambda$ and $\hat{Z} \subseteq Z$, $\hat{C}$ contains exactly one edge on every path $P_j$. Also, $\hat{C} \subseteq \hat{B}$ by the definition of the set $\hat{B}$. Since $\hat{C}$ is the minimum $\hat{Z}$-respecting XY-cut that is closest to $Y$, $\hat{C} = \{e_1, e_2, \dots, e_\lambda\}$ where $e_j$ is the last (closest to $Y$) edge of $\hat{B}$ on the path $P_j$ for every $j \in [\lambda]$.

Let $R_0$ and $\hat{R}$ be the set of vertices reachable from $X$ in $G - C_0$ and $G - \hat{C}$, respectively.
**ImportantCut(I, Z)**

Input: A MULTI-BUDGETED CUT instance $I = (G, X, Y, \ell, (E_i, k_i)_{i=1}^\ell)$ and a set $Z \subseteq \bigcup_{i=1}^\ell E_i$.

Output: a family $\mathcal{S}$ of minimal Z-respecting budget-respecting XY-cuts that contains all important ones.

1. $\mathcal{S} := \emptyset$;

2. apply the algorithm of Theorem 5 to $(G, X, Y, k, Z)$ with $k = \sum_{i=1}^\ell k_i$, obtaining either objects $(P_i)_{i=1}^\lambda, B$, and $C$, or an answer NO;

3. if an answer NO is obtained, **then return** $\mathcal{S}$;

4. **for each** $(A_1, \dots, A_\ell)$ such that for every $i$ in $[\ell]$, $A_i \subseteq [\lambda]$ and $|A_i| \le k_i$ **do**

4.1 $\mathcal{S} := \mathcal{S} \cup \text{Enum}(I, Z, (P_j)_{j=1}^\lambda, B, C, (A_i)_{i=1}^\ell)$

5. **return** $\mathcal{S}$

**Enum(I, Z, (P_j)_{j=1}^\lambda, B, C, (A_i)_{i=1}^\ell)**

Input: A MULTI-BUDGETED CUT instance $I = (G, X, Y, \ell, (E_i, k_i)_{i=1}^\ell)$, a set $Z \subseteq \bigcup_{i=1}^\ell E_i$, a family $(P_j)_{j=1}^\lambda$ of paths from $X$ to $Y$ such that every edge of $Z$ appears on at most one path $P_j$, a set $B$ consisting of all edges that participate in some minimum Z-respecting XY-cut, a minimum Z-respecting XY-cut $C$ closest to $Y$, and sets $A_i \subseteq [\lambda]$ of size at most $k_i$ for every $i \in [\ell]$

Output: a family $\mathcal{S}$ of minimal Z-respecting budget-respecting XY-cuts that contains all cuts $C_0$ that are important Z-respecting budget respecting XY-cuts and satisfy $\{j|E(P_j) \cap B \cap C_0 \cap E_i \neq \emptyset\} \subseteq A_i$ for every $i \in [\ell]$.

a. $\hat{Z} := Z$;

b. **for each** $i \in [\ell]$ **do**
   for each $j \in [\lambda] \setminus A_i$ **do**

$$ \hat{Z} := \hat{Z} \setminus (B \cap E_i \cap E(P_j)); $$

c. apply the algorithm of Theorem 5 to $(G, X, Y, k, \hat{Z})$, obtaining either objects $(\hat{P}_i)_{i=1}^\lambda, \hat{B}$, and $\hat{C}$ or an answer NO;

d. if $\hat{\lambda}$ exists and $\hat{\lambda} > \lambda$, **then**

d.1 $\mathcal{S} := \mathcal{S} \cup \text{ImportantCut}(I, \hat{Z})$;

e. **else if** $\hat{\lambda}$ exists and equals $\lambda$, **then**

e.1 $\mathcal{S} := \mathcal{S} \cup \{\hat{C}\}$;

e.2 **for each** $i \in [\ell]$ **do**
   **for each** $j \in A_i$ **do**

$$ A'_i := A_i \setminus \{j\} \text{ and } A'_{i'} := A_{i'} \text{ for every } i' \in [\ell] \setminus \{i\} $$

$$ \mathcal{S} := \mathcal{S} \cup \text{Enum}(I, \hat{Z}, (P_j)_{j=1}^\lambda, \hat{B}, \hat{C}, (A'_i)_{i=1}^\ell). $$

f. **return** $\mathcal{S}$

<caption>**Figure 2** FPT algorithm for enumerating important multi-budgeted Z-respecting XY-cuts.</caption>

For $i \in [\ell]$, let $\hat{A}_i = \{j|E_i \cap E(P_j) \cap \hat{B} \cap C_0 \neq \emptyset\}$. Since $\hat{Z} \subseteq Z$ but the sizes of minimum Z-respecting and $\hat{Z}$-respecting XY-cuts are the same, we have $\hat{B} \subseteq B$. Consequently, $\hat{A}_i \subseteq A_i$ for every $i \in [\ell]$.

Assume there exists $i \in [\ell]$ such that $\hat{A}_i \subsetneq A_i$ and let $j \in A_i \setminus \hat{A}_i$. Consider then the branch $(i, j)$ of the **Enum** procedure, that is, the recursive call with $A'_i = A_i \setminus \{j\}$ and $A'_{i'} = A_{i'}$ for $i' \in [\ell] \setminus \{i\}$. Observe that we have $\{j|E_{i'} \cap E(P_j) \cap \hat{B} \cap C_0 \neq \emptyset\} \subseteq A'_{i'}$ for every $i' \in [\ell]$ and, by the inductive hypothesis, the corresponding call to **Enum** enumerates $C_0$. Hence, we are left only with the case $\hat{A}_i = A_i$, that is, $A_i = \{j|E_i \cap E(P_j) \cap \hat{B} \cap C_0 \neq \emptyset\}$ for every $i \in [\ell]$.

We claim that in this case $C_0 = \hat{C}$. Assume otherwise. Since $|\hat{C}| = \hat{\lambda} = \lambda$ and $\hat{Z} \subseteq Z$, $\hat{C}$ contains exactly one edge on every path $P_j$. Also, $\hat{C} \subseteq \hat{B}$ by the definition of the set $\hat{B}$. Since $\hat{C}$ is the minimum $\hat{Z}$-respecting XY-cut that is closest to $Y$, $\hat{C} = \{e_1, e_2, \dots, e_\lambda\}$ where $e_j$ is the last (closest to $Y$) edge of $\hat{B}$ on the path $P_j$ for every $j \in [\lambda]$.

Let $R_0$ and $\hat{R}$ be the set of vertices reachable from $X$ in $G - C_0$ and $G - \hat{C}$, respectively.
<figure><img src="image_98.png" /><figcaption>Figure 3 A schematic picture of a 4-bowtie.</figcaption></figure>

Let $D$ be a minimal $XY$-cut contained in $\delta^+(R_0 \cup \hat{R})$. (Note that $\delta^+(R_0 \cup \hat{R})$ is an $XY$-cut because $X \subseteq R_0 \cup \hat{R}$ and $Y \cap (R_0 \cup \hat{R}) = \emptyset$.) Then since $D \subseteq C_0 \cup \hat{C} \subseteq Z$, $D$ is $Z$-respecting. By definition, every vertex reachable from $X$ in $G - R_0$ is also reachable from $X$ in $G - D$.

We claim that $D$ is budget-respecting and, furthermore, dominates $C_0$. Fix a color $i \in [l]$; our goal is to prove that $|D \cap E_i| \le |C_0 \cap E_i|$. To this end, we charge every edge of color $i$ in $D \setminus C_0$ to a distinct edge of color $i$ in $C_0 \setminus D$. Since $D \subseteq C_0 \cup \hat{C}$, we have that $D \setminus C_0 \subseteq \hat{C}$, that is, an edge of $D \setminus C_0$ of color $i$ is an edge $e_j$ for some $j \in [\lambda]$ with $e_j \in E_i$ and $e_j \in D \setminus C_0$.

Recall that we are working in the case $A_i = \{j | E_i \cap E(P_j) \cap \hat{B} \cap C_0 \neq \emptyset\}$. Since $e_j \in \hat{C} \subseteq \hat{Z}$, we have that $j \in A_i$. Hence, there exists $e'_j \in E_i \cap E(P_j) \cap \hat{B} \cap C_0$. By the definition of $\hat{C}$, $e_j$ is the last (closest to $Y$) edge of $\hat{B}$ on $P_j$. Since $e_j \notin C_0$, $e'_j \neq e_j$ and $e'_j$ lies on the subpath of $P_j$ between $X$ and the tail of $e_j$. This entire subpath is contained in $\hat{R}$ and, hence, $e'_j \notin D$.

We charge $e_j$ to $e'_j$. Since $e'_j \in E(P_j) \cap \hat{B} \cap (C_0 \setminus D)$, for distinct $j$, the edges $e'_j$ are distinct as the paths $P_j$ do not share an edge belonging to $Z$ and $\hat{B} \subseteq \hat{Z} \subseteq Z$. Consequently, $|D \cap E_i| \le |C_0 \cap E_i|$. This finishes the proof that $D$ dominates $C_0$.

Since $C_0$ is important, we have $D = C_0$. In particular, $\hat{R} \subseteq R_0$. On the other hand, for every $j \in [\lambda]$ we have that $e_j \in \hat{C} \subseteq \hat{Z} \subseteq Z \subseteq \bigcup_{i=1}^l E_i$. In particular, there exists $i \in [l]$ such that $e_j \in E_i$ and $j \in A_i$. Hence, we also have $E_i \cap E(P_j) \cap \hat{B} \cap C_0 \neq \emptyset$. But the entire subpath of $P_j$ from $X$ to the tail of $e_j$ lies in $\hat{R} \subseteq R_0$, while $e_j$ is the last edge of $\hat{B}$ on $P_j$. Hence, $e_j \in C_0$. Since the choice of $j$ is arbitrary, $\hat{C} \subseteq C_0$. Since $\hat{C}$ is an $XY$-cut and $C_0$ is minimal, $\hat{C} = C_0$ as claimed.

This finishes the proof of Theorem 9.

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

5 Bound on the number of solutions closest to t

In this section we sketch the proofs of Theorems 3 and 4. The central definition of this section is the following (see also Figure 3).

► **Definition 10.** Let $G$ be a directed graph with distinguished vertices $s$ and $t$ and let $k$ be an integer. An *a-bowtie* is a sequence $C_1, C_2, \dots, C_a$ of pairwise disjoint minimal $st$-cuts of size $k$ each such that each cut $C_i$ can be partitioned $C_i = A_i \uplus B_i$ such that for every $1 \le i < j \le a$, the set $A_i$ is exactly the set of edges of $C_i$ reachable from $s$ in $G - C_j$ and $B_j$ is exactly the set of edges of $C_j$ reachable from $s$ in $G - C_i$.

Our main graph-theoretic result is the following. The proof is deferred to the full version of the paper.
<figure><img src="image_101.png" /><figcaption>Figure 3 A schematic picture of a 4-bowtie.</figcaption></figure>

Let $D$ be a minimal $XY$-cut contained in $\delta^+(R_0 \cup \hat{R})$. (Note that $\delta^+(R_0 \cup \hat{R})$ is an $XY$-cut because $X \subseteq R_0 \cup \hat{R}$ and $Y \cap (R_0 \cup \hat{R}) = \emptyset$.) Then since $D \subseteq C_0 \cup \hat{C} \subseteq Z$, $D$ is $Z$-respecting. By definition, every vertex reachable from $X$ in $G - R_0$ is also reachable from $X$ in $G - D$.

We claim that $D$ is budget-respecting and, furthermore, dominates $C_0$. Fix a color $i \in [l]$; our goal is to prove that $|D \cap E_i| \le |C_0 \cap E_i|$. To this end, we charge every edge of color $i$ in $D \setminus C_0$ to a distinct edge of color $i$ in $C_0 \setminus D$. Since $D \subseteq C_0 \cup \hat{C}$, we have that $D \setminus C_0 \subseteq \hat{C}$, that is, an edge of $D \setminus C_0$ of color $i$ is an edge $e_j$ for some $j \in [\lambda]$ with $e_j \in E_i$ and $e_j \in D \setminus C_0$.

Recall that we are working in the case $A_i = \{j | E_i \cap E(P_j) \cap \hat{B} \cap C_0 \neq \emptyset\}$. Since $e_j \in \hat{C} \subseteq \hat{Z}$, we have that $j \in A_i$. Hence, there exists $e'_j \in E_i \cap E(P_j) \cap \hat{B} \cap C_0$. By the definition of $\hat{C}$, $e_j$ is the last (closest to $Y$) edge of $\hat{B}$ on $P_j$. Since $e_j \notin C_0$, $e'_j \neq e_j$ and $e'_j$ lies on the subpath of $P_j$ between $X$ and the tail of $e_j$. This entire subpath is contained in $\hat{R}$ and, hence, $e'_j \notin D$.

We charge $e_j$ to $e'_j$. Since $e'_j \in E(P_j) \cap \hat{B} \cap (C_0 \setminus D)$, for distinct $j$, the edges $e'_j$ are distinct as the paths $P_j$ do not share an edge belonging to $Z$ and $\hat{B} \subseteq \hat{Z} \subseteq Z$. Consequently, $|D \cap E_i| \le |C_0 \cap E_i|$. This finishes the proof that $D$ dominates $C_0$.

Since $C_0$ is important, we have $D = C_0$. In particular, $\hat{R} \subseteq R_0$. On the other hand, for every $j \in [\lambda]$ we have that $e_j \in \hat{C} \subseteq \hat{Z} \subseteq Z \subseteq \bigcup_{i=1}^l E_i$. In particular, there exists $i \in [l]$ such that $e_j \in E_i$ and $j \in A_i$. Hence, we also have $E_i \cap E(P_j) \cap \hat{B} \cap C_0 \neq \emptyset$. But the entire subpath of $P_j$ from $X$ to the tail of $e_j$ lies in $\hat{R} \subseteq R_0$, while $e_j$ is the last edge of $\hat{B}$ on $P_j$. Hence, $e_j \in C_0$. Since the choice of $j$ is arbitrary, $\hat{C} \subseteq C_0$. Since $\hat{C}$ is an $XY$-cut and $C_0$ is minimal, $\hat{C} = C_0$ as claimed.

This finishes the proof of Theorem 9.

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

5 Bound on the number of solutions closest to t

In this section we sketch the proofs of Theorems 3 and 4. The central definition of this section is the following (see also Figure 3).

► **Definition 10.** Let $G$ be a directed graph with distinguished vertices $s$ and $t$ and let $k$ be an integer. An *a-bowtie* is a sequence $C_1, C_2, \dots, C_a$ of pairwise disjoint minimal $st$-cuts of size $k$ each such that each cut $C_i$ can be partitioned $C_i = A_i \uplus B_i$ such that for every $1 \le i < j \le a$, the set $A_i$ is exactly the set of edges of $C_i$ reachable from $s$ in $G - C_j$ and $B_j$ is exactly the set of edges of $C_j$ reachable from $s$ in $G - C_i$.

Our main graph-theoretic result is the following. The proof is deferred to the full version of the paper.