s10107-024-02179-9

Mathematical Programming
https://doi.org/10.1007/s10107-024-02179-9
FULL LENGTH PAPER

Series A
Polyhedral aspects of feedback vertex set and pseudoforest

deletion set
Karthekeyan Chandrasekaran1 · Chandra Chekuri1 · Samuel Fiorini2 ·

Shubhang Kulkarni1 · Stefan Weltge3
Received: 25 March 2023 / Accepted: 16 November 2024

© Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2024
Abstract
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
Supported in part by NSF grants CCF-1814613, CCF-1907937, and CCF-2402667. Supported in part by
NSF grants CCF-1910149 and CCF-1907937. Supported in part by Deutsche Forschungsgemeinschaft
(DFG, German Research Foundation), project number 451026932.
B Karthekeyan Chandrasekaran
karthe@illinois.edu
Chandra Chekuri
chekuri@illinois.edu
Samuel Fiorini
sfiorini@ulb.ac.de
Shubhang Kulkarni
smkulka2@illinois.edu
Stefan Weltge
weltge@tum.de
1 University of Illinois, Urbana-Champaign, Urbana, USA

2 Université libre de Bruxelles, Brussels, Belgium
3 Technische Universität München, Munich, Germany
123
K. Chandrasekaran et al.
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.
Contents
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 Pseudoforest deletion set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1 Orientation and 2-pseudotree cover constraints . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Extreme point property of the weak density polyhedron . . . . . . . . . . . . . . . . . . . . . .
3.2.1 Background on supermodular functions and set families . . . . . . . . . . . . . . . . . .
3.2.2 Conditional supermodularity of weak density constraints . . . . . . . . . . . . . . . . . .
3.2.3 Conditional properties of tight sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.4 Conditional basis structure for extreme points . . . . . . . . . . . . . . . . . . . . . . . .
3.2.5 Proof of Theorem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Extreme point property of the orientation polyhedron . . . . . . . . . . . . . . . . . . . . . . .
4 Feedback vertex set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1 Weak density and cycle cover constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1 Minimal FVS and weak density constraints . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.2 Proof of integrality gap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Orientation and cycle cover constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Alternative formulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A Pseudoforest deletion set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.1 Polynomial-time separation oracle for 2-pseudotree cover constraints . . . . . . . . . . . . . .
B Feedback vertex set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.1 Polynomial-sized formulation of the cycle cover polyhedron . . . . . . . . . . . . . . . . . . .
B.2 Chekuri–Madan formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.2.1 Chekuri–Madan’s ILP for SFVS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.2.2 Reduction from FVS to SFVS satisfying the CM-properties . . . . . . . . . . . . . . . .
B.2.3 Bounding the integrality gap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.3 Orientation formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 Introduction
We consider the feedback vertex set problem in undirected graphs. For a graph
G = (V , E), a subset U ⊆ V is a feedback vertex set if G − U is acyclic; in
other words U is a hitting set for the cycles of G. In the feedback vertex set prob-
lem (FVS), the input is an undirected graph G = (V , E) with non-negative vertex
123
Polyhedral aspects of feedback vertex set and pseudoforest…
costs c :V → R≥0 and the goal is to find a feedback vertex set of minimum cost,
i.e., min u∈U c(u) : U ⊆ V and U is a feedback vertex set for G . FVS is a funda-
mental vertex deletion problem in the field of combinatorial optimization and appears
in Karp’s list of 21 NP-Complete problems (as a decision version). We consider the
approximability of FVS, in particular via polynomial-time solvable polyhedral for-
mulations. First, we mention some known lower bounds. Via a simple reduction, the
well-known weighted vertex cover problem can be reduced to FVS in an approxima-
tion preserving fashion. Hence, known results for the vertex cover problem imply that
there is no polynomial-time (2 − )-approximation for every fixed constant > 0
under the Unique Games Conjecture (UGC) [15] and that there is no polynomial-
time (1.36 − )-approximation for every fixed constant > 0 under the P = N P
assumption [9].
Approximation algorithms for the unweighted version of FVS (UFVS), i.e., when
all vertex costs are one, have been studied since 1980s. An O(log n)-approximation
for UFVS is implicit in the work of Erdös and Pósa [12]; Monien and Schulz √ [17]
seem to be the first ones to explicitly study the problem, and obtained an O( log n)-
approximation for UFVS. Bar-Yehuda, Geiger, Naor, and Roth [5] improved the ratio
for UFVS to 4, and also noted that an O(log n)-approximation holds for FVS. Soon
after that, Bafna, Berman, and Fujito [1], and independently Becker and Geiger [2],
obtained 2-approximation algorithms for FVS. While [1] explicitly uses the local-ratio
terminology, [2] describes the algorithm in a purely combinatorial fashion. Although
the algorithm in [1] is described via the local-ratio method, the underlying LP relax-
ation is not obvious. As observed in [5], the natural hitting set LP relaxation for FVS
has an integrality gap of (log n). Chudak, Goemans, Hochbaum, and Williamson [6]
described exponential sized integer linear programming (ILP) formulations for FVS,
and showed that the algorithms in [1, 2] can be viewed as primal-dual algorithms with
respect to the LP relaxations of these formulations. This also established that these
LP relaxations have an integrality gap of at most 2. Fujito [13] considered a unified
generalization of FVS and vertex cover, namely matroidal FVS, and gave a O(log n)-
approximation for matroidal FVS via connections to submodular set cover. In the same
work, Fujito formulated an exponential sized ILP for matroidal FVS, and designed a
primal-dual algorithm with respect to its LP relaxation. He proved that the algorithm
has an approximation ratio of 2 for a certain family of matroids. When specialized to
FVS, we note that the ILP and the resulting primal-dual algorithm in [13] is slightly
different from the one in [6] although they both yield 2-approximations.
We recall the integer linear program (ILP) formulation and the associated LP-
relaxation
a graph G = (V , E) and a subset S ⊆ V , let E[S] :=
from [6]. For
{u, v} ∈ E : u, v ∈ S and G[S] := (S, E[S]), and for a vertex v ∈ V , let d S (v)
denote the degree of v in G[S]. We will denote the following polyhedron as the strong
density polyhedron and the constraints describing the polyhedron as strong density
constraints1 :
1 The use of the “density” terminology will be clear later when we discuss the connection to the densest
subgraph problem and its LP relaxation.
123
⎧ ⎫
⎨ ⎬
PSD (G) := V :
x ∈ R≥0 (d S (u)−1)xu ≥ |E[S]|−|S|+1 ∀S such that E[S] = ∅ . (1)
⎩ ⎭
u∈S
Chudak, Goemans, Hochbaum, and Williamson proved that strong density constraints
are valid for FVS and that the following is an integer linear programming formulation
for FVS:
⎧ ⎫
⎨ ⎬
min cu xu : x ∈ PSD (G) ∩ ZV . (FVS-IP: SD)
⎩ ⎭
u∈V
They interpreted the local-ratio algorithm from [1] as a primal-dual algorithm with
respect to2 the LP-relaxation of (FVS-IP: SD) that we explicitly write below:
⎧ ⎫
⎨ ⎬
min cu xu : x ∈ PSD (G) . (FVS-LP: SD)
⎩ ⎭
u∈V
It is, however, not known whether (FVS-LP: SD) can be solved in polynomial time.
Equivalently, it is open to design a polynomial-time separation oracle for the family of
strong density constraints. Moreover, there has been no other polynomial-time solvable
LP relaxation through which one could obtain a 2-approximation for FVS. This status
leads to the following natural question:
Question 1 Does there exist an ILP formulation for FVS whose LP-relaxation can be
solved in polynomial time and has integrality gap at most 2?
The lack of solvable LP relaxations for FVS with small integrality gap has also been
a stumbling block for the design of approximation algorithms for a generalization of
FVS called the subset feedback vertex set problem (Subset-FVS) [10]: the input is
a vertex-weighted graph G and a terminal set T ⊆ V , and the goal is to remove a
minimum cost subset of vertices S to ensure that G − S has no cycle containing a
terminal t ∈ T . There is an 8-approximation for Subset-FVS [11] and this is based on
a complex algorithm that combines combinatorial and LP-based techniques. Chekuri
and Madan [8] formulated a polynomial-sized integer linear program for Subset-FVS
and showed that the integrality gap of its LP-relaxation is at most 13. They explicitly
raised the question of whether the integrality gap of their formulation is better for
FVS; in fact it is open whether their formulation’s integrality gap is at most 2 for
Subset-FVS.
In this work, we provide an affirmative answer to Question 1 by undertaking a poly-
hedral study of FVS and a closely related problem, namely the pseudoforest deletion
set problem that will be described shortly. In addition to formulating polynomial-time
2 An α-approximation with respect to an LP min{c T x : Ax ≤ b} is an algorithm that returns an integral

solution z ∗ satisfying Ax ≤ b such that c T z ∗ ≤ αOPTLP , where OPTLP is the optimum objective value
of the LP.
123
solvable LP relaxations with small integrality gap, it is also of interest to find algo-
rithms that can round fractional solutions to the LP relaxations, and to understand
properties of extreme points of the corresponding polyhedra. Based on several inter-
related technical considerations, we conjecture the following property for the strong
density polyhedron:
Conjecture 1 Let G = (V , E) be a graph that contains a cycle. For every extreme

point x of the polyhedron PSD (G), there exists a vertex u ∈ V such that xu ≥ 1/2.
This conjecture would lead to an alternative proof that the integrality gap of the
LP-relaxation (FVS-LP: SD) is at most 2 via iterative rounding (instead of the primal-
dual technique). Although we were unable to resolve this conjecture for the strong
density polyhedron, we were able to show that a variant of the conjecture holds for a
weak density polyhedron (to be defined later). The weak density polyhedron closely
resembles the strong density polyhedron and is associated with an ILP formulation of
the pseudoforest deletion set problem. We also discuss extreme point properties for
other formulations later in the paper.
Pseudoforest Deletion Set Problem (PFDS). A connected graph is a pseudotree if
it has exactly one cycle; in other words there is an edge whose removal results in
a spanning tree. A graph is a pseudoforest if every connected component is either
acyclic or a pseudotree. For a graph G = (V , E), a subset U ⊆ V is a pseudofor-
est deletion set if G − U is a pseudoforest. In the pseudoforest deletion set problem
(PFDS), the input is an undirected graph G = (V , E) with non-negative vertex costs
c : V→ R≥0 and the goal is to find a pseudoforest deletion set of minimum
cost, i.e.,
min u∈U c(u) : U ⊆ V and U is a pseudoforest deletion set for G . Intuitively, one
can see that PFDS is closely related to FVS: we note that a feasible solution for FVS
in a given graph G is a feasible solution to the PFDS instance on G. Also, finding an
FVS in a graph that is a pseudoforest is easy: for each connected component that is
a pseudotree, we remove the cheapest vertex in its unique cycle. PFDS and FVS are
special cases of the more general -pseudoforest deletion problem that was introduced
in [18] from the perspective of parameterized algorithms (FVS corresponds to = 0
and PFDS to = 1). Lin, Feng, Fu, and Wang [16] studied approximation algorithms
for -pseudoforest deletion problem. In this paper, we restrict attention to PFDS and
FVS and do not discuss the more general -pseudoforest deletion problem. The status
of PFDS is very similar to that of FVS. It has an approximation preserving reduction
from the vertex cover problem and consequently, it is NP-hard, and does not have a
polynomial time (2 − )-approximation for every constant > 0 assuming the UGC.
It admits a polynomial-time 2-approximation based on the local-ratio technique [16].
The authors in [16] do not discuss LP relaxations for PFDS. However, the local-ratio
technique of [16] can be converted to an LP-based 2-approximation for PFDS follow-
ing the ideas in [6]. We describe the associated LP relaxation. A graph G = (V , E)
is a 2-pseudotree if it is connected and has |E| ≥ |V | + 1 (i.e., the graph has at
least 2 edges in addition to a spanning tree). We will denote the following polyhe-
dra as weak density polyhedron and 2-pseudotree cover polyhedron respectively, and
the constraints describing them as weak density constraints and 2-pseudotree cover
constraints respectively:
123
⎧ ⎫
⎨ ⎬
V :
PWD (G) := x ∈ R≥0 (d S (u) − 1)xu ≥ |E[S]| − |S| ∀S ⊆ V , and (2)
⎩ ⎭
u∈S
⎧ ⎫
⎨ ⎬
V :
P2-PT-cover (G) := x ∈ R≥0 xu ≥ 1 ∀U ⊆ V such that G[U ] contains a 2-pseudotree .
⎩ ⎭
u∈U
(3)
We encourage the reader to compare and contrast the weak density constraints with
the strong density constraints. Weak density constraints and 2-pseudotree covering
constraints are valid for PFDS. In particular, the following are ILP formulations for
PFDS:
⎧ ⎫
⎨ ⎬
min cu xu : x ∈ PWD (G) ∩ ZV and (PFDS-IP: WD)
⎩ ⎭
u∈V
⎧ ⎫
⎨ ⎬
min cu xu : x ∈ PWD (G) ∩ P2-PT-cover (G) ∩ ZV .
⎩ ⎭
u∈V
(PFDS-IP: WD-and-2PT-cover)
The local-ratio technique for PFDS due to Lin, Feng, Fu, and Wang [16] can be
converted to a 2-approximation for PFDS with respect to the following LP-relaxation
via the primal-dual technique:
⎧ ⎫
⎨ ⎬
min cu xu : x ∈ PWD (G) ∩ P2-PT-cover (G) .
⎩ ⎭
u∈V
(PFDS-LP: WD-and-2PT-cover)
The family of 2-pseudotree cover constraints admits a polynomial-time separation

oracle (see Lemma 18). However, we do not know a polynomial-time separation
oracle for the family of weak density constraints (similar to the status of strong
density constraints), and for this reason we do not know how to solve (PFDS-LP:
WD-and-2PT-cover) in polynomial time3 . This leads to the following question (which
is the counterpart of Question 1 for PFDS):
Question 2 Does there exist an ILP formulation for PFDS whose LP-relaxation can
be solved in polynomial time and has integrality gap at most 2?
We emphasize that weak density constraints and our answer to Question 2 will play
a crucial role in our answer to Question 1. Furthermore, we prove an extreme point
property of the weak density polyhedron that closely resembles the extreme point
property of the strong density polyhedron mentioned in Conjecture 1.
3 We note that Fujito’s framework [13] encompasses PFDS and hence a 2-approximation follows from
his work. It appears that [16] were unaware of [13]. The authors of this paper also became aware of [13]
after completing an earlier version. The LP relaxation in [13] does not appear to have a polynomial-time
separation oracle.
123
1.1 Results
We begin with our results for PFDS. These results influence our results for FVS which
will be discussed subsequently.
PFDS: ILP formulations and LP integrality gap. We answer Question 2 affirma-
tively. Our ILP for PFDS is based on Charikar’s LP for the densest subgraph problem
(DSG) [7]. In DSG, the input is an undirected graph G = (V , E) and the goal is to
find an induced subgraph G[S] of maximum density where the density of S ⊆ V is
defined as |E(S)|/|S|. We define the density of G to be max{|E[S]|/|S| : ∅ = S ⊆ V }.
We note that a graph is a pseudoforest if and only if its density is at most one. Thus,
PFDS can equivalently be phrased as the problem of finding a minimum cost subset
of vertices to delete so that the remaining graph has density at most one. Charikar
formulated an LP to compute the density of a graph. The dual of Charikar’s LP can
be interpreted as a fractional orientation problem. Using that dual, we obtain an ILP
for PFDS. We describe the details now. Via Charikar’s LP and previous results, one
can show that an unweighted graph G has density at most λ iff the edges of G can be
fractionally oriented such that the total fractional in-degree at every vertex is at most
λ. For an edge e = uv we use variables ye,u and ye,v to denote the fractional amount
of e that is oriented towards u and v respectively. We recall that in PFDS the goal is
to remove vertices such that the residual graph has density at most 1. Thus, we also
have variables xu for each u ∈ V to indicate whether u is deleted. An edge e = uv is
in the residual graph only if u and v are not deleted. These observations allow us to
formulate the an ILP for PFDS based on the polyhedron below. We refer to this as the
orientation polyhedron:
⎧ ⎫
⎪
⎪ x + x v + y + y ≥ 1 ∀e ∈ E : e = uv ⎪
⎪
⎪
⎨
u e,u e,v ⎪
⎬
xu + e∈δ(u) ye,u ≤ 1 ∀u ∈ V
Porient (G) := (x, y) : .
⎪
⎪ xu ≥ 0 ∀u ∈ V ⎪
⎪
⎪
⎩ ⎪
⎭
ye,u ≥ 0 ∀e ∈ δ(u), u ∈ V .
The authors of this paper became aware, after completing an earlier version, of the
work of Bodlaender, Ono, and Otachi [3]. They had proposed the preceding LP as a
relaxation for PFDS and asked about its integrality gap — we answer their question
in this paper. The authors of [3] derived the relaxation directly without an explicit
connection to the notion of density or to Charikar’s formulation for DSG.
We will denote the projection of Porient (G) to the x variables by Q orient (G). For
non-negative costs c : V → R≥0 , we consider the following two formulations:
⎧ ⎫
⎨ ⎬
min cu xu : x ∈ Q orient (G) ∩ ZV and (PFDS-IP: orient)
⎩ ⎭
u∈V
⎧ ⎫
⎨ ⎬
min cu xu : x ∈ Q orient (G) ∩ P2-PT-cover (G) ∩ ZV .
⎩ ⎭
u∈V
(PFDS-IP: orient-and-2PT-cover)
123
We will be interested in the integrality gap of the following LP-relaxation of (PFD-

S-IP: orient-and-2PT-cover):
⎧ ⎫
⎨ ⎬
min cu xu : x ∈ Q orient (G) ∩ P2-PT-cover (G) .
⎩ ⎭
u∈V
(PFDS-LP: orient-and-2PT-cover)
Theorem 1 For an input graph G = (V , E) with non-negative costs c : V → R≥0 ,

(PFDS-IP: orient) and (PFDS-IP: orient-and-2PT-cover) are integer linear program-
ming formulations for PFDS. Moreover, we have the following properties:
(1) Q orient (G) ⊆ PWD (G) for every graph G and there exist graphs G for which
Q orient (G) PWD (G).
(2) The LP (PFDS-LP: orient-and-2PT-cover) is solvable in polynomial time and its
integrality gap is at most 2.
We note that a necessary step for showing Theorem 1(1) is to show that there exists
a polynomial-time separation oracle for the family of 2-pseudotree cover constraints.
We include a proof of this fact in Lemma 18 in Appendix A.1 for the sake of com-
pleteness. We also note that the upper bound of 2 on the integrality gap of (PFDS-LP:
orient-and-2PT-cover) mentioned in Theorem 1 is tight as shown in Figure 1. As a
consequence of Theorem 1, we immediately obtain an integer linear program for PFDS
whose LP-relaxation is solvable in polynomial time and has integrality gap at most 2
— namely (PFDS-IP: orient-and-2PT-cover). We also bound the integrality gap of the
LP-relaxation of (PFDS-IP: orient), but this will be based on extreme point properties
and will be discussed next.
PFDS: extreme point properties. Motivated by Conjecture 1 and the goal of designing
primal rounding algorithms for PFDS (and thus, for FVS), we investigate extreme point
properties of the weak density polyhedron and the orientation polyhedron. Although
we were unable to resolve Conjecture 1 for the strong density polyhedron, we were
able to prove an extreme point property for the weak density polyhedron.
Theorem 2 Let G = (V , E) be a graph that is not a pseudoforest. For every extreme
point x of the polyhedron PWD (G), there exists a vertex u ∈ V such that xu ≥ 1/3.
Our proof of Theorem 2 is based on a conditional supermodularity property—if all
coordinates are small, then the weak density constraints have a supermodular property;
we use this supermodular property to show the existence of a structured basis for the
extreme point which is subsequently used to arrive at a contradiction. To the best
of authors’ knowledge, the conditional supermodularity property based proof has not
previously appeared in the literature on iterated rounding, and might be of independent
interest. Theorem 2 implies the corollary below regarding the following LP-relaxation
of (PFDS-IP: WD):
⎧ ⎫
⎨ ⎬
min cu xu : x ∈ PWD (G) . (PFDS-LP: WD)
⎩ ⎭
u∈V
123
Fig. 1 An example showing that the integrality gap of (PFDS-LP: orient-and-2PT-cover) tends to 2 as
n tends to infinity. Consider the graph G = (V , E) as shown above (where K n denotes the complete
graph on n vertices) with cost of every vertex a ∈ V − {u, v, w} being 1 and costs of vertices u, v, w being
infinite. The optimum value of (PFDS-IP: orient-and-2PT-cover) is n −1. The optimum value of (PFDS-LP:
orient-and-2PT-cover) is at most n/2: the solution xa = 1/2 for every vertex a ∈ V − {u, v, w}, xu =
xv = xw = 0, ye,a = 0 for all edges e = ab where a, b ∈ V − {u, v, w}, yuv,v = yvw,w = ywu,u = 1,
yuv,u = yvw,v = ywu,w = 0, and yua,a = 1/2, yua,u = 0 for every a ∈ V − {u, v, w} is feasible for
(PFDS-LP: orient-and-2PT-cover) and has cost n/2
Corollary 2.1 The integrality gap of (PFDS-LP: WD) is at most 3.
Corollary 2.1 can be seen to follow from Theorem 2 by the iterative rounding
technique, where we repeatedly apply the following two steps until the graph G is a
pseudoforest: (1) Compute an extreme point optimum solution x of (PFDS-LP: WD).
(2) By Theorem 2, there exists a vertex u ∈ V such that xu ≥ 1/3; include the vertex
u in the solution and remove it from the graph G. The approximation factor of the
solution constructed by this procedure relative to the starting extreme point optimum
solution to the LP is at most 3. The example given in Figure 2a shows that the (1/3)-
bound in Theorem 2 and the integrality gap of 3 mentioned in Corollary 2.1 are both
tight.
We emphasize that the extreme point result given in Theorem 2 and the integrality
gap result mentioned in Corollary 2.1 are interesting only from a polyhedral viewpoint
currently, and are not of help from the perspective of algorithm design. This is because,
implementing the above-mentioned iterative rounding procedure requires us to solve
the LP-relaxation (PFDS-LP: WD) in polynomial time, but we do not know how to
do this yet.
We next show that although Q orient (G) is a subset of PWD (G) (as shown in The-
orem 1), the extreme point result for PWD (G) given in Theorem 2 still holds for
Q orient (G). We will say that an extreme point of a polyhedron is minimal if for each
variable, reducing the value of that variable by any > 0 while keeping the rest of
the variables unchanged results in a point that is outside the polyhedron. We note
that extreme points of a polyhedron along non-negative objective directions will be
minimal.
123
Fig. 2 .
Theorem 3 Let G = (V , E) be a graph that is not a pseudoforest. For every minimal

extreme point (x, y) of the polyhedron Porient (G), there exists a vertex u ∈ V such
that xu ≥ 1/3.
Similar to Corollary 2.1 that follows from Theorem 2, Theorem 3 implies the
corollary below regarding the following LP-relaxation of (PFDS-IP: orient):
⎧ ⎫
⎨ ⎬
min cu xu : x ∈ Q orient (G) (PFDS-LP: orient)
⎩ ⎭
u∈V
Corollary 3.1 The integrality gap of (PFDS-LP: orient) is at most 3. Moreover, given an
extreme point optimum solution x for the LP, there exists a polynomial time
algorithm
obtain an integral feasible solution x for the LP-relaxation such that u∈V cu xu ≤
to
3 u∈V cu xu .
Corollary 3.1 can be seen to follow from Theorem 3 by the iterative round-
ing technique, where we repeatedly apply the following two steps until the graph
G is a pseudoforest: (1) Compute an extreme point optimum solution x of
min c
u∈V u ux : x ∈ Q orient (G) . (2) By Theorem 3, there exists a vertex u ∈ V
such that xu ≥ 1/3; include the vertex u in the solution and remove it from the graph
G. The approximation factor of this procedure is 3. In contrast to the weak density
constraints based LP, namely (PFDS-LP: WD), we can solve the orientation based LP,
namely (PFDS-LP: orient), in polynomial time. The example given in Figure 2b shows
that the (1/3)-factor in Theorem 3 and the integrality gap of 3 mentioned in Corol-
lary 3.1 are both tight. These results answer the open question raised in [3] regarding
the integrality gap of (PFDS-LP: orient).
FVS: poly-sized ILP formulations and LP integrality gaps. Next, we answer Ques-
tion 1 affirmatively via a new ILP for FVS. In order to achieve this goal, we formulate
123
an intermediate ILP for FVS whose LP-relaxation has integrality gap at most 2, but it
is unclear if this LP-relaxation is polynomial-time solvable. We will later formulate a
polynomial-sized ILP for FVS whose LP-relaxation is at least as strong as that of the
intermediate ILP, thereby achieving our goal. Our intermediate ILP is based on weak
density constraints and the following polyhedron that will be referred to as the cycle
cover polyhedron:
⎧ ⎫
⎨ ⎬
Pcycle-cover (G) := V :
x ∈ R≥0 xu ≥ 1 ∀U ⊆ V such that G[U ] contains a cycle .
⎩ ⎭
u∈U
(4)
We will denote the constraints describing the cycle cover polyhedron as cycle cover
constraints. It is known that the integrality gap of this polyhedron for FVS is (log n)
[5].
For non-negative costs c : V → R≥0 , we consider the following formulation and
its LP-relaxation:
⎧ ⎫
⎨ ⎬
min cu xu : x ∈ PWD (G) ∩ Pcycle-cover (G) ∩ ZV and
⎩ ⎭
u∈V
(FVS-IP: WD-and-cycle-cover)
⎧ ⎫
⎨ ⎬
min cu xu : x ∈ PWD (G) ∩ Pcycle-cover (G) .
⎩ ⎭
u∈V
(FVS-LP: WD-and-cycle-cover)

(FVS-IP: WD-and-cycle-cover) is an integer linear programming formulation for FVS.
Moreover, the integrality gap of (FVS-LP: WD-and-cycle-cover) is at most 2.
Theorem 4 shows that (FVS-IP: WD-and-cycle-cover) is an ILP for FVS whose
LP-relaxation (FVS-LP: WD-and-cycle-cover) has integrality gap at most 2. However,
we do not have a polynomial-time algorithm to solve the LP-relaxation (FVS-LP:
WD-and-cycle-cover). This is because, we do not have a polynomial-time separation
oracle for the family of weak density constraints (although we do have a polynomial-
time separation oracle for the family of cycle cover constraints).
Remark 1 In the spirit of using iterative rounding to bound integrality gaps (e.g.,
Theorem 2 that leads to Corollary 2.1 and Theorem 3 that leads to Corollary 3.1), it is
tempting to bound the integrality gap of (FVS-LP: WD-and-cycle-cover) by proving an
extreme point result. In particular, if we could show that every extreme point optimum
of (FVS-LP: WD-and-cycle-cover) had a coordinate with value at least 1/2, then we
would have an alternative proof of the integrality gap bound mentioned in Theorem 4
via the iterative rounding technique. However, the example given in Figure 3 shows
that there exists an extreme point optimum of (FVS-LP: WD-and-cycle-cover) all of
whose coordinates have value at most 1/3.
123
Fig. 3 The unique extreme point optimum for (FVS-LP: WD-and-cycle-cover) along the all-ones objective
direction on the complete graph K 4 is as shown. Consequently, the integrality gap of (FVS-LP: WD-and–
cycle-cover) is at least 3
We will use Theorem 1 in conjunction with Theorem 4 to prove the following result:
Theorem 5 There exists a polynomial-sized integer linear programming formulation

for FVS whose LP-relaxation has integrality gap at most 2.
We prove Theorem 5 by showing three different polynomial-sized integer linear pro-

grams for FVS all of whose LP-relaxations have integrality gap at most 2:
1. The first formulation is
⎧ ⎫
⎨ ⎬
min cu xu : x ∈ Q orient (G) ∩ Pcycle-cover (G) ∩ ZV .
⎩ ⎭
u∈V
(FVS-IP: orient-and-cycle-cover)
By Theorem 1(1), we have that Q orient (G) ⊆ PWD (G). As a consequence of

Theorem 4, the integrality gap of the following LP-relaxation is also at most 2:
⎧ ⎫
⎨ ⎬
min cu xu : x ∈ Q orient (G) ∩ Pcycle-cover (G) .
⎩ ⎭
u∈V
(FVS-LP: orient-and-cycle-cover)
Both Q orient (G) and Pcycle-cover (G) admit a polynomial-sized description (see
Lemma 19 in Appendix B.1 for polynomial-sized description of Pcycle-cover (G)),
and thus, we have a polynomial-sized ILP for FVS whose LP-relaxation has inte-
grality gap at most 2.
2. The second formulation is the Chekuri–Madan formulation who, as we remarked
earlier, formulated an ILP for Subset-FVS and showed that the integrality gap of
its LP-relaxation is at most 13 [8]. We show that their LP-relaxation specialized
for FVS has integrality gap at most 2 by proving that it is at least as strong as
(FVS-LP: orient-and-cycle-cover). Our result gives additional impetus to improv-
ing the integrality gap of their LP-relaxation for Subset-FVS.
3. Our third formulation to prove Theorem 5 is based on the orientation perspective,
but without cycle cover constraints (as opposed to our first formulation). Here,
we give an orientation based ILP formulation whose associated polyhedron is
123
contained in the strong density polyhedron. Since the integrality gap of (FVS-LP:
SD) is at most 2 (as shown by Chudak, Goemans, Hochbaum, and Williamson
[6]), the integrality gap of our third formulation is also at most 2.
We emphasize that the proof of the integrality gap of the LP-relaxation of all three
of our ILPs rely on the integrality gap upper bound of (FVS-LP: WD-and-cycle-cover)
or (FVS-LP: SD). It would be interesting to have a direct proof. In particular, it would
be useful to design a primal rounding algorithm (for arbitrary LP-optimum solutions
or for extreme point LP-optimum solutions) that yields a 2-approximate solution.
Organization. We focus on PFDS in Sect. 3 and FVS in Sect. 4. In Sect. 3.1, we
prove properties of the orientation polyhedron and show Theorem 1. In Sects. 3.2
and 3.3, we prove extreme point properties of the weak density polyhedron and the
orientation polyhedron and show Theorems 2 and 3 respectively. In Sect. 4.1, we
prove properties of the weak density polyhedron and show Theorem 4. In Sect. 4.2,
we give a polynomial-sized ILP formulation for FVS with integrality gap at most 2,
thereby proving Theorem 5. For the sake of completeness, we discuss two additional
polynomial-sized ILP formulations for FVS with integrality gap at most 2 in Sect. 4.3.
2 Preliminaries
For a minimization IP min{c T x : Ax ≤ b, x ∈ Zn≥0 }, the integrality gap of its LP-

relaxation min{c T x : Ax ≤ b, x ≥ 0} is the maximum ratio, over all non-negative
cost functions, of the minimum cost of a feasible solution to the IP and that of the
LP, i.e., maxc∈Rn min{c T x : Ax ≤ b, x ∈ Zn≥0 }/ min{c T x : Ax ≤ b, x ≥ 0}. For a
graph G = (V , E), we will use δ(A, B) to denote the set of edges with exactly one
end-vertex in A and exactly one end-vertex in B. We summarize the results of Lin,
Feng, Fu, and Wang [16] in a manner that will be useful for our polyhedral study.
Theorem 6 (PFDS-IP: WD) and (PFDS-IP: WD-and-2PT-cover) are ILP formula-
tions for PFDS. Furthemore, the LP-relaxation (PFDS-LP: WD-and-2PT-cover) has
integrality gap at most 2.
We emphasize that Lin, Feng, Fu, and Wang did not prove Theorem 6 directly, but
their local ratio based algorithm and standard techniques to convert local ratio based
algorithms to LP-based primal-dual algorithms (following the ideas in [6]) lead to the
theorem.
3 Pseudoforest deletion set
In this section, we formally prove our main results for Pseudoforest Deletion Set. We
prove Theorem 1 in Sect. 3.1, Theorem 2 in Sect. 3.2, and Theorem 3 in Sect. 3.3.
3.1 Orientation and 2-pseudotree cover constraints
In this section, we restate and prove Theorem 1.
123

