Search Results

Documents authored by Greilhuber, Jakob

Document
DOI: 10.4230/LIPIcs.MFCS.2026.8
A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth

Authors: Jakob Greilhuber and Roohani Sharma

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract
In this work we study a classic generalization of the ubiquitous Vertex Cover (VC) problem, called the Component Order Connectivity (COC) problem. In COC, given an undirected graph G, integers d ≥ 1 and k, the goal is to determine if there is a set of at most k vertices whose deletion results in a graph where each connected component has at most d vertices. When d = 1, this is exactly VC. This work is inspired by polynomial kernelization results with respect to structural parameters for VC. On one hand, Jansen & Bodlaender [TOCS 2013] show that VC admits a polynomial kernel when the parameter is the distance to treewidth-1 graphs, on the other hand Cygan, Lokshtanov, Pilipczuk, Pilipczuk & Saurabh [TOCS 2014] showed that VC does not admit a polynomial kernel when the parameter is distance to treewidth-2 graphs. Greilhuber & Sharma [IPEC 2024] showed that, for any d ≥ 2, d-COC cannot admit a polynomial kernel when the parameter is distance to a forest of pathwidth 2. Here, d-COC is the variant of COC where d is a fixed constant rather than part of the input. We complement this result and show that, analogously to the VC setting, where distance to treewidth-1 graphs versus distance to treewidth-2 graphs is the dividing line between structural parameterizations that admit and respectively do not admit polynomial kernelization, for COC this dividing line lies between distance to pathwidth-1 graphs and distance to pathwidth-2 graphs. The main technical result of this work is that COC admits a polynomial kernel parameterized by distance to pathwidth-1 graphs plus d. The problem d-COC can also be expressed as an ℱ-MinorDeletion problem for an appropriate graph family ℱ. One of the central questions around ℱ-MinorDeletion is for which families ℱ and minor-closed graph classes 𝒢 the problem admits a polynomial kernel when parameterized by the distance to 𝒢. For some families ℱ complete dichotomies answering this question are known [Bougeret et al., SIDMA 2022][Bougeret et al., STACS 2026][Bougeret et al., arXiv 2026]. But, these results do not capture the 2-COC problem. We show that, when d ≥ 2, the line of tractability for polynomial kernelization of d-COC parameterized by the distance to 𝒢 is different from the tractability line of the ℱ-MinorDeletion problems for which the currently known dichotomies apply. Thus, with our result, d-COC serves as an outlier in the class of ℱ-MinorDeletion problems when it comes to understanding the dichotomies for polynomial kernelization when parameterizing by the distance to some minor-closed graph class.
Cite as

