Close relatives (of Feedback Vertex Set), revisited
share
At IPEC 2020, Bergougnoux, Bonnet, Brettell, and Kwon 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 clique-width 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 clique-width 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.
READ FULL TEXT