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^{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.