Search Results

Documents authored by Verhaegh, Ruben F. A.

Document
DOI: 10.4230/LIPIcs.IPEC.2024.15
Preprocessing to Reduce the Search Space for Odd Cycle Transversal

Authors: Bart M. P. Jansen, Yosuke Mizutani, Blair D. Sullivan, and Ruben F. A. Verhaegh

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

Abstract
The NP-hard Odd Cycle Transversal problem asks for a minimum vertex set whose removal from an undirected input graph G breaks all odd cycles, and thereby yields a bipartite graph. The problem is well-known to be fixed-parameter tractable when parameterized by the size k of the desired solution. It also admits a randomized kernelization of polynomial size, using the celebrated matroid toolkit by Kratsch and Wahlström. The kernelization guarantees a reduction in the total size of an input graph, but does not guarantee any decrease in the size of the solution to be sought; the latter governs the size of the search space for FPT algorithms parameterized by k. We investigate under which conditions an efficient algorithm can detect one or more vertices that belong to an optimal solution to Odd Cycle Transversal. By drawing inspiration from the popular crown reduction rule for Vertex Cover, and the notion of antler decompositions that was recently proposed for Feedback Vertex Set, we introduce a graph decomposition called tight odd cycle cut that can be used to certify that a vertex set is part of an optimal odd cycle transversal. While it is NP-hard to compute such a graph decomposition, we develop parameterized algorithms to find a set of at least k vertices that belong to an optimal odd cycle transversal when the input contains a tight odd cycle cut certifying the membership of k vertices in an optimal solution. The resulting algorithm formalizes when the search space for the solution-size parameterization of Odd Cycle Transversal can be reduced by preprocessing. To obtain our results, we develop a graph reduction step that can be used to simplify the graph to the point that the odd cycle cut can be detected via color coding.
Cite as

Bart M. P. Jansen, Yosuke Mizutani, Blair D. Sullivan, and Ruben F. A. Verhaegh. Preprocessing to Reduce the Search Space for Odd Cycle Transversal. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.IPEC.2024.15,
  author =	{Jansen, Bart M. P. and Mizutani, Yosuke and Sullivan, Blair D. and Verhaegh, Ruben F. A.},
  title =	{{Preprocessing to Reduce the Search Space for Odd Cycle Transversal}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{15:1--15:18},
  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.15},
  URN =		{urn:nbn:de:0030-drops-222412},
  doi =		{10.4230/LIPIcs.IPEC.2024.15},
  annote =	{Keywords: odd cycle transversal, parameterized complexity, graph decomposition, search-space reduction, witness of optimality}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.28
Search-Space Reduction via Essential Vertices Revisited: Vertex Multicut and Cograph Deletion

Authors: Bart M. P. Jansen and Ruben F. A. Verhaegh

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
For an optimization problem Π on graphs whose solutions are vertex sets, a vertex v is called c-essential for Π if all solutions of size at most c ⋅ opt contain v. Recent work showed that polynomial-time algorithms to detect c-essential vertices can be used to reduce the search space of fixed-parameter tractable algorithms solving such problems parameterized by the size k of the solution. We provide several new upper- and lower bounds for detecting essential vertices. For example, we give a polynomial-time algorithm for 3-Essential detection for Vertex Multicut, which translates into an algorithm that finds a minimum multicut of an undirected n-vertex graph G in time 2^𝒪(𝓁³)⋅n^𝒪(1), where 𝓁 is the number of vertices in an optimal solution that are not 3-essential. Our positive results are obtained by analyzing the integrality gaps of certain linear programs. Our lower bounds show that for sufficiently small values of c, the detection task becomes NP-hard assuming the Unique Games Conjecture. For example, we show that (2-ε)-Essential detection for Directed Feedback Vertex Set is NP-hard under this conjecture, thereby proving that the existing algorithm that detects 2-essential vertices is best-possible.
Cite as

Bart M. P. Jansen and Ruben F. A. Verhaegh. Search-Space Reduction via Essential Vertices Revisited: Vertex Multicut and Cograph Deletion. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.SWAT.2024.28,
  author =	{Jansen, Bart M. P. and Verhaegh, Ruben F. A.},
  title =	{{Search-Space Reduction via Essential Vertices Revisited: Vertex Multicut and Cograph Deletion}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{28:1--28:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.28},
  URN =		{urn:nbn:de:0030-drops-200683},
  doi =		{10.4230/LIPIcs.SWAT.2024.28},
  annote =	{Keywords: fixed-parameter tractability, essential vertices, integrality gap}
}
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