License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2021.21
URN: urn:nbn:de:0030-drops-154049
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15404/
Go to the corresponding LIPIcs Volume Portal


Jacob, Hugo ; Bellitto, Thomas ; Defrain, Oscar ; Pilipczuk, Marcin

Close Relatives (Of Feedback Vertex Set), Revisited

pdf-format:
LIPIcs-IPEC-2021-21.pdf (1 MB)


Abstract

At IPEC 2020, Bergougnoux, Bonnet, Brettell, and Kwon (Close Relatives of Feedback Vertex Set Without Single-Exponential Algorithms Parameterized by Treewidth, IPEC 2020, LIPIcs vol. 180, pp. 3:1-3:17) showed that a number of problems related to the classic Feedback Vertex Set (FVS) problem do not admit a 2^{o(k log k)} ⋅ n^{?(1)}-time algorithm on graphs of treewidth at most k, assuming the Exponential Time Hypothesis. This contrasts with the 3^{k} ⋅ k^{?(1)} ⋅ n-time algorithm for FVS using the Cut&Count technique.
During their live talk at IPEC 2020, Bergougnoux et al. posed a number of open questions, which we answer in this work.
- Subset Even Cycle Transversal, Subset Odd Cycle Transversal, Subset Feedback Vertex Set can be solved in time 2^{?(k log k)} ⋅ n in graphs of treewidth at most k. This matches a lower bound for Even Cycle Transversal of Bergougnoux et al. and improves the polynomial factor in some of their upper bounds.
- Subset Feedback Vertex Set and Node Multiway Cut can be solved in time 2^{?(k log k)} ⋅ n, if the input graph is given as a cliquewidth expression of size n and width k.
- Odd Cycle Transversal can be solved in time 4^k ⋅ k^{?(1)} ⋅ n if the input graph is given as a cliquewidth expression of size n and width k. Furthermore, the existence of a constant ε > 0 and an algorithm performing this task in time (4-ε)^k ⋅ n^{?(1)} would contradict the Strong Exponential Time Hypothesis. A common theme of the first two algorithmic results is to represent connectivity properties of the current graph in a state of a dynamic programming algorithm as an auxiliary forest with ?(k) nodes. This results in a 2^{?(k log k)} bound on the number of states for one node of the tree decomposition or cliquewidth expression and allows to compare two states in k^{?(1)} time, resulting in linear time dependency on the size of the graph or the input cliquewidth expression.

BibTeX - Entry

@InProceedings{jacob_et_al:LIPIcs.IPEC.2021.21,
  author =	{Jacob, Hugo and Bellitto, Thomas and Defrain, Oscar and Pilipczuk, Marcin},
  title =	{{Close Relatives (Of Feedback Vertex Set), Revisited}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15404},
  URN =		{urn:nbn:de:0030-drops-154049},
  doi =		{10.4230/LIPIcs.IPEC.2021.21},
  annote =	{Keywords: feedback vertex set, treewidth, cliquewidth}
}

Keywords: feedback vertex set, treewidth, cliquewidth
Collection: 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Issue Date: 2021
Date of publication: 22.11.2021


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI