2023/03/22 by Karthekeyan Chandrasekaran, Chandra Chekuri, Chandrasekaran, Karthekeyan +7
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Approximation algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computation #Computer science #Conjecture #Data Structures and Algorithms (cs.DS) #Discrete mathematics #FOS: Computer and information sciences #Feedback vertex set #Graph #Linear programming #Linear programming relaxation #Mathematics #Optimization and Search Problems #Parameterized complexity #Relaxation (psychology) #Set (abstract data type) #Time complexity #Undirected graph #Vertex (graph theory)
paper · pdf · doi:10.48550/arxiv.2303.12850
openalex publication_date 2023/03/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
We consider the feedback vertex set problem in undirected graphs (FVS). The input to FVS is an undirected graph G=(V,E) with non-negative vertex costs. The goal is to find a minimum cost subset of vertices S ⊆ V such that G-S is acyclic. FVS is a well-known NP-hard problem and does not admit a (2-ε)-approximation for any fixed ε> 0 assuming the Unique Games Conjecture. There are combinatorial 2-approximation algorithms and also primal-dual based 2-approximations. Despite the existence of these algorithms for several decades, there is no known polynomial-time solvable LP relaxation for FVS with a provable integrality gap of at most 2. More recent work (Chekuri and Madan, SODA '16) developed a polynomial-sized LP relaxation for a more general problem, namely Subset FVS, and showed that its integrality gap is at most 13 for Subset FVS, and hence also for FVS. Motivated by this gap in our knowledge, we undertake a polyhedral study of FVS and related problems. In this work, we formulate new integer linear programs (ILPs) for FVS whose LP-relaxation can be solved in polynomial time, and whose integrality gap is at most 2. The new insights in this process also enable us to prove that the formulation in (Chekuri and Madan, SODA '16) has an integrality gap of at most 2 for FVS. Our results for FVS are inspired by new formulations and polyhedral results for the closely-related pseudoforest deletion set problem (PFDS). Our formulations for PFDS are in turn inspired by a connection to the densest subgraph problem. We also conjecture an extreme point property for a LP-relaxation for FVS, and give evidence for the conjecture via a corresponding result for PFDS.