Abstract
At IPEC 2020, Bergougnoux, Bonnet, Brettell, and Kwon (Close Relatives of Feedback Vertex Set Without SingleExponential Algorithms Parameterized by Treewidth, IPEC 2020, LIPIcs vol. 180, pp. 3:13: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)} ⋅ ntime 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:121:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772167},
ISSN = {18688969},
year = {2021},
volume = {214},
editor = {Golovach, Petr A. and Zehavi, Meirav},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15404},
URN = {urn:nbn:de:0030drops154049},
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 