(PFDS-IP: orient) and (PFDS-IP: orient-and-2PT-cover) are integer linear program-
ming formulations for PFDS. Moreover, we have the following properties:
(1) Q orient (G) ⊆ PWD (G) for every graph G and there exist graphs G for which
Q orient (G) PWD (G).
(2) The LP (PFDS-LP: orient-and-2PT-cover) is solvable in polynomial time and its
integrality gap is at most 2.
Proof In order to show that (PFDS-IP: orient) and (PFDS-IP: orient-and-2PT-cover)
are ILP formulations for PFDS, it suffices to show that the ILP (PFDS-IP: orient) is
a formulation for PFDS. This is because 2-pseudotree cover constraints are valid for
PFDS.
For a subgraph G̃ = (Ṽ , Ẽ) of the graph G, we let dG̃ (u) := |δ(u) ∩ Ẽ| denote the
degree of the vertex u in the subgraph G̃. We now define an intermediate polyhedron
PWD-Subgraphs (G).
PWD-Subgraphs (G)
⎧ ⎫
⎪
⎨ ⎪
⎬
:= x ∈ R≥0 : V
(dG̃ (u) − 1)xu ≥ | Ẽ| − |Ṽ | ∀ subgraphs G̃ = (Ṽ , Ẽ) of G. .
⎪
⎩ ⎪
⎭
u∈Ṽ
(5)
We note that PWD-Subgraphs (G) ⊆ PWD (G). We will use the following claim to show
that the ILP (PFDS-IP: orient) formulates PFDS and also to conclude that Q orient (G) ⊆
PWD (G).
Claim 1 Q orient (G) ⊆ PWD-Subgraphs (G).
Proof Let x ∈ Q orient (G). Then, there exists a vector y such that (x, y) ∈ Porient (G).
Let G̃ = (Ṽ , Ẽ) be an arbitrary subgraph of G. We have the following:

| Ẽ| ≤ (xv + xw + ye,v + ye,w )
e=vw∈ Ẽ
⎛ ⎞
⎜ ⎟
= (dG̃ (v) − 1)xv + ⎝xv + ye,v ⎠
v∈Ṽ v∈Ṽ e∈δG̃ (v)

≤ (dG̃ (v) − 1)xv + |Ṽ |,
v∈Ṽ
where the inequalities are because the vector (x, y) ∈ Porient . Rearranging the
above inequality gives the constraint for G̃ given in PWD-Subgraphs (G). Hence, x ∈
PWD-Subgraphs (G).

We remark that Claim 1 can be strengthened to show that Q orient (G) =
PWD-Subgraphs (G), but we will not need this stronger version for the purposes of this
123
theorem. We now show that the ILP (PFDS-IP: orient) formulates PFDS. Let S ⊆ V
be a pseudoforest deletion set, i.e., the subgraph F := G − S is a pseudoforest. Let
x := χ S ∈ {0, 1}V denote the indicator vector of the set S. Select an arbitrary orienta-
tion of the pseudoforest F such that the maximum indegree of every vertex is at most
1, and let ye,v := 1 for the edge e = vw if e is an edge of F that is oriented towards
v, and ye,v := 0 otherwise. Then, (x, y) ∈ Porient (G).
Next, suppose x ∈ Q orient (G) ∩ ZV . Then, we have that x ∈ {0, 1}V . By Claim 1,
x ∈ PWD-Subgraphs (G) ⊆ PWD (G). Since (PFDS-IP: WD) is an ILP formulation for
PFDS by Theorem 6, it follows that the set S := {u ∈ V : xu = 1} is a pseudoforest
deletion set for the graph G. This concludes the proof that the ILP (PFDS-IP: orient)
formulates PFDS.
We now prove the two additional conclusions of the theorem statement.
(1) By Claim 1, we have that Q orient (G) ⊆ PWD-Subgraphs (G) ⊆ PWD (G). We now
show that there is a graph G such that PWD-Subgraphs (G) PWD (G). In particular,

we consider the graph K 5 = (V , E) where V = {v1 , v2 , . . . , v5 } and E = V2 .
Let x = (2/3, 2/3, 1/3, 0, 0). We note that x ∈ PWD (K 5 ). We now show that
x∈/ PWD-Subgraphs (K 5 ). Consider the subgraph G̃ = (Ṽ , Ẽ) obtained by removing

the edge {v1 , v2 } from the graph G, i.e. Ṽ = V and Ẽ = V2 − {v1 , v2 }. Then, we
have the following:
11
(dG̃ (u) − 1)xu = 2x1 + 2x2 + 3x3 + 3x4 + 3x5 = < 4 = | Ẽ| − |Ṽ |.
3
u∈Ṽ
In particular, the vector x does not satisfy the constraint of PWD-Subgraphs (K 5 )

defined by the subgraph G̃. Thus, we have that Q orient (K 5 ) ⊆ PWD-Subgraphs (K 5 ) ⊂
PWD (K 5 ).
(2) By Theorem 6, the ILP (PFDS-IP: WD-and-2PT-cover) is a valid formulation of
PFDS and its LP-relaxation (PFDS-LP: WD-and-2PT-cover) has integrality gap
at most 2. We have already shown that the ILP (PFDS-IP: orient-and-2PT-cover)
is a valid formulation of PFDS and that Q orient (G) ⊆ PWD (G). Consequently,
the integrality gap of (PFDS-LP: orient-and-2PT-cover) is at most 2. Finally,
we note that (PFDS-LP: WD-and-2PT-cover) can be solved in polynomial time
because Q orient (G) is the projection of Porient (G) which admits a polynomial sized
description, and because 2-pseudotree-cover constraints admit a polynomial time
separation oracle by Lemma 18 (in Appendix A.1). The polynomial time separation
oracle for 2-pseudotree-cover constraints is based on the fact that node-weighted
Steiner tree for constant number of terminals is solvable in polynomial time. We
present its proof in a separate subsection for clarity.

3.2 Extreme point property of the weak density polyhedron
In this section, we prove Theorem 2. We restate it below.
123

For a fixed x ∈ RV , we define the function f x : 2V → R as

f x (S) := |E[S]| − |S| − (d S (u) − 1)xu ∀S ⊆ V .
u∈S
Using this function, we can express the weak density polyhedron as

PWD (G) = x ∈ R≥0
V
: f x (S) ≤ 0 ∀S ⊆ V .
In Sect. 3.2.1, we recall properties of supermodular functions and chain set families.
In Sect. 3.2.2, we show that if xu ≤ 1/2 for all u ∈ V , then the function f x : 2V → R
is supermodular. This conditional supermodularity property allows us to uncross the
tight constraints that form a basis of an extreme point x for which xu ≤ 1/2 for
all u ∈ V . We prove properties about the tight constraints in Sect. 3.2.3 and show
the existence of a chain basis in Sect. 3.2.4. Using the chain basis structure and its
properties, we complete the proof of Theorem 2 in Sect. 3.2.5.
Notation. Let b(S) := |E[S]| − |S| for all S ⊆ V . For vertex u ∈ V , let χu ∈ {0, 1}V
denote the indicator vector of u. For a subset S ⊆ V , let row(S) denote the row of the
constraint matrix of PWD (G) corresponding to the set S, i.e,

d S (u) − 1 if u ∈ S
row(S)u = ∀u ∈ V .
0 o.w.
For J ⊆ 2V , let Rows(J ) = {row(S) : S ∈ J }. When the context is clear, we

also use Rows(J ) to denote the submatrix of the weak density polyhedron constraint
matrix given by the set Rows(J ). We let span(Rows(J )) denote the span of the set
of vectors Rows(J ), i.e. the smallest linear subspace that contains the set Rows(J ).
We let columns(J ) denote the set of columns of the submatrix Rows(J ). For matrix
M, we denote rank(M) as the rank of the matrix. We note that rank(Rows(J )) =
rank(columns(J )). For x ∈ RV , we will use gx (S) := u∈S (d S (u) − 1)xu for all
S ⊆ V , Tx := {S ⊆ V : f x (S) = 0} be the tight sets for x, and Z := {u ∈ V : xu = 0}.
Let x ∈ P(G) be an extreme point of the weak density polyhedron. For J ⊆ Tx , we
say that the set Rows(J ) is a basis for x if span(Rows(J )) = span(Rows(2V )).
3.2.1 Background on supermodular functions and set families
Here, we recall supermodular functions, chain set families, and some of their properties
that will be useful while proving the extreme point property of the weak density
polyhedron. A set function f : 2V → R is said to be supermodular if f (A) + f (B) ≤
f (A ∩ B) + f (A ∪ B) for all subsets A, B ⊆ V . We refer the reader to [14] for
background on supermodular set functions and their properties. We will rely on the
following property:
123
Proposition 1 Let G = (V , E) be an undirected graph with non-negative edge

weights
w : E → R≥0 . Then, the function f : 2V → R≥0 defined by f (S) := e∈E[S] we
for all S ⊆ V is supermodular.
Two sets A and B are said to cross if they have a non-empty intersection and neither
set is contained in the other, i.e. A ∩ B, A − B, B − A = ∅. For a ground set V , the set
C = {A1 , A2 , . . . A } ⊆ 2V is said to be a chain family if its elements can be ordered
such that A1 ⊆ A2 ⊆ . . . ⊆ A . We need the following proposition on chain families.
This is well-known but we give a proof for the sake of completeness.
Proposition 2 Let C be a chain family and A be a subset that crosses some set B ∈ C.
Then, the number of sets in C crossed by A ∪ B and A ∩ B is strictly less than the
number of sets in C crossed by A.
Proof Our strategy will be to pick an arbitrary set in C that crosses the set A ∪ B (resp.
A ∩ B) and show that this picked set also crosses the set A. The claim then follows
since the set B crosses the set A but not the set A ∪ B (resp A ∩ B).
Let P ∈ C be an arbitrary set that crosses the set A ∪ B. Since both B, P ∈ C,
it must be that either P ⊂ B or B ⊂ P. First, we consider the case where P ⊂ B.
Then P ⊂ A ∪ B and thus does not cross the set A ∪ B as it is contained in it. This
contradicts the choice of P. Next, we consider the case where B ⊂ P. If A ⊆ P then
A ∪ B ⊆ P, contradicting choice of P crossing A ∪ B. Furthermore, if P ⊆ A, then
B ⊂ P ⊆ A, contradicting the hypothesis that the set B crosses the set A. Finally,
A ∩ P = ∅ as A ∩ B = 0 and B ⊂ P. Thus the set P crosses the set A.
Let P ∈ C be an arbitrary set that crosses the set A ∩ B. Since the sets P, B ∈ C
are part of a chain family, it must be that either P ⊆ B or B ⊆ P. If B ⊆ P, then
A∩ B ⊆ P, contradicting the choice of set P. Thus P ⊆ B. If P ⊆ A, then P ⊆ A∩ B,
contradicting the choice of set P. Moreover, if A ⊆ P, then we have that A ⊆ B,
contradicting that A and B cross. Thus the set P crosses the set A.

3.2.2 Conditional supermodularity of weak density constraints
We now show that the function f x is supermodular if xu < 1

2 ∀u ∈ V .
Lemma 1 Let x ∈ RV . If xu < 1

2 ∀u ∈ V , then the function f x is supermodular.
Proof Let S ⊆ V . We have

f x (S) = |E[S]| − |S| − (d S (u) − 1)xu
u∈S

= |E[S]| − d S (u)xu − |S| + xu
u∈S u∈S

= |E[S]| − xu − (1 − xu )
u∈S v∈δ(u) u∈S

= |E[S]| − (xu + xv ) − (1 − xu )
uv∈E[S] u∈S
123

= 1 − (xu + xv ) − (1 − xu ) .
uv∈E[S] u∈S
px , qx : 2 → R
be expressed as f x = px −qx for functions
Thus, the function f x can V
defined by px (S) := uv∈E[S] (1 − (xu + xv )) and qx (S) := u∈S (1 − xu ). Since

xu < 1/2 for all u ∈ V , we have that px (S) ≥ 0 and qx (S) ≥ 0 for all S ⊆ V .
Now, let H = (V , E) be a graph with edge weights w : E → R defined by
w(uv) := 1 − (xu + xv ). We note that the edge weights are non-negative since
xa < 1/2 for all a ∈ V . By definition, px (S) = uv∈E[S] w(uv) for all S ⊆ V . By
Proposition 1, the function px is supermodular. Moreover, the function qx is modular.
Thus, the function f x is the sum of a supermodular function and a modular function.
Consequently, f x is a supermodular function.

3.2.3 Conditional properties of tight sets
Next, we prove certain properties of tight sets that help us to prove the existence of
a well-structured basis for the extreme point x under the condition that xu < 1/2 for
every u ∈ V .
Lemma 2 (Conditional Uncrossing Properties) Let x be an extreme point of PWD (G)

such that xu < 21 for all u ∈ V and the family of tight sets for x be Tx := {S ⊆ V :
f x (S) = 0}. Let A, B ∈ T. Then,
1. A ∩ B = ∅, i.e., tight sets overlap,
2. A ∩ B, A ∪ B ∈ Tx , i.e. tight sets form a lattice family,
3. δ(A − B, B − A) = ∅, i.e. tight sets admit no crossing edges, and
4. row(A) + row(B) = row(A ∩ B) + row(A ∪ B).
b(S) := |E[S]| − |S|. Moreover,

Proof We recall that for a set S ⊆ V , we denote
for the point x ∈ PW D (G), we denote gx (S) := u∈S (d S (u) − 1)xu . We prove each
property separately below.
1. By way of contradiction, assume that A ∩ B = ∅. We have that
b(A ∪ B) ≤ gx (A ∪ B)

= gx (A) + gx (B) + (xa + xb )
ab∈δ(A,B)

= |E[A] − |A| + |E[B] − |B| + (xa + xb )
ab∈δ(A,B)

= |E[A ∪ B]| − |A ∪ B| − |δ(A, B)| + (xa + xb )
ab∈δ(A,B)

= b(A ∪ B) − |δ(A, B)| + (xa + xb )
ab∈δ(A,B)
< b(A ∪ B) − |δ(A, B)| + |δ(A, B)|,
123
a contradiction. Here, the first inequality is by the weak density constraint for the
set A ∪ B. The first and third equalities are by the hypothesis that A ∩ B = ∅. The
final inequality is because xu < 21 ∀u ∈ V .
2. We have the following:
0 = f x (A) + f x (B) ≤ f x (A ∪ B) + f x (A ∩ B) ≤ 0.
Here, the first equality is due to the sets A, B ∈ Tx , and thus f x (A) = f x (B) = 0.
The first inequality follows from supermodularity of the function f x shown in
Lemma 1. The final inequality follows from weak density constraints for the sets
A∪ B and A∩ B. Thus, all inequalities are equalities, and we have that f x (A∩ B) =
f x (A ∪ B) = 0 using weak density constraints on the respective sets.
3. By way of contradiction, assume that δ(A − B, B − A) = ∅. Since A, B ∈ Tx ,
we have that A ∩ B, A ∪ B ∈ Tx by the previously shown property that tight sets
uncross. Thus, f x (A) = f x (B) = f x (A ∩ B) = f x (A ∪ B) = 0. We have that
0 = f x (A) + f x (B) − f x (A ∩ B) − f x (A ∪ B)

= 1 − (xu + xv ) > 0,
uv∈δ(A−B,B−A)
a contradiction. Here, the second equality is by definition of f x , and the final

inequality is because xu < 21 ∀u ∈ V .
4. Let u ∈ V be an arbitrary vertex. It suffices to show that (d A (u)−1)+(d B (u)−1) =
(d A∪B (u) − 1) + (d A∩B (u) − 1). We consider four cases:
First, we consider the case u ∈ A − B. Then, we have that (1) d A (u) = d A−B (u) +
δ(u, A ∩ B), (2) d B (u) = 0 (3) d A∩B (u) = 0 and (4) d A∪B (u) = d A−B (u) +
δ(u, A ∩ B). Here, (4) follows from δ(u, B − A) = ∅ by the previous part.
Thus, the claimed equality follows. We note that the argument for the case where
u ∈ B − A is similar to this case.
Next, we consider the case u ∈ A ∩ B. Then, we have that (1) d A (u) = d A∩B (u) +
δ(u, A − B), (2) d B (u) = d A∩B (u) + δ(u, B − A), and (3) d A∪B (u) = d A∩B (u) +
δ(u, A − B) + δ(u, B − A). Thus, the claimed equality follows.
Finally, we consider the case u ∈ V − (A ∪ B). Then, we have that d A (u) =
d B (u) = d A∩B (u) = d A∪B (u) = 0 and the claimed equality follows.

Next, we show that every tight set is of size at least 2 and the graph induced over
the tight set is connected.
Lemma 3 Let x be an extreme point of PWD (G) such that xu < 21 for all u ∈ V and
the family of tight sets for x be Tx := {S ⊆ V : f x (S) = 0}. For every A ∈ Tx , we
have that |A| ≥ 2 and the graph G[A] is connected.
Proof Let A ∈ Tx . Suppose that |A| = 1. Let A = {u}. Then, A ∈ Tx implies

that f x ({u}) = 0. Equivalently, −xu = −1 and hence, xu = 1, a contradiction.
Hence, |A| ≥ 2. Next, we show that G[A] is connected. By way of contradiction, let
123
A = A1 A2 such that G[A1 ], G[A2 ] are disconnected components of G[A]. Then,

