Close relatives (of Feedback Vertex Set) revisited
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 log k) nO(1) time algorithm on graphs of treewidth at most k, assuming the Exponential Time Hypothesis. This contrasts with the 3 kO(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 2O(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 2O(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 kO(1) n if the input graph is given as a cliquewidth expression of size n and width k. Furthermore, the existence of a constant e 0 and an algorithm performing this task in time (4 e) nO(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 O(k) nodes. This results in a 2O(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 kO(1) time, resulting in linear time dependency on the size of the graph or the input cliquewidth expression.
ArXiv