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 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 (Bafna et al., in: Algorithms and computations, pp 142–151, 1995; Becker and Geiger in Artif Intell 83:167–188, 1996) and also primal-dual based 2-approximations (Chudak et al. in Oper Res Lett 22(4):111–118, 1998; Fujito in J Algorithms 31(1):211–227, 1999). 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, in: Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms, pp 808–820, SODA, 2016) 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 (in: Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms, pp 808–820, SODA, 2016) 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.