Search Results

Documents authored by Hols, Eva-Maria C.

Document
DOI: 10.4230/LIPIcs.ESA.2020.60
Approximate Turing Kernelization for Problems Parameterized by Treewidth

Authors: Eva-Maria C. Hols, Stefan Kratsch, and Astrid Pieterse

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
We extend the notion of lossy kernelization, introduced by Lokshtanov et al. [STOC 2017], to approximate Turing kernelization. An α-approximate Turing kernel for a parameterized optimization problem is a polynomial-time algorithm that, when given access to an oracle that outputs c-approximate solutions in 𝒪(1) time, obtains an α ⋅ c-approximate solution to the considered problem, using calls to the oracle of size at most f(k) for some function f that only depends on the parameter. Using this definition, we show that Independent Set parameterized by treewidth 𝓁 has a (1+ε)-approximate Turing kernel with 𝒪(𝓁²/ε) vertices, answering an open question posed by Lokshtanov et al. [STOC 2017]. Furthermore, we give (1+ε)-approximate Turing kernels for the following graph problems parameterized by treewidth: Vertex Cover, Edge Clique Cover, Edge-Disjoint Triangle Packing and Connected Vertex Cover. We generalize the result for Independent Set and Vertex Cover, by showing that all graph problems that we will call friendly admit (1+ε)-approximate Turing kernels of polynomial size when parameterized by treewidth. We use this to obtain approximate Turing kernels for Vertex-Disjoint H-packing for connected graphs H, Clique Cover, Feedback Vertex Set and Edge Dominating Set.
Cite as

Eva-Maria C. Hols, Stefan Kratsch, and Astrid Pieterse. Approximate Turing Kernelization for Problems Parameterized by Treewidth. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 60:1-60:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hols_et_al:LIPIcs.ESA.2020.60,
  author =	{Hols, Eva-Maria C. and Kratsch, Stefan and Pieterse, Astrid},
  title =	{{Approximate Turing Kernelization for Problems Parameterized by Treewidth}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{60:1--60:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.60},
  URN =		{urn:nbn:de:0030-drops-129261},
  doi =		{10.4230/LIPIcs.ESA.2020.60},
  annote =	{Keywords: Approximation, Turing kernelization, Graph problems, Treewidth}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.36
Elimination Distances, Blocking Sets, and Kernels for Vertex Cover

Authors: Eva-Maria C. Hols, Stefan Kratsch, and Astrid Pieterse

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
The Vertex Cover problem plays an essential role in the study of polynomial kernelization in parameterized complexity, i.e., the study of provable and efficient preprocessing for NP-hard problems. Motivated by the great variety of positive and negative results for kernelization for Vertex Cover subject to different parameters and graph classes, we seek to unify and generalize them using so-called blocking sets. A blocking set is a set of vertices such that no optimal vertex cover contains all vertices in the blocking set, and the study of minimal blocking sets played implicit and explicit roles in many existing results. We show that in the most-studied setting, parameterized by the size of a deletion set to a specified graph class ?, bounded minimal blocking set size is necessary but not sufficient to get a polynomial kernelization. Under mild technical assumptions, bounded minimal blocking set size is showed to allow an essentially tight efficient reduction in the number of connected components. We then determine the exact maximum size of minimal blocking sets for graphs of bounded elimination distance to any hereditary class ?, including the case of graphs of bounded treedepth. We get similar but not tight bounds for certain non-hereditary classes ?, including the class ?_{LP} of graphs where integral and fractional vertex cover size coincide. These bounds allow us to derive polynomial kernels for Vertex Cover parameterized by the size of a deletion set to graphs of bounded elimination distance to, e.g., forest, bipartite, or ?_{LP} graphs.
Cite as

Eva-Maria C. Hols, Stefan Kratsch, and Astrid Pieterse. Elimination Distances, Blocking Sets, and Kernels for Vertex Cover. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hols_et_al:LIPIcs.STACS.2020.36,
  author =	{Hols, Eva-Maria C. and Kratsch, Stefan and Pieterse, Astrid},
  title =	{{Elimination Distances, Blocking Sets, and Kernels for Vertex Cover}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{36:1--36:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.36},
  URN =		{urn:nbn:de:0030-drops-118974},
  doi =		{10.4230/LIPIcs.STACS.2020.36},
  annote =	{Keywords: Vertex Cover, kernelization, blocking sets, elimination distance, structural parameters}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.36
On Kernelization for Edge Dominating Set under Structural Parameters

Authors: Eva-Maria C. Hols and Stefan Kratsch

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
In the NP-hard Edge Dominating Set problem (EDS) we are given a graph G=(V,E) and an integer k, and need to determine whether there is a set F subseteq E of at most k edges that are incident with all (other) edges of G. It is known that this problem is fixed-parameter tractable and admits a polynomial kernelization when parameterized by k. A caveat for this parameter is that it needs to be large, i.e., at least equal to half the size of a maximum matching of G, for instances not to be trivially negative. Motivated by this, we study the existence of polynomial kernelizations for EDS when parameterized by structural parameters that may be much smaller than k. Unfortunately, at first glance this looks rather hopeless: Even when parameterized by the deletion distance to a disjoint union of paths P_3 of length two there is no polynomial kernelization (under standard assumptions), ruling out polynomial kernelizations for many smaller parameters like the feedback vertex set size. In contrast, somewhat surprisingly, there is a polynomial kernelization for deletion distance to a disjoint union of paths P_5 of length four. As our main result, we fully classify for all finite sets H of graphs, whether a kernel size polynomial in |X| is possible when given X such that each connected component of G-X is isomorphic to a graph in H.
Cite as

Eva-Maria C. Hols and Stefan Kratsch. On Kernelization for Edge Dominating Set under Structural Parameters. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 36:1-36:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{hols_et_al:LIPIcs.STACS.2019.36,
  author =	{Hols, Eva-Maria C. and Kratsch, Stefan},
  title =	{{On Kernelization for Edge Dominating Set under Structural Parameters}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{36:1--36:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.36},
  URN =		{urn:nbn:de:0030-drops-102752},
  doi =		{10.4230/LIPIcs.STACS.2019.36},
  annote =	{Keywords: Edge dominating set, kernelization, structural parameters}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2017.20
Smaller Parameters for Vertex Cover Kernelization

Authors: Eva-Maria C. Hols and Stefan Kratsch

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Abstract
We revisit the topic of polynomial kernels for Vertex Cover relative to structural parameters. Our starting point is a recent paper due to Fomin and Strømme [WG 2016] who gave a kernel with O(|X|^{12}) vertices when X is a vertex set such that each connected component of G-X contains at most one cycle, i.e., X is a modulator to a pseudoforest. We strongly generalize this result by using modulators to d-quasi-forests, i.e., graphs where each connected component has a feedback vertex set of size at most d, and obtain kernels with O(|X|^{3d+9}) vertices. Our result relies on proving that minimal blocking sets in a d-quasi-forest have size at most d+2. This bound is tight and there is a related lower bound of O(|X|^{d+2-epsilon}) on the bit size of kernels. In fact, we also get bounds for minimal blocking sets of more general graph classes: For d-quasi-bipartite graphs, where each connected component can be made bipartite by deleting at most d vertices, we get the same tight bound of d+2 vertices. For graphs whose connected components each have a vertex cover of cost at most d more than the best fractional vertex cover, which we call d-quasi-integral, we show that minimal blocking sets have size at most 2d+2, which is also tight. Combined with existing randomized polynomial kernelizations this leads to randomized polynomial kernelizations for modulators to d-quasi-bipartite and d-quasi-integral graphs. There are lower bounds of O(|X|^{d+2-epsilon}) and O(|X|^{2d+2-epsilon}) for the bit size of such kernels.
Cite as

Eva-Maria C. Hols and Stefan Kratsch. Smaller Parameters for Vertex Cover Kernelization. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 20:1-20:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hols_et_al:LIPIcs.IPEC.2017.20,
  author =	{Hols, Eva-Maria C. and Kratsch, Stefan},
  title =	{{Smaller Parameters for Vertex Cover Kernelization}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{20:1--20:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.20},
  URN =		{urn:nbn:de:0030-drops-85638},
  doi =		{10.4230/LIPIcs.IPEC.2017.20},
  annote =	{Keywords: Vertex Cover, Kernelization, Structural Parameterization}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.35
Preprocessing Under Uncertainty: Matroid Intersection

Authors: Stefan Fafianie, Eva-Maria C. Hols, Stefan Kratsch, and Vuong Anh Quyen

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
We continue the study of preprocessing under uncertainty that was initiated independently by Assadi et al. (FSTTCS 2015) and Fafianie et al. (STACS 2016). Here, we are given an instance of a tractable problem with a large static/known part and a small part that is dynamic/uncertain, and ask if there is an efficient algorithm that computes an instance of size polynomial in the uncertain part of the input, from which we can extract an optimal solution to the original instance for all (usually exponentially many) instantiations of the uncertain part. In the present work, we focus on the Matroid Intersection problem. Amongst others we present a positive preprocessing result for the important case of finding a largest common independent set in two linear matroids. Motivated by an application for intersecting two gammoids we also revisit Maximum Flow. There we tighten a lower bound of Assadi et al. and give an alternative positive result for the case of low uncertain capacity that yields a Maximum Flow instance as output rather than a matrix.
Cite as

Stefan Fafianie, Eva-Maria C. Hols, Stefan Kratsch, and Vuong Anh Quyen. Preprocessing Under Uncertainty: Matroid Intersection. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 35:1-35:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{fafianie_et_al:LIPIcs.MFCS.2016.35,
  author =	{Fafianie, Stefan and Hols, Eva-Maria C. and Kratsch, Stefan and Quyen, Vuong Anh},
  title =	{{Preprocessing Under Uncertainty: Matroid Intersection}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{35:1--35:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.35},
  URN =		{urn:nbn:de:0030-drops-64490},
  doi =		{10.4230/LIPIcs.MFCS.2016.35},
  annote =	{Keywords: preprocessing, uncertainty, maximum flow, matroid intersection}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.43
A Randomized Polynomial Kernel for Subset Feedback Vertex Set

Authors: Eva-Maria C. Hols and Stefan Kratsch

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
The SUBSET FEEDBACK VERTEX SET problem generalizes the classical FEEDBACK VERTEX SET problem and asks, for a given undirected graph G=(V,E), a set S subseteq V, and an integer k, whether there exists a set X of at most k vertices such that no cycle in G-X contains a vertex of S. It was independently shown by Cygan et al. (ICALP'11, SIDMA'13) and Kawarabayashi and Kobayashi (JCTB'12) that SUBSET FEEDBACK VERTEX SET is fixed-parameter tractable for parameter k. Cygan et al. asked whether the problem also admits a polynomial kernelization. We answer the question of Cygan et al. positively by giving a randomized polynomial kernelization for the equivalent version where S is a set of edges. In a first step we show that EDGE SUBSET FEEDBACK VERTEX SET has a randomized polynomial kernel parameterized by |S|+k with O(|S|^2k) vertices. For this we use the matroid-based tools of Kratsch and Wahlstrom (FOCS'12). Next we present a preprocessing that reduces the given instance (G,S,k) to an equivalent instance (G',S',k') where the size of S' is bounded by O(k^4). These two results lead to a polynomial kernel for SUBSET FEEDBACK VERTEX SET with O(k^9) vertices.
Cite as

Eva-Maria C. Hols and Stefan Kratsch. A Randomized Polynomial Kernel for Subset Feedback Vertex Set. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 43:1-43:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{hols_et_al:LIPIcs.STACS.2016.43,
  author =	{Hols, Eva-Maria C. and Kratsch, Stefan},
  title =	{{A Randomized Polynomial Kernel for Subset Feedback Vertex Set}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{43:1--43:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.43},
  URN =		{urn:nbn:de:0030-drops-57448},
  doi =		{10.4230/LIPIcs.STACS.2016.43},
  annote =	{Keywords: parameterized complexity, kernelization, subset feedback vertex set}
}
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