1 Search Results for "Bumpus, Benjamin Merlin"

Search-Space Reduction via Essential Vertices

Authors: Benjamin Merlin Bumpus, Bart M. P. Jansen, and Jari J. H. de Kroon

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

We investigate preprocessing for vertex-subset problems on graphs. While the notion of kernelization, originating in parameterized complexity theory, is a formalization of provably effective preprocessing aimed at reducing the total instance size, our focus is on finding a non-empty vertex set that belongs to an optimal solution. This decreases the size of the remaining part of the solution which still has to be found, and therefore shrinks the search space of fixed-parameter tractable algorithms for parameterizations based on the solution size. We introduce the notion of a c-essential vertex as one that is contained in all c-approximate solutions. For several classic combinatorial problems such as Odd Cycle Transversal and Directed Feedback Vertex Set, we show that under mild conditions a polynomial-time preprocessing algorithm can find a subset of an optimal solution that contains all 2-essential vertices, by exploiting packing/covering duality. This leads to FPT algorithms to solve these problems where the exponential term in the running time depends only on the number of non-essential vertices in the solution.

Cite as

Benjamin Merlin Bumpus, Bart M. P. Jansen, and Jari J. H. de Kroon. Search-Space Reduction via Essential Vertices. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 30:1-30:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

  author =	{Bumpus, Benjamin Merlin and Jansen, Bart M. P. and de Kroon, Jari J. H.},
  title =	{{Search-Space Reduction via Essential Vertices}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{30:1--30:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.30},
  URN =		{urn:nbn:de:0030-drops-169687},
  doi =		{10.4230/LIPIcs.ESA.2022.30},
  annote =	{Keywords: fixed-parameter tractability, essential vertices, covering versus packing}
  • Refine by Author
  • 1 Bumpus, Benjamin Merlin
  • 1 Jansen, Bart M. P.
  • 1 de Kroon, Jari J. H.

  • Refine by Classification
  • 1 Theory of computation → Fixed parameter tractability
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Linear programming
  • 1 Theory of computation → Packing and covering problems

  • Refine by Keyword
  • 1 covering versus packing
  • 1 essential vertices
  • 1 fixed-parameter tractability

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail