Search Results

Documents authored by Kunz, Pascal

Document
DOI: 10.4230/LIPIcs.IPEC.2023.32
Approximate Turing Kernelization and Lower Bounds for Domination Problems

Authors: Stefan Kratsch and Pascal Kunz

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
An α-approximate polynomial Turing kernelization is a polynomial-time algorithm that computes an (α c)-approximate solution for a parameterized optimization problem when given access to an oracle that can compute c-approximate solutions to instances with size bounded by a polynomial in the parameter. Hols et al. [ESA 2020] showed that a wide array of graph problems admit a (1+ε)-approximate polynomial Turing kernelization when parameterized by the treewidth of the graph and left open whether Dominating Set also admits such a kernelization. We show that Dominating Set and several related problems parameterized by treewidth do not admit constant-factor approximate polynomial Turing kernelizations, even with respect to the much larger parameter vertex cover number, under certain reasonable complexity assumptions. On the positive side, we show that all of them do have a (1+ε)-approximate polynomial Turing kernelization for every ε > 0 for the joint parameterization by treewidth and maximum degree, a parameter which generalizes cutwidth, for example.
Cite as

Stefan Kratsch and Pascal Kunz. Approximate Turing Kernelization and Lower Bounds for Domination Problems. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kratsch_et_al:LIPIcs.IPEC.2023.32,
  author =	{Kratsch, Stefan and Kunz, Pascal},
  title =	{{Approximate Turing Kernelization and Lower Bounds for Domination Problems}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{32:1--32:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.32},
  URN =		{urn:nbn:de:0030-drops-194516},
  doi =		{10.4230/LIPIcs.IPEC.2023.32},
  annote =	{Keywords: Approximate Turing kernelization, approximation lower bounds, exponential-time hypothesis, dominating set, capacitated dominating, connected dominating set, independent dominating set, treewidth, vertex cover number}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2022.19
Vertex Cover and Feedback Vertex Set Above and Below Structural Guarantees

Authors: Leon Kellerhals, Tomohiro Koana, and Pascal Kunz

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

Abstract
Vertex Cover parameterized by the solution size k is the quintessential fixed-parameter tractable problem. FPT algorithms are most interesting when the parameter is small. Several lower bounds on k are well-known, such as the maximum size of a matching. This has led to a line of research on parameterizations of Vertex Cover by the difference of the solution size k and a lower bound. The most prominent cases for such lower bounds for which the problem is FPT are the matching number or the optimal fractional LP solution. We investigate parameterizations by the difference between k and other graph parameters including the feedback vertex number, the degeneracy, cluster deletion number, and treewidth with the goal of finding the border of fixed-parameter tractability for said difference parameterizations. We also consider similar parameterizations of the Feedback Vertex Set problem.
Cite as

Leon Kellerhals, Tomohiro Koana, and Pascal Kunz. Vertex Cover and Feedback Vertex Set Above and Below Structural Guarantees. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kellerhals_et_al:LIPIcs.IPEC.2022.19,
  author =	{Kellerhals, Leon and Koana, Tomohiro and Kunz, Pascal},
  title =	{{Vertex Cover and Feedback Vertex Set Above and Below Structural Guarantees}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.19},
  URN =		{urn:nbn:de:0030-drops-173758},
  doi =		{10.4230/LIPIcs.IPEC.2022.19},
  annote =	{Keywords: parameterized complexity, vertex cover, feedback vertex set, above guarantee parameterization}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.29
Most Classic Problems Remain NP-Hard on Relative Neighborhood Graphs and Their Relatives

Authors: Pascal Kunz, Till Fluschnik, Rolf Niedermeier, and Malte Renken

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
Proximity graphs have been studied for several decades, motivated by applications in computational geometry, geography, data mining, and many other fields. However, the computational complexity of classic graph problems on proximity graphs mostly remained open. We study 3-Colorability, Dominating Set, Feedback Vertex Set, Hamiltonian Cycle, and Independent Set on the following classes of proximity graphs: relative neighborhood graphs, Gabriel graphs, and relatively closest graphs. We prove that all of the aforementioned problems remain NP-hard on these graphs, except for 3-Colorability and Hamiltonian Cycle on relatively closest graphs, where the former is trivial and the latter is left open. Moreover, for every NP-hard case we additionally show that no 2^{o(n^{1/4})}-time algorithm exists unless the Exponential-Time Hypothesis (ETH) fails, where n denotes the number of vertices.
Cite as

Pascal Kunz, Till Fluschnik, Rolf Niedermeier, and Malte Renken. Most Classic Problems Remain NP-Hard on Relative Neighborhood Graphs and Their Relatives. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 29:1-29:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kunz_et_al:LIPIcs.SWAT.2022.29,
  author =	{Kunz, Pascal and Fluschnik, Till and Niedermeier, Rolf and Renken, Malte},
  title =	{{Most Classic Problems Remain NP-Hard on Relative Neighborhood Graphs and Their Relatives}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{29:1--29:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.29},
  URN =		{urn:nbn:de:0030-drops-161891},
  doi =		{10.4230/LIPIcs.SWAT.2022.29},
  annote =	{Keywords: Proximity Graphs, Relatively Closest Graphs, Gabriel Graphs, 3-Colorability, Dominating Set, Feedback Vertex Set, Hamiltonian Cycle, Independent Set, Exponential-Time Hypothesis}
}
Document
DOI: 10.4230/LIPIcs.SAND.2022.16
Bipartite Temporal Graphs and the Parameterized Complexity of Multistage 2-Coloring

Authors: Till Fluschnik and Pascal Kunz

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract
We consider the algorithmic complexity of recognizing bipartite temporal graphs. Rather than defining these graphs solely by their underlying graph or individual layers, we define a bipartite temporal graph as one in which every layer can be 2-colored in a way that results in few changes between any two consecutive layers. This approach follows the framework of multistage problems that has received a growing amount of attention in recent years. We investigate the complexity of recognizing these graphs. We show that this problem is NP-hard even if there are only two layers or if only one change is allowed between consecutive layers. We consider the parameterized complexity of the problem with respect to several structural graph parameters, which we transfer from the static to the temporal setting in three different ways. Finally, we consider a version of the problem in which we only restrict the total number of changes throughout the lifetime of the graph. We show that this variant is fixed-parameter tractable with respect to the number of changes.
Cite as

Till Fluschnik and Pascal Kunz. Bipartite Temporal Graphs and the Parameterized Complexity of Multistage 2-Coloring. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fluschnik_et_al:LIPIcs.SAND.2022.16,
  author =	{Fluschnik, Till and Kunz, Pascal},
  title =	{{Bipartite Temporal Graphs and the Parameterized Complexity of Multistage 2-Coloring}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.16},
  URN =		{urn:nbn:de:0030-drops-159587},
  doi =		{10.4230/LIPIcs.SAND.2022.16},
  annote =	{Keywords: structural parameters, NP-hardness, parameterized algorithms, multistage problems}
}
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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact