Polyhedral Aspects of Feedback Vertex Set and Pseudoforest Deletion Set

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 least cost subset of vertices $S \subseteq V$ such that $G-S$ is acyclic. FVS is a well-known NP-hard problem with no $(2-\epsilon)$-approximation assuming the Unique Games Conjecture and it admits a $2$-approximation via combinatorial local-ratio methods (Bafna, Berman and Fujito, Algorithms and Computations '95; Becker and Geiger, Artificial Intelligence '96) which can also be interpreted as LP-based primal-dual algorithms (Chudak, Goemans, Hochbaum and Williamson, Operations Research Letters '98). 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.