we have the following:
gx (A1 ) + gx (A2 ) = gx (A)

= b(A)
= |E[A]| − |A|
= |E[A1 ]| − |A1 | + |E[A2 ]| − |A2 |
= b(A1 ) + b(A2 )
≤ gx (A1 ) + gx (A2 ).
Here, the first and fourth equalities are because A1 ∩ A2 = ∅. The second equality
holds because A ∈ Tx . The final inequality holds by the weak density constraints on
A1 and A2 .
The chain of inequalities implies that the final inequality is an equality. By weak
density constraints for A1 and A2 , we also have that b(A1 ) ≤ gx (A1 ) and b(A2 ) ≤
gx (A2 ) and consequently, A1 and A2 are tight sets, i.e., A1 , A2 ∈ Tx . However,
A1 ∩ A2 = ∅ by assumption, contradicting Lemma 2 that tight sets must overlap.
3.2.4 Conditional basis structure for extreme points
In this section, we use the conditional structural properties of tight sets proved in
Sect. 3.2.3 to show that every extreme point x for the weak density polyhedron for
which xu < 1/2 for all u ∈ V has a well-structured basis. We recall that a 2-pseudotree
is a connected graph that has one more edge than the number of vertices. The following
lemma is the main result of this section.
Lemma 4 Let x be an extreme point of PWD (G) such that xu < 21 ∀u ∈ V , the family
of tight sets for x be Tx := {S ⊆ V : f x (S) = 0}, and let Z := {u ∈ V : xu = 0}.
Then, there exists a family C ⊆ Tx such that
(1) the family C is a chain family,
(2) the set of vectors Rows(C ∪ Z) is linearly independent,
(3) span(Rows(C ∪ Z)) = span(Rows(Tx ∪ Z)),
(4) For each S ∈ C, the subgraph G[S] contains a 2-psuedotree,
(5) For each S ∈ C and each vertex u ∈ S, we have that d S (u) ≥ 2, and
(6) For every A, B ∈ C such that A ⊂ B, there exists a vertex v ∈ B − A such that
xv > 0.
Proof We first show that there exists a family satisfying properties (1)–(4). Let
C(1) ⊆ Tx be an inclusion-wise maximal chain family. Claim 2 below shows that
span(Rows(C(1) )) = span(Rows(Tx )).
Claim 2 span(Rows(C(1) )) = span(Rows(Tx )).
Proof By way of contradiction assume false. Let A ∈ Tx such that row(A) ∈ /

span(Rows(C(1) )) and A crosses the fewest number of sets in C(1) . Consider a set B ∈
123
C(1) such that B crosses A. We note that such a set B exists since otherwise the family
C(1) ∪ {A} contradicts the inclusion-wsie maximality of C(1) . Recall that by Lemma 2,
the sets A ∩ B, A ∪ B ∈ Tx are also tight. We note that by Proposition 2, the sets A ∩ B
and A ∪ B cross fewer sets in C(1) than the number of sets in C(1) crossed by A. We
consider two cases based on whether row(A ∪ B), row(A ∩ B) ∈ span(Rows(C(1) )).
First, consider the case where row(A ∪ B) ∈ / span(Rows(C(1) )) without loss of gen-
erality. Since A ∪ B crosses fewer sets in C, the set A ∪ B contradicts the choice
of A. Next, consider the case where row(A ∪ B), row(A ∩ B) ∈ span(Rows(C(1) )).
By Lemma 2, we have that row(A) + row(B) = row(A ∪ B) + row(A ∩ B). Thus
row(A) ∈ span(Rows(B, A ∩ B, A ∪ B)), contradicting choice of A.

Let C(2) ⊆ C(1) be an inclusion-wise maximal family such that the set Rows(C(2) ∪Z)
is linearly independent. We note that span(Rows(C(2) ∪ Z)) = span(Rows(C(1) ∪
Z)) = span(Rows(Tx ∪ Z)), where the first equality is because the family C(2) is
inclusion-wise maximal. In particular, we have that the family C(2) satisfies properties
(1)–(3). Claim 3 below shows that the family C(2) also satisfies property (4).
Claim 3 For every S ∈ C(2) , the subgraph G[S] contains a 2-pseudotree.
Proof By way of contradiction, let S ∈ C(2) such that G[S] does not contain a 2-
pseudotree. Let S i := {u ∈ S : d S (u) = i} and S ≥i := {u ∈ S : d S (u) ≥ i}. We note
that b(S) ≤ 0 since G[S] does not contain a 2-pseudotree. Hence, we have that
0 ≥ b(S) = g(S)

= (d S (u) − 1)xu
u∈S

= (d S (u) − 1)xu + (d S (u) − 1)xu + (d S (u) − 1)xu
u∈S 0 u∈S 1 u∈S ≥2

≥ xu
u∈S ≥2
≥0
Here, the first equality holds because S ∈ Tx . The final inequality holds since |S| ≥ 2
and G[S] has no isolated vertices by Lemma 3, and by the non-negativity constraints
on vertex variables of PWD (G).
Thus, all inequalities above are equalities, and consequently, we have that
u∈S ≥2 x u = 0 This, coupled with the non-negativity constraints on vertex vari-
ables, implies that xu = 0 for each u ∈ S ≥2 . We also note that row(S)u = 0 for
each u ∈ S 1 ∪ S 0 as S 0 = ∅ and d S (u) − 1 = 0 for u ∈ S 1 . Thus, we have that
row(S) ∈ span(Rows(Z)), contradicting linear independence of Rows(C(2) ∪ Z).
We now show the existence of a family satisfying properties
(1)–(5). Let C ⊆ Tx be
a family satisfying properties (1)–(4) which minimizes S∈C |S|. We will show that
this C also satisfies property (5). By way of contradiction, suppose there exists S ∈ C
with u ∈ S such that d S (u) < 2. Since S ∈ Tx , we have that |S| ≥ 2 and d S (u) ≥ 1
since tight sets cannot have isolated vertices by Lemma 3. Thus, d S (u) = 1. Let
123
uv ∈ E[S] be the unique edge incident to u in G[S]. We note that E[S] should contain
at least one more edge apart from the edge uv as otherwise row(S) = 0. Furthermore,
by Lemma 3, the subgraph G[S] must be connected. Thus, d S (v) ≥ 2 and we have
the following:
gx (S − u) = gx (S) − xv
= b(S) − xv
= |E[S]| − |S| − xv
= (|E[S − u]| + 1) − (|S − u| + 1) − xv
= b(S − u) − xv
≤ gx (S − u) − xv
The above chain of inequalities implies that xv ≤ 0. By the non-negativity constraints

on xv , we have that xv = 0. Thus, the final inequality in the above chain is in fact an
equality, and hence, the set S − u is in Tx .
We now make three observations:
1. row(S) − χv = row(S − u) (we note that the LHS subtracts the indicator vector
of the vertex v while the RHS considers the row vector of the set S − u, where u
is the vertex with d S (u) = 1),
2. Every X ∈ C such that X ⊂ S either has d X (u) = 1 or X does not contain u, and
3. For every X ⊂ S such that X ∈ C and u, v ∈ X , row(X ) − χv = row(X − u).
Here, the first observation is due to d S (u) = 1 and thus row(S)u = 0. The second
observation follows because of monotonicity of the induced-degree function and the
fact that tight sets cannot have isolated vertices by Lemma 3. The third observation
follows by writing down the corresponding chain of inequalities as above for each
such set X . Then, by the three observations, we can remove the vertex u from every
set in C that contains u resulting C = C that still satisfies properties
in a set family
(1)–(4). However, we have that S∈C |S| < S∈C |S|, contradicting our choice of
family C.
Finally, we show that C also satisfies property (6). By way of contradiction, assume
that there exists A, B ∈ C such that A ⊂ B and xu = 0 for each u ∈ B − A. We first
show a lower bound on |δ(A, B − A)|.
|δ(A,B−A)|
Claim 4 2 ≥ −b(B − A).
Proof First, we argue that the subgraph G[B − A] is a forest. By way of contradiction,
suppose that the subgraph G[B − A] contains a cycle. Let C be a minimal cycle in the
subgraph G[B − A]. Then, gx (C) = 0 as xu = 0 for each u ∈ B − A by our hypothesis.
Furthermore, b(C) = 0 as C is a cycle. Thus, C ∈ Tx is a tight set. However, since
C ⊆ B − A, we have that C ∩ A = ∅. This contradicts the fact that all tight sets must
overlap (as shown by Lemma 2).
Let k be the number of disconnected acyclic components of the forest G[B − A].
Then, we have the following two observations:
1. b(B − A) = −k and
123
2. |δ(A, B − A)| ≥ 2k.

We note that the claim follows from above observations. We justify these observations
next.
The first observation follows from the fact that the subgraph G[B − A] is a forest.
In particular, we have that

b(B − A) = |E[B − A]| − |B − A| = (|B − A| − 1) − (k − 1) − |B − A| = −k.
We now prove the second observation. Each of the k acyclic components of the sub-
graph G[B − A] is either a singleton or has at least two leaves. If the component is a
singleton vertex v, then we have that |δ(v, A)| = d B (v) ≥ 2, where the inequality is
because B ∈ C and the family C satisfies property (5). Alternatively, suppose that the
component has two leaves. Let v be an arbitrary leaf of the component. We note that
the induced degree d B−A (v) = 1. Thus, |δ(v, A)| = d B (v) − d B−A (v) ≥ 1, where
the inequality is once again because B ∈ C and C satisfies property (5).

With the above lower bound on the cut size |δ(A, B − A)|, we get the required con-
tradiction as follows:
|δ(A, B − A)|
gx (A) + > gx (A) + xu
2
uv∈δ(A,B−A)

= gx (A) + gx (B − A) + (xu + xv )
uv∈δ(A,B−A)
= gx (B)
= b(B)
= |E[B]| − |B|

= |E[A]| + |E[B − A]| + |δ(A, B − A)|

− |A| + |B − A|
= b(A) + b(B − A) + |δ(A, B − A)|
|δ(A, B − A)|
≥ b(A) +
2
|δ(A, B − A)|
= gx (A) + .
2
The first inequality follows from xu < 1/2 ∀u ∈ V . The first equality follows from
the assumption that xu = 0 for each u ∈ B − A. The penultimate inequality follows
from Claim 4, and the final equality holds since the set A ∈ Tx is a tight set.

3.2.5 Proof of Theorem 2
We now complete the proof of Theorem 2. In the next lemma, we use a stronger
hypothesis that xu < 1/3 for all u ∈ V to show that there exist at least two vertices
u, v which take non-zero values. We emphasize that the lemma does not rely on extreme
point properties and holds for every feasible point x satisfying the hypothesis.
123
Lemma 5 Let G = (V , E) be a graph and S ⊆ V be such that G[S] is connected,

has minimum degree at least 2, and contains a 2-pseudotree. Let x ∈ PWD (G) such
that xu < 1/3 for all u ∈ V . Then, there exist distinct vertices u, v ∈ V such that
xu , xv > 0.
Proof By way of contradiction, let S ⊆ V be a set such that the subgraph G[S] is
connected, has minimum-degree at least 2, contains a 2-pseudotree, but S contains at
most one vertex with a corresponding non-zero vertex variable. We first consider the
case where xv = 0 for all v ∈ S. Observe that in this case, gx (S) = 0. Consequently,
we have that 0 = gx (S) ≥ b(S) = |E[S]| − |S| ≥ 1, a contradiction. Here, the first
inequality is by the weak-density constraint on S, and the second inequality is because
G[S] is connected and contains a 2-pseudotree—this can be observed by starting with
the 2-pseudotree, and then charging the remaining vertices to the edges which connect
them to the 2-pseudotree.
We next consider the case where the set S contains exactly one vertex v ∈ S such
that xv > 0. It follows that
(d S (v) − 1)xv = gx (S) ≥ b(S) = |E[S]| − |S|.
Here the first equality is because xv is the only non-zero variable, while the first
inequality is by the weak-density constraint for the set S. We now consider two cases
based on the degree of v in G[S].
First, consider the case where d S (v) ≥ 4. Then we have the following:
1
|E[S]| − |S| u∈S d S (u) − |S| |S| − 1 + d S2(v) − |S|
xv = = 2
≥
d S (v) − 1 d (u) − 1 d S (v) − 1
S
1 1 1 2 1
= 1− ≥ · = ,
2 d S (v) − 1 2 3 3
a contradiction to our hypothesis that xu < 1/3 ∀u ∈ V . Here, the first inequality is
by hypothesis that d S (u) ≥ 2 for each u ∈ S.
Next, consider the case where d S (v) ≤ 3. We recall (from the last sentence of the
first paragraph) that b(S) = |E[S]| − |S| ≥ 1 since G[S] is connected and contains a
2-pseudotree. This gives us the required contradiction as follows:
1 ≤ b(S) ≤ gx (S) = (d S (v) − 1)xv ≤ 2xv < 1,
Here, the first inequality holds by the weak-density constraint for the set S, while the
final inequality holds due to our hypothesis that xv < 21 .

We use Lemma 5 to conclude the following:
Corollary 5.1 Let G = (V , E) be a connected graph with minimum degree at least 2

such that G contains a 2-pseudotree. Let x be an extreme point of PWD (G) such that
xu < 13 for all u ∈ V , the family of tight sets for x be Tx := {S ⊆ V : f x (S) = 0},
and let Z := {u ∈ V : xu = 0}. Let C ⊆ Tx be a chain family satisfying the properties
123
in Lemma 4. Then, for every S ∈ C, there exist distinct vertices u, v ∈ S such that
xu , xv > 0.
Proof By Lemma 4, we have that for every A ∈ C, the subgraph G[A] has minimum
degree at least 2 and contains a 2-pseudotree. The claim follows by applying Lemma 5
to the connected component of G[A] containing the 2-pseudotree.

We now restate and prove Theorem 2.

Proof By way of contradiction, let xu < 13 for all u ∈ V . Let C = {C1 , C2 , C3 , . . . , Ct }

be the chain basis guaranteed by Lemma 4. We order the sets in the basis so that
C0 ⊆ C1 ⊆ C2 ⊆ C3 ⊆ · · · ⊆ Ct ⊆ Ct+1 , where we denote C0 := ∅ and
Ct+1 := V for notational convenience. Let NZ(Ci ) = {v ∈ Ci : xv > 0}. Let
NZ := NZ(V ) be the set of vertices v with xv > 0. Then, NZ can be partitioned as
follows: NZ(V ) = i∈[t+1] NC(Ci )\NC(Ci−1 ). Hence, we have that

|C| < NZ(Ci )\NZ(Ci−1 ) ≤ |NZ|.
i∈[t]
The first inequality holds due to the following two reasons: (i)|NZ(C1 )\NZ(C0 )| =
|NZ(C1 )| ≥ 2 by Corollary 5.1 and (ii) |NZ(Ci )\NZ(Ci−1 )| ≥ 1 for i ∈ [2, t] by
property (6) of Lemma 4. The second inequality is because |NZ(Ct+1 )\NZ(Ct )| ≥ 0
and our observation that the set of differences of subsequent basis sets in the chain
ordering of C partitions the set of non-zero variables. Thus, we have that
|V | = |Z| + |C| < |Z| + |NZ| = |V |,
a contradiction. The first equality is because x is an extreme point and C is such that
Rows(C ∪ Z) is linearly independent and span(Rows(C ∪ Z)) = span(Rows(Tx ∪ Z))
by Lemma 4. The last equality is because the number of variables is equal to the sum
of the number of zero variables and the number of non-zero variables.

3.3 Extreme point property of the orientation polyhedron
In this section, we prove Theorem 3. We restate it below.

that xu ≥ 1/3.
We recall that an extreme point of Porient (G) is said to be minimal if we cannot

lower any single variable, keeping the others unchanged, while maintaining feasibility.
Before proceeding with the proof of Theorem 3, we establish a few lemmas. In the
lemmas below, we always assume that G is not a pseudoforest, (x̄, ȳ) is a minimal
123
extreme point of Porient (G) and, aiming toward a contradiction, x̄(v) < 1/3 for all
vertices v ∈ V (G).
For a graph G, we denote its edge-vertex incidence graph by H . Thus, V (H ) =
V (G) ∪ E(G) and E(H ) = {ev : e ∈ E(G), v ∈ V (G), e ∈ δ(v)}. We note that
|V (H )| = |V (G)| + |E(G)| and |E(H )| = 2|E(G)|. The support graph of ȳ is the
subgraph of the incidence graph H whose vertices are all the vertices of the incidence
graph H and whose edges are those for which ȳe,v > 0. Denoting this subgraph by
H ( ȳ), we have V (H ( ȳ)) = V (H ) = V (G) ∪ E(G) and E(H ( ȳ)) = {ev ∈ E(H ) :
ȳe,v > 0}.
Lemma 6 The support graph H ( ȳ) is a forest.
Proof Towards a contradiction, suppose that there exists a cycle in H ( ȳ). Since H ( ȳ)
is bipartite, the edge set of this cycle can be partitioned into two matchings M1 and M2 .
Given some ε > 0, we define two points ȳ ± ∈ R E(H ) by letting ȳ ± := ȳ ± εχ M1 ∓
εχ M2 . If ε is sufficiently small, both (x̄, ȳ + ) and (x̄, ȳ − ) are feasible (that is, belong to
the orientation polytope), which contradicts the fact that (x̄, ȳ) = 21 (x̄, ȳ + )+ 21 (x̄, ȳ − )
is extreme.

Lemma 7 The number of (connected) components of H ( ȳ) is |V (G)| − |E(G)| + m 0 ,

where m 0 denotes the number of edges ev ∈ E(H ) such that ȳe,v = 0.
Proof We have that |V (H ( ȳ))| = |V (G)| + |E(G)| and |E(H ( ȳ))| = 2|E(G)| − m 0
by definition. By Lemma 6, the number of components of H ( ȳ) is
|V (H ( ȳ))| − |E(H ( ȳ))| = (|V (G)| + |E(G)|) − (2|E(G)| − m 0 )

= |V (G)| − |E(G)| + m 0 .

Lemma 8 Every edge e = vw ∈ E(G), we have ȳe,v > 0 or ȳe,w > 0 (or both) and
x̄v + x̄w + ȳe,v + ȳe,w = 1.
Proof If both ȳe,v = 0 and ȳe,w = 0 then, since (x̄, ȳ) is feasible, we have x̄v + x̄w ≥ 1.
Hence, x̄v ≥ 1/2 or x̄w ≥ 1/2, a contradiction.
For the second part, toward a contradiction, suppose that x̄v + x̄w + ȳe,v + ȳe,w > 1.
We may assume (by symmetry) that ȳe,v > 0. Then, slightly decreasing ȳe,v preserves
the feasibility of (x̄, ȳ). This contradicts the minimality of (x̄, ȳ).

Now consider a component T of the support graph H ( ȳ). By Lemma 6, the com-
ponent T is a tree. We define the defect of T as the number vertices v ∈ V (T ) ∩ V (G)
such that x̄v > 0, plus the number of vertices v ∈ V (T ) ∩ V (G) such that
x̄v + e∈δ(v) ȳe,v < 1. Below, we denote this quantity
by defect(T ).
We say that component T is tight if x̄v + e∈δ(v) ȳe,v = 1 for all vertices v ∈
V (T ) ∩ V (G). Tight components play an important role in our analysis. We seek a
tight component with extra properties, dubbed ‘interesting’ (Lemma 11 below states
that such tight components exist).
123
Lemma 9 Let T be a tight component of H ( ȳ). Suppose that some vertex v ∈ V (G) is
a leaf of T . Then T has exactly two vertices and x̄w = 0 for the other vertex w ∈ V (G)
that is incident to the unique edge of G in T .

Proof Since T is tight, we have x̄v + e∈δ(v) ȳe,v = 1. If ȳe,v = 0 for all e ∈ δ(v), we
get x̄v = 1, a contradiction. Hence, T has at least two vertices and we have ȳe,v = 0
for all e ∈ δ(v) except for precisely one edge, say f = vw. From x̄v + ȳ f ,v = 1 and
x̄v + x̄w + ȳ f ,v + ȳ f ,w (see Lemma 8), we get x̄w + ȳ f ,w = 0, which implies x̄w = 0
and ȳ f ,w = 0. The result follows.

We will call a tight component T with exactly two vertices as a dyad. Let T be a
say, with V (T ) = {v, f } where v ∈ V (G) and f = vw ∈ E(G). We note that
dyad,
xv + e∈δ(v) ye,v = 1 follows from the tight constraints xv + xw + y f ,v + y f ,w = 1,
xw = 0, ye,v = 0 for all e ∈ δ(v) \ { f } and y f ,w = 0.
Lemma 10 Let T1 , …, Tk denote the components of H ( ȳ) and let d denote the number
of dyads. We have
k
defect(Ti ) ≤ k − d . (6)
i=1
Proof The number of variables defining the orientation polytope is |V (G)|+|E(H )| =

|V (G)| + 2|E(G)|. By Lemma 8, we can write the total number of constraints that
are tight at (x̄, ȳ) as |E(G)| + n tight
+ n 0 + m 0 , where n tight denotes the number of
vertices v ∈ V (G) such that x̄v + e∈δ(v) ȳe,v = 1, n 0 denotes the number of vertices
v ∈ V (G) such that x̄v = 0, and m 0 (as above) denotes the number of edges ev ∈ E(H )
such that ȳe,v = 0. For every dyad T , the tight constraint x̄v + e∈δ(v) ȳe,v = 1 follows
from the other tight constraints, where v is the unique vertex of G in T . Since (x̄, ȳ) is
an extreme point, we have that the number of variables is at most the number of tight
constraints. Hence,
|V (G)| + 2|E(G)| ≤ |E(G)| + n tight + n 0 + m 0 − d.
Rewriting the above gives
|V (G)| − n tight + |V (G)| − n 0 ≤ |V (G)| − |E(G)| + m 0 − d .
Inequality (6) follows from this and Lemma 7.

We call a component T of H ( ȳ) interesting if it is tight, has defect at most 1 and
is not a dyad. By Lemma 9, interesting components T have the following properties:
(i) T has at least three vertices, (ii) every leaf of T is an edge of G, and (iii) x̄(v) = 0
for all vertices v ∈ V (T ) ∩ V (G) except at most one.
Lemma 11 At least one component of H ( ȳ) is interesting.
Proof First, we observe that if x̄v = 0 for all vertices v ∈ V (G), then G is a pseudo-
forest, which contradicts our hypothesis. Hence, there exists a vertex r ∈ V (G) with
x̄r > 0.
123
Let T1 , …, Tk denote the components of H ( ȳ). If some Ti which is not a dyad has
defect(Ti ) = 0, then Ti is interesting. Hence, we may assume that defect(Ti ) ≥ 1 for
all components that are not dyads. By Lemma 10, this implies defect(Ti ) = 0 for all
dyads and defect(Ti ) = 1 for all the other components. Then, the unique component
containing r is interesting.


that xu ≥ 1/3.
Proof Aiming toward a contradiction, suppose that x̄v < 1/3 for all vertices v ∈ V (G).
Hence, each one of the above lemmas apply. Let T denote an interesting component
of H ( ȳ), which exists by Lemma 11. Since it is interesting, T has at least two vertices
and each leaf of T is an edge of G.
Let r ∈ V (T ) ∩ V (G) denote any vertex such that x̄v = 0 for all vertices v ∈
V (T ) ∩ V (G) distinct from r . We call r the root of T . For w ∈ V (G), let dT (w)
denote the number of edges e ∈ V (T ) ∩ E(G) that are incident to w. (This is a slight
abuse of notation since dT (w) is also defined for vertices w ∈ V (G) outside of T .) We
let N (T ) denote the set of vertices w ∈ V (G) such that dT (w) > 0 and w ∈ / V (T ).
Finally, we let L(T ) ⊆ E(G) denote the leaf set of T .
By Lemma 8 and since T is an interesting component of the support graph H ( ȳ),
we have
|V (T ) ∩ E(G)| − |V (T ) ∩ V (G)|
⎛ ⎞

= x̄v + x̄w + ȳe,v + ȳe,w − ⎝x̄v + ȳe,v ⎠
e=vw∈V (T )∩E(G) v∈V (T )∩V (G) e∈δ(v)

= (dT (r ) − 1)x̄r + dT (w)x̄w .
w∈N (T )
We notice that |V (T ) ∩ E(G)| − |V (T ) ∩ V (G)| = |L(T )| − 1. Hence, from the

equations above, we get

(dT (r ) − 1)x̄r + dT (w)x̄w = |L(T )| − 1 . (7)
w∈N (T )

Let M := (dT (r ) − 1) + w∈N (T ) dT (w) = (dT (r ) − 1) + |L(T )| denote the
sum of the coefficients in the left-hand side of (7). We note that dT (r ) ≤ |L(T )|. This
implies M ≤ 2|L(T )| − 1. Thus,
⎛ ⎞
1 ⎝ |L(T )| − 1 1
(dT (r ) − 1)x̄r + dT (w)x̄w ⎠ ≥ ≥ .
M 2|L(T )| − 1 3
w∈N (T )
123
Fig. 4 WD-CC Primal and Dual LPs for FVS
This is a contradiction since the left-hand side is an average of values that are all
strictly less than 1/3.

4 Feedback vertex set
In this section, we prove our main results for FVS. We prove Theorem 4 in Sect. 4.1 and
Theorem 5 in Sect. 4.2. We discuss two additional polynomial-sized ILP formulations
for FVS with integrality gap at most 2 in Sect. 4.3.
4.1 Weak density and cycle cover constraints
In this section, we restate and prove Theorem 4.

(FVS-IP: WD-and-cycle-cover) is an integer linear programming formulation for FVS.
Moreover, the integrality gap of (FVS-LP: WD-and-cycle-cover) is at most 2.
Let G = (V , E) be agraph with non-negative vertex costs c : V → R≥0 . By
definition, the ILP min{ u∈V cu xu : x ∈ Pcycle-cover (G) ∩ ZV } formulates FVS.
We note that weak density constraints are valid for FVS. Consequently, (FVS-IP:
WD-and-cycle-cover) is an ILP formulation for FVS. The rest of the section is devoted
to proving the integrality gap bound mentioned in Theorem 4.
Lemma 12 The integrality gap of the LP (FVS-LP: WD-and-cycle-cover) is at most 2.
Let C be the set of cycles in the input graph G. Let b(S) := |E[S]| − |S| for all
S ⊆ V . We rewrite (FVS-LP: WD-and-cycle-cover) and its dual in Figure 4.
We will need the definition of semi-disjoint cycles from [6]: A cycle C in graph G is
semi-disjoint (with respect to the graph G) if there is at most one vertex in C of degree
strictly larger than 2. We call such a vertex as the pivot vertex of the semi-disjoint
cycle. We note that such cycles can be viewed as “hanging off” the graph via their
pivots which are cut vertices.
4.1.1 Minimal FVS and weak density constraints
In this section, we show an important property of inclusion-wise minimal feedback

vertex sets. Let F be a feedback vertex set for a graph G. A witness cycle for a vertex
f ∈ F is a cycle C of the graph G such that F ∩ C = { f } i.e. f is the only vertex that
123
witnesses the cycle C. We note that every vertex of a minimal FVS must have a witness
cycle. In Lemma 13, we show that for a graph with non-trivial degree and no semi-
disjoint cycles, every minimal feedback vertex set is essentially a 2-approximation to
the optimal feedback vertex set with respect to an appropriate cost function. We note
that our proof of the lemma appears implicitly in [6]. However, we include it here for
completeness.
Lemma 13 Let G be a graph with minimum-degree at least 2 and containing no semi-

disjoint cycles. Then, for every minimal feedback vertex set F, we have that

(d(v) − 1) ≤ 2b(V ).
v∈F
Proof We first show a convenient sufficient condition that proves the claimed upper
bound. We subsequently prove this sufficient condition by an edge-counting argument.
Let t denote the number of connected components in G − F.

Claim 5 If |δ(F, V − F)| ≥ |F| + 2t, then v∈F (d(v) − 1) ≤ 2b(V ).
Proof We have the following:

(d(v) − 1) = 2|E| − |F| − d(v)
v∈F v∈V −F

= 2|E| − |F| − |δ(F, V − F)| + 2|E[V − F]|

= 2|E| − |F| − |δ(F, V − F)| + 2(|V | − |F| − t)

≤ 2|E| − |F| − 2|V | − |F|
= 2b(V ).
Here, the first equality holds because the sum of all vertex degrees is 2|E|, the third
equality is because G − F is acyclic, and the inequality is due to the hypothesis that
|δ(F, V − F)| ≥ |F| + 2t.

We now show that a minimal feedback vertex set F has at least |F| + 2t edges
crossing it. For this, we consider the auxiliary bipartite graph H = (K ∪ F, E H ) as
follows: Each vertex k ∈ K corresponds to a connected component Ck in G − F. For
vertices k ∈ K , f ∈ F, the graph H contains the edge (k, f ) if there exists a vertex
v ∈ Ck such that the edge (v, f ) ∈ E exists in the original graph G. Furthermore, we
define the weight of an edge (k, f ) ∈ E H as w H (k, f ) := |δG (Ck , f )|. We note that
|K | = t.
Since F is an inclusionwise minimal feedback vertex set, every vertex f ∈ F has
a witness cycle. We note that there are no edges between the components of G − F.
Thus, every witness cycle is completely contained in some component Ck for some
k ∈ K . In particular, this implies that in the graph H , every vertex f ∈ F has an
edge of weight at least 2 incident on it. For each f ∈ F pick an arbitrary such edge
e f ∈ δ H ( f ) of weight at least 2 and call it f ’s primary edge. Then, reducing the
weight of all primary edges by 1 still leaves all edges in E H with positive weight, but
123
counts |F| edges in the cut |δ(F, V − F)| in the original graph G. Let H denote the
residual graph after this weight reduction. By Claim 5, it now suffices to show that the
weight of all edges in H is at least 2|K |.
For this, we claim that each vertex k ∈ K must have a cumulative edge-weight of
at least 2 incident on it in the residual graph H . By way of contradiction, suppose that
there exists a vertex k ∈ K with total incident edge-weight at most 1. We consider two
cases. First, suppose that k has no incident edges. We recall that we reduced the weight
of only primary edges in our weight-reduction step. Thus, if there was a primary edge
incident to k, then k would have a weight 1 edge incident on it in the residual graph,
contradicting the case assumption. Thus, there are no edges incident to Ck in G, i.e.
Ck is a disconnected acyclic component of G. In particular, Ck contains a leaf vertex,
contradicting the hypothesis that the minimum degree of G is at least 2.
Next, consider the case where k has a total weight of 1 incident on it in the residual
graph H . Let f ∈ F be its unique neighbor in the residual graph. Then, f must also
be its unique neighbor in H . We note that if Ck has only one edge to f in G, then
Ck must contain a leaf node in G as it is acyclic, a contradiction. Thus, Ck does not
contain any leaf nodes, is acyclic, and has exactly 2 edges to f in G. In particular,
Ck ∪ { f } is a semi-disjoint cycle in G, contradicting the hypothesis that G has no
semi-disjoint cycles.

4.1.2 Proof of integrality gap
In this section, we prove Lemma 12, i.e., we show that the integrality gap of the LP-
relaxation for FVS given in Figure 4 is at most 2. We prove this by constructing a dual
feasible solution (y, z) and a FVS F such that the cost of F is at most twice the dual
objective value of (y, z). This implies that the integrality gap of the LP is at most 2 since
the LP is a relaxation for FVS. We construct such a pair of solutions via a primal-
dual algorithm. Our primal-dual algorithm is an extension of the 2-approximation
primal-dual algorithm due to [6]. We state our algorithm in Algorithm 1.
Algorithm 1 Primal-Dual for FVS

Input: (1) Graph G = (V , E); (2) Vertex weights c : V → R+ .
Output: Feedback vertex set F ⊆ V .
1. Initialize (y, z) := 0, i := 1, F := ∅, and G 1 = G.
2. While the graph G i = (Vi , E i ) has a cycle:
(a) Recursively remove vertices of degree 1 from G i .
(b) If G i has a semi-disjoint cycle Ci :
Define the set Si = Ci as the semi-disjoint cycle.
Increase dual variable z Si until the first dual constraint for some vertex vi ∈ Ci becomes tight.
(c) Else:
Define the set Si = Vi as the entire vertex set.
Increase dual variable y Si until the first dual constraint becomes tight for some vertex vi ∈ Vi .
(d) Update F := F ∪ {vi }
G i+1 := G i − vi
i := i + 1.
3. Perform reverse-delete on F.
4. Return F.
123
Algorithm 1 is a primal-dual algorithm based on the LP relaxation for FVS given

in Figure 4. The algorithm initializes with the dual feasible solution (y = 0, z = 0).
In the ith iteration of the while-loop, the algorithm selects a specific set Si of vertices
(which is either a cycle Ci or entire vertex set Vi ) and increases the corresponding dual
variable until a dual constraint for some vertex vi ∈ Si becomes tight. It then includes
the vertex vi into the FVS and removes vi from the graph. Adding vi to the candidate
set F is interpreted as setting the primal variable xvi = 1. Thus, Algorithm 1 always
maintains dual feasibility and primal complementary slackness (i.e., xvi = 1 only if
the dual constraint for vi is tight).
We now explain the reverse-delete procedure mentioned in Algorithm 1. Let be the
number of iteration of the while loop. The reverse-delete procedure iteratively consid-
ers vertices in the reverse-order in which they were added into F, i.e. v , v−1 , . . . v1 .
For every vertex in this order, the procedure checks whether removal of this vertex
from F is still a feasible FVS for G. If so, then the vertex is removed from F. We will
later rely on reverse-delete to show that F ∩ Si is a minimal FVS in G[Si ] for every
iteration i.
We now observe that the algorithm terminates in polynomial time to return a feasible
FVS.
Lemma 14 (Feasibility and Runtime) Algorithm 1 returns a feasible FVS for the input
graph G in polynomial time.
Proof Each step of the while loop and reverse-delete procedure can be implemented
to run in polynomial time. In ith iteration of the while-loop, at least one vertex of
the graph G i is removed. The empty graph has no cycles and so the while-loop will
terminate in at most linear number of iterations. Furthermore, the reverse delete step
considers every vertex in F exactly once, and so, it also terminates in at most linear
number of steps. The output set F is a feasible FVS by the terminating condition
of the while-loop and the fact that reverse-delete deletes a vertex only if its deletion
maintains feasibility.

We now bound the approximation factor of the solution F returned by Algorithm 1.

Let (y, z) be the dual solution constructed by Algorithm 1 and let χ F ∈ {0, 1}V be the
indicator vector of F. We note that Lemma 14 implies that χ F is a feasible solution
to the primal LP. Let primal(χ F ), dual(y, z) denote the objective values of the
primal and dual LPs for solutions χ F and (y, z) respectively.
Let I1 ⊆ [] denote the set of iterations in which the dual variable for the entire
residual graph was increased (i.e. statement (c) of Algorithm 1 is executed) and let
I2 ⊆ [] denote the set of iterations in which the dual variable for a semi-disjoint cycle
in the residual graph was increased (i.e. statement (b) of Algorithm 1 is executed). For
notational convenience, we let F j = F ∩ {v j } and F≥ j = ∪k∈[ j,] F j . The next lemma
shows that the set Si ∩ F≥i is a minimal feedback vertex set for the subgraph G[Si ]
for each i ∈ [].
Lemma 15 The set Si ∩ F≥i is a minimal feedback vertex set for the subgraph G[Si ]
for each i ∈ [].
123
Proof We prove by induction on −i. For the base case, we consider i = . We observe
that F≥ = {v } as otherwise, the following two observations result in a contradiction:
(i) The reverse-delete step only removes v from F if the set F − {v } is a feasible
feedback vertex set for G; and (ii) if F − {v } were a FVS for G, then the algorithm
would have terminated after the ( − 1)th iteration. We note that F is a FVS for G as
there was no ( + 1)th iteration. If the set S = V is the entire vertex set of the graph
G , then v ∈ V . Alternatively, if the set S is a semi-disjoint cycle C , then v ∈ C ,
as otherwise the cycle C would remain in G +1 contradicting that there were only
iterations. In both scenarios, the set S ∩ F≥ is a minimal FVS for G[S ].
For the inductive case, assume that 0 ≤ i < . By the inductive hypothesis, we
have that the set S j ∩ F≥ j is a minimal FVS for the graph G[S j ] for all ≥ j > i.
We consider two cases based on whether the set Si is a semi-disjoint cycle of G i or
the entire vertex set of G i .
First, we consider the case where Si is a semi-disjoint cycle Ci . We need to show
that |F ∩ Ci | = 1. We observe that 1 ≤ |F ∩ Ci | ≤ 2: The lower bound follows
from the fact that the set F≥i is a feasible FVS for G i and thus intersects all cycles
in at least one vertex. The upper bound holds by the following three observations: (i)
The vertex vi is the first vertex of the set Ci to be selected into F by the algorithm;
(ii) If the vertex vi is the pivot vertex, then all vertices in Ci − {vi } get recursively
removed and thus cannot be selected into F in any subsequent iteration after i; and
(iii) If the vertex vi is not the pivot vertex, then all vertices in Ci − {vi } except the
pivot vertex get recursively removed due to step (a) and thus, only the pivot vertex
can be included into F in some subsequent iteration after i. We note that if scenario
(ii) happens, then F≥i ∩ Ci = {vi } and hence, |F ∩ Ci | = 1. Alternatively, suppose
that scenario (iii) happens. If the pivot is never selected into F, then once again we
have F≥i ∩ Ci = {vi } and hence, |F ∩ Ci | = 1. Otherwise the pivot is selected
into F and the reverse-delete step processes the pivot vertex before processing vi .
If the reverse-delete step removes the pivot vertex from F, then once again we have
F≥i ∩ Ci = {vi } and hence, |F ∩ Ci | = 1. Otherwise, the reverse-delete step does
not remove the pivot from F. Consider the iteration of reverse-delete that processes
vi —we need to show that reverse-delete will indeed remove vi in this iteration. We
observe that the set {vk : k ∈ [1, i − 1]} has not been processed by reverse-delete and
this set intersects every cycle that is not entirely contained in G i (this is true since G i
is the residual graph after removal of {v1 , . . . vi−1 } along with recursively removing
degree-1 vertices in each step). Since the pivot for Ci is already in F and the cycle
Ci is semi-disjoint in G i , the reverse-delete step must remove the vertex vi from F as
vi intersects no cycles other than those already intersected by F − {vi }. In particular,
F≥i ∩ Ci is a singleton set consisting of the pivot vertex for Ci . Thus, in all cases we
have that |F≥i ∩ Ci | = 1. It follows that Fi is a minimal FVS for the cycle G[Ci ].
Next, we consider the case when Si = Vi is the entire vertex set of the subgraph
G i . Here, we consider the set of all cycles that vi intersects in G and partition them
into two types: (1) Cycles completely contained in G i ; and (2) cycles that include at
least one vertex from V − Vi . Since F≥i is a feasible FVS for G i , we have that F≥i
intersects all cycles of the first type. Furthermore, since the vertices in V − Vi do not
exist in G i , the set {v1 , . . . , vi−1 } intersect all cycles of the second type. We recall that
the set F≥i+1 is a minimal FVS for G i+1 .
123
We consider the first subcase where the set F≥i+1 is an FVS for the graph G i . Then,
the set F≥i+1 intersects all cycles contained in G i . In particular, it intersects all cycles
of type (1). Thus, the set {v1 , . . . , vi−1 } ∪ F≥i+1 is a feasible FVS for the original
graph G. Due to this, the reverse-delete step removes the vertex vi from F and we
have that F≥i = F≥i+1 . Furthermore, by the inductive hypothesis we have that F≥i+1
is a minimal FVS for G i+1 . Thus, the set F≥i is a minimal FVS for G i = G[Si ].
We next consider the remaining subcase where the set F≥i+1 is not a FVS for the
graph G i . In particular, there must be a cycle of the first type that vi intersects, but
none of the vertices of F≥i+1 intersect. In particular, the set {v1 , . . . , vi−1 } ∪ F≥i+1
is not a feasible FVS for the original graph G as the set does not intersect all type
(1) cycles. Thus, the reverse-delete step cannot remove vi from F. By the induction
hypothesis, we have that F≥i+1 is a minimal FVS for G ≥i+1 . Consequently, none of
these vertices can be removed from F≥i as the resulting set would not be a feasible
FVS. It follows that F≥i is a minimal FVS for G i = G[Si ].

We show in Lemma 16 that the solution F constructed by the algorithm has cost
at most twice the objective value of the dual feasible solution (y, z) constructed by
the algorithm. We recall that χ F ∈ {0, 1}V is the indicator vector of the set F and
primal(χ F ), dual(y, z) denote the objective values of the primal and dual LPs for
solutions χ F and (y, z) respectively.
Lemma 16 (Integrality gap bound) We have that
primal(χ F ) ≤ 2 · dual(y, z).
Proof We have that

primal(χ F ) = cv
v∈F
⎛ ⎞

= ⎝ (d S (v) − 1)y S + zC ⎠
v∈F S⊆V :v∈S C∈C:v∈C

= yS (d S (v) − 1) + zC 1
S⊆V v∈F∩S C∈C v∈F∩C

= y Si (d Si (v) − 1) + z Ci |F ∩ Ci |
i∈I1 v∈F∩Si i∈I2

≤2 y Si b(Si ) + z Ci
i∈I1 i∈I2
≤ 2 · dual(y, z).
Here, the second equality follows by the primal complementary slackness maintained
by Algorithm 1. The fourth equality follows by the fact that all dual variables that
were not incremented during some iteration of Algorithm 1 have value zero. The
first inequality follows by Lemma 15 and Lemma 13. Here, we note that for i ∈ I2 ,
123
|F ∩ Ci | = 1 (by Lemma 15) because G[Ci ] is an induced cycle and consequently a

minimal FVS for G[Ci ] contains exactly 1 vertex.

dual(y, z) ≤ primal(χ )
Lemma 16 completes the proof of Lemma 12 since F
by weak duality and the fact that the ILP min{ u∈V cu xu : x ∈ PWD (G) ∩
Pcycle-cover (G) ∩ ZV } is an ILP formulation for FVS (whose LP-relaxation is given in
Figure 4). It also proves that the approximation factor of the solution F returned by
Algorithm 1 is at most 2.
4.2 Orientation and cycle cover constraints
In this section, we give a polynomial-sized ILP for FVS based on orientation and cycle
cover constraints. Moreover, we show that the integrality gap of the LP-relaxation of
this formulation is at most 2. We consider the following formulation:
⎧ ⎫
⎨ ⎬
min cu xu : x ∈ Q orient (G) ∩ Pcycle-cover (G) ∩ ZV .
⎩ ⎭
u∈V
(FVS-IP: orient-and-cycle-cover)
Lemma 17 For an input graph G = (V , E) with non-negative vertex costs c : V →

R≥0 , (FVS-IP: orient-and-cycle-cover) is an integer linear programming formulation
for FVS. Moreover, its LP-relaxation has integrality gap at most 2.
Proof The indicator vector x of a feedback vertex set of G is contained in Q orient (G) ∩
Pcycle-cover (G). Moreover, every integral solution x ∈ Q orient (G) ∩ Pcycle-cover (G) is
the indicator vector of a feedback vertex set: since x ∈ Q orient (G) ∩ ZV , we have that
x ∈ {0, 1}V and since x ∈ Pcycle-cover (G), we have that x is the indicator vector of a
feedback vertex.
We now show that the integrality gap of the LP-relaxation is at most 2. By Theo-
rem 1(1), we have that Q orient (G) ⊆ PWD (G) and hence, the integrality gap of the
LP-relaxation is at most the integrality gap of (FVS-LP: WD-and-cycle-cover). By
Theorem 4, the integrality gap of (FVS-LP: WD-and-cycle-cover) is at most 2.

Theorem 5 follows from Lemma 17, the observation that Q orient (G) can be
expressed using polynomial number of variables and constraints (see the descrip-
tion of Porient (G)), and the fact that the cycle cover polyhedron can equivalently be
described using polynomial number of variables and constraints. We note that this fact
is folklore, but we include a proof of it in Lemma 19 in the appendix.
4.3 Alternative formulations
In Sect. 4.2, we described an ILP formulation based on orientation and cycle cover
polyhedra and showed that its LP-relaxation is at least as strong as (FVS-LP: WD-and–
cycle-cover). We briefly discuss two more polynomial-sized LP-relaxations for FVS
123
with integrality gap at most 2. We give full details in the appendix for the sake of
completeness.
We recall that Chekuri and Madan [8] gave a polynomial-sized ILP formulation for
Subset-FVS. We note that the LP-relaxation of their ILP-formulation specialized for
FVS has integrality gap at most that of the LP-relaxation of (FVS-IP: orient-and-cycle-
cover). Consequently, the LP-relaxation of their ILP formulation has integrality gap at
most 2. We present the details in Appendix B.2. This result gives additional impetus
to improving the integrality gap analysis of their LP-relaxation for Subset-FVS.
Next, we give an ILP formulation based only on orientation constraints (without
relying on cycle cover constraints) - see Appendix B.3. We show that its LP-relaxation
is at least as strong as that of the strong density constraints based formulation and
consequently is also at most 2.
A Pseudoforest deletion set
A.1 Polynomial-time separation oracle for 2-pseudotree cover constraints
In this section, we show that the family of 2-pseudotree cover constraints admits a
polynomial time separation oracle.
Lemma 18 The family of 2-pseudotree cover constraints admits a polynomial-time

separation oracle.
In order to solve the separation problem, it suffices to design a polynomial time

algorithm for the Minimum
Cost 2-Pseudotree problem:
The input to MC2PT is a
vertex-weighted graph G = (V , E) , w : V → R≥0 , and the goal is to compute a
minimum weight subset U ⊆ V of vertices such that G[U ] is a 2-pseudotree, i.e.,
⎧ ⎫
⎨ ⎬
min w(u) : U ⊆ V and G[U ] is a 2-pseudotree .
⎩ ⎭
u∈U
Our strategy to solve MC2PT is to reduce it to solving a polynomial number

of special instances of the Minimum Node-Weighted Steiner Tree4 (NWST), and
use the result of [4] which says that these special instances of NWST can be
solved
in polynomial time. Formally,
the input to NWST is a vertex-weighted graph
G = (V , E) , w : V → R≥0 and a terminal set S ⊆ V . We will say that a graph
H is a Steiner tree in G for terminal set S if H is connected, acyclic, and is
a subgraph of G with S ⊆ VH . Moreover, the weight of a subgraph H of G
is the sum of weights of vertices in H . The NWST problem is to find a mini-
mum weight Steiner tree in G for terminal set S, i.e., min{ u∈VH w(u) : H =
(VH , E H ) is a Steiner tree in G for terminal set S}. NWST can be solved in polyno-
mial time if the number of terminals is a constant.
4 We refer to nodes as vertices for consistency with the rest of our technical sections.
123
Proposition 3 (Theorem 1 of [4]) There exists a O(3k n + 2k n 2 + n 3 ) time algorithm

for NWST, where k denotes the number of terminals and n denotes the number of
vertices in the input instance.
The following proposition shows a correspondence between minimum weight 2-

pseudotrees in a vertex-weighted graph and Steiner trees.
Proposition 4 Let G = (V , E) be a graph with non-negative vertex weights w : V →

let W ≥ 0. Then, there exists a subset U ⊆ V such that G[U ] is a 2-pseudotree
R≥0 and
with u∈U w(u) ≤ W if and only if there exists a pair of edges e1 = u 1 v1 , e2 = u 2 v2
in G such that there exists a Steiner tree H =(VH , E H ) in the graph G := G−{e1 , e2 }
for terminal set S := {u 1 , v1 , u 2 , v2 } with u∈VH w(u) ≤ W .
Proof We will say that a graph T = (VT , E T ) is a minimal 2-pseudotree if it is

connected and has exactly |VT | + 1 edges. Equivalently, T has exactly 2 edges in
addition to a spanning tree. We observe that for a subset U ⊆ V , the subgraph G[U ] is
a 2-pseudotree if and only if there exists a subgraph T = (U , E T ) of G[U ] such that T
is a minimal 2-pseudotree. Hence, it suffices to show that there exists a subset U ⊆ V
such that G[U ] has a subgraph that is a minimal 2-pseudotree with u∈U w(u) ≤ W
if and only if there exists a pair of edges e1 = u 1 v1 , e2 = u 2 v2 in G such that there
exists a Steiner tree H = (V H , E H ) in the graph G := G − {e1 , e2 } for terminal set
S := {u 1 , v1 , u 2 , v2 } with u∈VH w(u) ≤ W . We prove this statement now.
Let U ⊆ V suchthat G[U ] contains a subgraph T = (U , E T ) that is a minimal
2-pseudotree with u∈U w(u) ≤ W . Then, there exists a pair of edges e1 = u 1 v2
and e2 = u 2 v2 in T such that the subgraph H := T − {e1 , e2 } is acyclic, connected,
and is a subgraph of T . In particular, we have that H is acyclic, connected, and is a
subgraph of G := G − {e1 , e2 } with S = {u 1 , v1 , u 2 , v2 } ⊆ U = V (H ). Hence, for
of edges e1 , e2 in
the pair G, we have that H is a Steiner tree in G for terminal set S
with u∈V (H ) w(u) = u∈U w(u) ≤ W .
Next, let e1 = u 1 v2 , e2 = u 2 v2 be a pair of edges in G such that there exists
a Steiner tree H = (VH , E H ) in the graph G := G − {e1 , e2 } for terminal set
S = {u 1 , v1 , u 2 , v2 } with u∈VH w(u) ≤ W . Consider the graph T := H + {e1 , e2 }.
Then, T is a minimal 2-pseudotree. The vertex set of T is U := VH and T is a subgraph
of G[U ]. Hence, we have a subset U ⊆ V such that G[U ] has a subgraph that is a
minimal 2-pseudotree with u∈U w(u) ≤ W .

Lemma 18 The family of 2-pseudotree cover constraints admits a polynomial-time

separation oracle.
Proof It suffices to show that MC2PT can be solved in polynomial time. Let G =
(V , E) with vertex weights w : V → R≥0 be the input instance of MC2PT. Consider
the following algorithm: for all pairs of edges e1 = u 1 v1 and e2 = u 2 v2 in E, use
the algorithm guaranteed by Proposition 3 to solve NWST on the graph G − {e1 , e2 }
with vertex weights w for terminal set {u 1 , v1 , u 2 , v2 }, and return the minimum weight
solution over all instances. The correctness of the algorithm follows from Proposition 4.
We now analyze the runtime of the algorithm. There are O(|V |2 ) pairs of edges to
123
enumerate. Furthermore, for each pair of edges, the associated NWST instance can
be solved in polynomial time using the algorithm from Proposition 3 since each such
instance has only four terminals. Thus, the algorithm runs in polynomial time.

B Feedback vertex set
B.1 Polynomial-sized formulation of the cycle cover polyhedron
In this section, we show that Pcycle-cover (G) can be expressed using polynomial num-
ber of variables and constraints. This is folklore, but we include its proof for the
sake of completeness. For a graph G = (V , E), we define E := {(e, s), (e, t) :
∃ cycle in G containing e = st ∈ E} and consider
Pdist-cycle-cover (G)
⎧ ⎫
⎪
⎪ (e,s)
=0 ∀(e = st, s) ∈ E ⎪
⎪
⎨ ds ⎬
V V ×E
:= (x, d) ∈ R≥0 × R≥0 : dt(e,s) + xs ≥ 1 ∀(e = st, s) ∈ E .
⎪
⎪ (e,s) (e,s) ⎪
⎪
⎩ da + xb ≥ db ∀(e, s) ∈ E , ab ∈ E − {e} ⎭
(8)
Lemma 19 For every graph G = (V , E), the polyhedron Pcycle-cover (G) is the projec-
tion of the polyhedron Pdist-cycle-cover (G) to x variables. Consequently, Pcycle-cover (G)
admits a polynomial-sized description.
Proof Let Q dist-cycle-cover (G) be the projection of Pdist-cycle-cover (G) to the x variables.
We prove that Q dist-cycle-cover (G) = Pcycle-cover (G) by showing inclusion in both
directions.
First, we show that Q dist-cycle-cover (G) ⊆ Pcycle-cover (G). Let x ∈ Q dist-cycle-cover (G).
V ×E
Let d ∈ R≥0 be a vector such that (x, d) ∈ Pdist-cycle-cover (G). It suffices to show that
for every cycle C in G, we have that u∈V (C) xu ≥ 1. Let C be a cycle in G. Fix an edge
e = st ∈ E(C). By definition of the set E , we have that (e, s) ∈ E . Consequently,
ds(e,s) = 0 and dt(e,s) + xs ≥ 1 by the first two constraints of Pdist-cycle-cover (G). Let
a1 = s, a2 , a3 , . . . , ar −1 , ar = t be the ordered vertices along the s − t path induced
by E(C) − e. Then, for every i ∈ [r − 1], we have that da(e,s) i + xai+1 ≥ da(e,s)
i+1 by
the third constraint of Pdist-cycle-cover (G). Adding all of these constraints gives us that
r (e,s) (e,s)
i=2 x ai ≥ dar = dt ≥ 1 − xs = 1 − xa1 . Thus, the constraint ri=1 xai ≥ 1
holds.
Next, we show that Q dist-cycle-cover (G) ⊇ Pcycle-cover (G). Let x ∈ Pcycle-cover (G).
V ×E
Let d ∈ R≥0 be defined as follows: for each (e = st, s) ∈ E , let
⎧ ⎫
⎨ ⎬
du(e,s) := min xv : P is a path from s to u and P = {s, t} .
⎩ ⎭
v∈P−{s}
123
We show that (x, d) ∈ Pdist-cycle-cover (G). We note that the vector (x, d) is non-
(e,s)
negative by definition. Let (e = st, s) ∈ E . Then, ds = 0 by definition. Moreover,
(e,s)
dt + xs ≥ 1 holds because of the following reasoning: let P be a path from s
(e,s)
to t such that dt = v∈P−{s} xv and P = {s, t}. Then, P concatenated with the
(e,s)
edge st forms a cycle C and dt + xs = xs + v∈P−{s} xv = u∈V (C) xu ≥ 1.
(e,s) (e,s)
Finally, the inequality da + xb ≥ db for every edge ab ∈ E holds because
of the following reasoning: for an edge ab ∈ E, let P be a path from s to a such
(e,s)
that da = v∈P−{s} xv . Then, P concatenated with b is a path from s to b and
(e,s)
consequently, db ≤ v∈P+{b}−{s} xv by definition.

B.2 Chekuri–Madan formulation
In this section, we show that the polynomial-sized ILP for FVS given by Chekuri and
Madan is such that its LP-relaxation has integrality gap at most 2. Chekuri and Madan
formulated a polynomial-sized ILP for the more general problem of Subset Feedback
Vertex Set (SFVS). SFVS is defined as follows: The input is a graph G = (V , E)
with non-negative vertex costs c : V → R≥0 along with a set of terminals T ⊆ V . A
subset U of non-terminals is said to be a subset feedback vertex set if G − U has no
cycle containing a vertex of T . The goal is to find a least cost subset feedback vertex
set. In Sect. B.2.1, we discuss Chekuri–Madan’s ILP for SFVS (henceforth referred to
as (SFVS- IP: CM)) with some background and notation. In Sect. B.2.2, we discuss
a reduction from FVS to SFVS satisfying certain technical properties. In Sect. B.2.3,
we show that the integrality gap of the LP-relaxation of (SFVS- IP: CM) specialized
for FVS (henceforth referred to as the (FVS- LP: CM)) is at most 2.
B.2.1 Chekuri–Madan’s ILP for SFVS
In this section, we discuss the (SFVS- IP: CM). Let H = (VH , E H ) denote the input
graph, S H ⊆ VH denote the terminal set, and c H : VH → R≥0 denote the vertex cost
function. We will say that a cycle is interesting if it contains a terminal. Let C H denote
the set of interesting cycles in the graph H .
Henceforth, we will assume that a SFVS of finite cost exists in the graph H . Fur-
thermore, we will assume without loss of generality that the instance H satisfies the
following properties (see [8] for a justification of these assumptions):
(i) the graph H is connected,
(ii) each terminal si ∈ S H has infinite cost, is a degree two vertex with neighbors ai , bi
having infinite cost,
(iii) no two terminals are connected by an edge or share a neighbor,
(iv) there exists a special non-terminal degree one vertex r ∈ V with infinite cost, and
(v) each interesting cycle contains at least two terminals.
We refer to properties (i)–(v) as CM-properties.
Notation. Throughout this section we will use the following notation: We let k = |S H |
denote the number of terminals. We refer to the set Pi := {ai , bi } as the pivot set for
123
the terminal si , and the set PH = ∪i∈[k] Pi as the set of all pivots. We define the set
H (u)
= {i ∈ [k] : si is reachable from u via a path not containing any other terminals}
∪{k + 1}
as the set of labels for each vertex u ∈ VH \S. We denote ṼH as the set of vertices in
VH that are not in S H PH {r }. We denote Ẽ H as the set of edges in E H that are
not incident to any terminals and the set E H as the set of edges incident to terminals.
We will refer to E H as special edges.
(SFVS-IP: CM). See Figure 5 for the labelling-based (SFVS- IP: CM). In this ILP,
we have vertex variables xu for each u ∈ Ṽ indicating whether the vertex u is in the
SFVS F, and vertex labelling variables z u,i for each u ∈ Ṽ ∪ PH , i ∈ [k] indicating
whether vertex u receives label i. We note that Figure 5 simplifies the exposition
of the ILP from [8] by explicitly substituting the values for variables whose values
are directly set by constraints, i.e. xu = 0 for u ∈ S ∪ {r }, z si ,i = 1 for i ∈ [k], and
zr ,k+1 = 1. Moreover, it slightly strengthens
the first constraint (Chekuri–Madan used
a slightly weaker constraint: xu + i∈[k+1] z u,i = 1).
The constraints can be interpreted as follows: Let F be a minimal finite cost subset
feedback vertex set of H . Constraint (1) says that if a vertex u ∈ ṼH is not in F,
then it must receive exactly one of the labels in H (u). Constraint (2) says that exactly
one of ai and bi can receive the label i for each i ∈ [k]. Constraint (3) is a spreading
constraint that says that both end vertices of every non-special edge in H − F must
receive the same label. Constraint (4) is a cycle covering constraint and says that the
solution F must intersect every interesting cycle in at least one vertex. Constraint (5)
ensures that the set F contains no pivot vertices.
We now briefly address why a labeling satisfying the LP constraints must exist for
every minimal finite weight subset feedback vertex set F (see [8] for further details).
We note that none of the vertices of S ∪ P ∪ {r } are in F as these have infinite cost.
Let the graph H = (VH , E H ) be defined as H = H − F. For simplicity, we
first assume that the graph H is connected and then address the more general case
when H is not connected. Since there is no cycle containing any terminal in H , each
terminal is a cut vertex in H . Consider the block-cut-vertex tree decomposition T of
H — (refer to [19] for details on block-cut-vertex tree decompositions). We label a
vertex u of H as i ∈ [k] if terminal si is the first terminal encountered on any path
from vertex u to the root r in the graph H . If no terminals are encountered, then we
label the vertex as k + 1. We note that such a labelling is well-defined as T is the
block-cut-vertex tree and the set S are cut vertices. In this labelling, we observe that
every non-special edge uv ∈ Ẽ H has the property that both end points receive the
same label. Finally, in the case where H is not connected, we can justify the existence
of such a labeling by picking an arbitrary non-terminal vertex from each component,
imagining a dummy edge connecting it to the root r , and considering the labeling
corresponding to block-cut-vertex tree of this (implicit) graph.
123
Fig. 5 (SFVS- IP: CM)
B.2.2 Reduction from FVS to SFVS satisfying the CM-properties
FVS can be seen as a special case of SFVS where every vertex in the graph is a terminal.
However, this simple reduction does not result in an SFVS instance satisfying the CM-
properties (see properties (i)–(v) mentioned in the first paragraph of Sect. B.2.1). In this
section, we show how to construct an SFVS instance from an FVS instance such that
the SFVS instance satisfies the required properties. Let G = (VG , E G ) with vertex
costs cG : VG → R≥0 be the FVS instance. We will construct an SFVS instance
H = (VH , E H ) with terminals S H and vertex costs c H : VH → R≥0 satisfying the
required properties. We may assume that the FVS instance G has an infinite-weighted
degree-1 root vertex r , satisfying property (iv) since adding such a vertex does not
change the set of minimal feasible solutions. We construct H as follows:
1. For each edge e = uv ∈ E G , we subdivide the edge e so that the edge becomes
a path u, ae , s
e , be , v of length 4.
2. We let S H = e∈E(G) {se } denote the terminal set. Thus, the set Pe := {ae , be } is
the set of pivot vertices for each terminal se ∈ S H , and the set PH := e∈E(G) Pe
is the set of all pivots of the graph H .
3. We define the cost function as c H (u) = cG (u) if u ∈ VG , and c H (u) = ∞
otherwise (i.e., if u ∈ S H ∪ PH ).
We observe that the graph H satisfies properties (i)–(v) assumed by the Chekuri–
Madan LP. The next proposition says that solving FVS in the graph G with cost
function cG is equivalent to solving SFVS in the graph H with terminal set S H with
cost function c H . The proposition follows by construction.
Proposition 5 Let F ⊆ VG . The set F is a feedback vertex set for G if and only if the set
F is a subset feedback vertex set for the graph H with terminal set S H . Furthermore,
the cost of F in both graphs is the same, i.e. cG (F) = c H (F).
123
[8] showed that the LP-relaxation of (SFVS- IP: CM) given in Figure 5 has integral-
ity gap at most 13. It immediately follows that the integrality gap of that LP-relaxation
on the instance H constructed as above is also at most 13. In the subsequent section,
we tighten this integrality gap to 2 for instances H constructed as above.
B.2.3 Bounding the integrality gap
In this section, we show that the LP-relaxation of the (SFVS- IP: CM) given in Figure 5
for the instance H constructed as given in the reduction in Sect. B.2.2 has integrality
gap at most 2. We prove this by showing that the LP constraints imply orientation and
cycle cover constraints.
Consequently, the integrality gap of the LP-relaxation is at
most that of min{ u∈V cu xu : x ∈ Q orient (G) ∩ Pcycle-cover (G)}. By Lemma 17, it
follows that the integrality gap of the LP-relaxation is at most 2.
We begin by simplifying the (SFVS- IP: CM) given in Figure 5 for SFVS
instances H that are constructed from FVS instances as obtained from the reduc-
tion in Sect. B.2.2. We make two observations that will help us in the simplification.
The first observation is that each edge e ∈ E G corresponds to a unique terminal
se ∈ VH . Thus, we may replace the set [k] which indexed the set of terminals in the
ILP of Figure 5 with the set E G . For ease of exposition, we denote er by the label
k + 1. We now give the second observation. Let u ∈ VG be arbitrary. Since each edge
e ∈ δG (u) has been subdivided in the graph H and contains a terminal se , the only
terminals that u can reach via a path that does not contain any other terminal is exactly
{se : e ∈ δG (u)}. For an arbitrary pivot vertex u ∈ PH , let g(u) denote the unique
non-terminal neighbor of u in H . Then, the only terminals that u can reach via a path
that does not contain any other terminal is exactly {se : e ∈ δG (g(u))}. We summarize
these observations in the next proposition.
Proposition 6 We have that
1. For each vertex u ∈ VG , we have that H (u) = δG (u) ∪ {er };
2. For each pivot vertex u ∈ P, we have that H (u) = δG (g(u)) ∪ {er }.
Using Proposition 6 and the first observation mentioned above, we simplify the
(SFVS- IP: CM) in Figure 5 for the SFVS instance H and write its LP-relaxation
(FVS- LP: CM) in Figure 6.
We now show that the constraints of the LP in Figure 6 imply the orientation and
cycle cover constraints for G.
Lemma 20 Let (x, z) be a feasible solution to (FVS- LP: CM) from Figure 6. Then,
1. x ∈ Pcycle-cover (G) and
2. (x, y) ∈ Porient (G), where y e,u = z u,e for all e ∈ δ(u), u ∈ VG .
Proof We have that x ∈ Pcycle-cover (G) owing to inequality (4). We now show that
(x, y) ∈ Porient (G). We have that x u ≥ 0for all u ∈ VG and y e,u ≥ 0 for all
e ∈ δG (u), u ∈ VG . We now show that x u + e∈δG (u) y e,u ≤ 1 for every u ∈ VG . Let
u ∈ V . We have that

xu + y e,u = x u + z u,e − z u,er = 1 − z u,er ≤ 1,
e∈δG (u) e∈ H (u)
123
Fig. 6 (FVS- LP: CM)
where the last inequality holds since z u,er ≥ 0.

Finally, we show that x u + x v + y e,u + y e,v ≥ 1 for every e = uv ∈ E G . Let
e = uv ∈ E G . Let u, ae , se , be , v be the path in the graph H corresponding to the
subdivided edge e. Then, we have that
x u + x v + y e,u + y e,v = x u + x v + z u,e + z v,e

= (x u + x v + z u,e + z v,e ) + (z ae ,e + z be ,e ) − (z ae ,e + z be ,e )
= 1 + (x u + z u,e − z ae ,e ) + (x v + z v,e − z be ,e )
≥ 1.
Here, the third equality follows from constraint (2) and the final inequality follows
from constraint (3) of (FVS- LP: CM) in Figure 6.

