  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.
