Search Results

Documents authored by Greilhuber, Jakob

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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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