Since $K$ is a clique, there is an index $i$ such that $K \subseteq C_i$. For each $v \in K$, let $\ell_v$ be the smallest index such that $v \in C_{\ell_v}$ and $r_v$ be the largest index such that $v \in C_{r_v}$. Recall that $\ell_v$ and $r_v$ completely define the neighborhood of $v$. Note that for all $v \in K$, $\ell_v \le i \le r_v$ and that either $\ell_v \ne 1$ or $r_v \ne p$, since otherwise $v$ would be a universal vertex, which is impossible because we applied Rule 1 exhaustively. Hence, the maximum number of distinct possible combinations of indices $\ell_v$ and $r_v$ is $i \cdot (p - i + 1) - 1$, which is maximized when $i = \lfloor \frac{p+1}{2} \rfloor$, giving a total number of

$$ \lfloor \frac{p+1}{2} \rfloor \cdot \lfloor \frac{p+1}{2} \rfloor - 1 $$

distinct equivalence classes. Using the fact that $p \le 2|\bar{M}|+1$ by Claim 5, and that $|\bar{M}| \le k-1$, we get

$$ \lfloor \frac{p+1}{2} \rfloor \cdot \lfloor \frac{p+1}{2} \rfloor - 1 = k^2 - 1. $$

Since, by virtue of the application of Rule 2, each class has at most $(k-1)$ elements, we have

$$ |V(G)| = |V(\bar{M})| + |V(K)| \le 2(k-1) + (k-1) \cdot (k^2 - 1) = k^3 - k^2 + k - 1. \quad \triangle $$

Similarly to Theorem 2, we can show that the analysis of the kernel size in the proof of Proposition 4 is tight. Indeed, given an integer $k$, it is possible to build an interval graph with $2k-1$ maximal cliques, with $(k-1)$ vertices belonging exactly to cliques $C_i, \dots, C_j$, for each

$$ (i, j) \in [1, k] \times [k, 2k-1] \setminus \{(1, 2k-1)\}, $$

and one exclusive vertex in each clique, except for clique $C_k$, corresponding to vertices of $V(\bar{M})$. That interval graph attains the bound in the statement of Proposition 4 and cannot be reduced by Rule 1 or Rule 2.

**Remark.** The result of Proposition 4 cannot be generalized to chordal graphs, as split graphs are chordal, and by Theorem 3 the existence of a polynomial kernel on split graphs would imply that $\mathrm{NP} \subseteq \mathrm{coNP/poly}$.

Our last result deals with a subclass of split graphs motivated by the fact that DUAL WEIGHTED COLORING on split graphs seems to have a close relation with the SET COVER problem.

**Proposition 5.** The DUAL WEIGHTED COLORING problem restricted to split graphs such that each vertex in the clique has at most $d$ non-neighbors in the stable set, for some constant $d \ge 1$, admits a kernel with at most $k^{d+1}$ vertices. Furthermore, for any $d \ge 2$ and $\varepsilon > 0$, a kernel with $O(k^{\frac{d-3}{2}-\varepsilon})$ vertices does not exist unless $\mathrm{NP} \subseteq \mathrm{coNP/poly}$.

**Proof.** For the positive result, let $(G, w, k)$ be an instance of DUAL WEIGHTED COLORING, with $G$ being a split graph such that each vertex in the clique has at most $d$ non-neighbors in the stable set, for some integer $d \ge 2$. We mimic the proof of Theorem 2, and we slightly change the analysis. Recall that $|V(\bar{M})| \le 2(k-1)$ and that the number of special classes in $C$, each containing exactly one vertex, is at most $k_s$. Concerning the normal classes in $C$, we will obtain an improved bound using that each vertex in the clique has at most $d$ non-neighbors in the stable set, and therefore in the graph $G$ itself as well. Thus, the number of distinct neighborhoods in the set consisting of the avoidable vertices in
12:12 Dual Parameterization of Weighted Coloring

the normal edges in $\bar{M}$, which is an upper bound on the number of normal classes, is at most $\sum_{i=0}^{d} \binom{k_n}{i} \le \sum_{i=0}^{d} \frac{k_n^i}{i!} \le \max\{2, k_n^d\}$, where the last inequality can be easily proved by induction.

Therefore, if $(G, w, k)$ is a reduced instance, then

$$ 
\begin{aligned}
|V(G)| &= |V(\bar{M})| + |K| \le 2(k-1) + k_s + k_n^d \cdot (k-1) \\
&\le 2(k-1) + (k-1)^d \cdot (k-1) \le k^{d+1}.
\end{aligned}
$$

For the negative result, we reuse the reduction of Theorem 3, but starting from the d-SET COVER problem, that is, the restriction of SET COVER to instances where each set contains at most $d$ elements. Hermelin and Wu [30] proved that, for any fixed $d \ge 2$, d-SET COVER does not admit kernels of size $O(k^{d-3-\epsilon})$ for any $\epsilon > 0$, unless NP $\subseteq$ coNP/poly, where $k$ is the size of the solution. Nevertheless, in the hardness proof for d-SET COVER given in [30], the size of the universe of the constructed instance is equal to $kd$. Therefore, we can conclude that d-SET COVER does not admit kernels of size $O(k^{d-3-\epsilon})$ for any $\epsilon > 0$, unless NP $\subseteq$ coNP/poly, where $k$ is the size of the universe. Moreover, the results in [30] also rule out the existence of a bikernel, that is, a relaxed kernelization notion where the output instance is not necessarily of the same problem.

Given an instance $(U, S, k, \ell)$ of d-SET COVER, where $k$ is the size of the universe, we construct an instance $(G, w, k')$ of DUAL WEIGHTED COLORING as in the proof of Theorem 3. Note that $G$ is indeed a split graph such that each vertex in the clique has at most $d$ non-neighbors in the stable set, and recall that $k' = k(\ell+1) - \ell$. Since we may assume that $\ell \le k$, it follows that $k' \le k^2$. Assume for contradiction that DUAL WEIGHTED COLORING restricted to this type of instances admits a kernel with $O(k^{\frac{d-3}{2}-\epsilon})$ vertices, for some $\epsilon > 0$. Then the composition of the above reduction with such a kernel would yield a bikernel for d-SET COVER of size $O(k^{d-3-\epsilon})$ for some $\epsilon > 0$, which is impossible by the results of [30] unless NP $\subseteq$ coNP/poly. $\quad$

5 Further research

In this article we investigated the dual parameterization of the WEIGHTED COLORING problem, and we provided several positive and negative results, especially concerning polynomial kernelization. It would be interesting to identify other classes of (dense) graphs on which the problem admits polynomial kernels. It remains to close the gap in the degree of the polynomial kernels on the subclasses of split graphs considered in Proposition 5. Another question is whether the cubic kernel on interval graphs given in Proposition 4 can be improved, even on proper interval graphs.

Concerning Theorem 1, using the techniques of Björklund et al. [4] it may be possible to compute the values $T(X, i)$ defined in the proof, for every $X$ and $i$, in time $2^{|V(\bar{M})| \cdot n^{O(1)}} \cdot \max_{v \in V(G)} w(v)$, which would yield an overall running time of $4^k \cdot n^{O(1)} \cdot \max_{v \in V(G)} w(v)$. Finally, one could try to prove lower bounds under the SETH (see [36]) on the running time of any FPT algorithm solving DUAL WEIGHTED COLORING, hopefully getting close to the running time given in Theorem 1.

References

1 Júlio Araújo, Julien Baste, and Ignasi Sau. Ruling out FPT algorithms for Weighted Coloring on forests. *Theoretical Computer Science*, 729:11–19, 2018.

2 Júlio Araújo, Nicolas Nisse, and Stéphane Pérennes. Weighted Coloring in Trees. *SIAM Journal on Discrete Mathematics*, 28(4):2029–2041, 2014.
12:12 Dual Parameterization of Weighted Coloring

the normal edges in $\bar{M}$, which is an upper bound on the number of normal classes, is at most $\sum_{i=0}^{d} \binom{k_n}{i} \le \sum_{i=0}^{d} \frac{k_n^i}{i!} \le \max\{2, k_n^d\}$, where the last inequality can be easily proved by induction.

Therefore, if $(G, w, k)$ is a reduced instance, then

$$ 
\begin{aligned}
|V(G)| &= |V(\bar{M})| + |K| \le 2(k-1) + k_s + k_n^d \cdot (k-1) \\
&\le 2(k-1) + (k-1)^d \cdot (k-1) \le k^{d+1}.
\end{aligned}
$$

For the negative result, we reuse the reduction of Theorem 3, but starting from the d-SET COVER problem, that is, the restriction of SET COVER to instances where each set contains at most $d$ elements. Hermelin and Wu [30] proved that, for any fixed $d \ge 2$, d-SET COVER does not admit kernels of size $O(k^{d-3-\epsilon})$ for any $\epsilon > 0$, unless NP $\subseteq$ coNP/poly, where $k$ is the size of the solution. Nevertheless, in the hardness proof for d-SET COVER given in [30], the size of the universe of the constructed instance is equal to $kd$. Therefore, we can conclude that d-SET COVER does not admit kernels of size $O(k^{d-3-\epsilon})$ for any $\epsilon > 0$, unless NP $\subseteq$ coNP/poly, where $k$ is the size of the universe. Moreover, the results in [30] also rule out the existence of a bikernel, that is, a relaxed kernelization notion where the output instance is not necessarily of the same problem.

Given an instance $(U, S, k, \ell)$ of d-SET COVER, where $k$ is the size of the universe, we construct an instance $(G, w, k')$ of DUAL WEIGHTED COLORING as in the proof of Theorem 3. Note that $G$ is indeed a split graph such that each vertex in the clique has at most $d$ non-neighbors in the stable set, and recall that $k' = k(\ell+1) - \ell$. Since we may assume that $\ell \le k$, it follows that $k' \le k^2$. Assume for contradiction that DUAL WEIGHTED COLORING restricted to this type of instances admits a kernel with $O(k^{\frac{d-3}{2}-\epsilon})$ vertices, for some $\epsilon > 0$. Then the composition of the above reduction with such a kernel would yield a bikernel for d-SET COVER of size $O(k^{d-3-\epsilon})$ for some $\epsilon > 0$, which is impossible by the results of [30] unless NP $\subseteq$ coNP/poly. $\quad$

5 Further research

In this article we investigated the dual parameterization of the WEIGHTED COLORING problem, and we provided several positive and negative results, especially concerning polynomial kernelization. It would be interesting to identify other classes of (dense) graphs on which the problem admits polynomial kernels. It remains to close the gap in the degree of the polynomial kernels on the subclasses of split graphs considered in Proposition 5. Another question is whether the cubic kernel on interval graphs given in Proposition 4 can be improved, even on proper interval graphs.

Concerning Theorem 1, using the techniques of Björklund et al. [4] it may be possible to compute the values $T(X, i)$ defined in the proof, for every $X$ and $i$, in time $2^{|V(\bar{M})| \cdot n^{O(1)}} \cdot \max_{v \in V(G)} w(v)$, which would yield an overall running time of $4^k \cdot n^{O(1)} \cdot \max_{v \in V(G)} w(v)$. Finally, one could try to prove lower bounds under the SETH (see [36]) on the running time of any FPT algorithm solving DUAL WEIGHTED COLORING, hopefully getting close to the running time given in Theorem 1.

References

1 Júlio Araújo, Julien Baste, and Ignasi Sau. Ruling out FPT algorithms for Weighted Coloring on forests. *Theoretical Computer Science*, 729:11–19, 2018.

2 Júlio Araújo, Nicolas Nisse, and Stéphane Pérennes. Weighted Coloring in Trees. *SIAM Journal on Discrete Mathematics*, 28(4):2029–2041, 2014.
3 Manu Basavaraju, Mathew C. Francis, M. S. Ramanujan, and Saket Saurabh. Partially Polynomial Kernels for Set Cover and Test Cover. *SIAM Journal on Discrete Mathematics*, 30(3):1401–1423, 2016. doi:10.1137/15M1039584.

4 Andreas Björklund, Thore Husfeldt, and Mikko Koivisto. Set Partitioning via Inclusion-Exclusion. *SIAM Journal on Computing*, 39(2):546–563, 2009.

5 Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On problems without polynomial kernels. *Journal of Computer and System Sciences*, 75(8):423–434, 2009.

6 Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization Lower Bounds by Cross-Composition. *SIAM Journal on Discrete Mathematics*, 28(1):277–305, 2014.

7 Hans L. Bodlaender, Stéphan Thomassé, and Anders Yeo. Kernel bounds for disjoint cycles and disjoint paths. *Theoretical Computer Science*, 412(35):4570–4578, 2011. doi: 10.1016/j.tcs.2011.04.039.

8 Édouard Bonnet and Vangelis Th. Paschos. Dual parameterization and parameterized approximability of subset graph problems. *RAIRO - Operations Research*, 51(1):261–266, 2017. doi:10.1051/ro/2016018.

9 Benny Chor, Mike Fellows, and David W. Juedes. Linear Kernels in Linear Time, or How to Save *k* Colors in *O*(n²) Steps. In *Proc. of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)*, volume 3353 of LNCS, pages 257–269, 2004. doi:10.1007/978-3-540-30559-0_22.

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

11 Dominique de Werra, Marc Demange, Bruno Escoffier, Jérôme Monnot, and Vangelis Th. Paschos. Weighted coloring on planar, bipartite and split graphs: Complexity and approximation. *Discrete Applied Mathematics*, 157(4):819–832, 2009.

12 Marc Demange, Dominique de Werra, Jérôme Monnot, and Vangelis Th. Paschos. Weighted Node Coloring: When Stable Sets Are Expensive. In *Proc. of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)*, volume 2573 of LNCS, pages 114–125. Springer, 2002.

13 Marc Demange, Pascal Grisoni, and Vangelis Th. Paschos. Approximation Results for the Minimum Graph Coloring Problem. *Information Processing Letters*, 50(1):19–23, 1994. doi:10.1016/0020-0190(94)90039-6.

14 Reinhard Diestel. *Graph Theory*, volume 173. Springer-Verlag, 4th edition, 2010.

15 Michael Dom, Daniel Lokshtanov, and Saket Saurabh. Kernelization Lower Bounds Through Colors and IDs. *ACM Transactions on Algorithms*, 11(2):13:1–13:20, 2014. doi:10.1145/2650261.

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

17 Rong-chii Duh and Martin Fürer. Approximation of *k*-Set Cover by Semi-Local Optimization. In *Proc. of the 29th Annual ACM Symposium on the Theory of Computing (STOC)*, pages 256–264, 1997. doi:10.1145/258533.258599.

18 Bruno Escoffier. Saving Colors and Max Coloring: Some Fixed-Parameter Tractability Results. In *Proc. of the 42nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG)*, volume 9941 of LNCS, pages 50–61, 2016.

19 Bruno Escoffier, Jérôme Monnot, and Vangelis Th. Paschos. Weighted Coloring: further complexity and approximability results. *Information Processing Letters*, 97(3):98–103, 2006.

20 Fedor V. Fomin and Dieter Kratsch. *Exact Exponential Algorithms*. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2010.
3 Manu Basavaraju, Mathew C. Francis, M. S. Ramanujan, and Saket Saurabh. Partially Polynomial Kernels for Set Cover and Test Cover. *SIAM Journal on Discrete Mathematics*, 30(3):1401–1423, 2016. doi:10.1137/15M1039584.

4 Andreas Björklund, Thore Husfeldt, and Mikko Koivisto. Set Partitioning via Inclusion-Exclusion. *SIAM Journal on Computing*, 39(2):546–563, 2009.

5 Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On problems without polynomial kernels. *Journal of Computer and System Sciences*, 75(8):423–434, 2009.

6 Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization Lower Bounds by Cross-Composition. *SIAM Journal on Discrete Mathematics*, 28(1):277–305, 2014.

7 Hans L. Bodlaender, Stéphan Thomassé, and Anders Yeo. Kernel bounds for disjoint cycles and disjoint paths. *Theoretical Computer Science*, 412(35):4570–4578, 2011. doi: 10.1016/j.tcs.2011.04.039.

8 Édouard Bonnet and Vangelis Th. Paschos. Dual parameterization and parameterized approximability of subset graph problems. *RAIRO - Operations Research*, 51(1):261–266, 2017. doi:10.1051/ro/2016018.

9 Benny Chor, Mike Fellows, and David W. Juedes. Linear Kernels in Linear Time, or How to Save *k* Colors in *O*(n²) Steps. In *Proc. of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)*, volume 3353 of *LNCS*, pages 257–269, 2004. doi:10.1007/978-3-540-30559-0_22.

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

11 Dominique de Werra, Marc Demange, Bruno Escoffier, Jérôme Monnot, and Vangelis Th. Paschos. Weighted coloring on planar, bipartite and split graphs: Complexity and approximation. *Discrete Applied Mathematics*, 157(4):819–832, 2009.

12 Marc Demange, Dominique de Werra, Jérôme Monnot, and Vangelis Th. Paschos. Weighted Node Coloring: When Stable Sets Are Expensive. In *Proc. of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)*, volume 2573 of *LNCS*, pages 114–125. Springer, 2002.

13 Marc Demange, Pascal Grisoni, and Vangelis Th. Paschos. Approximation Results for the Minimum Graph Coloring Problem. *Information Processing Letters*, 50(1):19–23, 1994. doi:10.1016/0020-0190(94)90039-6.

14 Reinhard Diestel. *Graph Theory*, volume 173. Springer-Verlag, 4th edition, 2010.

15 Michael Dom, Daniel Lokshtanov, and Saket Saurabh. Kernelization Lower Bounds Through Colors and IDs. *ACM Transactions on Algorithms*, 11(2):13:1–13:20, 2014. doi:10.1145/2650261.

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

17 Rong-chii Duh and Martin Fürer. Approximation of *k*-Set Cover by Semi-Local Optimization. In *Proc. of the 29th Annual ACM Symposium on the Theory of Computing (STOC)*, pages 256–264, 1997. doi:10.1145/258533.258599.

18 Bruno Escoffier. Saving Colors and Max Coloring: Some Fixed-Parameter Tractability Results. In *Proc. of the 42nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG)*, volume 9941 of *LNCS*, pages 50–61, 2016.

19 Bruno Escoffier, Jérôme Monnot, and Vangelis Th. Paschos. Weighted Coloring: further complexity and approximability results. *Information Processing Letters*, 97(3):98–103, 2006.

20 Fedor V. Fomin and Dieter Kratsch. *Exact Exponential Algorithms*. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2010.
12:14 Dual Parameterization of Weighted Coloring

21 Lance Fortnow and Rahul Santhanam. Infeasibility of instance compression and succinct PCPs for NP. *Journal of Computer and System Sciences*, 77(1):91–106, 2011.

22 Delbert Fulkerson and Oliver Gross. Incidence matrices and interval graphs. *Pacific journal of mathematics*, 15(3):835–855, 1965.

23 P. Gilmore and A. Hoffman. A characterization of comparability graphs and of interval graphs. *Canadian Journal of Mathematics*, 16:539–548, 1964.

24 D. J. Guan and Xuding Zhu. A Coloring Problem for Weighted Graphs. *Information Processing Letters*, 61(2):77–81, 1997.

25 Gregory Z. Gutin, Mark Jones, and Anders Yeo. Kernels for below-upper-bound parametrizations of the hitting set and directed dominating set problems. *Theoretical Computer Science*, 412(41):5744–5751, 2011. doi:10.1016/j.tcs.2011.06.018.

26 Magnús M. Halldórsson. Approximating Discrete Collections via Local Improvements. In *Proc. of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pages 160–169, 1995. URL: http://dl.acm.org/citation.cfm?id=313651.313687.

27 Magnús M. Halldórsson. Approximating *k*-Set Cover and Complementary Graph Coloring. In *Proc. of the 5th International Conference on Integer Programming and Combinatorial Optimization (IPCO)*, volume 1084 of LNCS, pages 118–131, 1996. doi:10.1007/3-540-61310-2_10.

28 Refael Hassin and Shlomo Lahav. Maximizing the Number of Unused Colors in the Vertex Coloring Problem. *Information Processing Letters*, 52(2):87–90, 1994. doi:10.1016/0020-0190(94)00113-8.

29 Frédéric Havet and Leonardo Sampaio. On the Grundy and *b*-Chromatic Numbers of a Graph. *Algorithmica*, 65(4):885–899, 2013.

30 Danny Hermelin and Xi Wu. Weak compositions and their applications to polynomial lower bounds for kernelization. In *Proc. of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pages 104–113, 2012.

31 Russell Impagliazzo and Ramamohan Paturi. On the Complexity of *k*-SAT. *Journal of Computer and System Sciences*, 62(2):367–375, 2001. doi:10.1006/jcss.2000.1727.

32 Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which Problems Have Strongly Exponential Complexity? *Journal of Computer and System Sciences*, 63(4):512–530, 2001.

33 Richard M. Karp. Reducibility Among Combinatorial Problems. In *Proc. of a symposium on the Complexity of Computer Computations*, The IBM Research Symposia Series, pages 85–103. Plenum Press, New York, 1972.

34 Telikepalli Kavitha and Julián Mestre. Max-coloring paths: tight bounds and extensions. *Journal of Combinatorial Optimization*, 24(1):1–14, 2012.

35 E. L. Lawler. A note on the complexity of the chromatic number problem. *Information Processing Letters*, 5(3):66–67, 1976. doi:10.1016/0020-0190(76)90065-X.

36 Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the Exponential Time Hypothesis. *Bulletin of the EATCS*, 105:41–72, 2011. URL: http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/view/96.

37 Sriram V. Pemmaraju, Sriram Penumatcha, and Rajiv Raman. Approximating interval coloring and max-coloring in chordal graphs. *ACM Journal of Experimental Algorithmics*, 10, 2005.

38 Chee-Keng Yap. Some Consequences of Non-Uniform Conditions on Uniform Classes. *Theoretical Computer Science*, 26:287–300, 1983.
12:14 Dual Parameterization of Weighted Coloring

21 Lance Fortnow and Rahul Santhanam. Infeasibility of instance compression and succinct PCPs for NP. *Journal of Computer and System Sciences*, 77(1):91–106, 2011.

22 Delbert Fulkerson and Oliver Gross. Incidence matrices and interval graphs. *Pacific journal of mathematics*, 15(3):835–855, 1965.

23 P. Gilmore and A. Hoffman. A characterization of comparability graphs and of interval graphs. *Canadian Journal of Mathematics*, 16:539–548, 1964.

24 D. J. Guan and Xuding Zhu. A Coloring Problem for Weighted Graphs. *Information Processing Letters*, 61(2):77–81, 1997.

25 Gregory Z. Gutin, Mark Jones, and Anders Yeo. Kernels for below-upper-bound parametrizations of the hitting set and directed dominating set problems. *Theoretical Computer Science*, 412(41):5744–5751, 2011. doi:10.1016/j.tcs.2011.06.018.

26 Magnús M. Halldórsson. Approximating Discrete Collections via Local Improvements. In *Proc. of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pages 160–169, 1995. URL: http://dl.acm.org/citation.cfm?id=313651.313687.

27 Magnús M. Halldórsson. Approximating *k*-Set Cover and Complementary Graph Coloring. In *Proc. of the 5th International Conference on Integer Programming and Combinatorial Optimization (IPCO)*, volume 1084 of LNCS, pages 118–131, 1996. doi:10.1007/3-540-61310-2_10.

28 Refael Hassin and Shlomo Lahav. Maximizing the Number of Unused Colors in the Vertex Coloring Problem. *Information Processing Letters*, 52(2):87–90, 1994. doi:10.1016/0020-0190(94)00113-8.

29 Frédéric Havet and Leonardo Sampaio. On the Grundy and *b*-Chromatic Numbers of a Graph. *Algorithmica*, 65(4):885–899, 2013.

30 Danny Hermelin and Xi Wu. Weak compositions and their applications to polynomial lower bounds for kernelization. In *Proc. of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pages 104–113, 2012.

31 Russell Impagliazzo and Ramamohan Paturi. On the Complexity of *k*-SAT. *Journal of Computer and System Sciences*, 62(2):367–375, 2001. doi:10.1006/jcss.2000.1727.

32 Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which Problems Have Strongly Exponential Complexity? *Journal of Computer and System Sciences*, 63(4):512–530, 2001.

33 Richard M. Karp. Reducibility Among Combinatorial Problems. In *Proc. of a symposium on the Complexity of Computer Computations*, The IBM Research Symposia Series, pages 85–103. Plenum Press, New York, 1972.

34 Telikepalli Kavitha and Julián Mestre. Max-coloring paths: tight bounds and extensions. *Journal of Combinatorial Optimization*, 24(1):1–14, 2012.

35 E. L. Lawler. A note on the complexity of the chromatic number problem. *Information Processing Letters*, 5(3):66–67, 1976. doi:10.1016/0020-0190(76)90065-X.

36 Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the Exponential Time Hypothesis. *Bulletin of the EATCS*, 105:41–72, 2011. URL: http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/view/96.

37 Sriram V. Pemmaraju, Sriram Penumatcha, and Rajiv Raman. Approximating interval coloring and max-coloring in chordal graphs. *ACM Journal of Experimental Algorithmics*, 10, 2005.

38 Chee-Keng Yap. Some Consequences of Non-Uniform Conditions on Uniform Classes. *Theoretical Computer Science*, 26:287–300, 1983.
# Computing Kernels in Parallel: Lower and Upper Bounds

## Max Bannach

Institute for Theoretical Computer Science, Universität zu Lübeck, Lübeck, Germany
bannach@tcs.uni-luebeck.de

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

https://orcid.org/0000-0002-6475-5512