Jakob Greilhuber and Roohani Sharma. A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{greilhuber_et_al:LIPIcs.MFCS.2026.8,
  author =	{Greilhuber, Jakob and Sharma, Roohani},
  title =	{{A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{8:1--8:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.8},
  URN =		{urn:nbn:de:0030-drops-273890},
  doi =		{10.4230/LIPIcs.MFCS.2026.8},
  annote =	{Keywords: Kernelization, Component Order Connectivity, Caterpillars, Pathwidth, Structural Parameterization}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.41
Residue Domination in Bounded-Treewidth Graphs

Authors: Jakob Greilhuber, Philipp Schepper, and Philip Wellnitz

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
For the vertex selection problem (σ,ρ)-DomSet one is given two fixed sets σ and ρ of integers and the task is to decide whether we can select vertices of the input graph such that, for every selected vertex, the number of selected neighbors is in σ and, for every unselected vertex, the number of selected neighbors is in ρ [Telle, Nord. J. Comp. 1994]. This framework covers many fundamental graph problems such as Independent Set and Dominating Set. We significantly extend the recent result by Focke et al. [SODA 2023] to investigate the case when σ and ρ are two (potentially different) residue classes modulo m ≥ 2. We study the problem parameterized by treewidth and present an algorithm that solves in time m^tw ⋅ n^O(1) the decision, minimization and maximization version of the problem. This significantly improves upon the known algorithms where for the case m ≥ 3 not even an explicit running time is known. We complement our algorithm by providing matching lower bounds which state that there is no (m-ε)^pw ⋅ n^O(1)-time algorithm parameterized by pathwidth pw, unless SETH fails. For m = 2, we extend these bounds to the minimization version as the decision version is efficiently solvable.
Cite as

Jakob Greilhuber, Philipp Schepper, and Philip Wellnitz. Residue Domination in Bounded-Treewidth Graphs. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 41:1-41:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{greilhuber_et_al:LIPIcs.STACS.2025.41,
  author =	{Greilhuber, Jakob and Schepper, Philipp and Wellnitz, Philip},
  title =	{{Residue Domination in Bounded-Treewidth Graphs}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{41:1--41:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.41},
  URN =		{urn:nbn:de:0030-drops-228675},
  doi =		{10.4230/LIPIcs.STACS.2025.41},
  annote =	{Keywords: Parameterized Complexity, Treewidth, Generalized Dominating Set, Strong Exponential Time Hypothesis}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2024.21
Component Order Connectivity Admits No Polynomial Kernel Parameterized by the Distance to Subdivided Comb Graphs

Authors: Jakob Greilhuber and Roohani Sharma

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

Abstract
In this paper we show that the d-Component Order Connectivity (d-COC) problem parameterized by the distance to subdivided comb graphs (dist-to-subdivided-combs) does not admit a polynomial kernel, unless NP ⊆ coNP/poly. The d-COC problem is a generalization of the classical Vertex Cover problem. An instance of the d-COC problem consists of an undirected graph G and a positive integer k, and the question is whether there exists a set S ⊆ V(G) of size at most k, such that each connected component of G-S contains at most d vertices. When d = 1, d-COC is the Vertex Cover problem. Vertex Cover is a ubiquitous problem in parameterized complexity, and it admits a kernel with O(k²) edges and O(k) vertices, which is tight [Dell & van Melkebeek, JACM 2014]. Our result is inspired by the work of Jansen & Bodlaender [TOCS 2013], who gave the first polynomial kernel for Vertex Cover where the parameter is provably smaller or equal to the standard parameter, solution size k. They used fvs, the feedback vertex set number, as the parameter. In this work, we show that unlike most other existing results or techniques for kernelization of Vertex Cover that generalize to d-COC, this is not the case when dist-to-subdivided-combs, which is at least as large as fvs, is the parameter. Our lower bound is achieved in two stages. In the first stage we extend the result of Hols, Kratsch & Pieterse [SIDMA 2022] where they show that if a graph family 𝒞, which is closed under taking disjoint unions, has unbounded "blocking set" size, then Vertex Cover does not admit a polynomial kernel parameterized by the size of a vertex modulator to 𝒞, unless NP ⊆ coNP/poly. We show that a similar sufficient condition for proving the non-existence of polynomial kernels also holds for d-COC. In the second stage, we show that when 𝒞 is the family of subdivided comb graphs, contrary to Vertex Cover, where the size of minimal blocking sets of graphs in 𝒞 is at most two [Jansen & Bodlaender, STACS 2011], the size of minimal blocking sets of graphs in 𝒞 for the d-COC problem can be arbitrarily large. This yields the desired lower bound. In addition to this we also show that when 𝒞 is a class of paths, then it still has blocking sets of size at most two for d-COC, indicating that polynomial kernels might be achievable when the parameter is the size of a vertex modulator to the class of disjoint unions of paths (linear forests).
Cite as

Jakob Greilhuber and Roohani Sharma. Component Order Connectivity Admits No Polynomial Kernel Parameterized by the Distance to Subdivided Comb Graphs. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 21:1-21:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{greilhuber_et_al:LIPIcs.IPEC.2024.21,
  author =	{Greilhuber, Jakob and Sharma, Roohani},
  title =	{{Component Order Connectivity Admits No Polynomial Kernel Parameterized by the Distance to Subdivided Comb Graphs}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{21:1--21:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.21},
  URN =		{urn:nbn:de:0030-drops-222471},
  doi =		{10.4230/LIPIcs.IPEC.2024.21},
  annote =	{Keywords: Component Order Connectivity, Kernelization, Structural Parameterizations, Feedback Vertex Set, Vertex Cover, Blocking Sets, Subdivided Comb Graphs}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact