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/
Jacob, Hugo ;
Bellitto, Thomas ;
Defrain, Oscar ;
Pilipczuk, Marcin
Close Relatives (Of Feedback Vertex Set), Revisited
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 |