## Till Tantau

Institute for Theoretical Computer Science, Universität zu Lübeck, Lübeck, Germany
tantau@tcs.uni-luebeck.de

### Abstract

Parallel fixed-parameter tractability studies how parameterized problems can be solved in parallel. A surprisingly large number of parameterized problems admit a high level of parallelization, but this does not mean that we can also efficiently compute small problem kernels in parallel: known kernelization algorithms are typically highly sequential. In the present paper, we establish a number of upper and lower bounds concerning the sizes of kernels that can be computed in parallel. An intriguing finding is that there are complex trade-offs between kernel size and the depth of the circuits needed to compute them: For the vertex cover problem, an exponential kernel can be computed by $AC^0$-circuits, a quadratic kernel by $TC^0$-circuits, and a linear kernel by randomized NC-circuits with derandomization being possible only if it is also possible for the matching problem. Other natural problems for which similar (but quantitatively different) effects can be observed include tree decomposition problems parameterized by the vertex cover number, the undirected feedback vertex set problem, the matching problem, or the point line cover problem. We also present natural problems for which computing kernels is inherently sequential.

**2012 ACM Subject Classification** Theory of computation → Design and analysis of algorithms

**Keywords and phrases** parallel computation, fixed-parameter tractability, kernelization

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

**Related Version** https://arxiv.org/abs/1807.03604

## 1 Introduction

The core objective of parameterized complexity has classically been to determine which problems can be solved in "FPT time," meaning time $f(k) \cdot n^c$ for instances of size $n$, where $c$ is a constant, $f$ is an arbitrary computable function (usually at least exponential), and $k$ is a hopefully small instance parameter. Over the last 25 years, theoreticians in the field have been very successful at determining which problems admit algorithms of this kind and practitioners have been very successful at implementing them. In both cases, the focus has traditionally been on finding *sequential* algorithms, but in recent years interest in *parallel* algorithms has sparked, leading to the new field of parallel fixed parameter tractability.

In classical sequential FPT algorithms, *kernelization algorithms* play a key role. They shrink the input to a small but difficult core (called the *kernel*), leading to the following design principle of modern parameterized algorithms: Firstly, in polynomial time, a kernelization algorithm computes a kernel that is, secondly, solved using an exponential (or worse) time

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

© Max Bannach and Till Tantau;
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. 13; pp. 13:1–13:14

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

LIPICS

Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
# Computing Kernels in Parallel: Lower and Upper Bounds

## Max Bannach

Institute for Theoretical Computer Science, Universität zu Lübeck, Lübeck, Germany
bannach@tcs.uni-luebeck.de

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

https://orcid.org/0000-0002-6475-5512

## Till Tantau

Institute for Theoretical Computer Science, Universität zu Lübeck, Lübeck, Germany
tantau@tcs.uni-luebeck.de

### Abstract

Parallel fixed-parameter tractability studies how parameterized problems can be solved in parallel. A surprisingly large number of parameterized problems admit a high level of parallelization, but this does not mean that we can also efficiently compute small problem kernels in parallel: known kernelization algorithms are typically highly sequential. In the present paper, we establish a number of upper and lower bounds concerning the sizes of kernels that can be computed in parallel. An intriguing finding is that there are complex trade-offs between kernel size and the depth of the circuits needed to compute them: For the vertex cover problem, an exponential kernel can be computed by $AC^0$-circuits, a quadratic kernel by $TC^0$-circuits, and a linear kernel by randomized NC-circuits with derandomization being possible only if it is also possible for the matching problem. Other natural problems for which similar (but quantitatively different) effects can be observed include tree decomposition problems parameterized by the vertex cover number, the undirected feedback vertex set problem, the matching problem, or the point line cover problem. We also present natural problems for which computing kernels is inherently sequential.

**2012 ACM Subject Classification** Theory of computation → Design and analysis of algorithms

**Keywords and phrases** parallel computation, fixed-parameter tractability, kernelization

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

**Related Version** https://arxiv.org/abs/1807.03604

## 1 Introduction

The core objective of parameterized complexity has classically been to determine which problems can be solved in "FPT time," meaning time $f(k) \cdot n^c$ for instances of size $n$, where $c$ is a constant, $f$ is an arbitrary computable function (usually at least exponential), and $k$ is a hopefully small instance parameter. Over the last 25 years, theoreticians in the field have been very successful at determining which problems admit algorithms of this kind and practitioners have been very successful at implementing them. In both cases, the focus has traditionally been on finding *sequential* algorithms, but in recent years interest in *parallel* algorithms has sparked, leading to the new field of parallel fixed parameter tractability.

In classical sequential FPT algorithms, *kernelization algorithms* play a key role. They shrink the input to a small but difficult core (called the *kernel*), leading to the following design principle of modern parameterized algorithms: Firstly, in polynomial time, a kernelization algorithm computes a kernel that is, secondly, solved using an exponential (or worse) time

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

© Max Bannach and Till Tantau;
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. 13; pp. 13:1–13:14

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

LIPICS

Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
## 13:2 Computing Kernels in Parallel: Lower and Upper Bounds

algorithm – yielding a total running time of the form $f(k) + n^c$. Regarding the parallelization of these two algorithmic steps, it turns out that the second one is usually the easier one: the kernel is typically processed using the search tree technique or just by “brute force,” both of which allow natural parallelizations. In contrast, kernelization algorithms are typically described in a very sequential way, namely “apply these reduction rules over and over again.” This means that designing parallel fixed-parameter algorithms effectively means designing parallel kernelization algorithms – which is exactly what this paper addresses.

**Our Contributions.** We start our systematic investigation of parallel kernelization by linking the parameterized analogues of the NC-hierarchy to kernel computation using NC-circuits. Such a link is already known for FPT and kernels computed in polynomial time. We establish a circuit version of the well-known result that all algorithms running in time $f(k) \cdot n^c$ can also be implemented with running time $g(k) + n^c$: We can turn any circuit family of size $f(k) \cdot n^c$ and depth $f(k) + c \log^i n$ into one of size $g(k) + n^{c'}$ and depth $c' \log^i n$ (note that we can remove the parameter dependence from the depth).

The bulk of the paper consists of a series of lower and upper bounds on the size of kernels that can be computed by circuits of certain depths. We show that for natural problems like the vertex cover problem intriguing trade-offs arise: the faster our algorithm, the worse our kernel. For *p*-VERTEX-COVER we show that a simple exponential kernel can be computed in AC$^0$, a quadratic kernel can be computed in TC$^0$, and a linear kernel can be computed in randomized NC. Other problems for which we establish similar results include the tree width, path width, and tree depth problems parameterized by the vertex cover number of the input graph.

On the negative side, we also establish a number of lower bounds for the parallel computation of small kernels. We show that a classical 2k kernel for the vertex cover problem can only be computed in parallel if the maximum matching problem for bipartite graphs is in NC, for which RNC$^2$ and quasi-NC$^2$ are the best known upper bounds; that classic reduction rules for feedback vertex set are P-complete (but an exponential kernel can be computed in AC$^2$); that for the point line cover problem we cannot (absolutely, without any assumptions) compute any kernel in AC$^0$ (but we can compute a quadratic one in TC$^0$); and that kernels for generalized versions of Horn satisfiability, linear programming, and maximum flow cannot be computed in polylogarithmic time unless NC = P. The later results in fact presents three *natural* FPT-complete problems, which demonstrate the limits of fixed parameter parallelization.

Table 1 summarizes which trade-offs are established in this paper between the parallel time needed to compute kernels and their sizes.

**Related Work.** Parameterized complexity is a rapidly growing field, see [14, 15, 18] for an introduction, in which parallelization is a recent research direction. Early research in the late 1990s was done by Cai, Chen, Downey, and Fellows [9] who studied parameterized logaritmic space. A structural study of parameterized logspace and parameterized circuit classes was started around 2015 by Elberfeld et al. [16]; see also the references therein. The parameterized version of the NC-hierarchy we use in this paper was introduced in [2]. Chen and Flum studied lower bounds in this context and especially provide some details and alternative characterizations for parameterized AC$^0$. There is a huge body of literature on polynomial-time algorithms for computing small kernels, but the authors are not aware of results concerning how quickly these kernels can be computed in parallel.
13:2 Computing Kernels in Parallel: Lower and Upper Bounds

algorithm – yielding a total running time of the form $f(k) + n^c$. Regarding the parallelization of these two algorithmic steps, it turns out that the second one is usually the easier one: the kernel is typically processed using the search tree technique or just by “brute force,” both of which allow natural parallelizations. In contrast, kernelization algorithms are typically described in a very sequential way, namely “apply these reduction rules over and over again.” This means that designing parallel fixed-parameter algorithms effectively means designing parallel kernelization algorithms – which is exactly what this paper addresses.

**Our Contributions.** We start our systematic investigation of parallel kernelization by linking the parameterized analogues of the NC-hierarchy to kernel computation using NC-circuits. Such a link is already known for FPT and kernels computed in polynomial time. We establish a circuit version of the well-known result that all algorithms running in time $f(k) \cdot n^c$ can also be implemented with running time $g(k) + n^c$: We can turn any circuit family of size $f(k) \cdot n^c$ and depth $f(k) + c \log^i n$ into one of size $g(k) + n^{c'}$ and depth $c' \log^i n$ (note that we can remove the parameter dependence from the depth).

The bulk of the paper consists of a series of lower and upper bounds on the size of kernels that can be computed by circuits of certain depths. We show that for natural problems like the vertex cover problem intriguing trade-offs arise: the faster our algorithm, the worse our kernel. For *p*-** VERTEX-COVER** we show that a simple exponential kernel can be computed in AC$^0$, a quadratic kernel can be computed in TC$^0$, and a linear kernel can be computed in randomized NC. Other problems for which we establish similar results include the tree width, path width, and tree depth problems parameterized by the vertex cover number of the input graph.

On the negative side, we also establish a number of lower bounds for the parallel computation of small kernels. We show that a classical 2k kernel for the vertex cover problem can only be computed in parallel if the maximum matching problem for bipartite graphs is in NC, for which RNC$^2$ and quasi-NC$^2$ are the best known upper bounds; that classic reduction rules for feedback vertex set are P-complete (but an exponential kernel can be computed in AC$^2$); that for the point line cover problem we cannot (absolutely, without any assumptions) compute any kernel in AC$^0$ (but we can compute a quadratic one in TC$^0$); and that kernels for generalized versions of Horn satisfiability, linear programming, and maximum flow cannot be computed in polylogarithmic time unless NC = P. The later results in fact presents three *natural* FPT-complete problems, which demonstrate the limits of fixed parameter parallelization.

Table 1 summarizes which trade-offs are established in this paper between the parallel time needed to compute kernels and their sizes.

**Related Work.** Parameterized complexity is a rapidly growing field, see [14, 15, 18] for an introduction, in which parallelization is a recent research direction. Early research in the late 1990s was done by Cai, Chen, Downey, and Fellows [9] who studied parameterized logaritmic space. A structural study of parameterized logspace and parameterized circuit classes was started around 2015 by Elberfeld et al. [16]; see also the references therein. The parameterized version of the NC-hierarchy we use in this paper was introduced in [2]. Chen and Flum studied lower bounds in this context and especially provide some details and alternative characterizations for parameterized AC$^0$. There is a huge body of literature on polynomial-time algorithms for computing small kernels, but the authors are not aware of results concerning how quickly these kernels can be computed in parallel.
<table><caption>**Table 1** An overview of problems studied in this paper, showing which kernel size can be achieved in certain layers of the NC-hierarchy. An explicit function represents the best bound the authors are aware of, pointed out in this work or (for the P-column) in cited works; $f(k)$ corresponds to kernels originating from Theorem 2.3; and “–” means that there is no kernel of any size (either absolutely or unless $TC^0 = L$ for $-1$, unless $TC^0 = NL$ for $-2$, unless $TC^0 = P$ for $-3$, unless $NC = P$ for $-4$, unless $P \subseteq \text{RNC}$ for $-5$, and unless $NC^1 = P$ for $-6$). For problems parameterized by the vertex cover number, $S$ is the given vertex cover; the $\delta$ in the first column can be any fixed positive integer.</caption><thead><tr><th rowspan="2">Problem</th><th colspan="5">Kernel size achievable in</th></tr><tr><th>AC<sup>0</sup></th><th>TC<sup>0</sup></th><th>NC</th><th>RNC</th><th>P</th></tr></thead><tbody><tr><td>p-VERTEX-COVER</td><td>2<sup>δ√k</sup></td><td>k<sup>2</sup> + 2k</td><td>k<sup>2</sup> + 2k</td><td>2k</td><td>2k - c log k</td></tr><tr><td>p-MATCHING</td><td>2<sup>δ√k</sup></td><td>6k<sup>2</sup></td><td>6k<sup>2</sup></td><td>1</td><td>1</td></tr><tr><td>p<sub>vc</sub>-TREE-WIDTH</td><td>2<sup>δ√|S|</sup></td><td>|S|<sup>3</sup></td><td>|S|<sup>3</sup></td><td>|S|<sup>3</sup></td><td>|S|<sup>3</sup></td></tr><tr><td>p<sub>vc</sub>-PATH-WIDTH</td><td>2<sup>δ√|S|</sup></td><td>|S|<sup>3</sup></td><td>|S|<sup>3</sup></td><td>|S|<sup>3</sup></td><td>|S|<sup>3</sup></td></tr><tr><td>p<sub>vc</sub>-TREE-DEPTH</td><td>2<sup>δ√|S|</sup></td><td>|S|<sup>3</sup></td><td>|S|<sup>3</sup></td><td>|S|<sup>3</sup></td><td>|S|<sup>3</sup></td></tr><tr><td>p-POINT-LINE-COVER</td><td>—</td><td>k<sup>2</sup></td><td>k<sup>2</sup></td><td>k<sup>2</sup></td><td>k<sup>2</sup></td></tr><tr><td>p-FEEDBACK-VERTEX-SET</td><td>—</td><td>—<sup>1</sup></td><td>f(k)</td><td>f(k)</td><td>2k<sup>2</sup> + k</td></tr><tr><td>p-STRONG-BACKDOOR-2CNF-SAT</td><td>—</td><td>—<sup>2</sup></td><td>f(k)</td><td>f(k)</td><td>f(k)</td></tr><tr><td>p-STRONG-BACKDOOR-HORN-SAT</td><td>—</td><td>—<sup>3</sup></td><td>—<sup>3</sup></td><td>—<sup>5</sup></td><td>f(k)</td></tr><tr><td>p-MIXED-INTEGER-PROGRAMMING</td><td>—</td><td>—<sup>6</sup></td><td>—<sup>4</sup></td><td>—<sup>5</sup></td><td>f(k)</td></tr><tr><td>p-MAX-FLOW-QUANTITIES</td><td>—</td><td>—<sup>6</sup></td><td>—<sup>4</sup></td><td>—<sup>5</sup></td><td>f(k)</td></tr></tbody></table>

**Organization of This Paper.** We review basic terminology in Section 2, where we also establish the link between parameterized parallel complexity and parallel kernel computation. Each of the following sections studies a different well-known parameterized problem and establishes trade-offs between kernel size and speed. We start with the vertex cover and the matching problem in Section 3, followed by the feedback vertex set problem in Section 4, structural parameterizations for tree width, path width, and tree depth in Section 5, the p-POINT-LINE-COVER problem in Section 6, and finally generalized versions of Horn satisfiability, linear programming, and maximum flow in Section 7. Due to lack of space, most proofs are given only in the full version, but we sketch some of them in the main text.

## 2 Parameterized Parallel Complexity Classes and Kernelization

We use standard terminology of parameterized complexity theory, see for instance [18]. A parameterized problem is a tuple $(Q, \kappa)$ consisting of a language $Q \subseteq \Sigma^*$ and a parameterization $\kappa: \Sigma^* \to \mathbb{N}$. The complexity of $\kappa$ should not exceed the power of the classes that we consider, and since we study small parameterized circuit classes, we require $\kappa$ to be computable by DLOGTIME-uniform constant-depth AC-circuits or, equivalently, to be first-order computable. We denote parameterized problems by a leading “p-” as in p-VERTEX-COVER, and, whenever the parameterization $\kappa$ is not clear from the context, we add it as an index as in $p_{vc}-TREE-WIDTH$. A parameterized problem $(Q, \kappa)$ is fixed-parameter tractable (or in FPT) if there is a computable function $f: \mathbb{N} \to \mathbb{N}$ and a constant $c$ such that we can decide $x \in Q$ in time $f(\kappa(x)) \cdot |x|^c$ for all $x \in \Sigma^*$. In this paper we study the parallel complexity of parameterized problems, that is, the parameterized counter part of the NC-hierarchy. Formally we study the following classes, see for instance [2, 11] for a detailed discussion:
<table><caption>**Table 1** An overview of problems studied in this paper, showing which kernel size can be achieved in certain layers of the NC-hierarchy. An explicit function represents the best bound the authors are aware of, pointed out in this work or (for the P-column) in cited works; $f(k)$ corresponds to kernels originating from Theorem 2.3; and “–” means that there is no kernel of any size (either absolutely or unless $TC^0 = L$ for $-^1$, unless $TC^0 = NL$ for $-^2$, unless $TC^0 = P$ for $-^3$, unless $NC = P$ for $-^4$, unless $P \subseteq \text{RNC}$ for $-^5$, and unless $NC^1 = P$ for $-^6$). For problems parameterized by the vertex cover number, $S$ is the given vertex cover; the $\delta$ in the first column can be any fixed positive integer.</caption><thead><tr><th rowspan="2">Problem</th><th colspan="5">Kernel size achievable in</th></tr><tr><th>AC<sup>0</sup></th><th>TC<sup>0</sup></th><th>NC</th><th>RNC</th><th>P</th></tr></thead><tbody><tr><td>p-VERTEX-COVER</td><td>2<sup>δ√k</sup></td><td>k<sup>2</sup> + 2k</td><td>k<sup>2</sup> + 2k</td><td>2k</td><td>2k - c log k</td></tr><tr><td>p-MATCHING</td><td>2<sup>δ√k</sup></td><td>6k<sup>2</sup></td><td>6k<sup>2</sup></td><td>1</td><td>1</td></tr><tr><td>p<sub>vc</sub>-TREE-WIDTH</td><td>2<sup>δ√|S|</sup></td><td>|S|<sup>3</sup></td><td>|S|<sup>3</sup></td><td>|S|<sup>3</sup></td><td>|S|<sup>3</sup></td></tr><tr><td>p<sub>vc</sub>-PATH-WIDTH</td><td>2<sup>δ√|S|</sup></td><td>|S|<sup>3</sup></td><td>|S|<sup>3</sup></td><td>|S|<sup>3</sup></td><td>|S|<sup>3</sup></td></tr><tr><td>p<sub>vc</sub>-TREE-DEPTH</td><td>2<sup>δ√|S|</sup></td><td>|S|<sup>3</sup></td><td>|S|<sup>3</sup></td><td>|S|<sup>3</sup></td><td>|S|<sup>3</sup></td></tr><tr><td>p-POINT-LINE-COVER</td><td>-</td><td>k<sup>2</sup></td><td>k<sup>2</sup></td><td>k<sup>2</sup></td><td>k<sup>2</sup></td></tr><tr><td>p-FEEDBACK-VERTEX-SET</td><td>-</td><td>-<sup>1</sup></td><td>f(k)</td><td>f(k)</td><td>2k<sup>2</sup> + k</td></tr><tr><td>p-STRONG-BACKDOOR-2CNF-SAT</td><td>-</td><td>-<sup>2</sup></td><td>f(k)</td><td>f(k)</td><td>f(k)</td></tr><tr><td>p-STRONG-BACKDOOR-HORN-SAT</td><td>-</td><td>-<sup>3</sup></td><td>-<sup>3</sup></td><td>-<sup>5</sup></td><td>f(k)</td></tr><tr><td>p-MIXED-INTEGER-PROGRAMMING</td><td>-</td><td>-<sup>6</sup></td><td>-<sup>4</sup></td><td>-<sup>5</sup></td><td>f(k)</td></tr><tr><td>p-MAX-FLOW-QUANTITIES</td><td>-</td><td>-<sup>6</sup></td><td>-<sup>4</sup></td><td>-<sup>5</sup></td><td>f(k)</td></tr></tbody></table>

**Organization of This Paper.** We review basic terminology in Section 2, where we also establish the link between parameterized parallel complexity and parallel kernel computation. Each of the following sections studies a different well-known parameterized problem and establishes trade-offs between kernel size and speed. We start with the vertex cover and the matching problem in Section 3, followed by the feedback vertex set problem in Section 4, structural parameterizations for tree width, path width, and tree depth in Section 5, the p-POINT-LINE-COVER problem in Section 6, and finally generalized versions of Horn satisfiability, linear programming, and maximum flow in Section 7. Due to lack of space, most proofs are given only in the full version, but we sketch some of them in the main text.

## 2 Parameterized Parallel Complexity Classes and Kernelization

We use standard terminology of parameterized complexity theory, see for instance [18]. A parameterized problem is a tuple $(Q, \kappa)$ consisting of a language $Q \subseteq \Sigma^*$ and a parameterization $\kappa: \Sigma^* \to \mathbb{N}$. The complexity of $\kappa$ should not exceed the power of the classes that we consider, and since we study small parameterized circuit classes, we require $\kappa$ to be computable by DLOGTIME-uniform constant-depth AC-circuits or, equivalently, to be first-order computable. We denote parameterized problems by a leading “p-” as in p-VERTEX-COVER, and, whenever the parameterization $\kappa$ is not clear from the context, we add it as an index as in $p_{vc}-TREE-WIDTH$. A parameterized problem $(Q, \kappa)$ is fixed-parameter tractable (or in FPT) if there is a computable function $f: \mathbb{N} \to \mathbb{N}$ and a constant $c$ such that we can decide $x \in Q$ in time $f(\kappa(x)) \cdot |x|^c$ for all $x \in \Sigma^*$. In this paper we study the parallel complexity of parameterized problems, that is, the parameterized counter part of the NC-hierarchy. Formally we study the following classes, see for instance [2, 11] for a detailed discussion:
13:4 Computing Kernels in Parallel: Lower and Upper Bounds

**► Definition 2.1.** For each $i > 0$, a parameterized problem $(Q, \kappa)$ is in DLOGTIME-uniform para-AC$^i$ if there exists a computable function $f: \mathbb{N} \to \mathbb{N}$, a constant $c \in \mathbb{N}$, and a family of AC-circuits $(C_{n,k})_{n,k \in \mathbb{N}}$ such that:

1. For all $x \in \Sigma^*$ we have $C_{|x|, \kappa(x)}(x) = 1 \iff x \in Q$.

2. The depth of each $C_{n,k}$ is at most $f(k) + c \log^i n$.

3. The size of each $C_{n,k}$ is at most $f(k) \cdot n^c$.

4. There is a deterministic Turing machine that on input of bin($i$)#bin($k$)#bin($n$), where bin($x$) is the binary encoding of $x$, outputs the $i$th bit of a suitable encoding of $C_{n,k}$ in at most $f(k) + c \log n$ steps.

The class para-AC$^0$ is defined as above, but with circuits of constant depth. Additionally, we define for all $i \ge 0$ the class para-AC$^i$↑ with circuits of depth $f(k) \cdot \log^i n$. In particular, para-AC$^0$↑-circuits have depth $f(k)$. Recall that AC-circuits are defined over the standard base of NOT-, OR-, and AND-gates and that the last two may have unlimited fan-in. The same definition works for NC-circuits (all gates have bounded fan-in) and TC-circuits (additional threshold gates are allowed). It is known that the parameterized classes inherit their inclusion structure from their classical counterparts [2]:

$$ \text{para-AC}^0 \subseteq \text{para-TC}^0 \subseteq \text{para-NC}^1 \subseteq \text{para-AC}^1 \subseteq \text{para-TC}^1 \subseteq \dots \subseteq \text{para-NC} \subseteq \text{FPT}. $$

**A Parallel Analogue of “FPT = Kernels Computable in Polynomial Time”**. One of the most fruitful aspects of parameterized complexity is the concept of kernelization. Let $f: \mathbb{N} \to \mathbb{N}$ be a computable function. A kernelization of a parameterized problem $(Q, \kappa)$ is a self-reduction $K: \Sigma^* \to \Sigma^*$ such that for every $x \in \Sigma^*$ we have $x \in Q \iff K(x) \in Q$ and $|K(x)| \le f(\kappa(x))$. The images of $K$ are called kernels and as they later need to be processed by at least exponential-time algorithms, we are interested in kernels that are as small as possible – while they still need to be efficiently computable, meaning in polynomial time from the view point of FPT theory. The following result is well-known and gives a deep connection between parameterized complexity and kernelization:

**Fact 2.2 (for instance [18]).** A decidable parameterized problem $(Q, \kappa)$ is in FPT if, and only if, it admits a polynomial-time computable kernelization.

The following theorem shows that the same relation also connects the AC-hierarchy with its parameterized counterpart. Note that in the theorem the AC$^i$-circuits are really “normal AC$^i$-circuits,” meaning that their size is just polynomial in the input length.

**Theorem 2.3.** A decidable parameterized problem $(Q, \kappa)$ is in para-AC$^i$ if, and only if, it admits a kernelization computable by a DLOGTIME-uniform family of AC$^i$-circuits.

**Sketch of Proof.** For the reverse direction, let $(C_n)_{n \in \mathbb{N}}$ be a family computing a kernelization. Circuit $C_{n,k}$ uses $C_n$ as a first black box and reduces the input to an instance of size at most $f(\kappa(x))$. Then the circuit essentially applies naive “brute force” in the form of a big OR-gate that checks if any element of $Q$ of length at most $f(\kappa(x))$ equals the computed kernel. For the other direction let $\tilde{k} \in \mathbb{N}$ be the maximum $k$ such that $f(k) \le c \log^i n$ and let $C_n$ consist of $\tilde{k}$ subcircuits $C_n^0, \dots, C_n^{\tilde{k}}$ that are evaluated in parallel. The circuit $C_n^j$ first checks on input $x$ whether $\kappa(x) = j$, and, if so, uses $C_{n,j}$ to solve the problem and outputs a trivial kernel. Otherwise, it signals that it is not responsible for this instance. If any $C_n^j$ produces a kernel, then $C_n$ just presents this kernel as result. Otherwise $C_n$ can just present the input as output, as we have $\kappa(x) > \tilde{k}$ and $f(\kappa(x)) > c \log^i n$. ◀

The theorem also holds if we replace AC$^i$ with NC$^i$ or TC$^i$. The only exception is NC$^0$, as this class may not be powerful enough to compute $\kappa$.
13:4 Computing Kernels in Parallel: Lower and Upper Bounds

**► Definition 2.1.** For each $i > 0$, a parameterized problem $(Q, \kappa)$ is in DLOGTIME-uniform para-AC$^i$ if there exists a computable function $f: \mathbb{N} \to \mathbb{N}$, a constant $c \in \mathbb{N}$, and a family of AC-circuits $(C_{n,k})_{n,k \in \mathbb{N}}$ such that:

1. For all $x \in \Sigma^*$ we have $C_{|x|, \kappa(x)}(x) = 1 \iff x \in Q$.

2. The depth of each $C_{n,k}$ is at most $f(k) + c \log^i n$.

3. The size of each $C_{n,k}$ is at most $f(k) \cdot n^c$.

4. There is a deterministic Turing machine that on input of bin($i$) # bin($k$) # bin($n$), where bin($x$) is the binary encoding of $x$, outputs the $i$th bit of a suitable encoding of $C_{n,k}$ in at most $f(k) + c \log n$ steps.

The class para-AC$^0$ is defined as above, but with circuits of constant depth. Additionally, we define for all $i \ge 0$ the class para-AC$^{i\uparrow}$ with circuits of depth $f(k) \cdot \log^i n$. In particular, para-AC$^{0\uparrow}$-circuits have depth $f(k)$. Recall that AC-circuits are defined over the standard base of NOT-, OR-, and AND-gates and that the last two may have unlimited fan-in. The same definition works for NC-circuits (all gates have bounded fan-in) and TC-circuits (additional threshold gates are allowed). It is known that the parameterized classes inherit their inclusion structure from their classical counterparts [2]:

$$ \text{para-AC}^0 \subseteq \text{para-TC}^0 \subseteq \text{para-NC}^1 \subseteq \text{para-AC}^1 \subseteq \text{para-TC}^1 \subseteq \dots \subseteq \text{para-NC} \subseteq \text{FPT}. $$

**A Parallel Analogue of “FPT = Kernels Computable in Polynomial Time”**. One of the most fruitful aspects of parameterized complexity is the concept of kernelization. Let $f: \mathbb{N} \to \mathbb{N}$ be a computable function. A kernelization of a parameterized problem $(Q, \kappa)$ is a self-reduction $K: \Sigma^* \to \Sigma^*$ such that for every $x \in \Sigma^*$ we have $x \in Q \iff K(x) \in Q$ and $|K(x)| \le f(\kappa(x))$. The images of $K$ are called kernels and as they later need to be processed by at least exponential-time algorithms, we are interested in kernels that are as small as possible – while they still need to be efficiently computable, meaning in polynomial time from the view point of FPT theory. The following result is well-known and gives a deep connection between parameterized complexity and kernelization:

**Fact 2.2 (for instance [18]).** A decidable parameterized problem $(Q, \kappa)$ is in FPT if, and only if, it admits a polynomial-time computable kernelization.

The following theorem shows that the same relation also connects the AC-hierarchy with its parameterized counterpart. Note that in the theorem the AC$^i$-circuits are really “normal AC$^i$-circuits,” meaning that their size is just polynomial in the input length.

**Theorem 2.3.** A decidable parameterized problem $(Q, \kappa)$ is in para-AC$^i$ if, and only if, it admits a kernelization computable by a DLOGTIME-uniform family of AC$^i$-circuits.

**Sketch of Proof.** For the reverse direction, let $(C_n)_{n \in \mathbb{N}}$ be a family computing a kernelization. Circuit $C_{n,k}$ uses $C_n$ as a first black box and reduces the input to an instance of size at most $f(\kappa(x))$. Then the circuit essentially applies naive “brute force” in the form of a big OR-gate that checks if any element of $Q$ of length at most $f(\kappa(x))$ equals the computed kernel. For the other direction let $\tilde{k} \in \mathbb{N}$ be the maximum $k$ such that $f(k) \le c \log^i n$ and let $C_n$ consist of $\tilde{k}$ subcircuits $C_n^0, \dots, C_n^{\tilde{k}}$ that are evaluated in parallel. The circuit $C_n^j$ first checks on input $x$ whether $\kappa(x) = j$, and, if so, uses $C_{n,j}$ to solve the problem and outputs a trivial kernel. Otherwise, it signals that it is not responsible for this instance. If any $C_n^j$ produces a kernel, then $C_n$ just presents this kernel as result. Otherwise $C_n$ can just present the input as output, as we have $\kappa(x) > \tilde{k}$ and $f(\kappa(x)) > c \log^i n$. ◀

The theorem also holds if we replace AC$^i$ with NC$^i$ or TC$^i$. The only exception is NC$^0$, as this class may not be powerful enough to compute $\kappa$.
**Application: Improve the Work of Parallel Algorithms.** When we study the performance of parallel algorithms, we usually do not only measure the time of the algorithm (as we would in the sequential case), but also its work (the total number of computational steps performed by the algorithm). This is important as a parallel algorithm may need polynomially many processors to reach its promised runtime: For instance, an algorithm that runs in time $O(\log n)$ with $O(n^2)$ work will need at least time $O(n^2/p)$ on a machine with $p$ processors – which is bad if there exists a linear time sequential algorithm and $p < n$. In the circuit model the parallel time of an algorithm corresponds to the depth of the circuit, and the work to its size. While the layers of the AC- and para-AC-hierarchy measure the time of parallel algorithms quite precisely, they only require the size of the circuits to be polynomial or to be bounded by $f(k) \cdot n^c$, respectively. Using Theorem 2.3, we can improve the work of any parameterized parallel algorithm from $f(k) \cdot n^c$ to $g(k) + n^{c'}$ while, at the same time, reducing the depth of the circuit from $f(k) + c \log^i n$ to $c' \log^i n$.

**Lemma 2.4.** Let $(Q, \kappa)$ be a parameterized problem with $(Q, \kappa) \in \text{para-AC}^i$. Then there are a computable function $g: \mathbb{N} \to \mathbb{N}$ and a constant $c'$ such that there is a DLOGTIME-uniform family $(C'_{n,k})_{n,k \in \mathbb{N}}$ of para-AC$^i$-circuits that decides $(Q, \kappa)$ and in which every $C'_{n,k}$ has depth at most $c' \log^i n$ and size at most $g(k) + n^{c'}$.

**Sketch of Proof.** Use the AC$^i$-circuit from Theorem 2.3 to compute a kernel in depth $c \log^i n$ and solve the kernel using “brute force” in constant depth afterwards. ◀

Note that the function $g$ from the lemma may grow exponentially faster than $f$, as the circuit from the lemma internally solves an instance $x'$ with $|x'| \le f(\kappa(x))$ and $\kappa(x') \le f(\kappa(x))$. A direct application of Lemma 2.4 is therefore only of theoretical interest. It shows, however, that we can always search for parameterized parallel algorithms that run in polylogarithmic time and whose work is polynomial plus an *additive* term depending only on the parameter.

## 3 Parallel Kernels for Vertex Cover and Matching

The parameterized vertex cover problem is a prime example used to demonstrate many different kernelization techniques, and an outrider in the race for small kernels. In this section we revisit the problem from the point of view of circuit complexity and establish a link between circuit complexity and kernel size. An early result in this context is due to Cai et al. [9] which, translated into the terminology of the present paper, implies that a kernel for *p*-VERTEX-COVER can be computed in logarithmic space and, hence, in AC$^1$. Elberfeld et al. [16] later noticed that the kernel of size $k^2 + 2k$ computed by Cai et al. can actually also be computed in TC$^0$. This result was later once more refined by showing that the same kernel can be computed in para-AC$^0$ [2]. Together with Theorem 2.3 this implies that a kernel of size $f(k)$ can be computed in AC$^0$ for some computable function $f$. In fact, we can improve the bound in this case to $2^{\sqrt{k}}$ for any fixed $\delta > 0$:

**Lemma 3.1.** For every $\delta \in \mathbb{N}$ there is a DLOGTIME-uniform family of AC$^0$-circuits that, on input of a tuple $(G, k)$, outputs a *p*-VERTEX-COVER kernel with at most $2^{\sqrt{k}}$ vertices.

**Proof.** Let $I$ be the input instance and let $n = |I|$ be the size of its encoding. The circuit first checks if we have $k \le \log^\delta(n)$. If not, we have $2^{\sqrt{k}} > n$ and the instance is already the desired kernel. Otherwise the circuit can simulate threshold gates up to $k$ using standard hashing techniques, as AC$^0$-circuits can simulate polylogarithmic threshold gates [30]. Since the TC$^0$-circuit from Elberfeld et al. [16] only uses threshold gates up to $k$, it follows that the AC$^0$-circuit under construction can simulate this TC$^0$-circuit, which completes the proof. ◀
**Application: Improve the Work of Parallel Algorithms.** When we study the performance of parallel algorithms, we usually do not only measure the time of the algorithm (as we would in the sequential case), but also its work (the total number of computational steps performed by the algorithm). This is important as a parallel algorithm may need polynomially many processors to reach its promised runtime: For instance, an algorithm that runs in time $O(\log n)$ with $O(n^2)$ work will need at least time $O(n^2/p)$ on a machine with $p$ processors – which is bad if there exists a linear time sequential algorithm and $p < n$. In the circuit model the parallel time of an algorithm corresponds to the depth of the circuit, and the work to its size. While the layers of the AC- and para-AC-hierarchy measure the time of parallel algorithms quite precisely, they only require the size of the circuits to be polynomial or to be bounded by $f(k) \cdot n^c$, respectively. Using Theorem 2.3, we can improve the work of any parameterized parallel algorithm from $f(k) \cdot n^c$ to $g(k) + n^{c'}$ while, at the same time, reducing the depth of the circuit from $f(k) + c \log^i n$ to $c' \log^i n$.

**Lemma 2.4.** Let $(Q, \kappa)$ be a parameterized problem with $(Q, \kappa) \in \text{para-AC}^i$. Then there are a computable function $g: \mathbb{N} \to \mathbb{N}$ and a constant $c'$ such that there is a DLOGTIME-uniform family $(C'_{n,k})_{n,k \in \mathbb{N}}$ of para-AC$^i$-circuits that decides $(Q, \kappa)$ and in which every $C'_{n,k}$ has depth at most $c' \log^i n$ and size at most $g(k) + n^{c'}$.

**Sketch of Proof.** Use the AC$^i$-circuit from Theorem 2.3 to compute a kernel in depth $c \log^i n$ and solve the kernel using “brute force” in constant depth afterwards. ◀

Note that the function $g$ from the lemma may grow exponentially faster than $f$, as the circuit from the lemma internally solves an instance $x'$ with $|x'| \le f(\kappa(x))$ and $\kappa(x') \le f(\kappa(x))$. A direct application of Lemma 2.4 is therefore only of theoretical interest. It shows, however, that we can always search for parameterized parallel algorithms that run in polylogarithmic time and whose work is polynomial plus an *additive* term depending only on the parameter.

### 3 Parallel Kernels for Vertex Cover and Matching

The parameterized vertex cover problem is a prime example used to demonstrate many different kernelization techniques, and an outrider in the race for small kernels. In this section we revisit the problem from the point of view of circuit complexity and establish a link between circuit complexity and kernel size. An early result in this context is due to Cai et al. [9] which, translated into the terminology of the present paper, implies that a kernel for *p*-VERTEX-COVER can be computed in logarithmic space and, hence, in AC$^1$. Elberfeld et al. [16] later noticed that the kernel of size $k^2 + 2k$ computed by Cai et al. can actually also be computed in TC$^0$. This result was later once more refined by showing that the same kernel can be computed in para-AC$^0$ [2]. Together with Theorem 2.3 this implies that a kernel of size $f(k)$ can be computed in AC$^0$ for some computable function $f$. In fact, we can improve the bound in this case to $2^{\sqrt{k}}$ for any fixed $\delta > 0$:

**Lemma 3.1.** For every $\delta \in \mathbb{N}$ there is a DLOGTIME-uniform family of AC$^0$-circuits that, on input of a tuple $(G, k)$, outputs a *p*-VERTEX-COVER kernel with at most $2^{\sqrt{k}}$ vertices.

**Proof.** Let $I$ be the input instance and let $n = |I|$ be the size of its encoding. The circuit first checks if we have $k \le \log^\delta(n)$. If not, we have $2^{\sqrt{k}} > n$ and the instance is already the desired kernel. Otherwise the circuit can simulate threshold gates up to $k$ using standard hashing techniques, as AC$^0$-circuits can simulate polylogarithmic threshold gates [30]. Since the TC$^0$-circuit from Elberfeld et al. [16] only uses threshold gates up to $k$, it follows that the AC$^0$-circuit under construction can simulate this TC$^0$-circuit, which completes the proof. ◀
13:6 Computing Kernels in Parallel: Lower and Upper Bounds

The central observation in the proof of Lemma 3.1 is that the threshold-gates in the corresponding family of TC$^0$-circuits only “count up to the parameter.” We will use exactly the same trick for other TC$^0$-kernelizations, but will then only formulate it as corollary. Summarizing the statements from above, we can compute an exponential kernel for p- VERTEX-COVER in AC$^0$ and a quadratic kernel in TC$^0$. However, the best known kernelizations for p- VERTEX-COVER are able to produce linear kernels – and a reasonable next step is to implement them in parallel as well. Unfortunately, this is a way more challenging task, as both the classical 3k kernel based on crown decomposition [14] and the 2k kernel due to Chen et al. [10] require the computation of sufficiently large matchings. We can state this more precisely for the latter observation, by showing that the core part of the kernelization is NC-equivalent to computing maximum matchings in bipartite graphs. The kernelization of Chen et al. is based on the following fact, known as the Nemhauser–Trotter Theorem:

► **Fact 3.2 ([29]).** Let $G = (V, E)$ be a graph and $I = \{x_v | v \in V\}$ be a set of variables. For every optimal solution $\beta$: $I \to \mathbb{R}$ for the following linear program (LPVC)

$$
\begin{array}{ll}
\min & \sum_{v \in V} x_v \\
\text{for all } \{u, v\} \in E \\
\text{for all } v \in V \\
\text{let } V_0 = \{v | \beta(x_v) < 1/2\}, V_{1/2} = \{v | \beta(x_v) = 1/2\}, V_1 = \{v | \beta(x_v) > 1/2\} \text{ be a} \\
\text{partition of } V. \text{ There is a minimum vertex cover } S \text{ of } G \text{ that satisfies } V_1 \subseteq S \subseteq V_1 \cup V_{1/2}.
\end{array}
$$

let $V_0 = \{v | \beta(x_v) < 1/2\}$, $V_{1/2} = \{v | \beta(x_v) = 1/2\}$, $V_1 = \{v | \beta(x_v) > 1/2\}$ be a partition of $V$. There is a minimum vertex cover $S$ of $G$ that satisfies $V_1 \subseteq S \subseteq V_1 \cup V_{1/2}$.

Chen et al. have shown that one can obtain the desired kernel from a solution of LPVC by discarding the vertices of $V_0$ and by taking the vertices of $V_1$ into the solution. The remaining $2k$ vertices of $V_{1/2}$ constitute the kernel [10]. The following theorem shows that solving LPVC is tightly linked to the maximum matching problems for bipartite graphs.

**Theorem 3.3.** *Computing a solution for LPVC is NC-equivalent to computing a maximum matching in bipartite graphs.*

**Sketch of Proof.** For the first direction we construct a bipartite auxiliary graph $H$ such that an optimal vertex cover of $H$ can be turned into a half-integral solution of LPVC on $G$. This vertex cover of $H$ can be computed using a maximum matching subroutine and König's Theorem [25]. In the second direction we wish to compute a maximum matching in a bipartite graph with the help of LPVC. We first turn an optimal real solution of LPVC into an optimal half-integral solution. Afterwards, we transform this half-integral solution into an optimal integral solution, that is, into a minimal vertex cover. Applying König's Theorem again results in the desired matching. ◀

The parallel complexity of the maximum matching problem is still not fully resolved. The currently best parallel algorithms run in RNC$^2$ [28] or quasi-NC$^2$ [17]. From the theorem we can deduce that we can compute the Nemhauser–Trotter-based 2k-vertex kernel for p- VERTEX-COVER in RNC and quasi-NC; and we can deduce that we cannot compute this kernel in NC without improving the parallel complexity of the maximum matching problem – which is a longstanding open problem.

► **Corollary 3.4.** There is a DLOGTIME-uniform family of NC-circuits of polylogarithmic depth that, on input of a graph $G = (V, E)$ and an integer $k$, outputs a kernel of p-vertex-cover with at most 2k vertices. The circuits of the family either use randomness and have size $|V|^c$, or are deterministic and of size $|V|^{c \log |V|}$.
13:6 Computing Kernels in Parallel: Lower and Upper Bounds

The central observation in the proof of Lemma 3.1 is that the threshold-gates in the corresponding family of TC$^0$-circuits only “count up to the parameter.” We will use exactly the same trick for other TC$^0$-kernelizations, but will then only formulate it as corollary. Summarizing the statements from above, we can compute an exponential kernel for p- VERTEX-COVER in AC$^0$ and a quadratic kernel in TC$^0$. However, the best known kernelizations for p- VERTEX-COVER are able to produce linear kernels – and a reasonable next step is to implement them in parallel as well. Unfortunately, this is a way more challenging task, as both the classical 3k kernel based on crown decomposition [14] and the 2k kernel due to Chen et al. [10] require the computation of sufficiently large matchings. We can state this more precisely for the latter observation, by showing that the core part of the kernelization is NC-equivalent to computing maximum matchings in bipartite graphs. The kernelization of Chen et al. is based on the following fact, known as the Nemhauser–Trotter Theorem:

► **Fact 3.2 ([29]).** Let $G = (V, E)$ be a graph and $I = \{x_v | v \in V\}$ be a set of variables. For every optimal solution $\beta: I \to \mathbb{R}$ for the following linear program (LPVC)

$$
\begin{array}{ll}
\min & \sum_{v \in V} x_v \\
\text{for all } \{u, v\} \in E \\
\text{for all } v \in V \\
\text{let } V_0 = \{v | \beta(x_v) < 1/2\}, V_{1/2} = \{v | \beta(x_v) = 1/2\}, V_1 = \{v | \beta(x_v) > 1/2\} \text{ be a} \\
\text{partition of } V. \text{ There is a minimum vertex cover } S \text{ of } G \text{ that satisfies } V_1 \subseteq S \subseteq V_1 \cup V_{1/2}.
\end{array}
$$

let $V_0 = \{v | \beta(x_v) < 1/2\}$, $V_{1/2} = \{v | \beta(x_v) = 1/2\}$, $V_1 = \{v | \beta(x_v) > 1/2\}$ be a partition of $V$. There is a minimum vertex cover $S$ of $G$ that satisfies $V_1 \subseteq S \subseteq V_1 \cup V_{1/2}$.

Chen et al. have shown that one can obtain the desired kernel from a solution of LPVC by discarding the vertices of $V_0$ and by taking the vertices of $V_1$ into the solution. The remaining $2k$ vertices of $V_{1/2}$ constitute the kernel [10]. The following theorem shows that solving LPVC is tightly linked to the maximum matching problems for bipartite graphs.

► **Theorem 3.3.** *Computing a solution for LPVC is NC-equivalent to computing a maximum matching in bipartite graphs.*

**Sketch of Proof.** For the first direction we construct a bipartite auxiliary graph $H$ such that an optimal vertex cover of $H$ can be turned into a half-integral solution of LPVC on $G$. This vertex cover of $H$ can be computed using a maximum matching subroutine and König's Theorem [25]. In the second direction we wish to compute a maximum matching in a bipartite graph with the help of LPVC. We first turn an optimal real solution of LPVC into an optimal half-integral solution. Afterwards, we transform this half-integral solution into an optimal integral solution, that is, into a minimal vertex cover. Applying König's Theorem again results in the desired matching. ◀

The parallel complexity of the maximum matching problem is still not fully resolved. The currently best parallel algorithms run in RNC$^2$ [28] or quasi-NC$^2$ [17]. From the theorem we can deduce that we can compute the Nemhauser–Trotter-based 2k-vertex kernel for p- VERTEX-COVER in RNC and quasi-NC; and we can deduce that we cannot compute this kernel in NC without improving the parallel complexity of the maximum matching problem – which is a longstanding open problem.

► **Corollary 3.4.** There is a DLOGTIME-uniform family of NC-circuits of polylogarithmic depth that, on input of a graph $G = (V, E)$ and an integer $k$, outputs a kernel of p-vertex-cover with at most 2k vertices. The circuits of the family either use randomness and have size $|V|^c$, or are deterministic and of size $|V|^{c \log |V|}$.
Note that other kernels that are based on the Nemhauser-Trotter Theorem, such as the one by Soleimanfallah and Yeo [31], or the one by Lampis [27], also do not bypass Theorem 3.3. A natural goal is, thus, to compute linear kernels for *p*- VERTEX-COVER in NC – most likely using an algorithm that does not rely on a LPVC relaxation. Table 1 summarizes the complexity of computing kernels of certain size for *p*- VERTEX-COVER.

Since *p*-MATCHING turns out to be an obstruction for parallel kernelization, it is a natural question in the light of this paper, whether or not we are able to compute polynomial kernels for the matching problem in NC. Note that the problem is in para-AC<sup>0</sup>, and hence we can compute a size-*f*(*k*) kernel in AC<sup>0</sup>; and since MATCHING ∈ RNC we can compute a size-1 kernel in RNC.

**Lemma 3.5.** *There is a DLOGTIME-uniform family of TC<sup>0</sup>-circuits that, on input of a tuple (G, k), outputs a p-MATCHING kernel with at most O(k<sup>2</sup>) vertices.*

The circuits of Lemma 3.5 need their threshold gates “only” to count up to *k*. We can thus deduce the following corollary (the proof argument is the same as for Lemma 3.1):

**Corollary 3.6.** *For every $\delta \in \mathbb{N}$ there is a DLOGTIME-uniform family of AC$^0$-circuits that, on input of a tuple $(G, k)$, outputs a $p$-MATCHING kernel with at most $O(2^{\delta/\sqrt{k}})$ vertices.*

## 4 Parallel Kernels for the Feedback Vertex Set Problem

The input for *p*-FEEDBACK-VERTEX-SET = *p*-FVS is an undirected multigraph $G = (V, E)$ and an integer *k*, the question is whether it is possible to delete *k* vertices such that the remaining graph is a forest. The problem is well-known to be fixed-parameter tractable. Concerning the parallel complexity, it is known that membership in FPT can be witnessed by a machine that uses “FPT time and XL space” [16] and the problem was recently shown to lie in para-NC<sup>2+ϵ</sup> ⊆ para-NC<sup>3</sup> [3].

A lot of effort has been put into the design of sequential kernels for this problem, ultimately resulting in a kernel with $O(k^2)$ vertices [8, 7, 33, 22]. Much less is known concerning parallel kernels. Since the $k=0$ slice of *p*-FVS is exactly the L-complete [13] problem whether a given graph is a forest, we get as a lower bound that no kernel of any size can be computed for *p*-FVS by any circuit class $C$ unless $L \subseteq C$ and the smallest AC-class for which this is known is AC<sup>1</sup>. On the other hand, the mentioned membership in para-NC<sup>2+ϵ</sup> together with Theorem 2.3 yield an NC<sup>2+ϵ</sup> kernel. In summary:

**Lemma 4.1.** *There is a DLOGTIME-uniform family of NC<sup>2+ϵ</sup>-circuits that, on input of a tuple (G, k), outputs a p-FVS kernel with at most f(k) vertices. There is no such family of AC<sup>1-ϵ</sup>-circuits, unless L ⊆ AC<sup>1-ϵ</sup>.*

A natural first question arising from this lemma is: Can we improve the bounds? It turns out that we can lower the upper bound from NC<sup>2+ϵ</sup> to AC<sup>1+ϵ</sup> by observing the reduction rules used in sequential kernels for *p*-FVS can, in certain cases, be applied in parallel. In detail, the known sequential kernels for *p*-FVS all repeatedly apply (at least) the below rules, whose correctness is very easily seen. We will show that each of the first three rules can individually be applied exhaustively in AC<sup>1</sup>. Based on this, we show *p*-FVS ∈ para-AC<sup>1↑</sup>.

**Leaf Rule** Delete a vertex $v$ of degree 1.

**Chain Rule** Contract a vertex $v$ of degree 2 to one of its neighbors.

**Loop Rule** Delete a vertex $v$ with $v \in N(v)$, reduce $k$ by 1.

**Flower Rule** Delete a vertex $v$ that appears in more than $k$ cycles that only share the vertex $v$, reduce $k$ by 1.
Note that other kernels that are based on the Nemhauser-Trotter Theorem, such as the one by Soleimanfallah and Yeo [31], or the one by Lampis [27], also do not bypass Theorem 3.3. A natural goal is, thus, to compute linear kernels for *p*-VERTEX-COVER in NC – most likely using an algorithm that does not rely on a LPVC relaxation. Table 1 summarizes the complexity of computing kernels of certain size for *p*-VERTEX-COVER.

Since *p*-MATCHING turns out to be an obstruction for parallel kernelization, it is a natural question in the light of this paper, whether or not we are able to compute polynomial kernels for the matching problem in NC. Note that the problem is in para-AC<sup>0</sup>, and hence we can compute a size-*f*(*k*) kernel in AC<sup>0</sup>; and since MATCHING ∈ RNC we can compute a size-1 kernel in RNC.

**Lemma 3.5.** *There is a DLOGTIME-uniform family of TC<sup>0</sup>-circuits that, on input of a tuple (G, k), outputs a p-MATCHING kernel with at most O(k<sup>2</sup>) vertices.*

The circuits of Lemma 3.5 need their threshold gates “only” to count up to *k*. We can thus deduce the following corollary (the proof argument is the same as for Lemma 3.1):

**Corollary 3.6.** *For every $\delta \in \mathbb{N}$ there is a DLOGTIME-uniform family of AC$^0$-circuits that, on input of a tuple $(G, k)$, outputs a $p$-MATCHING kernel with at most $O(2^{\delta/\sqrt{k}})$ vertices.*

## 4 Parallel Kernels for the Feedback Vertex Set Problem

The input for *p*-FEEDBACK-VERTEX-SET = *p*-FVS is an undirected multigraph $G = (V, E)$ and an integer *k*, the question is whether it is possible to delete *k* vertices such that the remaining graph is a forest. The problem is well-known to be fixed-parameter tractable. Concerning the parallel complexity, it is known that membership in FPT can be witnessed by a machine that uses “FPT time and XL space” [16] and the problem was recently shown to lie in para-NC<sup>2+ε</sup> ⊆ para-NC<sup>3</sup> [3].

A lot of effort has been put into the design of sequential kernels for this problem, ultimately resulting in a kernel with $O(k^2)$ vertices [8, 7, 33, 22]. Much less is known concerning parallel kernels. Since the $k=0$ slice of *p*-FVS is exactly the L-complete [13] problem whether a given graph is a forest, we get as a lower bound that no kernel of any size can be computed for *p*-FVS by any circuit class $C$ unless $L \subseteq C$ and the smallest AC-class for which this is known is AC<sup>1</sup>. On the other hand, the mentioned membership in para-NC<sup>2+ε</sup> together with Theorem 2.3 yield an NC<sup>2+ε</sup> kernel. In summary:

**Lemma 4.1.** *There is a DLOGTIME-uniform family of NC<sup>2+ε</sup>-circuits that, on input of a tuple (G, k), outputs a p-FVS kernel with at most f(k) vertices. There is no such family of AC<sup>1-ε</sup>-circuits, unless L ⊆ AC<sup>1-ε</sup>.*

A natural first question arising from this lemma is: Can we improve the bounds? It turns out that we can lower the upper bound from NC<sup>2+ε</sup> to AC<sup>1+ε</sup> by observing the reduction rules used in sequential kernels for *p*-FVS can, in certain cases, be applied in parallel. In detail, the known sequential kernels for *p*-FVS all repeatedly apply (at least) the below rules, whose correctness is very easily seen. We will show that each of the first three rules can individually be applied exhaustively in AC<sup>1</sup>. Based on this, we show *p*-FVS ∈ para-AC<sup>1↑</sup>.

**Leaf Rule** Delete a vertex $v$ of degree 1.

**Chain Rule** Contract a vertex $v$ of degree 2 to one of its neighbors.

**Loop Rule** Delete a vertex $v$ with $v \in N(v)$, reduce $k$ by 1.

**Flower Rule** Delete a vertex $v$ that appears in more than $k$ cycles that only share the vertex $v$, reduce $k$ by 1.
<figure><img src="image_77.png" /><figcaption>Figure 1 A graph that is fully reduced by the Chain Rule and the Loop Rule in $k = 6$ rounds. In every round, the Chain Rule can only be applied after the Loop Rule was used exhaustively.</figcaption></figure>

**Lemma 4.2.** *There is a DLOGTIME-uniform family of AC$^1$-circuits that, on input of a tuple $(G, k)$, outputs a tuple $(G', k')$ that results from repeatedly applying (only) the Leaf Rule as long as possible. The same holds for the Chain Rule and for the Loop Rule.*

**Theorem 4.3.** *p-FVS* ∈ para-AC$^{1\uparrow}$.

**Sketch of Proof.** The circuit implements a search-tree of depth $O(k)$ that, on any layer, applies the reduction rules of Lemma 4.2 using an AC$^1$-circuit. This either reduces $k$ immediately by one, or provides a small set of vertices on which the circuit can branch. ◀

**Corollary 4.4.** *There is a DLOGTIME-uniform family of AC$^{1+\epsilon}$-circuits that, on input of a tuple $(G, k)$, outputs a p-FVS kernel with at most $f(k)$ vertices.*

**Proof.** Follows by Theorem 2.3 and by the fact that para-AC$^{i\uparrow} \subseteq$ para-AC$^{i+\epsilon}$ [2]. ◀

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

We now have rather tight bounds (an upper bound of AC$^{1+\epsilon}$ and a conditional lower bound of AC$^{1-\epsilon}$) on how quickly we can compute some kernel for p-FVS in parallel. However, there is a natural second question arising from Lemma 4.1: Can we also compute a polynomial kernel in parallel?

We claim that progress towards such a kernel cannot solely be based on the presented reduction rules. In the proof of Theorem 4.3 we may need to branch after the exhaustive application of one of the rules Leaf Rule, Chain Rule, or Loop Rule. If we seek to implement a polynomial kernel for p-FVS in NC, we have to implement these rules without branching and have to apply the rules exhaustively together while they may influence each other. Figure 1 provides an intuition why this interplay is “very sequential,” and Theorem 4.5 provides evidence that it is in fact very unlikely that there exists a parallel algorithm that computes the result of jointly applying all rules exhaustively.

**Theorem 4.5.** *The problem of deciding whether a specific vertex of a given graph will be removed by an exhaustive application of the Leaf Rule, the Chain Rule, and the Loop Rule is P-hard under NC$^1$-reduction.*

**Sketch of Proof.** We encode the monotone circuit value problem into a graph similar to the one of Figure 1. The reduction rules then simulate the propagation of truth values through the circuit. ◀

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

**Remark 4.6.** *The proof of Theorem 4.5 shows that the problem remains P-hard restricted to the Chain Rule and the Loop Rule, even if they are alternatingly executed exhaustively.*

We close this section with the observation that also the last rule, the Flower Rule, is unlikely to yield a parallel algorithm.

**Theorem 4.7.** *Unless MATCHING ∈ NC, there is no DLOGTIME-uniform family of NC$^i$-circuits for any i that determines, give a graph G = (V, E), an integer k, and a vertex v, whether the Flower Rule can be applied to v.*
<figure><img src="image_80.png" /><figcaption>Figure 1 A graph that is fully reduced by the Chain Rule and the Loop Rule in $k = 6$ rounds. In every round, the Chain Rule can only be applied after the Loop Rule was used exhaustively.</figcaption></figure>

**Lemma 4.2.** *There is a DLOGTIME-uniform family of AC$^1$-circuits that, on input of a tuple $(G, k)$, outputs a tuple $(G', k')$ that results from repeatedly applying (only) the Leaf Rule as long as possible. The same holds for the Chain Rule and for the Loop Rule.*

**Theorem 4.3.** *p-FVS* ∈ para-AC$^{1\uparrow}$.

**Sketch of Proof.** The circuit implements a search-tree of depth $O(k)$ that, on any layer, applies the reduction rules of Lemma 4.2 using an AC$^1$-circuit. This either reduces $k$ immediately by one, or provides a small set of vertices on which the circuit can branch. ◀

**Corollary 4.4.** *There is a DLOGTIME-uniform family of AC$^{1+\epsilon}$-circuits that, on input of a tuple $(G, k)$, outputs a p-FVS kernel with at most $f(k)$ vertices.*

**Proof.** Follows by Theorem 2.3 and by the fact that para-AC$^{i\uparrow} \subseteq$ para-AC$^{i+\epsilon}$ [2]. ◀

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

We now have rather tight bounds (an upper bound of AC$^{1+\epsilon}$ and a conditional lower bound of AC$^{1-\epsilon}$) on how quickly we can compute some kernel for p-FVS in parallel. However, there is a natural second question arising from Lemma 4.1: Can we also compute a polynomial kernel in parallel?

We claim that progress towards such a kernel cannot solely be based on the presented reduction rules. In the proof of Theorem 4.3 we may need to branch after the exhaustive application of one of the rules Leaf Rule, Chain Rule, or Loop Rule. If we seek to implement a polynomial kernel for p-FVS in NC, we have to implement these rules without branching and have to apply the rules exhaustively together while they may influence each other. Figure 1 provides an intuition why this interplay is “very sequential,” and Theorem 4.5 provides evidence that it is in fact very unlikely that there exists a parallel algorithm that computes the result of jointly applying all rules exhaustively.

**Theorem 4.5.** *The problem of deciding whether a specific vertex of a given graph will be removed by an exhaustive application of the Leaf Rule, the Chain Rule, and the Loop Rule is P-hard under NC$^1$-reduction.*

**Sketch of Proof.** We encode the monotone circuit value problem into a graph similar to the one of Figure 1. The reduction rules then simulate the propagation of truth values through the circuit. ◀

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

**Remark 4.6.** *The proof of Theorem 4.5 shows that the problem remains P-hard restricted to the Chain Rule and the Loop Rule, even if they are alternatingly executed exhaustively.*

We close this section with the observation that also the last rule, the Flower Rule, is unlikely to yield a parallel algorithm.

**Theorem 4.7.** *Unless MATCHING ∈ NC, there is no DLOGTIME-uniform family of NC$^i$-circuits for any i that determines, give a graph G = (V, E), an integer k, and a vertex v, whether the Flower Rule can be applied to v.*
# 5 Parallel Kernels for Structural Parameterizations

It is known that NP-hard graph parameters that are closed under taking disjoint union do not allow a polynomial kernel unless NP ⊆ coNP/poly [14]. Famous problems that suffer from this result are the decision versions of tree width, path width, and tree depth, which has led to a growing body of research that considers structural parameters for these problems [6, 5, 24]. A commonly used parameter in this line of research is the vertex cover number of the input graph and in this section we extend the cited results by proving that the corresponding kernels can be computed in small circuit classes.

We use the following standard definitions: A tree decomposition of a graph $G = (V, E)$ is a tuple $(T, \iota)$ where $T$ is a tree and $\iota$ a mapping from the nodes of $T$ to subsets of $V$ (which we call bags) such that for every $u \in V$ and every $\{v, w\} \in E$ there is (1) a node $n$ with $u \in \iota(n)$, (2) a node $m$ with $\{v, w\} \subseteq \iota(m)$, and (3) the set $\{n \mid u \in \iota(n)\}$ is connected in $T$. The width of a tree decomposition is the maximum size of the bags minus one. For a graph $G$, its tree width $\text{tw}(G)$ is the minimum width of all tree decompositions of $G$, its path width $\text{pw}(G)$ is the minimum width of all tree decompositions of $G$ that are paths, and its tree depth $\text{td}(G)$ is the minimum width of all tree decompositions $(T, \iota)$ of $G$ that can be rooted in such a way that for all $n, m \in V(T)$ we have $\iota(n) \subseteq \iota(m)$ if $m$ is an descendant of $n$. The following two facts will be useful, where $N(v) = \{u \mid \{u, v\} \in E\}$ is the neighborhood of $v$, $N[v] = N(v) \cup \{v\}$, and where we call a vertex $v$ simplicial if $N(v)$ is a clique:

**Fact 5.1 ([6, 5, 24]).** Let $G = (V, E)$ be a graph with tree width, path width, or tree depth at most $k$ and with $u, v \in V$, $\{u, v\} \notin E$, and $|N(u) \cap N(v)| > k$. Then adding the edge $\{u, v\}$ to $G$ will not increase the tree width, path width, or tree depth of $G$, respectively.

**Fact 5.2 ([4]).** Let $G = (V, E)$ be a graph and $v \in V$ be a simplicial vertex, then we have $\text{tw}(G) \ge |N(v)|$.

**Computing a Kernel for Tree Width.** For the problem $p_{\text{vc}}$-TREE-WIDTH we are given a graph $G = (V, E)$, an integer $k$, and a vertex cover $S \subseteq V$ of $G$; the parameter is $|S|$ and the question is whether $\text{tw}(G) \le k$ holds.

**Theorem 5.3.** There is a DLOGTIME-uniform family of TC$^0$-circuits that, on inputs of a triple $(G, k, S)$, outputs a $p_{\text{vc}}$-TREE-WIDTH kernel with at most $O(|S|^3)$ vertices.

**Sketch of Proof.** We check in parallel for every pair $u, v \in S$ with $\{u, v\} \notin E$ if they have more than $k$ common neighbors in $V \setminus S$ and, if so, add the edge $\{u, v\}$ by Fact 5.1. By Fact 5.2 simplicial vertices in $V \setminus S$ can not have high degree and we may safely remove them by standard arguments. A counting argument then provides the claimed kernel size. $\quad$

**Corollary 5.4.** For every $\delta \in \mathbb{N}$ there is a DLOGTIME-uniform family of AC$^0$-circuits that, on input of a triple $(G, k, S)$, outputs a $p_{\text{vc}}$-TREE-WIDTH kernel with at most $2^{\delta \sqrt{|S|}}$ vertices.

**Computing a Kernel for Path Width.** We define $p_{\text{vc}}$-PATH-WIDTH analogously to $p_{\text{vc}}$-TREE-WIDTH and the aim of this section is to reformulate Theorem 5.3 in terms of path width. The main difference is that we cannot simply delete simplicial vertices as this would, for instance, eliminate trees completely. We can, however, use the following weaker result:

**Fact 5.5 ([5]).** Let $G = (V, E)$ be a graph, $k \in \mathbb{N}$, and $v \in V$ be a simplicial vertex. If the degree $|N(v)|$ of $v$ is 1 and the neighbor of $v$ has another degree-1 neighbor, or if we have $2 \le |N(v)| \le k$ and for each pair $x, y \in N(v)$ there is a simplicial vertex $w \in N(x) \cap N(y)$ with $w \notin N[v]$, then $\text{pw}(G) \le k$ if, and only if, $\text{pw}(G[V \setminus \{v\}]) \le k$.
# 5 Parallel Kernels for Structural Parameterizations

It is known that NP-hard graph parameters that are closed under taking disjoint union do not allow a polynomial kernel unless NP ⊆ coNP/poly [14]. Famous problems that suffer from this result are the decision versions of tree width, path width, and tree depth, which has led to a growing body of research that considers structural parameters for these problems [6, 5, 24]. A commonly used parameter in this line of research is the vertex cover number of the input graph and in this section we extend the cited results by proving that the corresponding kernels can be computed in small circuit classes.

We use the following standard definitions: A tree decomposition of a graph $G = (V, E)$ is a tuple $(T, \iota)$ where $T$ is a tree and $\iota$ a mapping from the nodes of $T$ to subsets of $V$ (which we call *bags*) such that for every $u \in V$ and every $\{v, w\} \in E$ there is (1) a node $n$ with $u \in \iota(n)$, (2) a node $m$ with $\{v, w\} \subseteq \iota(m)$, and (3) the set $\{n \mid u \in \iota(n)\}$ is connected in $T$. The *width* of a tree decomposition is the maximum size of the bags minus one. For a graph $G$, its *tree width* $\text{tw}(G)$ is the minimum width of all tree decompositions of $G$, its *path width* $\text{pw}(G)$ is the minimum width of all tree decompositions of $G$ that are paths, and its *tree depth* $\text{td}(G)$ is the minimum width of all tree decompositions $(T, \iota)$ of $G$ that can be rooted in such a way that for all $n, m \in V(T)$ we have $\iota(n) \subseteq \iota(m)$ if $m$ is an descendant of $n$. The following two facts will be useful, where $N(v) = \{u \mid \{u, v\} \in E\}$ is the neighborhood of $v$, $N[v] = N(v) \cup \{v\}$, and where we call a vertex $v$ *simplicial* if $N(v)$ is a clique:

**Fact 5.1 ([6, 5, 24]).** Let $G = (V, E)$ be a graph with tree width, path width, or tree depth at most $k$ and with $u, v \in V$, $\{u, v\} \notin E$, and $|N(u) \cap N(v)| > k$. Then adding the edge $\{u, v\}$ to $G$ will not increase the tree width, path width, or tree depth of $G$, respectively.

**Fact 5.2 ([4]).** Let $G = (V, E)$ be a graph and $v \in V$ be a simplicial vertex, then we have $\text{tw}(G) \ge |N(v)|$.

**Computing a Kernel for Tree Width.** For the problem $p_{\text{vc}}$-TREE-WIDTH we are given a graph $G = (V, E)$, an integer $k$, and a vertex cover $S \subseteq V$ of $G$; the parameter is $|S|$ and the question is whether $\text{tw}(G) \le k$ holds.

**Theorem 5.3.** There is a DLOGTIME-uniform family of TC$^0$-circuits that, on inputs of a triple $(G, k, S)$, outputs a $p_{\text{vc}}$-TREE-WIDTH kernel with at most $O(|S|^3)$ vertices.

**Sketch of Proof.** We check in parallel for every pair $u, v \in S$ with $\{u, v\} \notin E$ if they have more than $k$ common neighbors in $V \setminus S$ and, if so, add the edge $\{u, v\}$ by Fact 5.1. By Fact 5.2 simplicial vertices in $V \setminus S$ can not have high degree and we may safely remove them by standard arguments. A counting argument then provides the claimed kernel size. $\quad$

**Corollary 5.4.** For every $\delta \in \mathbb{N}$ there is a DLOGTIME-uniform family of AC$^0$-circuits that, on input of a triple $(G, k, S)$, outputs a $p_{\text{vc}}$-TREE-WIDTH kernel with at most $2^{\delta \sqrt{|S|}}$ vertices.

**Computing a Kernel for Path Width.** We define $p_{\text{vc}}$-PATH-WIDTH analogously to $p_{\text{vc}}$-TREE-WIDTH and the aim of this section is to reformulate Theorem 5.3 in terms of path width. The main difference is that we cannot simply delete simplicial vertices as this would, for instance, eliminate trees completely. We can, however, use the following weaker result:

**Fact 5.5 ([5]).** Let $G = (V, E)$ be a graph, $k \in \mathbb{N}$, and $v \in V$ be a simplicial vertex. If the degree $|N(v)|$ of $v$ is 1 and the neighbor of $v$ has another degree-1 neighbor, or if we have $2 \le |N(v)| \le k$ and for each pair $x, y \in N(v)$ there is a simplicial vertex $w \in N(x) \cap N(y)$ with $w \notin N[v]$, then $\text{pw}(G) \le k$ if, and only if, $\text{pw}(G[V \setminus \{v\}]) \le k$.
13:10 Computing Kernels in Parallel: Lower and Upper Bounds

**Theorem 5.6.** There is a DLOGTIME-uniform family of TC$^0$-circuits that, on input of a triple (G, k, S), outputs a $p_{\text{vc}}$-PATH-WIDTH kernel with at most $O(|S|^3)$ vertices.

**Sketch of Proof.** In difference to the proof of Theorem 5.3, we must now identify the vertices for which Fact 5.5 applies in constant time. This is not trivial because of dependencies between them, but a circuit can use a two-stage marking process to find them. ◀

**Corollary 5.7.** For every $\delta \in \mathbb{N}$ there is a DLOGTIME-uniform family of AC$^0$-circuits that, on input of a triple (G, k, S), outputs a $p_{\text{vc}}$-PATH-WIDTH kernel with at most $2^{\delta\sqrt{|S|}}$ vertices.

**Computing a Kernel for Tree Depth.** The last problem we consider is tree depth, and, as for path width, we prove a version of Theorem 5.3 for it. The main problem is once more that we cannot simply remove simplicial vertices. However, by the following fact of Kobayashi and Tamaki there are still enough simplicial vertices that are safe to remove:

**Fact 5.8 ([24]).** Let $G = (V, E)$ be a graph, $k \in \mathbb{N}$, and let $v \in V$ be a simplicial vertex with $1 \le |N(v)| \le k$. If every neighbor of $v$ has degree at least $k+1$, then we have $\text{td}(G) \le k$ if, and only if, $\text{td}(G[V \setminus \{v\}]) \le k$.

**Theorem 5.9.** There is a DLOGTIME-uniform family of TC$^0$-circuits that, on input of a triple (G, k, S), outputs a $p_{\text{vc}}$-TREE-DEPTH kernel with at most $O(|S|^3)$ vertices.

**Sketch of Proof.** Similar to the proofs of the Theorems 5.3 and 5.6, we identify vertices for which Fact 5.8 holds in parallel constant time. This time, we mark for every vertex $v \in S$ with $|N(v)| > k$ the $k+1$ lexicographically smallest neighbors of $v$, then the circuit marks every simplicial vertex $v \in V \setminus S$ that has at least one neighbor of degree less than $k$. ◀

**Corollary 5.10.** For every $\delta \in \mathbb{N}$ there is a DLOGTIME-uniform family of AC$^0$-circuits that, on inputs of a triple (G, k, S), outputs a $p_{\text{vc}}$-TREE-DEPTH kernel with at most $2^{\delta\sqrt{|S|}}$ vertices.

6 A Parallel Kernel for Point Line Cover

In this section we study a natural, well-known problem for which we can prove (unconditionally) that we *cannot* compute a kernel using AC$^0$-circuits while we *can* compute polynomially-sized kernels in TC$^0$. In the *p-POINT-LINE-COVER* problem we are given distinct points $p_1, \dots, p_n \in \mathbb{Z}^d$ for some dimension $d \ge 2$ and a natural number $k \in \mathbb{N}$, the question is whether we can cover all points by at most $k$ lines. This problem is NP-hard in general (even for $d=2$) and in FPT parameterized by $k$ [26]. There is a simple $k^2$ kernel, which is essentially optimal [26]: If any line covers at least $k+1$ points, remove all points on this line and reduce $k$ by one. This is safe since we would require at least $k+1$ different lines if we would not use this line. Because no set of $k+1$ points lies on the same line after the reduction, we have at most $k^2$ points left or we deal with a no-instance.

**Lemma 6.1.** There is a DLOGTIME-uniform family of TC$^0$-circuits that, on input of a dimension $d$, a set of distinct points $p_1, \dots, p_n \in \mathbb{Z}^d$, and an integer $k$, outputs a *p-POINT-LINE-COVER* kernel with at most $k^2$ points.

The lemma shows that the optimal kernel for *p-POINT-LINE-COVER* can be computed in TC$^0$ and it is natural to ask if we can do the same using a AC$^0$-circuit or, failing that, to at least compute *some* kernel using a AC$^0$-circuit (as we could for the problems in the previous sections). We answer this question in the negative, settling the complexity of the problem to para-TC$^0$:
13:10 Computing Kernels in Parallel: Lower and Upper Bounds

**Theorem 5.6.** There is a DLOGTIME-uniform family of TC$^0$-circuits that, on input of a triple (G, k, S), outputs a $p_{\text{vc}}$-PATH-WIDTH kernel with at most $O(|S|^3)$ vertices.

**Sketch of Proof.** In difference to the proof of Theorem 5.3, we must now identify the vertices for which Fact 5.5 applies in constant time. This is not trivial because of dependencies between them, but a circuit can use a two-stage marking process to find them. ◀

**Corollary 5.7.** For every $\delta \in \mathbb{N}$ there is a DLOGTIME-uniform family of AC$^0$-circuits that, on input of a triple (G, k, S), outputs a $p_{\text{vc}}$-PATH-WIDTH kernel with at most $2^{\delta\sqrt{|S|}}$ vertices.

**Computing a Kernel for Tree Depth.** The last problem we consider is tree depth, and, as for path width, we prove a version of Theorem 5.3 for it. The main problem is once more that we cannot simply remove simplicial vertices. However, by the following fact of Kobayashi and Tamaki there are still enough simplicial vertices that are safe to remove:

**Fact 5.8 ([24]).** Let $G = (V, E)$ be a graph, $k \in \mathbb{N}$, and let $v \in V$ be a simplicial vertex with $1 \le |N(v)| \le k$. If every neighbor of $v$ has degree at least $k+1$, then we have $\text{td}(G) \le k$ if, and only if, $\text{td}(G[V \setminus \{v\}]) \le k$.

**Theorem 5.9.** There is a DLOGTIME-uniform family of TC$^0$-circuits that, on input of a triple (G, k, S), outputs a $p_{\text{vc}}$-TREE-DEPTH kernel with at most $O(|S|^3)$ vertices.

**Sketch of Proof.** Similar to the proofs of the Theorems 5.3 and 5.6, we identify vertices for which Fact 5.8 holds in parallel constant time. This time, we mark for every vertex $v \in S$ with $|N(v)| > k$ the $k+1$ lexicographically smallest neighbors of $v$, then the circuit marks every simplicial vertex $v \in V \setminus S$ that has at least one neighbor of degree less than $k$. ◀

**Corollary 5.10.** For every $\delta \in \mathbb{N}$ there is a DLOGTIME-uniform family of AC$^0$-circuits that, on inputs of a triple (G, k, S), outputs a $p_{\text{vc}}$-TREE-DEPTH kernel with at most $2^{\delta\sqrt{|S|}}$ vertices.

6 A Parallel Kernel for Point Line Cover

In this section we study a natural, well-known problem for which we can prove (unconditionally) that we *cannot* compute a kernel using AC$^0$-circuits while we *can* compute polynomially-sized kernels in TC$^0$. In the *p-POINT-LINE-COVER* problem we are given distinct points $p_1, \dots, p_n \in \mathbb{Z}^d$ for some dimension $d \ge 2$ and a natural number $k \in \mathbb{N}$, the question is whether we can cover all points by at most $k$ lines. This problem is NP-hard in general (even for $d=2$) and in FPT parameterized by $k$ [26]. There is a simple $k^2$ kernel, which is essentially optimal [26]: If any line covers at least $k+1$ points, remove all points on this line and reduce $k$ by one. This is safe since we would require at least $k+1$ different lines if we would not use this line. Because no set of $k+1$ points lies on the same line after the reduction, we have at most $k^2$ points left or we deal with a no-instance.

**Lemma 6.1.** There is a DLOGTIME-uniform family of TC$^0$-circuits that, on input of a dimension $d$, a set of distinct points $p_1, \dots, p_n \in \mathbb{Z}^d$, and an integer $k$, outputs a *p-POINT-LINE-COVER* kernel with at most $k^2$ points.

The lemma shows that the optimal kernel for *p-POINT-LINE-COVER* can be computed in TC$^0$ and it is natural to ask if we can do the same using a AC$^0$-circuit or, failing that, to at least compute some kernel using a AC$^0$-circuit (as we could for the problems in the previous sections). We answer this question in the negative, settling the complexity of the problem to para-TC$^0$:
**► Lemma 6.2.** For every fixed $k$, the $k$th slice of $p$-POINT-LINE-COVER is $\mathbf{TC}^0$-complete under $\mathbf{AC}^0$-reduction.

**► Corollary 6.3.** $p$-POINT-LINE-COVER is para-$\mathbf{TC}^0$-complete under $\mathbf{AC}^0$-reduction.

Now assume there would be a uniform family of $\mathbf{AC}^0$-circuits computing a kernel of arbitrary size for $p$-POINT-LINE-COVER. Then by Theorem 2.3 the problem is in para-$\mathbf{AC}^0$, which on the other hand implies that for every fixed $k$ the problem must be in $\mathbf{AC}^0$. This contradicts Lemma 6.2 as it is known that $\mathbf{AC}^0 \subsetneq \mathbf{TC}^0$ [19]. Therefore, no family of $\mathbf{AC}^0$-circuits can compute such a kernel.

# 7 Problems for Which Computing Kernels is Inherently Sequential

As surprisingly many problems have NC-computable, in fact often even $\mathbf{AC}^0$-computable, kernelizations, we may ask which problems do not have this property. We would like to find problems for which the computation of any kernel is P-complete or, equivalently, which are FPT-complete under $\mathbf{AC}^0$- or $\mathbf{NC}^1$-reductions. While it is easy to find artificial problems with this property – such as any P-complete problem (like CVP) with the trivial parametrization $(\kappa(x) = 1)$ –, no *natural* problems that are FPT-complete for sensible parametrizations can be found in the literature. We remedy this situation in the following; but must caution the reader that in all our results the hardness of the parameterized problem for FPT stems from the fact that some slice of the problem is (essentially) a known P-complete problem. Unfortunately, it is known [18] that this “cannot be helped” since all FPT-complete problems have this property. Our main contribution here lies, thus, in the assembly of a diverse body of relevant, non-trivial FPT-problems that will serve as starting points for further studies of the limits of parameterized parallelization.

**Strong Backdoors to Satisfiability.** A *strong backdoor set* of a propositional formula $\phi$ is a set of variables such that under any assignment of these variables the resulting formula $\phi'$ belongs to a certain class of formulas [20]. In the $p$-STRONG-BACKDOOR-{$\text{HORN}$,$2\text{CNF}$}-SAT problems, we are given a formula $\phi$ and an integer $k$, the question is whether $\phi$ is satisfiable and has a strong backdoor set of size $k$ to Horn- or $2\text{CNF}$-formulas, respectively. Solving such problems is usually done in two phases: first *detect* the backdoor set and, second, *solve* the satisfiability problem of the formula for every assignment of the backdoor set. While the first part might seem harder in general, it is not from a parameterized point of view: (1) A strong backdoor set to Horn formulas is exactly a vertex cover of size $k$ in the positive primal graph of $\phi$, that is, the graph that has a vertex for each variable and an edge between any two variables appearing together positively in a clause; (2) strong backdoor sets to $2\text{CNF}$-formulas are exactly the hitting sets of the hypergraph that has the variables of $\phi$ as vertices and that connects three vertices by a hyperedge if they appear together in a clause. Since $p$- VERTEX-COVER $\in$ para-$\mathbf{AC}^0$ and also $p$-3-HITTING-SET $\in$ para-$\mathbf{AC}^0$ [2, 12], we can conclude:

**► Corollary 7.1.** There is a DLOGTIME-uniform family of para-$\mathbf{AC}^0$-circuits that, on input of a propositional formula $\phi$ and an integer $k$, either outputs a size-$k$ strong backdoor set to {$\text{Horn}$,$2\text{CNF}$}-formulas, or concludes that no such set exists.

The second step of solving $p$-STRONG-BACKDOOR-{$\text{HORN}$,$2\text{CNF}$}-SAT is to solve the satisfiability problem for $\phi$ on every assignment to the variables of the backdoor set. While we can nicely handle all assignments in parallel, checking if the formulas are satisfiable in parallel is difficult. Indeed, it is known that, under $\mathbf{AC}^0$-reductions, the satisfiability problem is NL-complete for $2\text{CNF}$-formulas, and is even P-complete for Horn formulas [1].
**► Lemma 6.2.** For every fixed $k$, the $k$th slice of $p$-POINT-LINE-COVER is $\mathbf{TC}^0$-complete under $\mathbf{AC}^0$-reduction.

**► Corollary 6.3.** $p$-POINT-LINE-COVER is para-$\mathbf{TC}^0$-complete under $\mathbf{AC}^0$-reduction.

Now assume there would be a uniform family of $\mathbf{AC}^0$-circuits computing a kernel of arbitrary size for $p$-POINT-LINE-COVER. Then by Theorem 2.3 the problem is in para-$\mathbf{AC}^0$, which on the other hand implies that for every fixed $k$ the problem must be in $\mathbf{AC}^0$. This contradicts Lemma 6.2 as it is known that $\mathbf{AC}^0 \subsetneq \mathbf{TC}^0$ [19]. Therefore, no family of $\mathbf{AC}^0$-circuits can compute such a kernel.

# 7 Problems for Which Computing Kernels is Inherently Sequential

As surprisingly many problems have NC-computable, in fact often even $\mathbf{AC}^0$-computable, kernelizations, we may ask which problems do not have this property. We would like to find problems for which the computation of any kernel is P-complete or, equivalently, which are FPT-complete under $\mathbf{AC}^0$- or $\mathbf{NC}^1$-reductions. While it is easy to find artificial problems with this property – such as any P-complete problem (like CVP) with the trivial parametrization $(\kappa(x) = 1)$ –, no *natural* problems that are FPT-complete for sensible parametrizations can be found in the literature. We remedy this situation in the following; but must caution the reader that in all our results the hardness of the parameterized problem for FPT stems from the fact that some slice of the problem is (essentially) a known P-complete problem. Unfortunately, it is known [18] that this “cannot be helped” since all FPT-complete problems have this property. Our main contribution here lies, thus, in the assembly of a diverse body of relevant, non-trivial FPT-problems that will serve as starting points for further studies of the limits of parameterized parallelization.

**Strong Backdoors to Satisfiability.** A *strong backdoor set* of a propositional formula $\phi$ is a set of variables such that under any assignment of these variables the resulting formula $\phi'$ belongs to a certain class of formulas [20]. In the $p$-STRONG-BACKDOOR-$\{\text{HORN}, 2\text{CNF}\}$-SAT problems, we are given a formula $\phi$ and an integer $k$, the question is whether $\phi$ is satisfiable and has a strong backdoor set of size $k$ to Horn- or $2\text{CNF}$-formulas, respectively. Solving such problems is usually done in two phases: first *detect* the backdoor set and, second, *solve* the satisfiability problem of the formula for every assignment of the backdoor set. While the first part might seem harder in general, it is not from a parameterized point of view: (1) A strong backdoor set to Horn formulas is exactly a vertex cover of size $k$ in the positive primal graph of $\phi$, that is, the graph that has a vertex for each variable and an edge between any two variables appearing together positively in a clause; (2) strong backdoor sets to $2\text{CNF}$-formulas are exactly the hitting sets of the hypergraph that has the variables of $\phi$ as vertices and that connects three vertices by a hyperedge if they appear together in a clause. Since $p$-VERTEX-COVER $\in$ para-$\mathbf{AC}^0$ and also $p$-3-HITTING-SET $\in$ para-$\mathbf{AC}^0$ [2, 12], we can conclude:

**► Corollary 7.1.** There is a DLOGTIME-uniform family of para-$\mathbf{AC}^0$-circuits that, on input of a propositional formula $\phi$ and an integer $k$, either outputs a size-$k$ strong backdoor set to $\{\text{Horn}, 2\text{CNF}\}$-formulas, or concludes that no such set exists.

The second step of solving $p$-STRONG-BACKDOOR-$\{\text{HORN}, 2\text{CNF}\}$-SAT is to solve the satisfiability problem for $\phi$ on every assignment to the variables of the backdoor set. While we can nicely handle all assignments in parallel, checking if the formulas are satisfiable in parallel is difficult. Indeed, it is known that, under $\mathbf{AC}^0$-reductions, the satisfiability problem is NL-complete for $2\text{CNF}$-formulas, and is even P-complete for Horn formulas [1].
**Corollary 7.2.** *p*-STRONG-BACKDOOR-2CNF-SAT is para-NL-complete under AC$^0$-reduction.

**Corollary 7.3.** *p*-STRONG-BACKDOOR-HORN-SAT is FPT-complete under AC$^0$-reduction.

The last corollary implies that there is no parallel polylogarithmic time kernelization for *p*-STRONG-BACKDOOR-HORN-SAT that produces a kernel of any size, unless NC = P.

**Mixed Integer Linear Programming.** The FPT-complete problem above is an intermediate problem between a P-complete problem (HORN-SAT) and a NP-complete problem (SAT); the transition between the problems is caused by the backdoor variables. A similar intermediate problem is known for LINEAR-PROGRAMMING (another classical P-complete problem) and its integer variant (which is NP-complete). The intermediate version of these problems is called *p*-MIXED-INTEGGER-PROGRAMMING, which asks, given a matrix $A \in \mathbb{Z}^{n \times n}$, vectors $b \in \mathbb{Z}^n$, $c \in \mathbb{Z}^n$, and integers $k$ and $w$, if there is a vector $x \in \mathbb{R}^n$ such that $Ax \leq b$, $c^T x \geq w$, and such that $x[i] \in \mathbb{Z}$ for $0 \leq i < k$. A celebrated result by Lenstra states that an instance $I$ of this problem can be solved in time $2^{O(k^3)} \cdot |I|^c$ for a suitable constant $c$, that is, the problem is in FPT. Therefore, every slice of the problem is in P and, as LINEAR-PROGRAMMING trivially reduced to it, we get that $k$-MIXED-INTEGGER-PROGRAMMING is P-complete for every $k$ (under NC$^1$-reductions [34]).

**Corollary 7.4.** *p*-MIXED-INTEGGER-PROGRAMMING is FPT-complete under NC$^1$-reductions.

**Maximum Flow with Minimum Quantities.** The last problem we review in this section is the maximum flow problem with minimum quantities: Inputs are directed graphs $G = (V, E)$ with $s, t \in V$, two weight functions $u, l: E \to \mathbb{N}$, an integer $w \in \mathbb{N}$, and a set of edges $B \subseteq E$; the question is whether there is a set $A \subseteq B$ such that in $G' = (V, E \setminus A)$ there is a valid *s*-t-flow *f* of value at least *w* that fulfills the flow conservation constraints and $l(e) \leq f(e) \leq u(e)$ for all $e \in E \setminus A$. For $B = \emptyset$ the problem boils down to classical maximum flow with lower bounds on the edges, which can be solved in polynomial time [23] and which is known to be P-hard under NC$^1$-reduction [34]. On the other hand, for $B = E$ the problem becomes NP-complete even on serial-parallel graphs [21] and it is also NP-hard to approximate the problem within any positive factor [32]. The intermediate problem between this two cases is the parameterized problem *p*-MAX-FLOW-QUANTITIES, defined as above, where the cardinality of *B* is the parameter.

**Lemma 7.5.** *p*-MAX-FLOW-QUANTITIES is FPT-complete under NC$^1$-reduction.

## 8 Conclusion and Outlook

Kernelization is a fundamental concept of parameterized complexity and we have studied its parallelization. Since traditional descriptions of kernelization algorithms are inherently sequential, we found it surprising how many parameterized problems lie in para-AC$^0$ – the smallest robust class in parallel parameterized complexity theory. We found, furthermore, that for many problems the equation “smaller circuit class = larger kernel” holds, see Table 1 for a summary of our results.

Apart from classifying more parameterized problems in the spirit of this paper, namely according to how well small kernels can be computed by small circuits, an interesting open problem is to improve any of the AC$^0$-kernelizations presented in the present paper so that they produce a *polynomially sized* kernel (which we, at best, can currently do only in TC$^0$). Perhaps even more challenging seems to be the design of a framework for proving that polynomially sized kernels for these problems *cannot* be computed in AC$^0$.
► **Corollary 7.2.** *p*-STRONG-BACKDOOR-2CNF-SAT is para-NL-complete under AC$^0$-reduction.

► **Corollary 7.3.** *p*-STRONG-BACKDOOR-HORN-SAT is FPT-complete under AC$^0$-reduction.

The last corollary implies that there is no parallel polylogarithmic time kernelization for *p*-STRONG-BACKDOOR-HORN-SAT that produces a kernel of any size, unless NC = P.

**Mixed Integer Linear Programming.** The FPT-complete problem above is an intermediate problem between a P-complete problem (HORN-SAT) and a NP-complete problem (SAT); the transition between the problems is caused by the backdoor variables. A similar intermediate problem is known for LINEAR-PROGRAMMING (another classical P-complete problem) and its integer variant (which is NP-complete). The intermediate version of these problems is called *p*-MIXED-INTEGER-PROGRAMMING, which asks, given a matrix $A \in \mathbb{Z}^{n \times n}$, vectors $b \in \mathbb{Z}^n$, $c \in \mathbb{Z}^n$, and integers $k$ and $w$, if there is a vector $x \in \mathbb{R}^n$ such that $Ax \leq b$, $c^T x \geq w$, and such that $x[i] \in \mathbb{Z}$ for $0 \leq i < k$. A celebrated result by Lenstra states that an instance $I$ of this problem can be solved in time $2^{O(k^3)} \cdot |I|^c$ for a suitable constant $c$, that is, the problem is in FPT. Therefore, every slice of the problem is in P and, as LINEAR-PROGRAMMING trivially reduced to it, we get that $k$-MIXED-INTEGER-PROGRAMMING is P-complete for every $k$ (under NC$^1$-reductions [34]).

► **Corollary 7.4.** *p*-MIXED-INTEGER-PROGRAMMING is FPT-complete under NC$^1$-reductions.

**Maximum Flow with Minimum Quantities.** The last problem we review in this section is the maximum flow problem with minimum quantities: Inputs are directed graphs $G = (V, E)$ with $s, t \in V$, two weight functions $u, l: E \to \mathbb{N}$, an integer $w \in \mathbb{N}$, and a set of edges $B \subseteq E$; the question is whether there is a set $A \subseteq B$ such that in $G' = (V, E \setminus A)$ there is a valid $s-t$-flow $f$ of value at least $w$ that fulfills the flow conservation constraints and $l(e) \leq f(e) \leq u(e)$ for all $e \in E \setminus A$. For $B = \emptyset$ the problem boils down to classical maximum flow with lower bounds on the edges, which can be solved in polynomial time [23] and which is known to be P-hard under NC$^1$-reduction [34]. On the other hand, for $B = E$ the problem becomes NP-complete even on serial-parallel graphs [21] and it is also NP-hard to approximate the problem within any positive factor [32]. The intermediate problem between this two cases is the parameterized problem *p*-MAX-FLOW-QUANTITIES, defined as above, where the cardinality of $B$ is the parameter.

► **Lemma 7.5.** *p*-MAX-FLOW-QUANTITIES is FPT-complete under NC$^1$-reduction.

## 8 Conclusion and Outlook

Kernelization is a fundamental concept of parameterized complexity and we have studied its parallelization. Since traditional descriptions of kernelization algorithms are inherently sequential, we found it surprising how many parameterized problems lie in para-AC$^0$ – the smallest robust class in parallel parameterized complexity theory. We found, furthermore, that for many problems the equation “smaller circuit class = larger kernel” holds, see Table 1 for a summary of our results.

Apart from classifying more parameterized problems in the spirit of this paper, namely according to how well small kernels can be computed by small circuits, an interesting open problem is to improve any of the AC$^0$-kernelizations presented in the present paper so that they produce a *polynomially sized kernel* (which we, at best, can currently do only in TC$^0$). Perhaps even more challenging seems to be the design of a framework for proving that polynomially sized kernels for these problems *cannot* be computed in AC$^0$.
References

1 E. Allender, M. Bauland, N. Immerman, H. Schnoor, and H. Vollmer. The complexity of satisfiability problems: Refining Schaefer's theorem. *J. Comput. Syst. Sci.*, 75(4):245-254, 2009. doi:10.1016/j.jcss.2008.11.001.

2 M. Bannach, C. Stockhusen, and T. Tantau. Fast Parallel Fixed-parameter Algorithms via Color Coding. In *Proceedings of IPEC 2015*, pages 224–235, 2015. doi:10.4230/LIPIcs.IPEC.2015.224.

3 M. Bannach and T. Tantau. Parallel Multivariate Meta-Theorems. In *Proceedings of IPEC 2016*, pages 4:1–4:17, 2016. doi:10.4230/LIPIcs.IPEC.2016.4.

4 H. L. Bodlaender. A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth. *SIAM J. Comput.*, 25(6):1305–1317, 1996. doi:10.1137/S0097539793251219.

5 H. L. Bodlaender, B. M. P. Jansen, and S. Kratsch. Kernel Bounds for Structural Parameterizations of Pathwidth. In *Proceedings of SWAT 2012*, pages 352–363, 2012. doi:10.1007/978-3-642-31155-0_31.

6 H. L. Bodlaender, B. M. P. Jansen, and S. Kratsch. Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization. *SIAM J. Discrete Math.*, 27(4):2108–2142, 2013. doi:10.1137/120903518.

7 H. L. Bodlaender and T. C. van Dijk. A Cubic Kernel for Feedback Vertex Set and Loop Cutset. *Theory Comput. Syst.*, 46(3):566–597, 2010. doi:10.1007/s00224-009-9234-2.

8 Kevin Burrage, Vladimir Estivill-Castro, Michael R. Fellows, Michael A. Langston, Shev Mac, and Frances A. Rosamond. The Undirected Feedback Vertex Set Problem Has a Poly($k$) Kernel. In *Proceedings of IWPEC 2006*, pages 192–202, 2006. doi:10.1007/11847250_18.

9 L. Cai, J. Chen, R. G. Downey, and M. R. Fellows. Advice Classes of Parameterized Tractability. *Ann. Pure Appl. Logic*, 84(1):119–138, 1997. doi:10.1016/S0168-0072(95)00020-8.

10 J. Chen, I. A. Kanj, and W. Jia. Vertex Cover: Further Observations and Further Improvements. *J. Algorithms*, 41(2):280–301, 2001. doi:10.1006/jagm.2001.1186.

11 Y. Chen and J. Flum. Some Lower Bounds in Parameterized AC$^0$. In *Proceedings of MFCS 2016*, pages 27:1–27:14, 2016. doi:10.4230/LIPIcs.MFCS.2016.27.

12 Yijia Chen, Jörg Flum, and Xuangui Huang. Slicewise Definability in First-Order Logic with Bounded Quantifier Rank. In Valentin Goranko and Mads Dam, editors, *Proceedings of CSL 2017*, volume 82, pages 19:1–19:16, 2017. doi:10.4230/LIPIcs.CSL.2017.19.

13 Stephen A. Cook and Pierre McKenzie. Problems Complete for Deterministic Logarithmic Space. *J. Algorithms*, 8(3):385–394, 1987. doi:10.1016/0196-6774(87)90018-6.

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

15 R. G. Downey and M. R. Fellows. *Fundamentals of Parameterized Complexity*. Texts in Computer Science. Springer, 2013. doi:10.1007/978-1-4471-5559-1.

16 M. Elberfeld, C. Stockhusen, and T. Tantau. On the Space and Circuit Complexity of Parameterized Problems: Classes and Completeness. *Algorithmica*, 71(3):661–701, 2015. doi:10.1007/s00453-014-9944-y.

17 S. A. Fenner, R. Gurjar, and T. Thierauf. Bipartite perfect matching is in quasi-NC. In *Proceedings of STOC 2016*, pages 754–763, 2016. doi:10.1145/2897518.2897564.

18 J. Flum and M. Grohe. *Parameterized Complexity Theory*. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. doi:10.1007/3-540-29953-X.

19 M. L. Furst, J. B. Saxe, and M. Sipser. Parity, Circuits, and the Polynomial-Time Hierarchy. *Mathematical Systems Theory*, 17(1):13–27, 1984. doi:10.1007/BF01744431.
References

1 E. Allender, M. Bauland, N. Immerman, H. Schnoor, and H. Vollmer. The complexity of satisfiability problems: Refining Schaefer's theorem. *J. Comput. Syst. Sci.*, 75(4):245-254, 2009. doi:10.1016/j.jcss.2008.11.001.

2 M. Bannach, C. Stockhusen, and T. Tantau. Fast Parallel Fixed-parameter Algorithms via Color Coding. In *Proceedings of IPEC 2015*, pages 224–235, 2015. doi:10.4230/LIPIcs.IPEC.2015.224.

3 M. Bannach and T. Tantau. Parallel Multivariate Meta-Theorems. In *Proceedings of IPEC 2016*, pages 4:1–4:17, 2016. doi:10.4230/LIPIcs.IPEC.2016.4.

4 H. L. Bodlaender. A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth. *SIAM J. Comput.*, 25(6):1305–1317, 1996. doi:10.1137/S0097539793251219.

5 H. L. Bodlaender, B. M. P. Jansen, and S. Kratsch. Kernel Bounds for Structural Parameterizations of Pathwidth. In *Proceedings of SWAT 2012*, pages 352–363, 2012. doi:10.1007/978-3-642-31155-0_31.

6 H. L. Bodlaender, B. M. P. Jansen, and S. Kratsch. Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization. *SIAM J. Discrete Math.*, 27(4):2108–2142, 2013. doi:10.1137/120903518.

7 H. L. Bodlaender and T. C. van Dijk. A Cubic Kernel for Feedback Vertex Set and Loop Cutset. *Theory Comput. Syst.*, 46(3):566–597, 2010. doi:10.1007/s00224-009-9234-2.

8 Kevin Burrage, Vladimir Estivill-Castro, Michael R. Fellows, Michael A. Langston, Shev Mac, and Frances A. Rosamond. The Undirected Feedback Vertex Set Problem Has a Poly($k$) Kernel. In *Proceedings of IWPEC 2006*, pages 192–202, 2006. doi:10.1007/11847250_18.

9 L. Cai, J. Chen, R. G. Downey, and M. R. Fellows. Advice Classes of Parameterized Tractability. *Ann. Pure Appl. Logic*, 84(1):119–138, 1997. doi:10.1016/S0168-0072(95)00020-8.

10 J. Chen, I. A. Kanj, and W. Jia. Vertex Cover: Further Observations and Further Improvements. *J. Algorithms*, 41(2):280–301, 2001. doi:10.1006/jagm.2001.1186.

11 Y. Chen and J. Flum. Some Lower Bounds in Parameterized AC$^0$. In *Proceedings of MFCS 2016*, pages 27:1–27:14, 2016. doi:10.4230/LIPIcs.MFCS.2016.27.

12 Yijia Chen, Jörg Flum, and Xuangui Huang. Slicewise Definability in First-Order Logic with Bounded Quantifier Rank. In Valentin Goranko and Mads Dam, editors, *Proceedings of CSL 2017*, volume 82, pages 19:1–19:16, 2017. doi:10.4230/LIPIcs.CSL.2017.19.

13 Stephen A. Cook and Pierre McKenzie. Problems Complete for Deterministic Logarithmic Space. *J. Algorithms*, 8(3):385–394, 1987. doi:10.1016/0196-6774(87)90018-6.

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

15 R. G. Downey and M. R. Fellows. *Fundamentals of Parameterized Complexity*. Texts in Computer Science. Springer, 2013. doi:10.1007/978-1-4471-5559-1.

16 M. Elberfeld, C. Stockhusen, and T. Tantau. On the Space and Circuit Complexity of Parameterized Problems: Classes and Completeness. *Algorithmica*, 71(3):661–701, 2015. doi:10.1007/s00453-014-9944-y.

17 S. A. Fenner, R. Gurjar, and T. Thierauf. Bipartite perfect matching is in quasi-NC. In *Proceedings of STOC 2016*, pages 754–763, 2016. doi:10.1145/2897518.2897564.

18 J. Flum and M. Grohe. *Parameterized Complexity Theory*. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. doi:10.1007/3-540-29953-X.

19 M. L. Furst, J. B. Saxe, and M. Sipser. Parity, Circuits, and the Polynomial-Time Hierarchy. *Mathematical Systems Theory*, 17(1):13–27, 1984. doi:10.1007/BF01744431.
20 S. Gaspers and S. Szeider. Backdoors to Satisfaction. In H.L. Bodlaender, R. Downey, F. V. Fomin, and D. Marx, editors, *The Multivariate Algorithmic Revolution and Beyond*, pages 287–317. Springer, 2012. doi:10.1007/978-3-642-30891-8_15.

21 D. Haugland, M. Eleyat, and M. Lie Hetland. The Maximum Flow Problem with Minimum Lot Sizes. In *Proceedings of ICCL 2011*, pages 170–182, 2011. doi:10.1007/978-3-642-24264-9_13.

22 Yoichi Iwata. Linear-Time Kernelization for Feedback Vertex Set. In *Proceedings of ICALP 2017*, pages 68:1–68:14, 2017. doi:10.4230/LIPIcs.ICALP.2017.68.

23 Jon M. Kleinberg and Éva Tardos. *Algorithm design*. Addison-Wesley, 2006.

24 Y. Kobayashi and H. Tamaki. Tree-depth Parameterized by Vertex Cover Number. In *Proceedings of IPEC 2016*, pages 18:1–18:11, 2016. doi:10.4230/LIPIcs.IPEC.2016.18.

25 D. König. Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. *Mathematische Annalen*, 77(4):453–465, 1916. doi:10.1007/BF01456961.

26 S. Kratsch, G. Philip, and S. Ray. Point Line Cover: The Easy Kernel is Essentially Tight. *ACM Trans. Algorithms*, 12(3):40:1–40:16, 2016. doi:10.1145/2832912.

27 M. Lampis. A kernel of order $2k - c \log k$ for vertex cover. *Inf. Process. Lett.*, 111(23-24):1089–1091, 2011. doi:10.1016/j.ipl.2011.09.003.

28 K. Mulmuley, U. V. Vazirani, and V. V. Vazirani. Matching is as easy as matrix inversion. *Combinatorica*, 7(1):105–113, 1987. doi:10.1007/BF02579206.

29 G. L. Nemhauser and L. E. Trotter Jr. Properties of vertex packing and independence system polyhedra. *Math. Program.*, 6(1):48–61, 1974. doi:10.1007/BF01580222.

30 I. Newman, P. Ragde, and A. Wigderson. Perfect Hashing, Graph Entropy, and Circuit Complexity. In *Proceedings of STC 1990*, pages 91–99. IEEE Computer Society, Los Alamitos, California, 1990. doi:10.1109/SCT.1990.113958.

31 A. Soleimanfallah and A. Yeo. A kernel of order $2k - c$ for Vertex Cover. *Discrete Mathematics*, 311(10-11):892–895, 2011. doi:10.1016/j.disc.2011.02.014.

32 Clemens Thielen and Stephan Westphal. Complexity and approximability of the maximum flow problem with minimum quantities. *Networks*, 62(2):125–131, 2013. doi:10.1002/net.21502.

33 Stéphan Thomassé. A $4k^2$ kernel for feedback vertex set. *ACM Trans. Algorithms*, 6(2):32:1–32:8, 2010. doi:10.1145/1721837.1721848.

34 Jacobo Toran. P-completeness. In Alan Gibbons and Paul Spirakis, editors, *Lectures on parallel computation*, pages 177–196. Cambridge University Press, 1993.
20 S. Gaspers and S. Szeider. Backdoors to Satisfaction. In H.L. Bodlaender, R. Downey, F. V. Fomin, and D. Marx, editors, *The Multivariate Algorithmic Revolution and Beyond*, pages 287–317. Springer, 2012. doi:10.1007/978-3-642-30891-8_15.

21 D. Haugland, M. Eleyat, and M. Lie Hetland. The Maximum Flow Problem with Minimum Lot Sizes. In *Proceedings of ICCL 2011*, pages 170–182, 2011. doi:10.1007/978-3-642-24264-9_13.

22 Yoichi Iwata. Linear-Time Kernelization for Feedback Vertex Set. In *Proceedings of ICALP 2017*, pages 68:1–68:14, 2017. doi:10.4230/LIPIcs.ICALP.2017.68.

23 Jon M. Kleinberg and Éva Tardos. *Algorithm design*. Addison-Wesley, 2006.

24 Y. Kobayashi and H. Tamaki. Tree-depth Parameterized by Vertex Cover Number. In *Proceedings of IPEC 2016*, pages 18:1–18:11, 2016. doi:10.4230/LIPIcs.IPEC.2016.18.

25 D. König. Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. *Mathematische Annalen*, 77(4):453–465, 1916. doi:10.1007/BF01456961.

26 S. Kratsch, G. Philip, and S. Ray. Point Line Cover: The Easy Kernel is Essentially Tight. *ACM Trans. Algorithms*, 12(3):40:1–40:16, 2016. doi:10.1145/2832912.

27 M. Lampis. A kernel of order $2k - c \log k$ for vertex cover. *Inf. Process. Lett.*, 111(23-24):1089–1091, 2011. doi:10.1016/j.ipl.2011.09.003.

28 K. Mulmuley, U. V. Vazirani, and V. V. Vazirani. Matching is as easy as matrix inversion. *Combinatorica*, 7(1):105–113, 1987. doi:10.1007/BF02579206.

29 G. L. Nemhauser and L. E. Trotter Jr. Properties of vertex packing and independence system polyhedra. *Math. Program.*, 6(1):48–61, 1974. doi:10.1007/BF01580222.

30 I. Newman, P. Ragde, and A. Wigderson. Perfect Hashing, Graph Entropy, and Circuit Complexity. In *Proceedings of STC 1990*, pages 91–99. IEEE Computer Society, Los Alamitos, California, 1990. doi:10.1109/SCT.1990.113958.

31 A. Soleimanfallah and A. Yeo. A kernel of order $2k - c$ for Vertex Cover. *Discrete Mathematics*, 311(10-11):892–895, 2011. doi:10.1016/j.disc.2011.02.014.

32 Clemens Thielen and Stephan Westphal. Complexity and approximability of the maximum flow problem with minimum quantities. *Networks*, 62(2):125–131, 2013. doi:10.1002/net.21502.

33 Stéphan Thomassé. A $4k^2$ kernel for feedback vertex set. *ACM Trans. Algorithms*, 6(2):32:1–32:8, 2010. doi:10.1145/1721837.1721848.

34 Jacobo Toran. P-completeness. In Alan Gibbons and Paul Spirakis, editors, *Lectures on parallel computation*, pages 177–196. Cambridge University Press, 1993.
# Exploring the Kernelization Borders for Hitting Cycles

**Akanksha Agrawal**

Institute of Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI),
Budapest, Hungary
akanksha@sztaki.mta.hu

**Pallavi Jain**

Institute of Mathematical Sciences, HBNI, Chennai, India
pallavij@imsc.res.in

**Lawqueen Kanesh**

Institute of Mathematical Sciences, HBNI, Chennai, India
lawqueen@imsc.res.in

**Pranabendu Misra**

University of Bergen, Bergen, Norway
Pranabendu.Misra@uib.no

**Saket Saurabh**

Institute of Mathematical Sciences, HBNI, Chennai, India
saket@imsc.res.in

## Abstract

A generalization of classical cycle hitting problems, called conflict version of the problem, is defined as follows. An input is undirected graphs $G$ and $H$ on the same vertex set, and a positive integer $k$, and the objective is to decide whether there exists a vertex subset $X \subseteq V(G)$ such that it intersects all desired “cycles” (all cycles or all odd cycles or all even cycles) and $X$ is an independent set in $H$. In this paper we study the conflict version of classical FEEDBACK VERTEX SET, and ODD CYCLE TRANSVERSAL problems, from the view point of kernelization complexity. In particular, we obtain the following results, when the conflict graph $H$ belongs to the family of $d$-degenerate graphs.

1. CF-FVS admits a $O(k^{O(d)})$ kernel.

2. CF-OCT does not admit polynomial kernel (even when $H$ is 1-degenerate), unless $NP \subseteq \text{coNP}$, $\text{poly}$. For our kernelization algorithm we exploit ideas developed for designing polynomial kernels for the classical FEEDBACK VERTEX SET problem, as well as, devise new reduction rules that exploit degeneracy crucially. Our main conceptual contribution here is the notion of “$k$-independence preserver”. Informally, it is a set of “important” vertices for a given subset $X \subseteq V(H)$, that is enough to capture the independent set property in $H$. We show that for $d$-degenerate graph independence preserver of size $k^{O(d)}$ exists, and can be used in designing polynomial kernel.

**2012 ACM Subject Classification** Theory of computation → Parameterized complexity and exact algorithms

**Keywords and phrases** Parameterized Complexity, Kernelization, Conflict-free problems, Feedback Vertex Set, Even Cycle Transversal, Odd Cycle Transversal

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

**Funding** This research has received funding from the European Research Council under ERC grant no. 306992 PARAPPROX, ERC grant no. 715744 PaPaALG and ERC grant no. 725978 SYSTEMATIC-GRAPH, and DST, India for SERB-NPDF fellowship [PDF/2016/003508].

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

© A. Agrawal, and P. Jain, and L. Kanesh, and P. Misra, and S. Saurabh; 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. 14; pp. 14:1–14:14

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

LIPICS

Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
# Exploring the Kernelization Borders for Hitting Cycles

**Akanksha Agrawal**

Institute of Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI),
Budapest, Hungary
akanksha@sztaki.mta.hu

**Pallavi Jain**

Institute of Mathematical Sciences, HBNI, Chennai, India
pallavij@imsc.res.in

**Lawqueen Kanesh**

Institute of Mathematical Sciences, HBNI, Chennai, India
lawqueen@imsc.res.in

**Pranabendu Misra**

University of Bergen, Bergen, Norway
Pranabendu.Misra@uib.no

**Saket Saurabh**

Institute of Mathematical Sciences, HBNI, Chennai, India
saket@imsc.res.in

**Abstract**

A generalization of classical cycle hitting problems, called conflict version of the problem, is defined as follows. An input is undirected graphs $G$ and $H$ on the same vertex set, and a positive integer $k$, and the objective is to decide whether there exists a vertex subset $X \subseteq V(G)$ such that it intersects all desired “cycles” (all cycles or all odd cycles or all even cycles) and $X$ is an independent set in $H$. In this paper we study the conflict version of classical FEEDBACK VERTEX SET, and ODD CYCLE TRANSVERSAL problems, from the view point of kernelization complexity. In particular, we obtain the following results, when the conflict graph $H$ belongs to the family of $d$-degenerate graphs.

1. CF-FVS admits a $O(k^{O(d)})$ kernel.

2. CF-OCT does not admit polynomial kernel (even when $H$ is 1-degenerate), unless $NP \subseteq \text{coNP}$, $\text{poly}$. For our kernelization algorithm we exploit ideas developed for designing polynomial kernels for the classical FEEDBACK VERTEX SET problem, as well as, devise new reduction rules that exploit degeneracy crucially. Our main conceptual contribution here is the notion of “$k$-independence preserver”. Informally, it is a set of “important” vertices for a given subset $X \subseteq V(H)$, that is enough to capture the independent set property in $H$. We show that for $d$-degenerate graph independence preserver of size $k^{O(d)}$ exists, and can be used in designing polynomial kernel.

**2012 ACM Subject Classification** Theory of computation → Parameterized complexity and exact algorithms

**Keywords and phrases** Parameterized Complexity, Kernelization, Conflict-free problems, Feedback Vertex Set, Even Cycle Transversal, Odd Cycle Transversal

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

**Funding** This research has received funding from the European Research Council under ERC grant no. 306992 PARAPPROX, ERC grant no. 715744 PaPaALG and ERC grant no. 725978 SYSTEMATIC-GRAPH, and DST, India for SERB-NPDF fellowship [PDF/2016/003508].

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

© A. Agrawal, and P. Jain, and L. Kanesh, and P. Misra, and S. Saurabh; 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. 14; pp. 14:1–14:14

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

LIPICS

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

Reducing the input data, in polynomial time, without altering the answer is one of the
popular ways in dealing with intractable problems in practice. While such polynomial
time heuristics can not solve NP-hard problems exactly, they work well on input instances
arising in real-life. It is a challenging task to assess the effectiveness of such heuristics
theoretically. Parameterized complexity, via kernelization, provides a natural way to quantify
the performance of such algorithms. In parameterized complexity each problem instance
comes with a parameter *k* and the parameterized problem is said to admit a *polynomial
kernel* if there is a polynomial time algorithm, called a *kernelization* algorithm, that reduces
the input instance down to an instance with size bounded by a polynomial *p*(*k*) in *k*, while
preserving the answer. The reduced instance is called a *p*(*k*) kernel for the problem.

The quest for designing polynomial kernels for “hitting cycles” in undirected graphs has
played significant role in advancing the field of polynomial time pre-processing – kernelization.
Hitting all cycles, odd cycles and even cycles correspond to well studied problems of FEEDBACK
VERTEX SET (FVS), ODD CYCLE TRANSVERSAL (OCT) and EVEN CYCLE TRANSVERSAL
(ECT), respectively. Alternatively, FVS, OCT and ECT correspond to deleting vertices such
that the resulting graph is a forest, a bipartite graph and an odd cactus graph, respectively.
All these problems, FVS, OCT, and ECT, have been extensively studied in parameterized
algorithms and kernelization. The earliest known FPT algorithms for FVS go back to the
late 80’s and the early 90’s [4, 11] and used the seminal Graph Minor Theory of Robertson
and Seymour. On the other hand the parameterized complexity of OCT was open for long
time. Only, in 2003, Reed et al. [24] gave a 3^k n^O(1) time algorithm for OCT. This is also
the paper which introduced the method of iterative compression to the field of parameterized
complexity. However, the existence of polynomial kernel, for FVS and OCT were open
questions for long time. For FVS, Burrage et al. [7] resolved the question in the affirmative
by designing a kernel of size O(k^{11}). Later, Bodlaender [5] reduced the kernel size to O(k^3),
and finally Thomassé [25] designed a kernel of size O(k^2). The kernel of Thomassé [25] is
best possible under a well known complexity theory hypothesis. It is important to emphasize
that [25] popularized the method of expansion lemma, one of the most prominent approach
in designing polynomial kernels. While, the kernelization complexity of FVS was settled
in 2006, it took another 6 years and a completely new methodology to design polynomial
kernel for OCT. Kratsch and Wahlström [16] resolved the question of existence of polynomial
kernel for OCT by designing a randomized kernel of size O(k^{4.5}) using matroid theory.<fnref n="1" /> As
a counterpart to OCT, Misra et al. [20] studied ECT and designed an O(k^3) kernel.

Fruitful and productive research on FVS and OCT have led to the study of several
variants and generalizations of FVS and OCT. Some of these admit polynomial kernels
and for some one can show that none can exist, unless some unlikely collapse happens in
complexity theory. In this paper we study the following generalization of FVS, and OCT,
from the view-point of kernelization complexity.

CONFLICT FREE FEEDBACK VERTEX SET (CF-FVS)

Parameter: *k*

**Input:** An undirected graph *G*, a conflict graph *H* on vertex set *V*(*G*) and a non-negative integer *k*.

**Question:** Does there exist $S \subseteq V(G)$, such that $|S| \le k$, $G-S$ is a forest and $H[S]$ is edgeless?

<footnote n="1">¹ This foundational paper has been awarded the Nerode Prize for 2018.</footnote>
# 1 Introduction

Reducing the input data, in polynomial time, without altering the answer is one of the popular ways in dealing with intractable problems in practice. While such polynomial time heuristics can not solve NP-hard problems exactly, they work well on input instances arising in real-life. It is a challenging task to assess the effectiveness of such heuristics theoretically. Parameterized complexity, via kernelization, provides a natural way to quantify the performance of such algorithms. In parameterized complexity each problem instance comes with a parameter *k* and the parameterized problem is said to admit a *polynomial kernel* if there is a polynomial time algorithm, called a *kernelization* algorithm, that reduces the input instance down to an instance with size bounded by a polynomial *p*(*k*) in *k*, while preserving the answer. The reduced instance is called a *p*(*k*) kernel for the problem.

The quest for designing polynomial kernels for “hitting cycles” in undirected graphs has played significant role in advancing the field of polynomial time pre-processing – kernelization. Hitting all cycles, odd cycles and even cycles correspond to well studied problems of FEEDBACK VERTEX SET (FVS), ODD CYCLE TRANSVERSAL (OCT) and EVEN CYCLE TRANSVERSAL (ECT), respectively. Alternatively, FVS, OCT and ECT correspond to deleting vertices such that the resulting graph is a forest, a bipartite graph and an odd cactus graph, respectively. All these problems, FVS, OCT, and ECT, have been extensively studied in parameterized algorithms and kernelization. The earliest known FPT algorithms for FVS go back to the late 80’s and the early 90’s [4, 11] and used the seminal Graph Minor Theory of Robertson and Seymour. On the other hand the parameterized complexity of OCT was open for long time. Only, in 2003, Reed et al. [24] gave a $3^k n^{O(1)}$ time algorithm for OCT. This is also the paper which introduced the method of iterative compression to the field of parameterized complexity. However, the existence of polynomial kernel, for FVS and OCT were open questions for long time. For FVS, Burrage et al. [7] resolved the question in the affirmative by designing a kernel of size $\mathcal{O}(k^{11})$. Later, Bodlaender [5] reduced the kernel size to $\mathcal{O}(k^3)$, and finally Thomassé [25] designed a kernel of size $\mathcal{O}(k^2)$. The kernel of Thomassé [25] is best possible under a well known complexity theory hypothesis. It is important to emphasize that [25] popularized the method of expansion lemma, one of the most prominent approach in designing polynomial kernels. While, the kernelization complexity of FVS was settled in 2006, it took another 6 years and a completely new methodology to design polynomial kernel for OCT. Kratsch and Wahlström [16] resolved the question of existence of polynomial kernel for OCT by designing a randomized kernel of size $\mathcal{O}(k^{4.5})$ using matroid theory.<fnref n="1" /> As a counterpart to OCT, Misra et al. [20] studied ECT and designed an $\mathcal{O}(k^3)$ kernel.

Fruitful and productive research on FVS and OCT have led to the study of several variants and generalizations of FVS and OCT. Some of these admit polynomial kernels and for some one can show that none can exist, unless some unlikely collapse happens in complexity theory. In this paper we study the following generalization of FVS, and OCT, from the view-point of kernelization complexity.

**CONFLICT FREE FEEDBACK VERTEX SET (CF-FVS)**

**Parameter:** *k*

**Input:** An undirected graph $G$, a conflict graph $H$ on vertex set $V(G)$ and a non-negative integer $k$.

**Question:** Does there exist $S \subseteq V(G)$, such that $|S| \le k$, $G-S$ is a forest and $H[S]$ is edgeless?

<footnote n="1">¹ This foundational paper has been awarded the Nerode Prize for 2018.</footnote>
One can similarly define CONFLICT FREE ODD CYCLE TRANSVERSAL (CF-OCT).

**Motivation.** On the outset, a natural thought is “*why does one care*” about such an esoteric (or obscure) problem. We thought *exactly the same* in the beginning, till we realized the modeling power the problem provides and the rich set of questions one can ask. In the course of this paragraph we will try to explain this. First observe that, if one wants to model “independent” version of these problems (where the solution is suppose to be an independent set), then one takes conflict graph to be same as the input graph. An astute reader will figure out that the problem as stated above is W[1]-hard – a simple reduction from MULTICOLOR INDEPENDENT SET with each color class being modeled as cycle and the conflict graph being the input graph. Thus, a natural question is: *when does the problem become FPT?* To state the question formally, let $\mathcal{F}$ and $\mathcal{G}$ be two families of graphs. Then, $(\mathcal{G}, \mathcal{F})$-CF-FVS is same problem as CF-FVS, but the input graph $\mathcal{G}$ and the conflict graph $\mathcal{H}$ are restricted to belong to $\mathcal{G}$ and $\mathcal{H}$, respectively. It immediately brings several questions: (a) for which pairs of families the problem is FPT; (b) can we obtain some kind of dichotomy results; and (c) what could we say about the kernelization complexity of the problem. We believe that answering these questions for basic problems such as FVS, OCT, and DOMINATING SET will extend both the tractability as well as intractability tools in parameterized complexity and led to some fruitful and rewarding research. It is worth to note that initially we were inspired to define these problems by similar problems in computational geometry. See related results for more on this.

**Our Results and Methods.** A graph $G$ is called $d$-degenerate if every subgraph of $G$ has a vertex of degree at most $d$. For a fixed positive integer $d$, let $\mathcal{D}_d$ denote the set of graphs of degeneracy at most $d$. In this paper we study the $(\star, \mathcal{D}_d)$-CF-FVS ($\mathcal{D}_d$-CF-FVS) problem. The symbol $\star$ denotes that the input graph $G$ is arbitrary. One can similarly define $\mathcal{D}_d$-CF-OCT. In fact, we study, CF-OCT for a very restricted family of conflict graphs, a family of disjoint union of paths of length at most three and at most two star graphs. We denote this family as $\mathcal{P}_{\le 3}^{**}$ and this variant of CF-OCT as $\mathcal{P}_{\le 3}^{**}$-CF-OCT. Starting point of our research is the recent study of Jain et al. [14], who studied conflict-free graph modification problems in the realm of parameterized complexity. As a part of their study they gave FPT algorithms for $\mathcal{D}_d$-CF-FVS, $\mathcal{D}_d$-CF-OCT and $\mathcal{D}_d$-CF-ECT using the independence covering families [17]. Their results also imply similar FPT algorithm when the conflict graph belongs to nowhere dense graphs. In this paper we focus on the kernelization complexity of $\mathcal{D}_d$-CF-FVS, and $\mathcal{P}_{\le 3}^{**}$-CF-OCT obtain the following results.

1. $\mathcal{D}_d$-CF-FVS admits a $\mathcal{O}(k^{\mathcal{O}(d)})$ kernel.

2. $\mathcal{P}_{\le 3}^{**}$-CF-OCT does not admit polynomial kernel, unless $\mathrm{NP} \subseteq \mathrm{coNP}_{\mathrm{poly}}$.

Note that $\mathcal{D}_0$ denotes edgeless graphs and hence $\mathcal{D}_0$-CF-FVS, and $\mathcal{D}_0$-CF-OCT are essentially FVS, and OCT, respectively. Thus, any polynomial kernel for $\mathcal{D}_d$-CF-FVS, and $\mathcal{P}_{\le 3}^{**}$-CF-OCT, must generalize the known kernels for these problems. We remark that the above result imply that CF-FVS admits polynomial kernels, when the conflict graph belong to several well studied graph families, such as planar graphs, graphs of bounded degree, graphs of bounded treewidth, graphs excluding some fixed graph as a minor, a topological minor and graphs of bounded expansion etc. (all these graphs classes have bounded degeneracy).

**Strategy for CF-FVS.** Our kernelization algorithm for CF-FVS consists of the following two steps. The first step of our kernelization algorithm is a structural decomposition of the
One can similarly define CONFLICT FREE ODD CYCLE TRANSVERSAL (CF-OCT).

**Motivation.** On the outset, a natural thought is “*why does one care*” about such an esoteric (or obscure) problem. We thought *exactly the same* in the beginning, till we realized the modeling power the problem provides and the rich set of questions one can ask. In the course of this paragraph we will try to explain this. First observe that, if one wants to model “independent” version of these problems (where the solution is suppose to be an independent set), then one takes conflict graph to be same as the input graph. An astute reader will figure out that the problem as stated above is W[1]-hard – a simple reduction from MULTICOLOR INDEPENDENT SET with each color class being modeled as cycle and the conflict graph being the input graph. Thus, a natural question is: *when does the problem become FPT?* To state the question formally, let $\mathcal{F}$ and $\mathcal{G}$ be two families of graphs. Then, $(\mathcal{G}, \mathcal{F})$-CF-FVS is same problem as CF-FVS, but the input graph $\mathcal{G}$ and the conflict graph $\mathcal{H}$ are restricted to belong to $\mathcal{G}$ and $\mathcal{H}$, respectively. It immediately brings several questions: (a) for which pairs of families the problem is FPT; (b) can we obtain some kind of dichotomy results; and (c) what could we say about the kernelization complexity of the problem. We believe that answering these questions for basic problems such as FVS, OCT, and DOMINATING SET will extend both the tractability as well as intractability tools in parameterized complexity and led to some fruitful and rewarding research. It is worth to note that initially we were inspired to define these problems by similar problems in computational geometry. See related results for more on this.

**Our Results and Methods.** A graph $G$ is called $d$-degenerate if every subgraph of $G$ has a vertex of degree at most $d$. For a fixed positive integer $d$, let $\mathcal{D}_d$ denote the set of graphs of degeneracy at most $d$. In this paper we study the $(\star, \mathcal{D}_d)$-CF-FVS ($\mathcal{D}_d$-CF-FVS) problem. The symbol $\star$ denotes that the input graph $G$ is arbitrary. One can similarly define $\mathcal{D}_d$-CF-OCT. In fact, we study, CF-OCT for a very restricted family of conflict graphs, a family of disjoint union of paths of length at most three and at most two star graphs. We denote this family as $\mathcal{P}_{\le 3}^{**}$ and this variant of CF-OCT as $\mathcal{P}_{\le 3}^{**}$-CF-OCT. Starting point of our research is the recent study of Jain et al. [14], who studied conflict-free graph modification problems in the realm of parameterized complexity. As a part of their study they gave FPT algorithms for $\mathcal{D}_d$-CF-FVS, $\mathcal{D}_d$-CF-OCT and $\mathcal{D}_d$-CF-ECT using the independence covering families [17]. Their results also imply similar FPT algorithm when the conflict graph belongs to nowhere dense graphs. In this paper we focus on the kernelization complexity of $\mathcal{D}_d$-CF-FVS, and $\mathcal{P}_{\le 3}^{**}$-CF-OCT obtain the following results.

1. $\mathcal{D}_d$-CF-FVS admits a $\mathcal{O}(k^{\mathcal{O}(d)})$ kernel.

2. $\mathcal{P}_{\le 3}^{**}$-CF-OCT does not admit polynomial kernel, unless $\mathrm{NP} \subseteq \mathrm{coNP}_{\mathrm{poly}}$.

Note that $\mathcal{D}_0$ denotes edgeless graphs and hence $\mathcal{D}_0$-CF-FVS, and $\mathcal{D}_0$-CF-OCT are essentially FVS, and OCT, respectively. Thus, any polynomial kernel for $\mathcal{D}_d$-CF-FVS, and $\mathcal{P}_{\le 3}^{**}$-CF-OCT, must generalize the known kernels for these problems. We remark that the above result imply that CF-FVS admits polynomial kernels, when the conflict graph belong to several well studied graph families, such as planar graphs, graphs of bounded degree, graphs of bounded treewidth, graphs excluding some fixed graph as a minor, a topological minor and graphs of bounded expansion etc. (all these graphs classes have bounded degeneracy).

**Strategy for CF-FVS.** Our kernelization algorithm for CF-FVS consists of the following two steps. The first step of our kernelization algorithm is a structural decomposition of the
14:4 Exploring the Kernelization Borders for Hitting Cycles

input graph $G$. This does not depend on the conflict graph $H$. In this phase of the algorithm,
given an instance $(G, H, k)$ of CF-FVS we obtain an equivalent instance $(G', H', k')$ of
CF-FVS such that:

- The minimum degree of $G'$ is at least 2.

- The number of vertices of degree at least 3 in $G'$ is upper bounded by $O(k^3)$. Let $V_{\ge 3}$ denote the set of vertices of degree at least 3 in $G'$.

- The number of maximal degree 2 paths in $G'$ is upper bounded by $O(k^3)$. That is, $G' - V_{\ge 3}$ consists of $O(k^3)$ connected components where each component is a path.

We obtain this structural decomposition using reduction rules inspired by the quadratic kernel for FVS [25]. As stated earlier, this step can be performed for any graph $H$. Thus the problem reduces to designing reduction rules that bound the number of vertices of degree 2 in the reduced graph. Note that we can not do this for any arbitrary graph $H$ as the problem is W[1]-hard. Once the decomposition is obtained we can not use the known reduction rules for FVS. This is for a simple reason that in $G'$ the only vertices that are not bounded have degree exactly 2 in $G'$. On the other hand for FVS we can do simple “short-circuit” of degree 2 vertices (remove the vertex and add an edge between its two neighbors) and assume that there is no vertices of degree two in the graph. So our actual contributions start here.

The second step of our kernelization algorithm bounds the degree two vertices in the graph $G'$. Here we must use the properties of the graph $H$. We propose new reduction rules for bounding degree two vertices, when $H$ belongs to the family of $d$-degenerate graphs. Towards this we use the notion of $d$-degeneracy sequence, which is an ordering of the vertices in $H$ such that any vertex can have at most $d$ forward neighbors. This is used in designing a marking scheme for the degree two vertices. Broadly speaking our marking scheme associates a set with every vertex $v$. Here, set consists of “paths and cycles of $G'$ on which the forward neighbors of $v$ are”. Two vertices are called similar if their associated sets are same. We show that if some vertex is not marked then we can safely contract this vertex to one of its neighbors. We then upper bound the degree two vertices by $O(k^{O(d)}d^{O(d)})$, and thus obtain a kernel of this size for $\mathcal{D}_d$-CF-FVS.

At the heart of our kernelization algorithm is a combinatorial tool of “*k*-independence
preserver”. Informally, it is a set of “important” vertices for a given subset $X \subseteq V(H)$, that
is enough to capture the independent set property in $H$. We show that for *d*-degenerate
graph independence preserver of size $k^{O(d)}$ exists, and can be used in designing polynomial
kernel. This is our main conceptual contribution.

**Strategy for CF-OCT.** The kernelization lower bound is obtained by the method of cross-composition [6]. We first define a conflict version of the *s*-*t*-CUT problem, where *H* belongs to $\mathcal{P}_{\le 3}^{**}$. Then, we show that the problem is NP-hard and cross composes to itself. Finally, we give a parameter preserving reduction from the problem to $\mathcal{P}_{\le 3}^{**}$-CF-OCT, and obtain the desired kernel lower bound.

**Related Work.** In the past, the conflict free versions of some classical problems have been studied, e.g. for **SHORTEST PATH** [15], **MAXIMUM FLOW** [21, 22], **KNAPSACK** [23], **BIN PACKING** [12], **SCHEDULING** [13], **MAXIMUM MATCHING** and **MINIMUM WEIGHT SPANNING TREE** [10, 9]. It is interesting to note that some of these problems are **NP**-hard even when their non-conflicting version is polynomial time solvable. The study of conflict free problems has also been recently initiated in computational geometry motivated by various applications (see [1, 2, 3]).
14:4 Exploring the Kernelization Borders for Hitting Cycles

input graph $G$. This does not depend on the conflict graph $H$. In this phase of the algorithm,
given an instance $(G, H, k)$ of CF-FVS we obtain an equivalent instance $(G', H', k')$ of
CF-FVS such that:

■ The minimum degree of $G'$ is at least 2.

- The number of vertices of degree at least 3 in $G'$ is upper bounded by $O(k^3)$. Let $V_{\ge 3}$ denote the set of vertices of degree at least 3 in $G'$.

- The number of maximal degree 2 paths in $G'$ is upper bounded by $O(k^3)$. That is, $G' - V_{\ge 3}$ consists of $O(k^3)$ connected components where each component is a path.

We obtain this structural decomposition using reduction rules inspired by the quadratic kernel for FVS [25]. As stated earlier, this step can be performed for any graph $H$. Thus the problem reduces to designing reduction rules that bound the number of vertices of degree 2 in the reduced graph. Note that we can not do this for any arbitrary graph $H$ as the problem is W[1]-hard. Once the decomposition is obtained we can not use the known reduction rules for FVS. This is for a simple reason that in $G'$ the only vertices that are not bounded have degree exactly 2 in $G'$. On the other hand for FVS we can do simple “short-circuit” of degree 2 vertices (remove the vertex and add an edge between its two neighbors) and assume that there is no vertices of degree two in the graph. So our actual contributions start here.

The second step of our kernelization algorithm bounds the degree two vertices in the
graph $G'$. Here we must use the properties of the graph $H$. We propose new reduction
rules for bounding degree two vertices, when $H$ belongs to the family of $d$-degenerate graphs.
Towards this we use the notion of $d$-degeneracy sequence, which is an ordering of the vertices
in $H$ such that any vertex can have at most $d$ forward neighbors. This is used in designing a
marking scheme for the degree two vertices. Broadly speaking our marking scheme associates
a set with every vertex $v$. Here, set consists of “ paths and cycles of $G'$ on which the forward
neighbors of $v$ are”. Two vertices are called similar if their associated sets are same. We
show that if some vertex is not marked then we can safely contract this vertex to one of its
neighbors. We then upper bound the degree two vertices by $O(k^{O(d)}d^{O(d)})$, and thus obtain
a kernel of this size for $\mathcal{D}_d$-CF-FVS.

At the heart of our kernelization algorithm is a combinatorial tool of “*k*-independence
preserver”. Informally, it is a set of “important” vertices for a given subset $X \subseteq V(H)$, that
is enough to capture the independent set property in $H$. We show that for *d*-degenerate
graph independence preserver of size $k^{O(d)}$ exists, and can be used in designing polynomial
kernel. This is our main conceptual contribution.

**Strategy for CF-OCT.** The kernelization lower bound is obtained by the method of cross-composition [6]. We first define a conflict version of the *s*-t-CUT problem, where *H* belongs to $\mathcal{P}_{\le 3}^{**}$. Then, we show that the problem is NP-hard and cross composes to itself. Finally, we give a parameter preserving reduction from the problem to $\mathcal{P}_{\le 3}^{**}$-CF-OCT, and obtain the desired kernel lower bound.

**Related Work.** In the past, the conflict free versions of some classical problems have been studied, e.g. for **SHORTEST PATH** [15], **MAXIMUM FLOW** [21, 22], **KNAPSACK** [23], **BIN PACKING** [12], **SCHEDULING** [13], **MAXIMUM MATCHING** and **MINIMUM WEIGHT SPANNING TREE** [10, 9]. It is interesting to note that some of these problems are **NP**-hard even when their non-conflicting version is polynomial time solvable. The study of conflict free problems has also been recently initiated in computational geometry motivated by various applications (see [1, 2, 3]).
## 2 Preliminaries

Throughout the paper, we follow the following notions. Let $G$ be a graph, $V(G)$ and $E(G)$ denote the vertex set and the edge set of graph $G$, respectively. Let $n$ and $m$ denote the number of vertices and the number of edges of $G$, respectively. Let $G$ be a graph and $X \subseteq V(G)$, then $G[X]$ is the graph induced on $X$ and $G-X$ is graph $G$ induced on $V(G) \setminus X$. Let $\Delta$ denotes the maximum degree of graph $G$. We use $N_G(v)$ to denote the neighborhood of $v$ in $G$ and $N_G[v]$ to denote $N_G(v) \cup \{v\}$. Let $E'$ be subset of edges of graph $G$, by $G[E']$ we mean the graph with the vertex set $V(G)$ and the edge set $E'$. Let $X \subseteq E(G)$, then $G-X$ is a graph with the vertex set $V(G)$ and the edge set $E(G) \setminus X$. Let $Y$ be a set of edges on vertex set $V(G)$, then $G \cup Y$ is graph with the vertex set $V(G)$ and the edge set $E(G) \cup Y$. Degree of a vertex $v$ in graph $G$ is denoted by $\deg_G(v)$. For an integer $\ell$, we denote the set $\{1, 2, \dots, \ell\}$ by $[\ell]$. A path $P = \{v_1, \dots, v_n\}$ is an ordered collection of vertices such that there is an edge between every consecutive vertices in $P$ and $v_1, v_n$ are endpoints of $P$. For a path $P$ by $V(P)$ we denote set of vertices in $P$ and by $E(P)$ we denote set of edges in $P$. A cycle $C = \{v_1, \dots, v_n\}$ is a path with an edge $v_1v_n$. We define a maximal degree two induced path in $G$ as an induced path of maximal length such that all vertices in path are of degree exactly two in $G$. An isolated cycle in graph $G$ is defined as an induced cycle whose all the vertices are of degree exactly two in $G$. Let $G'$ and $G$ be graphs, $V(G') \subseteq V(G)$ and $E(G') \subseteq E(G)$, then we say that $G'$ is a subgraph of $G$. The subscript in the notations will be omitted if it is clear from the context.

A graph $G$ has degeneracy $d$ if every subgraph of $G$ has a vertex of degree at most $d$. An ordering of vertices $\sigma: V(G) \to \{1, \dots, n\}$ is called a $d$-degeneracy sequence of graph $G$, if every vertex $v$ has at most $d$ neighbors $u$ with $\sigma(u) > \sigma(v)$. A graph $G$ is $d$-degenerate if and only if it has a $d$-degeneracy sequence. For a vertex $v$ in $d$-degenerate graph $G$, the neighbors of $v$ which comes after (before) $v$ in $d$-degeneracy sequence are called forward (backward) neighbors of $v$ in the graph $G$. Given a $d$-degenerate graph, we can find $d$-degeneracy sequence in linear time [18].

## 3 A Tool for Our Kernelization Algorithm

In this section, we give a tool, which we believe might be useful in obtaining kernelization algorithm for “conflict free” versions of various parameterized problems (admitting kernels), when the conflict graph belongs to the family of $d$-degenerate graphs. We particularly use this tool to obtain kernel for $\mathcal{D}_d$-CF-FVS (Section 4). For a parameterized problem $\Pi$, consider an instance $(G, H, k)$ of its conflict free variant, CONFLICT FREE $\Pi$. Then in the kernelization step where we want to bound the number of vertices, it is seemingly useful to be able to obtain a set of “important” vertices for a given subset $X \subseteq V(H)$ that will be enough to capture the independent set property in $H$. The above intuition becomes clear when we describe the kernelization algorithm for $\mathcal{D}_d$-CF-FVS.

To formalize the notion of “important” set of vertices, we give the following definition.

**Definition 1.** For a $d$-degenerate graph $H$ and a set $X \subseteq V(H)$, a $k$-independence preserver for $(H, X)$ is a set $X' \subseteq X$, such that for any independent set $S$ in $H$ of size at most $k$, if there is $v \in (S \cap X) \setminus X'$, then there is $v' \in X' \setminus S$, such that $(S \setminus \{v\}) \cup \{v'\}$ is an independent set in $H$.

Throughout this section, we work with a (fixed) $d$, which is the degeneracy of the input graph. The goal of this section will be to obtain an algorithm for computing a $k$-independence
## 2 Preliminaries

Throughout the paper, we follow the following notions. Let $G$ be a graph, $V(G)$ and $E(G)$ denote the vertex set and the edge set of graph $G$, respectively. Let $n$ and $m$ denote the number of vertices and the number of edges of $G$, respectively. Let $G$ be a graph and $X \subseteq V(G)$, then $G[X]$ is the graph induced on $X$ and $G-X$ is graph $G$ induced on $V(G) \setminus X$. Let $\Delta$ denotes the maximum degree of graph $G$. We use $N_G(v)$ to denote the neighborhood of $v$ in $G$ and $N_G[v]$ to denote $N_G(v) \cup \{v\}$. Let $E'$ be subset of edges of graph $G$, by $G[E']$ we mean the graph with the vertex set $V(G)$ and the edge set $E'$. Let $X \subseteq E(G)$, then $G-X$ is a graph with the vertex set $V(G)$ and the edge set $E(G) \setminus X$. Let $Y$ be a set of edges on vertex set $V(G)$, then $G \cup Y$ is graph with the vertex set $V(G)$ and the edge set $E(G) \cup Y$. Degree of a vertex $v$ in graph $G$ is denoted by $\text{deg}_G(v)$. For an integer $\ell$, we denote the set $\{1, 2, \dots, \ell\}$ by $[\ell]$. A path $P = \{v_1, \dots, v_n\}$ is an ordered collection of vertices such that there is an edge between every consecutive vertices in $P$ and $v_1, v_n$ are endpoints of $P$. For a path $P$ by $V(P)$ we denote set of vertices in $P$ and by $E(P)$ we denote set of edges in $P$. A cycle $C = \{v_1, \dots, v_n\}$ is a path with an edge $v_1v_n$. We define a maximal degree two induced path in $G$ as an induced path of maximal length such that all vertices in path are of degree exactly two in $G$. An isolated cycle in graph $G$ is defined as an induced cycle whose all the vertices are of degree exactly two in $G$. Let $G'$ and $G$ be graphs, $V(G') \subseteq V(G)$ and $E(G') \subseteq E(G)$, then we say that $G'$ is a subgraph of $G$. The subscript in the notations will be omitted if it is clear from the context.

A graph $G$ has degeneracy $d$ if every subgraph of $G$ has a vertex of degree at most $d$. An ordering of vertices $\sigma: V(G) \to \{1, \dots, n\}$ is called a $d$-degeneracy sequence of graph $G$, if every vertex $v$ has at most $d$ neighbors $u$ with $\sigma(u) > \sigma(v)$. A graph $G$ is $d$-degenerate if and only if it has a $d$-degeneracy sequence. For a vertex $v$ in $d$-degenerate graph $G$, the neighbors of $v$ which comes after (before) $v$ in $d$-degeneracy sequence are called forward (backward) neighbors of $v$ in the graph $G$. Given a $d$-degenerate graph, we can find $d$-degeneracy sequence in linear time [18].

## 3 A Tool for Our Kernelization Algorithm

In this section, we give a tool, which we believe might be useful in obtaining kernelization algorithm for “conflict free” versions of various parameterized problems (admitting kernels), when the conflict graph belongs to the family of $d$-degenerate graphs. We particularly use this tool to obtain kernel for $\mathcal{D}_d$-CF-FVS (Section 4). For a parameterized problem $\Pi$, consider an instance $(G, H, k)$ of its conflict free variant, CONFLICT FREE $\Pi$. Then in the kernelization step where we want to bound the number of vertices, it is seemingly useful to be able to obtain a set of “important” vertices for a given subset $X \subseteq V(H)$ that will be enough to capture the independent set property in $H$. The above intuition becomes clear when we describe the kernelization algorithm for $\mathcal{D}_d$-CF-FVS.

To formalize the notion of “important” set of vertices, we give the following definition.

**Definition 1.** For a $d$-degenerate graph $H$ and a set $X \subseteq V(H)$, a $k$-independence preserver for $(H, X)$ is a set $X' \subseteq X$, such that for any independent set $S$ in $H$ of size at most $k$, if there is $v \in (S \cap X) \setminus X'$, then there is $v' \in X' \setminus S$, such that $(S \setminus \{v\}) \cup \{v'\}$ is an independent set in $H$.

Throughout this section, we work with a (fixed) $d$, which is the degeneracy of the input graph. The goal of this section will be to obtain an algorithm for computing a $k$-independence
**14:6 Exploring the Kernelization Borders for Hitting Cycles**

preserver for (H, X) of “small” size. To quantify the “small” size, we need the following definition.

**► Definition 2.** For each $q \in [d]$, we define an integer $n_q$ as follows.

1. If $q = 1$, then $n_q = kd + k + 1$, and

2. $n_q = kn_{q-1} + kd + k + 1$, otherwise.

Next, we formally define the problem for which we want to design a polynomial time algorithm. We call this problem *d-BOUNDED INDEPENDENCE PRESERVER (d-BIP, for short).*

d-BOUNDED INDEPENDENCE PRESERVER (d-BIP)

**Input:** A *d*-degenerate graph *H*, a set *X* ⊆ *V*(*H*), and an integer *k*.

**Output:** A set $X' \subseteq X$ of size at most $n_{d+1}$, such that $X'$ is a $k$ independence preserver for $(H, X)$.

In the following, let $(H, X, k)$ be an instance of *d-BIP*. We work with a (fixed) *d*-degeneracy sequence, $\sigma$ of $H$. We recall that such a sequence can be computed in polynomial time [18]. Forward and backward neighbors of a vertex $v$ are also defined with respect to the ordering $\sigma$. If $\sigma(u) < \sigma(v)$, then $u$ is a backward neighbor of $v$ and $v$ is a forward neighbor of $u$. By $N_H^f(v)$ ($N_H^b(v)$) we denote the set of forward (backward) neighbors of the vertex $v$ in $H$.

To design our polynomial time algorithm for *d-BIP*, we need the notion of *q-reducible sets*, which is formally defined below.

**► Definition 3.** A set $Y \subseteq V(H)$ is *q-reducible*, if for every set $U \subseteq Y$, for which there is a set $Z \subseteq V(H)$, such that: (i) $Z$ is of size exactly $d-q+1$ and (ii) for each $u \in U$, we have $Z \subseteq N_H^f(u)$, it holds that $|U| \le n_q$.

Now, we give our polynomial time algorithm for *d-BIP* in Algorithm 1.

**Algorithm 1** Algo1(H, X).

**Require:** *d*-degenerate graph *H*, *X* ⊆ *V*(*H*), and an integer *k*.

**Ensure:** $X' \subseteq X$ of size at most $n_{d+1}$, which is a $k$-independence preserver of $(H, X)$.

1. For $q \in [d]$, set $n_q = kd + 1$, when $q = 1$, and $n_q = kn_{q-1} + kd + k + 1$, otherwise.

2. $q = 1$.

3. **while** $q \le d$ **do**

4. &nbsp;&nbsp;&nbsp;&nbsp;**while** *X* is not *q-reducible* **do**

5. &nbsp;&nbsp;&nbsp;&nbsp;Find $U \subseteq X$ of size $n_q + 1$, for which there is $Z \subseteq V(H)$ of size exactly $d-q+1$, such that for each $u \in U$, we have $Z \subseteq N_H^f(u)$.

6. &nbsp;&nbsp;&nbsp;&nbsp;Let *v* be an arbitrary vertex in *U*.

7. &nbsp;&nbsp;&nbsp;&nbsp;$$X = X \setminus \{v\}.$$

8. **end while**

9. $q = q + 1$.

10. **end while**

11. **while** $|X| > n_{d+1}$ **do**

12. &nbsp;&nbsp;&nbsp;&nbsp;Let *v* be an arbitrary vertex in *X*.

13. $$X = X \setminus \{v\}.$$

14. **end while**

15. Set $X' = X$.

16. **return** $X'$

To prove the correctness of our algorithm, we state an observation, the proof of which follows from the fact that any vertex can have at most *d* forward neighbors in *H*.
14:6 Exploring the Kernelization Borders for Hitting Cycles

preserver for (H, X) of “small” size. To quantify the “small” size, we need the following definition.

► **Definition 2.** For each $q \in [d]$, we define an integer $n_q$ as follows.

1. If $q = 1$, then $n_q = kd + k + 1$, and

2. $n_q = kn_{q-1} + kd + k + 1$, otherwise.

Next, we formally define the problem for which we want to design a polynomial time algorithm. We call this problem *d-BOUNDED INDEPENDENCE PRESERVER (d-BIP, for short).*

d-BOUNDED INDEPENDENCE PRESERVER (d-BIP)

**Input:** A *d*-degenerate graph *H*, a set *X* ⊆ *V*(*H*), and an integer *k*.

**Output:** A set $X' \subseteq X$ of size at most $n_{d+1}$, such that $X'$ is a $k$ independence preserver for $(H, X)$.

In the following, let $(H, X, k)$ be an instance of *d-BIP*. We work with a (fixed) *d*-degeneracy sequence, $\sigma$ of $H$. We recall that such a sequence can be computed in polynomial time [18]. Forward and backward neighbors of a vertex $v$ are also defined with respect to the ordering $\sigma$. If $\sigma(u) < \sigma(v)$, then $u$ is a backward neighbor of $v$ and $v$ is a forward neighbor of $u$. By $N_H^f(v)$ ($N_H^b(v)$) we denote the set of forward (backward) neighbors of the vertex $v$ in $H$.

To design our polynomial time algorithm for *d-BIP*, we need the notion of *q-reducible sets*, which is formally defined below.

► **Definition 3.** A set $Y \subseteq V(H)$ is *q-reducible*, if for every set $U \subseteq Y$, for which there is a set $Z \subseteq V(H)$, such that: (i) $Z$ is of size exactly $d-q+1$ and (ii) for each $u \in U$, we have $Z \subseteq N_H^f(u)$, it holds that $|U| \le n_q$.

Now, we give our polynomial time algorithm for *d-BIP* in Algorithm 1.

**Algorithm 1** Algo1(H, X).

**Require:** *d*-degenerate graph *H*, *X* ⊆ *V*(*H*), and an integer *k*.

**Ensure:** $X' \subseteq X$ of size at most $n_{d+1}$, which is a $k$-independence preserver of $(H, X)$.

1. For $q \in [d]$, set $n_q = kd + 1$, when $q = 1$, and $n_q = kn_{q-1} + kd + k + 1$, otherwise.

2. $q = 1$.

3. **while** $q \le d$ **do**

4. &nbsp;&nbsp;&nbsp;&nbsp;**while** *X* is not *q*-reducible **do**

5. &nbsp;&nbsp;&nbsp;&nbsp;Find $U \subseteq X$ of size $n_q + 1$, for which there is $Z \subseteq V(H)$ of size exactly $d-q+1$, such that for each $u \in U$, we have $Z \subseteq N_H^f(u)$.

6. &nbsp;&nbsp;&nbsp;&nbsp;Let *v* be an arbitrary vertex in *U*.

7. &nbsp;&nbsp;&nbsp;&nbsp;$X = X \setminus \{v\}$.

8. **end while**

9. $q = q + 1$.

10. **end while**

11. **while** $|X| > n_{d+1}$ **do**

12. &nbsp;&nbsp;&nbsp;&nbsp;Let *v* be an arbitrary vertex in *X*.

13. $X = X \setminus \{v\}$.

14. **end while**

15. Set $X' = X$.

16. **return** $X'$

To prove the correctness of our algorithm, we state an observation, the proof of which follows from the fact that any vertex can have at most *d* forward neighbors in *H*.
**Observation 4.** Let $H$ be a $d$-degenerate graph and $S$ be an independent set of $H$ of size at most $k$. Then, for any set $U \subseteq V(H)$, such that for each vertex $u \in U$, $N_H^b(u) \cap S \neq \emptyset$, we have that $|U| \leq kd$.

Now we are ready to prove the correctness of our algorithm (Algorithm 1) for $d$-BIP.

**Lemma 5.** *Algorithm 1 is correct.*

**Proof.** Let $(H, X, k)$ be an instance of $d$-BIP, and $X'$ be the output returned by Algorithm 1 with it as the input. Clearly, $X' \subseteq X$ as we do not add any new vertex to obtain the set $X'$, and size of $X'$ is bounded by $n_{d+1}$, since at Step 10-13 of the algorithm we reduce its size to (at most) $n_{d+1}$. Therefore, it remains to show that $X'$ is a $k$-independence preserver of $(H, X)$. To this end, we consider the following cases.

**Case 1:** $X$ is $q$-reducible, for each $q \in [d]$. In this case, the algorithm arbitrarily deletes vertices (if required) from $X$ to obtain $X'$. If $X = X'$, then the claim trivially holds. Therefore, we assume that $X'$ is a strict subset of $X$. To show that $X'$ is a $k$-independence preserver for $(H, X)$, consider an independent set $S$ in $H$ of size at most $k$. Furthermore, consider a vertex $v \in (S \cap X) \setminus X'$ (again, if such a vertex does not exists, the claim follows). To prove the desired result, we want to find a replacement vertex for $v$ in $X'$ which can be added to $S$ (after removing $v$) to obtain an independent set in $H$. To this end, we mark some vertices in $X'$. Firstly, mark all the forward neighbors of each $s \in S$ in the set $X'$. That is, we let $X'_M$ to be the set $(\cup_{s \in S} N_H^f(s)) \cap X'$. Also, we add all vertices in $S \cap X'$ to the set $X'_M$. By the property of $d$-degeneracy sequence, we have that $|X'_M| \leq kd + k$ (see Observation 4). Next, we will mark some more vertices in $X'_M$ with the hope to find a replacement vertex for $v$ in $X' \setminus X'_M$ to add to $S$. Recall that by our assumption $X$ is $q$-reducible, for each $q \in [d]$, and in particular, it is $d$-reducible. Thus, for each $s \in S$, the set $X_s = \{x \in X \mid s \in N_H^f(x)\} \subseteq X$ has size at most $n_d$. Based on the above observation, we describe our second level of marking of vertices in $X'$. For each $s \in S$, we add each vertex in $X_s$ to $X'_M$. From the discussions above, we have that $|X'_M| \leq kd + k + kn_d$. Since $|X'| = n_{d+1}$, and by definition, $n_{d+1} = kn_d + kd + k + 1$, we have $X' \setminus X'_M \neq \emptyset$. Moreover, no vertex in $X'$ has a neighbor in $S \setminus \{v\}$. Therefore, for $v' \in X' \setminus X'_M$, we have that $S' = (S \setminus \{v\}) \cup \{v'\}$ is an independent set in $H$.

**Case 2:** $X$ is not $q$-reducible, for some $q \in [d]$. Let $q'$ be the smallest integer for which $X$ is not $q'$-reducible. Since $X$ is not $q'$-reducible, there is a set $U \subseteq X$ of size at least $n_q + 1$, for which there is a set $Z \subseteq V(H)$ of size exactly $d - q + 1$, such that for each $u \in U$, we have $Z \subseteq N_H^f(u)$. Consider (first) such pair of sets $U, Z$ considered by the algorithm in Step 4. Furthermore, let $v \in U$ be the vertex deleted by the algorithm in Step 6. Let $\hat{U} = U \setminus \{v\}$. To prove the claim, it is enough to show that for an independent set $S$ of size at most $k$ containing $v$ in $H$, there is $v' \in \hat{U}$ such that $(S \setminus \{v\}) \cup \{v'\}$ is an independent set in $H$. Here, we will use the fact that deleting a vertex from a set does not change a set from being $\tilde{q}$-reducible to a set which is not $\tilde{q}$-reducible, where $\tilde{q} \in [d]$. In the following, consider an independent set $S$ of size at most $k$ containing $v$ in $H$. We construct a marked set $\hat{U}_M$, of vertices in $\hat{U}$. Firstly, we add all the vertices in $(\cup_{s \in S \setminus \{v\}} N_H^f(s)) \cap \hat{U}$ to $\hat{U}_M$. Also, we add all vertices in $S \cap \hat{U}$ to $\hat{U}_M$. Notice that at the end of above marking scheme, we have $|\hat{X}_M| \leq kd + k$. We will mark some more vertices in $\hat{U}$. Before stating the second level of marking, we remark that $S \cap Z = \emptyset$. For each $s \in S \setminus \{v\}$, let $Z_s = Z \cup \{s\}$. Since $S \cap Z = \emptyset$, we have that $|Z_s| = d - (q - 1) + 1$. For $s \in S \setminus \{v\}$, let $\hat{U}_s = \{u \in \hat{U} \mid Z_s \subseteq N_H^f(u)\}$. Since $X$ is $q^*$-reducible for each $q^* < q'$, we have $|\hat{U}_s| \leq n_{q-1}$, for each $s \in S \setminus \{v\}$. Now we are ready to describe our second
**► Observation 4.** Let $H$ be a $d$-degenerate graph and $S$ be an independent set of $H$ of size at most $k$. Then, for any set $U \subseteq V(H)$, such that for each vertex $u \in U$, $N_H^b(u) \cap S \neq \emptyset$, we have that $|U| \leq kd$.

Now we are ready to prove the correctness of our algorithm (Algorithm 1) for $d$-BIP.

**► Lemma 5.** *Algorithm 1 is correct.*

**Proof.** Let $(H, X, k)$ be an instance of $d$-BIP, and $X'$ be the output returned by Algorithm 1 with it as the input. Clearly, $X' \subseteq X$ as we do not add any new vertex to obtain the set $X'$, and size of $X'$ is bounded by $n_{d+1}$, since at Step 10-13 of the algorithm we reduce its size to (at most) $n_{d+1}$. Therefore, it remains to show that $X'$ is a $k$-independence preserver of $(H, X)$. To this end, we consider the following cases.

**Case 1:** $X$ is $q$-reducible, for each $q \in [d]$. In this case, the algorithm arbitrarily deletes vertices (if required) from $X$ to obtain $X'$. If $X = X'$, then the claim trivially holds. Therefore, we assume that $X'$ is a strict subset of $X$. To show that $X'$ is a $k$-independence preserver for $(H, X)$, consider an independent set $S$ in $H$ of size at most $k$. Furthermore, consider a vertex $v \in (S \cap X) \setminus X'$ (again, if such a vertex does not exists, the claim follows). To prove the desired result, we want to find a replacement vertex for $v$ in $X'$ which can be added to $S$ (after removing $v$) to obtain an independent set in $H$. To this end, we mark some vertices in $X'$. Firstly, mark all the forward neighbors of each $s \in S$ in the set $X'$. That is, we let $X'_M$ to be the set $(\cup_{s \in S} N_H^f(s)) \cap X'$. Also, we add all vertices in $S \cap X'$ to the set $X'_M$. By the property of $d$-degeneracy sequence, we have that $|X'_M| \leq kd + k$ (see Observation 4). Next, we will mark some more vertices in $X'_M$ with the hope to find a replacement vertex for $v$ in $X' \setminus X'_M$ to add to $S$. Recall that by our assumption $X$ is $q$-reducible, for each $q \in [d]$, and in particular, it is $d$-reducible. Thus, for each $s \in S$, the set $X_s = \{x \in X \mid s \in N_H^f(x)\} \subseteq X$ has size at most $n_d$. Based on the above observation, we describe our second level of marking of vertices in $X'$. For each $s \in S$, we add each vertex in $X_s$ to $X'_M$. From the discussions above, we have that $|X'_M| \leq kd + k + kn_d$. Since $|X'| = n_{d+1}$, and by definition, $n_{d+1} = kn_d + kd + k + 1$, we have $X' \setminus X'_M \neq \emptyset$. Moreover, no vertex in $X'$ has a neighbor in $S \setminus \{v\}$. Therefore, for $v' \in X' \setminus X'_M$, we have that $S' = (S \setminus \{v\}) \cup \{v'\}$ is an independent set in $H$.

**Case 2:** $X$ is not $q$-reducible, for some $q \in [d]$. Let $q'$ be the smallest integer for which $X$ is not $q'$-reducible. Since $X$ is not $q'$-reducible, there is a set $U \subseteq X$ of size at least $n_q + 1$, for which there is a set $Z \subseteq V(H)$ of size exactly $d - q + 1$, such that for each $u \in U$, we have $Z \subseteq N_H^f(u)$. Consider (first) such pair of sets $U, Z$ considered by the algorithm in Step 4. Furthermore, let $v \in U$ be the vertex deleted by the algorithm in Step 6. Let $\hat{U} = U \setminus \{v\}$. To prove the claim, it is enough to show that for an independent set $S$ of size at most $k$ containing $v$ in $H$, there is $v' \in \hat{U}$ such that $(S \setminus \{v\}) \cup \{v'\}$ is an independent set in $H$. Here, we will use the fact that deleting a vertex from a set does not change a set from being $\tilde{q}$-reducible to a set which is not $\tilde{q}$-reducible, where $\tilde{q} \in [d]$. In the following, consider an independent set $S$ of size at most $k$ containing $v$ in $H$. We construct a marked set $\hat{U}_M$, of vertices in $\hat{U}$. Firstly, we add all the vertices in $(\cup_{s \in S \setminus \{v\}} N_H^f(s)) \cap \hat{U}$ to $\hat{U}_M$. Also, we add all vertices in $S \cap \hat{U}$ to $\hat{U}_M$. Notice that at the end of above marking scheme, we have $|\hat{X}_M| \leq kd + k$. We will mark some more vertices in $\hat{U}$. Before stating the second level of marking, we remark that $S \cap Z = \emptyset$. For each $s \in S \setminus \{v\}$, let $Z_s = Z \cup \{s\}$. Since $S \cap Z = \emptyset$, we have that $|Z_s| = d - (q - 1) + 1$. For $s \in S \setminus \{v\}$, let $\hat{U}_s = \{u \in \hat{U} \mid Z_s \subseteq N_H^f(u)\}$. Since $X$ is $q^*$-reducible for each $q^* < q'$, we have $|\hat{U}_s| \leq n_{q-1}$, for each $s \in S \setminus \{v\}$. Now we are ready to describe our second
14:8 Exploring the Kernelization Borders for Hitting Cycles

level of marking. For each $s \in S \setminus \{v\}$, add all vertices in $U_s$ to the set $\hat{U}_M$. Notice that
$|\hat{U}_M| \le kd + k + kn_{q-1}$. Moreover, $|\hat{U}| \ge n_q$ and $n_q = kn_{q-1} + kd + k + 1$. Thus, there is
a vertex $v' \in \hat{U} \setminus \hat{U}_M$, such that $(S \setminus \{v\}) \cup \{v'\}$ is an independent set in $H$. ◀

► Lemma 6. $(\star)^2$ Algorithm 1 runs in time $n^{O(d)}$.

Using Lemma 5 and Lemma 6 we obtain the following theorem.

► **Theorem 7.** *d*-BOUNDED INDEPENDENCE PRESERVER admits an algorithm running in time $n^{O(d)}$.

4 A Polynomial Kernel for $\mathcal{D}_d$-CF-FVS

In this section, we design a kernelization algorithm for $\mathcal{D}_d$-CF-FVS.

To design a kernelization algorithm for $\mathcal{D}_d$-CF-FVS, we define another problem called $\mathcal{D}_d$-DISJOINT-CF-FVS ($\mathcal{D}_d$-DCF-FVS, for short). We first define the problem $\mathcal{D}_d$-DCF-FVS formally, and then explain its uses in our kernelization algorithm.

$\mathcal{D}_d$-DISJOINT-CF-FVS ($\mathcal{D}_d$-DCF-FVS)

Parameter: $k$

**Input:** An undirected graph $G$, a graph $H \in \mathcal{D}_d$ such that $V(G) = V(H)$, a subset $R \subseteq V(G)$, and a non-negative integer $k$.

**Question:** Is there a set $S \subseteq V(G) \setminus R$ of size at most $k$, such that $G-S$ does not have any cycle and $S$ is an independent set in $H$?

Notice that $\mathcal{D}_d$-CF-FVS is a special case of $\mathcal{D}_d$-DCF-FVS, where $R = \emptyset$. Given an instance of $\mathcal{D}_d$-CF-FVS, the kernelization algorithm creates an instance of $\mathcal{D}_d$-DCF-FVS by setting $R = \emptyset$. Then it applies a kernelization algorithm for $\mathcal{D}_d$-DCF-FVS. Finally, the algorithm takes the instance returned by the kernelization algorithm for $\mathcal{D}_d$-DCF-FVS and generates an instance of $\mathcal{D}_d$-CF-FVS. Before moving forward, we note that the purpose of having set $R$ is to be able to prohibit certain vertices to belong to a solution. This is particularly useful in maintaining the independent set property of the solution, when applying reduction rules which remove vertices from the graph (with an intention of it being in a solution).

We first focus on designing a kernelization algorithm for $\mathcal{D}_d$-DCF-FVS, and then give
a polynomial time linear parameter preserving reduction from $\mathcal{D}_d$-DCF-FVS to $\mathcal{D}_d$-CF-
FVS. If the kernelization algorithm for $\mathcal{D}_d$-DCF-FVS returns that $(G, H, R, k)$ is a YES
(NO) instance of $\mathcal{D}_d$-DCF-FVS, then conclude that $(G, H, k)$ is a YES (NO) instance of
$\mathcal{D}_d$-CF-FVS. In the following, we describe a kernelization algorithm for $\mathcal{D}_d$-DCF-FVS. Let
$(G, H, R, k)$ be an instance of $\mathcal{D}_d$-DCF-FVS. The algorithm starts by applying the following
simple reduction rules.

► Reduction Rule 1.

(a) If $k \ge 0$ and $G$ is acyclic, then return that $(G, H, R, k)$ is a YES instance of $\mathcal{D}_d$-DCF-FVS.

(b) Return that $(G, H, R, k)$ is a NO instance of $\mathcal{D}_d$-DCF-FVS, if one of the following conditions is satisfied:

(i) $k \le 0$ and $G$ is not acyclic,

(ii) $G$ is not acyclic and $V(G) \subseteq R$, or

<footnote n="2">² Due to space constraints, the proofs of results marked with ⋆ have been omitted from this extended abstract.</footnote>
14:8 Exploring the Kernelization Borders for Hitting Cycles

level of marking. For each $s \in S \setminus \{v\}$, add all vertices in $U_s$ to the set $\hat{U}_M$. Notice that
$|\hat{U}_M| \le kd + k + kn_{q-1}$. Moreover, $|\hat{U}| \ge n_q$ and $n_q = kn_{q-1} + kd + k + 1$. Thus, there is
a vertex $v' \in \hat{U} \setminus \hat{U}_M$, such that $(S \setminus \{v\}) \cup \{v'\}$ is an independent set in $H$. ◀

► **Lemma 6.** (⋆)<fnref n="2" /> *Algorithm 1 runs in time $n^{O(d)}$.*

Using Lemma 5 and Lemma 6 we obtain the following theorem.

► **Theorem 7.** *d*-BOUNDED INDEPENDENCE PRESERVER admits an algorithm running in time $n^{O(d)}$.

4 A Polynomial Kernel for $\mathcal{D}_d$-CF-FVS

In this section, we design a kernelization algorithm for $\mathcal{D}_d$-CF-FVS.

To design a kernelization algorithm for $\mathcal{D}_d$-CF-FVS, we define another problem called $\mathcal{D}_d$-DISJOINT-CF-FVS ($\mathcal{D}_d$-DCF-FVS, for short). We first define the problem $\mathcal{D}_d$-DCF-FVS formally, and then explain its uses in our kernelization algorithm.

$\mathcal{D}_d$-DISJOINT-CF-FVS ($\mathcal{D}_d$-DCF-FVS)

Parameter: $k$

**Input:** An undirected graph $G$, a graph $H \in \mathcal{D}_d$ such that $V(G) = V(H)$, a subset $R \subseteq V(G)$, and a non-negative integer $k$.

**Question:** Is there a set $S \subseteq V(G) \setminus R$ of size at most $k$, such that $G-S$ does not have any cycle and $S$ is an independent set in $H$?

Notice that $\mathcal{D}_d$-CF-FVS is a special case of $\mathcal{D}_d$-DCF-FVS, where $R = \emptyset$. Given an instance of $\mathcal{D}_d$-CF-FVS, the kernelization algorithm creates an instance of $\mathcal{D}_d$-DCF-FVS by setting $R = \emptyset$. Then it applies a kernelization algorithm for $\mathcal{D}_d$-DCF-FVS. Finally, the algorithm takes the instance returned by the kernelization algorithm for $\mathcal{D}_d$-DCF-FVS and generates an instance of $\mathcal{D}_d$-CF-FVS. Before moving forward, we note that the purpose of having set $R$ is to be able to prohibit certain vertices to belong to a solution. This is particularly useful in maintaining the independent set property of the solution, when applying reduction rules which remove vertices from the graph (with an intention of it being in a solution).

We first focus on designing a kernelization algorithm for $\mathcal{D}_d$-DCF-FVS, and then give
a polynomial time linear parameter preserving reduction from $\mathcal{D}_d$-DCF-FVS to $\mathcal{D}_d$-CF-
FVS. If the kernelization algorithm for $\mathcal{D}_d$-DCF-FVS returns that $(G, H, R, k)$ is a YES
(NO) instance of $\mathcal{D}_d$-DCF-FVS, then conclude that $(G, H, k)$ is a YES (NO) instance of
$\mathcal{D}_d$-CF-FVS. In the following, we describe a kernelization algorithm for $\mathcal{D}_d$-DCF-FVS. Let
$(G, H, R, k)$ be an instance of $\mathcal{D}_d$-DCF-FVS. The algorithm starts by applying the following
simple reduction rules.

► Reduction Rule 1.

(a) If $k \ge 0$ and $G$ is acyclic, then return that $(G, H, R, k)$ is a YES instance of $\mathcal{D}_d$-DCF-FVS.

(b) Return that $(G, H, R, k)$ is a NO instance of $\mathcal{D}_d$-DCF-FVS, if one of the following conditions is satisfied:

(i) $k \le 0$ and $G$ is not acyclic,

(ii) $G$ is not acyclic and $V(G) \subseteq R$, or

<footnote n="2">² Due to space constraints, the proofs of results marked with ★ have been omitted from this extended abstract.</footnote>
(iii) There are more than $k$ isolated cycles in $G$.

**► Reduction Rule 2.**

(a) Let $v$ be a vertex of degree at most 1 in $G$. Then delete $v$ from the graphs $G, H$ and the set $R$.

(b) If there is an edge in $G$ ($H$) with multiplicity more than 2 (more than 1), then reduce its multiplicity to 2 (1).

(c) If there is a vertex $v$ with self loop in $G$. If $v \notin R$, delete $v$ from the graphs $G$ and $H$, and decrease $k$ by one. Furthermore, add all the vertices in $N_H(v)$ to the set $R$, otherwise return that $(G, H, R, k)$ is a NO instance of $\mathcal{D}_d$-DCF-FVS.

(d) If there are parallel edges between (distinct) vertices $u, v \in V(G)$ in $G$:

(i) If $u, v \in R$, then return that $(G, H, R, k)$ is a NO instance of $\mathcal{D}_d$-DCF-FVS.

(ii) If $u \in R$ ($v \in R$), delete $v$ ($u$) from the graphs $G$ and $H$, and decrease $k$ by one. Furthermore, add all the vertices in $N_H(v)$ ($N_H(u)$) to the set $R$.

It is easy to see that the above reduction rules are correct, and can be applied in polynomial time. In the following, we define some notion and state some known results, which will be helpful in designing our next reduction rules.

**► Definition 8.** For a graph $G$, a vertex $v \in V(G)$, and an integer $t \in \mathbb{N}$, a *t-flower* at $v$ is a set of $t$ vertex disjoint cycles whose pairwise intersection is exactly $\{v\}$.

**► Proposition 9.** [8, 19, 25] For a graph $G$, a vertex $v \in V(G)$ without a self-loop in $G$, and an integer $k$, the following conditions hold.

(i) There is a polynomial time algorithm, which either outputs a $(k+1)$-flower at $v$, or it correctly concludes that no such $(k+1)$-flower exists. Moreover, if there is no $(k+1)$-flower at $v$, it outputs a set $X_v \subseteq V(G) \setminus \{v\}$ of size at most $2k$, such that $X_v$ intersects every cycle passing through $v$ in $G$.

(ii) If there is no $(k+1)$-flower at $v$ in $G$ and the degree of $v$ is at least $4k + (k+2)2k$. Then using a polynomial time algorithm we can obtain a set $X_v \subseteq V(G) \setminus \{v\}$ and a set $C_v$ of components of $G[V(G) \setminus (X_v \cup \{v\})]$, such that each component in $C_v$ is a tree, $v$ has exactly one neighbor in $C \in C_v$, and there exist at least $k+2$ components in $C_v$ corresponding to each vertex $x \in X_v$ such that these components are pairwise disjoint and vertices in $X_v$ have an edge to each of their associated components.

**► Reduction Rule 3.** Consider $v \in V(G)$, such that there is a $(k+1)$-flower at $v$ in $G$. If $v \in R$, then return that $(G, H, R, k)$ is a NO instance of $\mathcal{D}_d$-DCF-FVS. Otherwise, delete $v$ from $G, H$ and decrease $k$ by one. Furthermore, add all the vertices in $N_H(v)$ to $R$.

The correctness of the above reduction rule follows from the fact that such a vertex must be part of every solution of size at most $k$. Moreover, the applicability of it in polynomial time follows from Proposition 9 (item (i)).

**► Reduction Rule 4.** Let $v \in V(G)$, $X_v \subseteq V(G) \setminus \{v\}$, and $C_v$ be the set of components which satisfy the conditions in Proposition 9(ii) (in $G$), then delete edges between $v$ and the components of the set $C_v$, and add parallel edges between $v$ and every vertex $x \in X_v$ in $G$.

The polynomial time applicability of Reduction Rule 4 follows from Proposition 9. And, in the following lemma, we prove the safeness of this reduction rule.

**► Lemma 10.** (⋆) Reduction Rule 4 is safe.
(iii) There are more than $k$ isolated cycles in $G$.

**► Reduction Rule 2.**

(a) Let $v$ be a vertex of degree at most 1 in $G$. Then delete $v$ from the graphs $G, H$ and the set $R$.

(b) If there is an edge in $G$ ($H$) with multiplicity more than 2 (more than 1), then reduce its multiplicity to 2 (1).

(c) If there is a vertex $v$ with self loop in $G$. If $v \notin R$, delete $v$ from the graphs $G$ and $H$, and decrease $k$ by one. Furthermore, add all the vertices in $N_H(v)$ to the set $R$, otherwise return that $(G, H, R, k)$ is a NO instance of $\mathcal{D}_d$-DCF-FVS.

(d) If there are parallel edges between (distinct) vertices $u, v \in V(G)$ in $G$:

(i) If $u, v \in R$, then return that $(G, H, R, k)$ is a NO instance of $\mathcal{D}_d$-DCF-FVS.

(ii) If $u \in R$ ($v \in R$), delete $v$ ($u$) from the graphs $G$ and $H$, and decrease $k$ by one. Furthermore, add all the vertices in $N_H(v)$ ($N_H(u)$) to the set $R$.

It is easy to see that the above reduction rules are correct, and can be applied in polynomial time. In the following, we define some notion and state some known results, which will be helpful in designing our next reduction rules.

**► Definition 8.** For a graph $G$, a vertex $v \in V(G)$, and an integer $t \in \mathbb{N}$, a *t-flower* at $v$ is a set of $t$ vertex disjoint cycles whose pairwise intersection is exactly $\{v\}$.

**► Proposition 9.** [8, 19, 25] For a graph $G$, a vertex $v \in V(G)$ without a self-loop in $G$, and an integer $k$, the following conditions hold.

(i) There is a polynomial time algorithm, which either outputs a $(k+1)$-flower at $v$, or it correctly concludes that no such $(k+1)$-flower exists. Moreover, if there is no $(k+1)$-flower at $v$, it outputs a set $X_v \subseteq V(G) \setminus \{v\}$ of size at most $2k$, such that $X_v$ intersects every cycle passing through $v$ in $G$.

(ii) If there is no $(k+1)$-flower at $v$ in $G$ and the degree of $v$ is at least $4k + (k+2)2k$. Then using a polynomial time algorithm we can obtain a set $X_v \subseteq V(G) \setminus \{v\}$ and a set $C_v$ of components of $G[V(G) \setminus (X_v \cup \{v\})]$, such that each component in $C_v$ is a tree, $v$ has exactly one neighbor in $C \in C_v$, and there exist at least $k+2$ components in $C_v$ corresponding to each vertex $x \in X_v$ such that these components are pairwise disjoint and vertices in $X_v$ have an edge to each of their associated components.

**► Reduction Rule 3.** Consider $v \in V(G)$, such that there is a $(k+1)$-flower at $v$ in $G$. If $v \in R$, then return that $(G, H, R, k)$ is a NO instance of $\mathcal{D}_d$-DCF-FVS. Otherwise, delete $v$ from $G, H$ and decrease $k$ by one. Furthermore, add all the vertices in $N_H(v)$ to $R$.

The correctness of the above reduction rule follows from the fact that such a vertex must be part of every solution of size at most $k$. Moreover, the applicability of it in polynomial time follows from Proposition 9 (item (i)).

**► Reduction Rule 4.** Let $v \in V(G)$, $X_v \subseteq V(G) \setminus \{v\}$, and $C_v$ be the set of components which satisfy the conditions in Proposition 9(ii) (in $G$), then delete edges between $v$ and the components of the set $C_v$, and add parallel edges between $v$ and every vertex $x \in X_v$ in $G$.

The polynomial time applicability of Reduction Rule 4 follows from Proposition 9. And, in the following lemma, we prove the safeness of this reduction rule.

**► Lemma 10.** $(\star)$ Reduction Rule 4 is safe.