Lemma 20 implies that min{ u∈V cu xu : x ∈ Q orient (G) ∩ Pcycle-cover (G)} is a
(FVS- LP: CM) from Figure 6. Lemma 17 tells us that the integrality
relaxation of
gap of min{ u∈V cu xu : x ∈ Q orient (G) ∩ Pcycle-cover (G)} is at most 2. Consequently,
the integrality gap of (FVS- LP: CM) from Figure 6 is also at most 2. We note that
(FVS- LP: CM) from Figure 6 can be converted to a polynomial-sized LP by replacing
inequality (4) using a polynomial-sized description of cycle cover constraints as given
in Lemma 19.
B.3 Orientation formulation
In this section, we give another polynomial-sized ILP for FVS whose LP-relaxation
has integrality gap at most 2. This ILP is based only on orientation constraints and
does not require cycle cover constraints (in contrast to the ILP presented in Sect. 4.2).
We consider the following formulation and denote it as the (FVS- IP: Complete-
123
Orient):

min cu xu
u∈V
f f
xv + xw + ye,v + ye,w ≥ 1 ∀ e = vw ∈ E, f ∈ E (9)
f
xv + ye,w ≥ 1 ∀ v ∈ V , f ∈ E (10)
e=vw∈E
f f
xv + (ye,w + ye,v ) ≤ |V | − 2 ∀ f = ab ∈ E (11)
v∈V −{a,b} e=vw∈E−{ f }
xu ≥ 0 ∀u ∈ V (12)
f
ye,v≥ 0 ∀e ∈ δ(v), v ∈ V , f ∈ E (13)
xu ∈ Z ∀u ∈ V
f
ye,v ∈ Z ∀e ∈ δ(v), v ∈ V , f ∈ E.
Theorem 5 follows from the following lemma.
Lemma 21 For an input graph G = (V , E) with non-negative vertex costs c : V →

R≥0 , (FVS- IP: Complete- Orient) is an integer linear programming formulation
for FVS. Moreover, its LP-relaxation has integrality gap at most 2.
Proof Let x be the indicator vector of a feedback vertex set S of G. We show that
there exists a binary vector y satisfying the constraints. Let T be a spanning tree of G
containing all edges of G that are not incident to vertices in S. Fix an edge f = ab ∈ E.
f
For each vertex v ∈ V \ (S ∪ {a, b}), set ye,w = 1 where e = vw is the first edge
f f
on the unique path from v to a in T . Moreover, set y f ,a = y f ,b = 1 and all other y f
variables to 0. We prove that this choice of y satisfies all constraints.
For an edge e = vw ∈ E, if |S ∩ {v, w}| ≥ 1, then xv + xw ≥ 1 and if v, w ∈ / S,
f f
then e ∈ T and consequently, either ye,v = 1 or ye,w = 1 and hence, the constraint
f f
xv + xw + ye,v + ye,w ≥ 1 holds. For a vertex v ∈ V , if v ∈ S, then xv ≥ 1
f
and if v ∈ V − S, then there exists an edge e = vw ∈ T and hence, ye,w = 1 and
f
consequently, the constraint xv + e=vw∈E ye,w ≥ 1 holds. It remains to show that the
f f
constraint v∈V −{a,b} xv + e=vw∈E−{ f } (ye,w + ye,v ) ≤ |V |−2 holds. By the choice
f f
of x, it suffices to show that |S \ {a, b}| + e=vw∈T −{ f } (ye,w + ye,v ) ≤ |V | − 2 holds.
f f
By the choice of y f , it suffices to show that |S \{a, b}|+ e=vw∈T (ye,w + ye,v ) ≤ |V |.
Simplifying this further, it suffices to show that
f f
(ye,w + ye,v ) ≤ |(V − S) ∪ {a, b}|.
e=vw∈T
123
f f f
We note that e=vw∈T (ye,w
+ ye,v ) = v∈V ( e=vw∈T ye,w ). Hence, it suffices to
show that ⎛ ⎞

⎝ ye,w ⎠ ≤ |(V − S) ∪ {a, b}|.
f
v∈V e=vw∈T
We have the following four inequalities:

f
ye,w ≤ 1 ∀v ∈ V − (S ∪ {a, b}),
e=vw∈T
f
ye,w = 0 ∀v ∈ S − {a, b},
e=vw∈T
f f
ye,w = ye,b = 1, and
e=aw∈T
f f
ye,w = ye,a = 1.
e=bw∈T

f
Hence, v∈V e=vw∈T ye,w ≤ |(V − S) ∪ {a, b}|.
Next, we show that an integral solution to the system of inequalities (9), (10), (11),
(12), and (13) is the indicator vector of a feedback vertex set. We will use the following
claim.
Claim 6 Constraints (9), (10), (11), (12), and (13) imply the strong density constraints.
Proof Let (x, y) be a solution satisfying constraints (9), (10), (11), (12), and (13). Let
S ⊆ V such that E[S] = ∅. We will show that

(d S (u) − 1)xu ≥ |E[S]| − |S| + 1.
u∈S
Equivalently, we will show that

|E[S]| − |S| − (d S (u) − 1)xu ≤ −1.
u∈S
Let us rewrite the LHS as

|E[S]| − |S| − (d S (u) − 1)xu = (1 − xv − xw ) + (xv − 1).
u∈S vw∈E[S] v∈S
Let us inspect each sum separately. Fix an arbitrary f = ab ∈ E[S]. We have that

f f f f
(1 − xv − xw ) = 1 − xv − xw − ye,w − ye,v + ye,v + ye,w
vw∈E[S] vw∈E[S] vw∈E[S]

f f f f
≤ 1 − xa − xb − y f ,a − y f ,b + ye,v + ye,w
vw∈E[S]
123
where the inequality follows from (9) and the fact that f = ab ∈ E[S]. We also have
that
⎛ ⎞

(xv − 1) = ⎝xv − 1 + ye,w ⎠ −
f f
ye,w
v∈S v∈S e=vw∈E v∈S e=vw∈E
⎛ ⎞

≤ ⎝xv − 1 + ye,w ⎠ −
f
ye,w
f
v∈V e=vw∈E v∈S e=vw∈E
where the last inequality follows from (10). Before adding the two upper bounds, we
also note that f f

f
ye,v + ye,w − ye,w ≤ 0
vw∈E[S] v∈S e=vw∈E
by (13). Hence,

(1 − xv − xw ) + (xv − 1)
vw∈E[S] v∈S
⎛ ⎞

f
≤ 1 − xa − xb − y f ,a − y f ,b +
f ⎝xv − 1 + ye,w ⎠
f
v∈V e=vw∈E

f f
= 1 − |V | + xv + (ye,v + ye,w )
v∈V −{a,b} vw∈E−{ f }
≤ −1
where the last inequality follows from (11).

By the results of Chudak, Goemans, Hochbaum, and Williamson [6], every integral
solution satisfying strong density constraints corresponds to the indicator vector of a
feedback vertex set. Thus, by Claim 6, an integral solution to the system of inequalities
(9), (10), (11), (12), and (13) is the indicator vector of a feedback vertex set. This
completes the proof that the formulation given in the lemma is indeed an integer linear
programming formulation for FVS.
Finally, we bound the integrality gap of the LP-relaxation. By the results of Chudak,
Goemans, Hochbaum, and Williamson [6], we know that (FVS-IP: SD) is an ILP
formulation for FVS and the integrality gap of its LP-relaxation (FVS-LP: SD) is
at most 2. We have already shown that the ILP in the lemma statement is a valid
formulation for FVS. By Claim 6, the LP-relaxation of the ILP in the lemma statement
has integrality gap at most 2.

Acknowledgements Samuel Fiorini and Stefan Weltge would like to thank Gwenaël Joret and Yelena
Yuditsky for preliminary discussions. Karthekeyan Chandrasekaran and Samuel Fiorini would like to
acknowledge the support of the trimester program on Discrete Optimization at the Hausdorff Institute for
Mathematics (2021) for facilitating initial discussions on the problem. Chandra Chekuri, Samuel Fiorini and
Stefan Weltge would like to thank the Oberwolfach Research Institute for Mathematics and the organizers
of the Combinatorial Optimization workshop (2021) during which this research started. Shubhang Kulkarni
123
thanks Da Wei Zheng for engaging in preliminary discussions on the separation oracle for 2-pseudotree
cover constraints. We thank the reviewers for their comments which helped improve the presentation of the
paper.
Funding Karthekeyan Chandrasekaran and Shubhang Kulkarni were supported in part by NSF grants CCF-
1814613, CCF-1907937, and CCF-2402667. Chandra Chekuri was supported in part by NSF grants CCF-
1910149 and CCF-1907937. Stefan Weltge was supported in part by Deutsche Forschungsgemeinschaft
(DFG, German Research Foundation), project number 451026932.
Declarations
Conflict of interest All authors declare that they have no conflict of interest.
References
1. Bafna, V., Berman, P. and Fujito, T.: Constant ratio approximations of the weighted feedback vertex
set problem for undirected graphs. In: Algorithms and Computations, pp. 142–151 (1995)
2. Becker, A., Geiger, D.: Optimization of Pearl’s method of conditioning and greedy-like approximation
algorithms for the vertex feedback set problem. Artif. Intell. 83, 167–188 (1996)
3. Bodlaender, H.L., Ono, H., Otachi, Y.: A faster parameterized algorithm for Pseudoforest Deletion.
Discrete Appl. Math. 236, 42-56 (2018)
4. Buchanan, A., Wang, Y., Butenko, S.: Algorithms for node-weighted Stediner tree and maximum-
weight connected subgraph. Networks 72(2), 238–248 (2018)
5. Bar-Yehuda, R., Geiger, D., Naor, J., Roth, R.M.: Approximation algorithms for the feedback vertex set
problem with applications to constraint satisfaction and bayesian inference. SIAM J. Comput. 27(4),
942–959 (1998)
6. Chudak, F.A., Goemans, M.X., Hochbaum, D.S., Williamson, D.P.: A primal-dual interpretation of
two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Oper. Res.
Lett. 22(4), 111–118 (1998)
7. Charikar, M.: Greedy approximation algorithms for finding dense components in a graph. In: Approx-
imation Algorithms for Combinatorial Optimization, pp. 84–95 (2000)
8. Chekuri, C., Madan, V.: Constant factor approximation for subset feedback set problems via a new
LP relaxation. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete
Algorithms, pp. 808–820. SODA (2016)
9. Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 439–485
(2005)
10. Even, G., Naor, J., Schieber, B., Zosin, L.: Approximating minimum subset feedback sets in undirected
graphs with applications. SIAM J. Discrete Math. 13(2), 255–267 (2000)
11. Even, G., Naor, J., Zosin, L.: An 8-approximation algorithm for the subset feedback vertex set problem.
SIAM J. Comput. 30(4), 1231–1252 (2000)
12. Erdös, P., Pósa, L.: On the maximal number of disjoint circuits of a graph. Publ. Math. Debrecen 9,
3–12 (1962)
13. Fujito, T.: Approximating node-deletion problems for matroidal properties. J. Algorithms 31(1), 211–
227 (1999)
14. Fujishige, S.: Submodular Functions and Optimization. Elsevier (2005)
15. Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2-ε. J. Comput. Syst. Sci.
74(3), 335–349 (2008)
16. Lin, M., Feng, Q., Bin, F., Wang, J.: An approximation algorithm for the -pseudoforest deletion
problem. Theor. Comput. Sci. 806, 08 (2019)
17. Monien, B., Schulz, R.: Four approximation algorithms for the feedback vertex set problem. In WG,
pp. 315–326 (1981)
18. Philip, G., Rai, A., Saurabh, S.: Generalized pseudoforest deletion: algorithms and uniform kernel.
SIAM J. Discrete Math. 32(2), 882–901 (2018)
19. West, D.B.: Introduction to Graph Theory. Prentice Hall (2000)
123
Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps
and institutional affiliations.
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under
a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted
manuscript version of this article is solely governed by the terms of such publishing agreement and applicable
law.
123

s10107-024-02179-9

Uploaded by

Copyright:

Available Formats

s10107-024-02179-9

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

s10107-024-02179-9

Uploaded by

Copyright:

Available Formats

Mathematical Programming

FULL LENGTH PAPER

Polyhedral aspects of feedback vertex set and pseudoforest

Karthekeyan Chandrasekaran1 · Chandra Chekuri1 · Samuel Fiorini2 ·

Received: 25 March 2023 / Accepted: 16 November 2024

1 University of Illinois, Urbana-Champaign, Urbana, USA

2 An α-approximation with respect to an LP min{c T x : Ax ≤ b} is an algorithm that returns an integral

Conjecture 1 Let G = (V , E) be a graph that contains a cycle. For every extreme

The family of 2-pseudotree cover constraints admits a polynomial-time separation

We will be interested in the integrality gap of the following LP-relaxation of (PFD-

Theorem 1 For an input graph G = (V , E) with non-negative costs c : V → R≥0 ,

Corollary 2.1 The integrality gap of (PFDS-LP: WD) is at most 3.

Theorem 3 Let G = (V , E) be a graph that is not a pseudoforest. For every minimal

Theorem 4 For an input graph G = (V , E) with non-negative costs c : V → R≥0 ,

Theorem 5 There exists a polynomial-sized integer linear programming formulation

We prove Theorem 5 by showing three different polynomial-sized integer linear pro-

By Theorem 1(1), we have that Q orient (G) ⊆ PWD (G). As a consequence of

For a minimization IP min{c T x : Ax ≤ b, x ∈ Zn≥0 }, the integrality gap of its LP-

3 Pseudoforest deletion set

3.1 Orientation and 2-pseudotree cover constraints

In this section, we restate and prove Theorem 1.

Theorem 1 For an input graph G = (V , E) with non-negative costs c : V → R≥0 ,

In particular, the vector x does not satisfy the constraint of PWD-Subgraphs (K 5 )

3.2 Extreme point property of the weak density polyhedron

In this section, we prove Theorem 2. We restate it below.

Theorem 2 Let G = (V , E) be a graph that is not a pseudoforest. For every extreme

Using this function, we can express the weak density polyhedron as

For J ⊆ 2V , let Rows(J ) = {row(S) : S ∈ J }. When the context is clear, we

3.2.1 Background on supermodular functions and set families

Proposition 1 Let G = (V , E) be an undirected graph with non-negative edge

3.2.2 Conditional supermodularity of weak density constraints

We now show that the function f x is supermodular if xu < 1

Lemma 1 Let x ∈ RV . If xu < 1

Proof Let S ⊆ V . We have

defined by px (S) := uv∈E[S] (1 − (xu + xv )) and qx (S) := u∈S (1 − xu ). Since

3.2.3 Conditional properties of tight sets

Lemma 2 (Conditional Uncrossing Properties) Let x be an extreme point of PWD (G)

b(S) := |E[S]| − |S|. Moreover,

a contradiction. Here, the second equality is by definition of f x , and the final

Proof Let A ∈ Tx . Suppose that |A| = 1. Let A = {u}. Then, A ∈ Tx implies

A = A1  A2 such that G[A1 ], G[A2 ] are disconnected components of G[A]. Then,

gx (A1 ) + gx (A2 ) = gx (A)

3.2.4 Conditional basis structure for extreme points

Claim 2 span(Rows(C(1) )) = span(Rows(Tx )).

Proof By way of contradiction assume false. Let A ∈ Tx such that row(A) ∈ /

The above chain of inequalities implies that xv ≤ 0. By the non-negativity constraints

2. |δ(A, B − A)| ≥ 2k.

3.2.5 Proof of Theorem 2

Lemma 5 Let G = (V , E) be a graph and S ⊆ V be such that G[S] is connected,

(d S (v) − 1)xv = gx (S) ≥ b(S) = |E[S]| − |S|.

1 ≤ b(S) ≤ gx (S) = (d S (v) − 1)xv ≤ 2xv < 1,

We use Lemma 5 to conclude the following:

Corollary 5.1 Let G = (V , E) be a connected graph with minimum degree at least 2

We now restate and prove Theorem 2.

Theorem 2 Let G = (V , E) be a graph that is not a pseudoforest. For every extreme

Proof By way of contradiction, let xu < 13 for all u ∈ V . Let C = {C1 , C2 , C3 , . . . , Ct }

|V | = |Z| + |C| < |Z| + |NZ| = |V |,

3.3 Extreme point property of the orientation polyhedron

In this section, we prove Theorem 3. We restate it below.

Theorem 3 Let G = (V , E) be a graph that is not a pseudoforest. For every minimal

A = A1 A2 such that G[A1 ], G[A2 ] are disconnected components of G[A]. Then,

Inequality (6) follows from this and Lemma 7.

where the last inequality follows from (11).