2021/06/30 by Hugo Jacob, Jacob, Hugo, Thomas Bellitto +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · doi:10.48550/arxiv.2106.16015
openalex publication_date 2021/06/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 2o(k log k) ⋅ nO(1)-time algorithm on graphs of treewidth at most k, assuming the Exponential Time Hypothesis. This contrasts with the 3k ⋅ 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 clique-width expression of size n and width k. - Odd Cycle Transversal can be solved in time 4k ⋅ kO(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 ⋅ nO(1) would contradict the Strong Exponential Time Hypothesis.