# A Round and Bipartize Approximation Algorithm for Vertex Cover

Danish Kashaev<EMAIL_ADDRESS>Centrum Wiskunde & Informatica,
Amsterdam. Guido Schäfer<EMAIL_ADDRESS>Centrum Wiskunde & Informatica
and ILLC, University of Amsterdam.

###### Abstract

The vertex cover problem is a fundamental and widely studied combinatorial
optimization problem. It is known that its standard linear programming
relaxation is integral for bipartite graphs and half-integral for general
graphs. As a consequence, the natural rounding algorithm based on this
relaxation computes an optimal solution for bipartite graphs and a
$2$-approximation for general graphs. This raises the question of whether one
can obtain improved bounds on the approximation ratio, depending on how close
the graph is to being bipartite.

In this paper, we consider a round-and-bipartize algorithm that exploits the
knowledge of an induced bipartite subgraph to attain improved approximation
ratios. Equivalently, we suppose that we have access to a subset of vertices
$S$ whose removal bipartizes the graph.

If $S$ is an independent set, we prove a tight approximation ratio of
$1+1/\rho$, where $2\rho-1$ denotes the odd girth of the contracted graph
$\tilde{\mathcal{G}}:=\mathcal{G}/S$ and thus satisfies $\rho\geq 2$. We show
that this is tight for any graph and independent set by providing a family of
weight functions for which this bound is attained. In addition, we give tight
upper bounds for the fractional chromatic number and the integrality gap of
such graphs, both of which also depend on the odd girth.

If $S$ is an arbitrary set, we prove a tight approximation ratio of
$\left(1+1/\rho\right)(1-\alpha)+2\alpha$, where $\alpha\in[0,1]$ denotes the
total normalized dual sum of the edges lying inside of the set $S$. As an
algorithmic application, we show that for any efficiently $k$-colorable graph
with $k\geq 4$ we can find a bipartizing set satisfying $\alpha\leq 1-4/k$.
This provides an approximation algorithm recovering the bound of $2-2/k$ in
the worst case (i.e., when $\rho=2$), which is best possible for this setting
when using the standard relaxation.

##  1 Introduction

###  1.1 Vertex Cover

We focus in this paper on the vertex cover problem, an instance of which is
given by a weighted graph $\mathcal{G}=(V,E,w)$, where
$w:V\mapsto\mathbb{R}_{+}$ is a non-negative weight function on the vertices.
The optimization problem is to find the minimal weight subset of vertices
$S\subset V$ that covers every edge of the graph, i.e.

$\min\Big{\\{}w(S)\;\Big{|}\;S\subset V,|S\cap\\{i,j\\}|\geq
1\quad\forall(i,j)\in E\Big{\\}}.$

We denote by $OPT$ an optimal subset of vertices for this problem, and by
$w(OPT)$ the total weight of that solution. A natural linear programming
relaxation, as well as its dual, is given by:

$\displaystyle\min\sum_{v\in V}w_{v}x_{v}$ $\displaystyle x_{u}+x_{v}$
$\displaystyle\geq 1\quad\forall(u,v)\in E$ $\displaystyle x_{v}$
$\displaystyle\geq 0\quad\forall v\in V$

$\displaystyle\max\sum_{e\in E}y_{e}$ $\displaystyle y(\delta(v))$
$\displaystyle\leq w_{v}\quad\forall v\in V$ $\displaystyle y_{e}$
$\displaystyle\geq 0\quad\forall e\in E$

For a given graph $\mathcal{G}$, we denote the primal linear program by
$P(\mathcal{G})$ and the dual by $D(\mathcal{G})$. An important property of
$P(\mathcal{G})$ is the fact that any extreme point solution $x^{*}$ is half-
integral, i.e. $x^{*}_{v}\in\\{0,\frac{1}{2},1\\}$ for any $v\in V$, see [7,
37, 50]. This gives rises to a straightforward 2-approximation algorithm for
the vertex cover problem by solving $P(\mathcal{G})$ and outputting the
vertices whose LP variable is set to at least a half, hence returning
$S:=\\{v\in V\mid x^{*}_{v}\geq 1/2\\}$. This solution is a 2-approximation
because $w(S)\leq 2\>w(OPT)$, see [26]. Moreover, it turns out that
$P(\mathcal{G})$ is in fact integral for any bipartite graph, hence solving it
directly outputs $OPT$ [32].

The vertex cover problem is known to be NP-complete [29] and APX-complete
[41]. Moreover, it was shown to be NP-hard to approximate within a factor of
$7/6$ in [25], a factor later improved to 1.36 in [17]. It is in fact NP-hard
to approximate within a factor of $2-\varepsilon$ for any fixed
$\varepsilon>0$ if the unique games conjecture is true [30]. Several different
algorithms achieving approximation ratios of $2-o(1)$ have been found for the
weighted and unweighted versions of the problem: [28, 24, 10, 36, 9, 27].
Another large body of work is interested in finding exact fixed parameter
tractable algorithms for the decision version: [13, 6, 14, 15, 18, 39, 40, 49,
19].

The integrality gap of the standard linear relaxation $P(\mathcal{G})$ for a
graph on $n$ vertices equals to $2-2/n$. In fact, a more fine-grained analysis
shows that it is equal to $2-2/\chi^{f}(\mathcal{G})$, where
$\chi^{f}(\mathcal{G})$ is the fractional chromatic number of the graph [48].
An integrality gap of $2-\varepsilon$ is proved for a large class of linear
programs in [4]. In [11], it is shown that any linear program which
approximates vertex cover within a factor of $2-\varepsilon$ requires super-
polynomially many inequalities.

###  1.2 Problem definition and motivation

We consider the following set-up. We are given a weighted non-bipartite graph
$\mathcal{G}=(V,E)$ and an optimal solution $x^{*}\in\\{0,\frac{1}{2},1\\}$ to
$P(\mathcal{G})$. We denote by $V_{\alpha}:=\\{v\in V\mid x^{*}_{v}=\alpha\\}$
the vertices taking value $\alpha$ and by
$\mathcal{G}_{\alpha}=\mathcal{G}[V_{\alpha}]$ the subgraph of $\mathcal{G}$
induced by the vertices $V_{\alpha}$ for any $\alpha\in\\{0,\frac{1}{2},1\\}$.
Moreover, we suppose that we have knowledge of a vertex-induced bipartite
subgraph of $\mathcal{G}_{1/2}$. Equivalently, we suppose that we have access
to a set of vertices $S\subset V_{1/2}$ whose removal bipartizes
$\mathcal{G}_{1/2}$. The question of finding such a good set algorithmically
is also tackled in a later section.

We consider a simple rounding algorithm, detailed in Algorithm 1.1. It first
solves $P(\mathcal{G})$, takes the vertices assigned value one by the linear
program to the solution and removes all the integral nodes from the graph to
arrive at $\mathcal{G}_{1/2}$. The algorithm then takes all the vertices in
the set $S$ to the solution, removes them from the graph and solves another
(now integral) linear program on the bipartite remainder. The vertices with LP
value one are then also added to the solution. The question studied is the
following: what is the worst-case approximation ratio and which weight
functions are attaining it?

Algorithm 1.1 Round and Bipartize for Vertex Cover

Solve the linear program $P(\mathcal{G})$ to get $V_{0}\>,\>V_{1/2}$ and
$V_{1}$

Solve the integral linear program $P(\mathcal{G}_{1/2}\setminus S)$ to get
$W\subset V_{1/2}$

return $V_{1}\cup S\cup W$

The problem of algorithmically finding such a set $S$ for the unweighted
version is related to the _odd cycle transversal number_ of a graph, denoted
by oct$(\mathcal{G})$, see [43, 31]. This is defined as the minimal number of
vertices to be removed in order to make the graph bipartite. Another relevant
concept is the _odd cycle packing number_ ocp$(\mathcal{G})$, defined as the
maximum number of vertex-disjoint odd cycles of $\mathcal{G}$ and satisfying
ocp$(\mathcal{G})\leq$ oct$(\mathcal{G})$. An interesting observation of [22]
shows that the maximum subdeterminant of the vertex-edge incidence matrix of
$P(\mathcal{G})$ is equal to $2^{\text{ocp}(\mathcal{G})}$. The case where
ocp$(\mathcal{G})=0$ corresponds to the bipartite case, and the constraint
matrix is then _totally unimodular_ , i.e., its maximum subdeterminant is
equal to one, in which case the vertices of the linear relaxation are known to
be integral. The related maximum stable set problem has been studied in terms
of the ocp($\mathcal{G}$) in [12, 5, 16].

Note that such a bipartizing set always exists: we may simply take
$S=V_{1/2}$, which recovers the standard $2$-approximation algorithm for
vertex cover. Our analysis thus falls into the framework of beyond the worst-
case analysis [44]. It also has some interesting connections to _learning-
augmented algorithms_ , which have access to some prediction in their input,
obtained for instance through machine learning. This prediction is assumed to
come without any worst-case guarantees, and the goal is then to take advantage
of it by making the algorithm perform better when this prediction is good,
while still keeping robust worst-case guarantees. This framework has been
particularly fruitful for online algorithms: [8, 35, 42, 33, 1, 2]. In our
case, assuming a prediction on the set $S$, robustness is guaranteed since we
can never do worse than a $2$-approximation. In fact, even if the predicted
set is not bipartizing, one may simply greedily add vertices to it until it
becomes so while still guaranteeing a $2$-approximation.

Structurally, for the vertex cover problem (as for the stable set problem),
there is a significant difference between a bipartite and a non-bipartite
graph. The former is polynomial time solvable due to the integrality of the
linear relaxation, whereas the latter only has a $2$-approximation. However,
the polyhedron is still well understood for this setting, since any extreme
point solution is guaranteed to be half-integral. Moreover, non-bipartite
graphs have an exact characterization stating that they all contain at least
one odd cycle. A very natural parameter to look at in this setting is then the
length of the shortest odd cycle, also named the _odd girth_ of the graph. In
[23], it is shown that graphs with a large odd girth also admit a small
cardinality bipartizing set. We show in this paper that, in the setting we
consider, the odd girth is in fact the right parameter to look at, since it
determines tight bounds on the approximation ratio.

A key property implying the integrality of the polyhedron of a bipartite graph
is the total unimodularity of the constraint matrix, see for instance [46,
47]. We hope that the techniques introduced in this paper might allow to
tackle other problems in approximation algorithms by exploiting the fact that
a substructure of the problem instance could have a totally unimodular
constraint matrix. One technique which might benefit from this is iterative
rounding, which requires solving a linear program at each iteration [34].
Having a better analysis for the case where the linear program becomes
integral could potentially allow to get better guarantees and running times
for certain approximation algorithms, since iterative rounding can terminate
by simultaneously rounding on all the non-zero integral variables at this step
without losing solution quality.

We now state a high-level view of the main ideas of our analysis. We first
show that one can assume without loss of generality that we work on graphs
where the solution $x_{v}=\frac{1}{2}$ for every $v\in V$ is optimal, and
characterize the weight functions satisfying this assumption. We lower bound
$w(OPT(\mathcal{G}))$ by the weight of the optimal LP solution and split the
total cost of the algorithm into two parts: $w(S)$ and
$w(OPT(\mathcal{G}\setminus S))$. In order to get a hold of the second term,
we construct feasible solutions depending on the structure of the graph, as
well as on a dual understanding of the weight space. The minimum weight of
these feasible solutions is then a valid upper bound. Tightness is shown by
explicitly constructing classes of weight functions matching the obtained
upper bounds.

###  1.3 Contributions and organization of the paper

The rest of the paper is organized as follows. We introduce the setting and
needed notations in Section 2, devoted to preliminaries. In Section 3, we
introduce the weight space polytope we work with and compute its set of
vertices.

In Section 4.1, we focus on the case where $S$ is a single vertex, i.e.
$S=\\{v_{p}\\}$, and prove that the approximation ratio is bounded by
$1+1/\rho$ where $2\rho-1$ is the odd girth of the graph $\mathcal{G}$. We
moreover prove this bound is tight and exhibit a convex subset of the weight
space attaining it for any such graph. Note that $\rho\geq 2$, hence the
absolute worst-case ratio is $3/2$, which is smaller than $2$. In addition,
the ratio tends to one as the odd girth increases. A simple example is the odd
cycle $C_{2n-1}$, for which this framework yields a tight $1+1/n$
approximation.

In Section 4.2, we focus on the case where $S=I$ is now an arbitrary
independent set. We generalize the previous result and prove that the
approximation ratio is bounded by $1+1/\rho$, where $2\rho-1$ now denotes the
odd girth of the graph $\tilde{\mathcal{G}}:=\mathcal{G}/S$, where all the
vertices in $S$ are contracted into a single node. We also show this bound is
tight and provide a convex subset of the weight space attaining it for any
such graph and independent set. As in the previous setting, the absolute
worst-case for the ratio is $3/2$ and goes to one as the odd girth of the
contracted graph increases. These are in fact the graphs admitting a
3-coloring, where each color class can be used as the bipartizing set.

In Section 4.3, we consider the most general case of $S$ being an arbitrary
set. As previously, $2\rho-1$ denotes the odd girth of the contracted graph
$\tilde{\mathcal{G}}$, if the latter does in fact contain an odd cycle. We
prove an upper bound on the approximation ratio of
$\left(1+1/\rho\right)(1-\alpha)+2\alpha$, where $\alpha\in[0,1]$ is the total
normalized dual sum of the edges contained inside of the set $S$. Note that
this is simply a linear interpolation between $1+1/\rho$ and $2$ with respect
to this $\alpha$ parameter. In the case where $\tilde{\mathcal{G}}$ is
bipartite, we similarly prove an approximation ratio of $1+\alpha$, which is a
linear interpolation between $1$ and $2$ with respect to $\alpha$. In
addition, for any $\alpha\in[0,1]$ and any $\rho\geq 2$, we show that these
bounds are tight and can be attained.

In Section 5, we prove that any graph which can be $k$-colored in polynomial
time admits an efficiently findable bipartizing set $S$ satisfying $\alpha\leq
1-4/k$. This gives rises to a $2-2/k$ approximation algorithm for this setting
in the worst case, a previously known bound which is best possible when
working with the standard linear relaxation, since it coincides with the
integrality gap. A nice example here is the class of planar graphs, known to
be efficiently $4$-colorable [3], and for which a bipartizing set with
$\alpha=0$ can thus be found.

In Section 6, we analyze the integrality gap and the fractional chromatic
number for graphs which, as in Sections 4.1 and 4.2, contain an independent
set whose removal yields a bipartite graph. Equivalently, these are simply the
graphs with chromatic number three. We provide exact formulas in the case
where $S$ is a single vertex and tight upper bounds for the general case.

##  2 Preliminaries

We introduce in this section the setting, known results and notation that we
use throughout the paper. We define $\mathbb{R}_{+}$ to be the non-negative
real numbers and $[k]:=\\{1,\dots,k\\}$ to be the natural numbers up to
$k\in\mathbb{N}$. For a vector $x\in\mathbb{R}^{n}$, we denote the sum of the
coordinates on a subset by $x(A):=\sum_{i\in A}x_{i}$ for any $A\subset[n]$.

The primal standard linear programming relaxation on a graph
$\mathcal{G}=(V,E)$ is denoted by $P(\mathcal{G})$. A key property of
$P(\mathcal{G})$ was introduced by Nemhauser and Trotter in [38]. It
essentially allows to reduce an optimal solution
$x^{*}\in\\{0,\frac{1}{2},1\\}^{V}$ to a fully half-integral solution by
looking at the subgraph induced by the half-integral vertices. As before, we
denote by $V_{\alpha}:=\\{v\in V\mid x^{*}_{v}=\alpha\\}$ the vertices taking
value $\alpha$ and by $\mathcal{G}_{\alpha}=\mathcal{G}[V_{\alpha}]$ the
subgraph of $\mathcal{G}$ induced by the vertices $V_{\alpha}$ for any
$\alpha\in\\{0,\frac{1}{2},1\\}$.

######  Theorem 2.1 (Nemhauser, Trotter [38]).

Let $x^{*}\in\\{0,\frac{1}{2},1\\}^{V}$ be an optimal extreme point solution
to the linear programming relaxation $P(\mathcal{G})$. Then,

$w(OPT(\mathcal{G}_{1/2}))=w(OPT(\mathcal{G}))-w(V_{1}).$

A proof of this theorem can also be found in [20], Lemma 9.17. It directly
implies that it is sufficient for us to consider without loss of generality
graphs where the fully half-integral solution is optimal. This is formalized
in the next lemma.

######  Lemma 2.1.

Let $x^{*}\in\\{0,\frac{1}{2},1\\}^{V}$ be an optimal solution to
$P(\mathcal{G})$. If $U\subset V_{1/2}$ is a feasible vertex cover on
$\mathcal{G}_{1/2}$ with approximation ratio at most $\phi$, i.e.,
$w(U)\leq\phi\>\>w(OPT(\mathcal{G}_{1/2}))$, then

$w(U)+w(V_{1})\leq\phi\>w(OPT(\mathcal{G})).$

###### Proof.

The proof is an easy consequence of Theorem 2.1 and the fact that $\phi\geq
1$:

$w(U)+w(V_{1})\leq\phi\>w(OPT(\mathcal{G}_{1/2}))+w(V_{1})\leq\phi\>(w(OPT(\mathcal{G}_{1/2}))+w(V_{1}))=\phi\>w(OPT(\mathcal{G})).$

∎

We will thus in the rest of the paper assume that we work on weighted graphs
satisfying the fact that the solution $(\frac{1}{2},\dots,\frac{1}{2})$ is
optimal and introduce the weight space formally in Section 3. For a given set
$S\subset V$, we define $\mathcal{G}^{\prime}:=\mathcal{G}\setminus
S=(V^{\prime},E^{\prime})$ to be the graph obtained by removing the set $S$
and all the incident edges to it. Hence,

$E=E^{\prime}\cup\delta(S)\cup E[S]$

where $\delta(S):=\\{(u,v)\in E\mid u\in S,v\notin S\\}$ and
$E[S]:=\\{(u,v)\in E\mid u\in S,v\in S\\}$. We also denote by
$\tilde{\mathcal{G}}:=\mathcal{G}/S=(\tilde{V},\tilde{E})$ the graph obtained
by contracting all the vertices in $S$ into a single new node
$v^{S}\in\tilde{V}$. We allow for multiple edges, but no self-loops. The only
edges present in $E$ but not in $\tilde{E}$ are thus the ones with both
endpoints in $S$, i.e. $E[S]$. We also denote the neighbourhood of a vertex
$v\in V$ by $N(v)$.

If $S\subset V$ is such that $\mathcal{G}\setminus S$ is a bipartite graph, we
consider the following simple algorithm. First, take the vertices in $S\subset
V$ to the cover and remove them from the graph. Then solve the integral linear
program $P(\mathcal{G}\setminus S)$ and take the vertices having LP value one
to the cover. The _approximation ratio_ , given a weight function
$w:V\to\mathbb{R}_{+}$ is thus defined as

$R(w):=\frac{w(S)+w(OPT(\mathcal{G}\setminus S))}{w(OPT(\mathcal{G}))}.$ (2.1)

For simplicity of notation, we omit the dependence on $w$ of
$OPT(\mathcal{G})$ and $OPT(\mathcal{G}\setminus v_{p})$.

##  3 Weight Space

Given a graph $\mathcal{G}=(V,E)$, for which weight functions
$w:V\to\mathbb{R}_{+}$ is the fully half-integral solution
$x=(\frac{1}{2},\dots,\frac{1}{2})$ an optimal solution to the linear program
$P(\mathcal{G})$? We answer this question with the help of complementary
slackness.

######  Lemma 3.1.

Let $\mathcal{G}=(V,E)$ be a graph and let $w:V\to\mathbb{R}_{+}$ be a weight
function. The feasible solution $x_{v}=\frac{1}{2}$ for every $v\in V$ to the
linear program $P(\mathcal{G})$ is optimal if and only if there exists
$y\in\mathbb{R}^{E}_{+}$ satisfying $y(\delta(v))=w_{v}$ for every $v\in V$.

###### Proof.

By complementary slackness, a feasible solution $x\in\mathbb{R}^{V}_{+}$ to
the primal $P(\mathcal{G})$ and a feasible solution $y\in\mathbb{R}^{E}_{+}$
to the dual $D(\mathcal{G})$ are optimal if and only if:

$x_{v}>0\implies y(\delta(v))=w_{v}\quad\forall v\in V$

and

$y_{e}>0\implies x_{u}+x_{v}=1\quad\forall e=(u,v)\in E.$

If $x=(\frac{1}{2},\dots,\frac{1}{2})$ is an optimal solution, then, by strong
duality, there exists an optimal dual solution $y$ and this solution needs to
satisfy $y(\delta(v))=w_{v}$ for every $v\in V$. Conversely, if there exists a
dual solution $y$ satisfying $y(\delta(v))=w_{v}$ for every $v\in V$, then the
pair $x=(\frac{1}{2},\dots,\frac{1}{2})$ and $y$ satisfy both the conditions
of complementary slackness, implying that $x$ is optimal for $P(\mathcal{G})$.
∎

We now define the polyhedron
$Q^{Y,W}\subset\mathbb{R}_{+}^{E}\times\mathbb{R}_{+}^{V}$:

$Q^{Y,W}:=\Big{\\{}(y,w)\in\mathbb{R}_{+}^{E}\times\mathbb{R}_{+}^{V}\;\Big{|}\;y(\delta(v))=w_{v}\quad\forall
v\in V\Big{\\}}.$

The desired weights are the projection of this polyhedron to the subspace of
weights by Lemma 3.1.

$\text{proj}_{W}(Q^{Y,W}):=\\{w\in\mathbb{R}_{+}^{V}\mid\exists
y\in\mathbb{R}_{+}^{E}\text{ s.t. }y(\delta(v))=w_{v}\quad\forall v\in V\\}.$

This polyhedron can be computed using standard techniques such as the Fourier-
Motzkin elimination. Moreover, notice that this is in fact a polyhedral cone,
since for every $(y,w)\in Q^{Y,W}$ and any $\lambda\in\mathbb{R}_{+}$, we have
that $\lambda(y,w)\in Q^{Y,W}$. Without loss of generality, in order to work
with a bounded space, we can now intersect the projection with a hyperplane to
get a polytope. We make the normalization ensuring that the optimal linear
programming solution has objective value one, i.e. $w(V)/2=1$:

$Q^{W}:=\text{proj}_{W}(Q^{Y,W})\cap\left\\{w\in\mathbb{R}_{+}^{V}\mid
w(V)=2\right\\}.$

Notice also that any dual solution $y\in\mathbb{R}_{+}$ satisfying
$y(\delta(v))=w_{v}$ for every $v\in V$ now has a total sum of $y(E)=1$, since

$2=\sum_{v\in V}w_{v}=\sum_{v\in V}y(\delta(v))=\sum_{v\in V}\sum_{e\in
E}y_{e}\>1_{\\{e\in\delta(v)\\}}=\sum_{e\in E}y_{e}\sum_{v\in
V}1_{\\{e\in\delta(v)\\}}=2\;y(E).$

It turns out that the vertices of the polytope $Q^{W}$ have a one-to-one
correspondence with the edges of the graph $\mathcal{G}=(V,E)$. We denote by
$\mathds{1}_{v}\in\mathbb{R}^{V}$ the indicator vector of a vertex $v\in V$.

######  Theorem 3.1.

The polytope $Q^{W}$ of a graph $\mathcal{G}=(V,E)$ can be expressed as:

$Q^{W}=\text{\emph{conv}}\Big{(}\Big{\\{}\mathds{1}_{u}+\mathds{1}_{v}\;\big{|}\;(u,v)\in
E\Big{\\}}\Big{)}.$

Moreover, $\mathds{1}_{u}+\mathds{1}_{v}$ is an extreme point of $Q^{W}$ for
every edge $(u,v)\in E$.

###### Proof.

Let $w\in Q^{W}$ and $y\in\mathbb{R}^{E}_{+}$ such that $y(\delta(v))=w_{v}$
for every $v\in V$, as well as $y(E)=1$. Observe that:

$w=\sum_{(u,v)\in E}y_{(u,v)}\big{(}\mathds{1}_{u}+\mathds{1}_{v}\big{)}.$

By looking at this equality coordinate by coordinate, for a fixed vertex $v\in
V$, the contribution from the left hand side is $w_{v}$ whereas the
contribution from the right hand side is $y(\delta(v))$. We have thus managed
to decompose an arbitrary $w\in Q^{W}$ into a convex combination of the
vectors $\Big{\\{}\mathds{1}_{u}+\mathds{1}_{v}\;\big{|}\;(u,v)\in
E\Big{\\}}$.

Let $(u,v)\in E$ and let us now show that
$\bar{w}:=\mathds{1}_{u}+\mathds{1}_{v}$ is an extreme point of $Q^{W}$.
Firstly, it is clear that $\bar{w}\in Q^{W}$, the dual solution satisfying
complementary slackness being $y_{(u,v)}=1$ and $y_{e}=0$ for every $e\in
E\setminus(u,v)$, and the sum of all the weights being indeed equal to two.
Suppose for contradiction that there exist distinct $w^{1},w^{2}\in Q^{W}$
such that $\bar{w}=\frac{1}{2}(w^{1}+w^{2})$. Notice that, since the weight
vectors are required to be non-negative, $\bar{w}_{z}=w^{1}_{z}=w^{2}_{z}=0$
for every $z\in V\setminus\\{u,v\\}$. Thus, we can assume without loss of
generality that $w^{1}_{u}=w^{2}_{v}=1+\epsilon$ and
$w^{1}_{v}=w^{2}_{u}=1-\epsilon$ for some $\epsilon>0$. However, the fully
half-integral solution is now not an optimal LP solution on the weights
$w^{1}$ and $w^{2}$. Indeed, on the weight function $w^{1}$, the feasible
solution $V\setminus\\{u\\}$ has objective value $1-\epsilon$, whereas the
fully half-integral solution has weight $1$. Similarly, on the weight function
$w^{2}$, the feasible solution $V\setminus v$ has objective value
$1-\epsilon$. By Lemma 3.1, $w^{1},w^{2}\notin Q^{W}$, leading to a
contradiction. The weight function $\bar{w}$ thus cannot be written as a non-
trivial convex combination of two other points in the polytope $Q^{W}$ and is
therefore an extreme point (or a vertex) of $Q^{W}$. ∎

We will in the rest of the paper assume that every weight function satisfies
$w\in Q^{W}$, and thus also that $w(V)=2$ and $y(E)=1$ for every corresponding
dual solution $y\in\mathbb{R}^{E}_{+}$. We now end this section by showing
that this normalization of the weight space allows us to get a convenient
lower bound on $w(OPT(\mathcal{G}))$.

######  Lemma 3.2.

Let $\mathcal{G}=(V,E)$ be a graph. For any $w\in Q^{W}$,

$w(OPT(\mathcal{G}))\geq 1.$

###### Proof.

Since $w\in Q^{W}$, we know that the fully half-integral solution is an
optimal linear programming solution, showing $w(V)/2\leq w(OPT(\mathcal{G}))$,
by feasibility of $OPT(\mathcal{G})$. The result follows again by the
definition of $Q^{W}$, where we normalized the sum of the weights to be equal
to two: $w(V)=2$. Another way this bound can be obtained is by considering the
corresponding dual solution $y\in\mathbb{R}^{E}_{+}$ satisfying
$y(\delta(v))=w_{v}$ for every $v\in V$. Any feasible vertex cover needs to
count the dual value on every edge at least once, showing
$w(OPT(\mathcal{G}))\geq y(E)=1$. ∎

##  4 Round and Bipartize

###  4.1 One Vertex to Bipartite

We focus in this section on graphs where the removal of one vertex leads to a
bipartite graph. The framework is as follows.

  * •

We are given a non-bipartite graph $\mathcal{G}=(V,E)$ and a vertex $v_{p}\in
V$ such that $\mathcal{G}\setminus v_{p}=(A\cup B,E^{\prime})$ is a bipartite
graph.

  * •

Every weight function $w:V\to\mathbb{R}_{+}$ considered satisfies $w\in
Q^{W}$.

  * •

We assume that we round on the vertex $v_{p}$ in the first step. Since
$\mathcal{G}\setminus v_{p}$ is a bipartite graph, solving the linear program
$P(\mathcal{G}\setminus v_{p})$ directly outputs $OPT(\mathcal{G}\setminus
v_{p})$.

The approximation ratio, given weights $w\in Q^{W}$ and the fact that we round
on $v_{p}$ in the first step, is the following quantity:

$R(w):=\frac{w(v_{p})+w(OPT(\mathcal{G}\setminus
v_{p}))}{w(OPT(\mathcal{G}))}.$

Our goal is to pick a weight function $w\in Q^{W}$ maximizing the
approximation ratio, and we in fact show in this section that

$R(w)\leq 1+1/\rho\quad\forall w\in Q^{W}$

where $2\rho-1$ is the odd girth of $\mathcal{G}$ and thus satisfies $\rho\geq
2$. We also prove that this bound is tight and is attained for a certain class
of weight functions $\mathcal{W}\subset Q^{W}$, which are related to all the
shortest odd cycles of length $2\rho-1$:

$R(w)=1+1/\rho\quad\forall w\in\mathcal{W}.$

We now dive deeper into the structure of the graph $\mathcal{G}\setminus
v_{p}$. By assumption, this graph admits a bipartition $A\cup B$ of the
vertices. Let us assume that it has $k$ connected components $A_{1}\cup
B_{1},\dots,A_{k}\cup B_{k}$, all of which are bipartite as well, where
$A=\bigcup_{i}A_{i}$ and $B=\bigcup_{i}B_{i}$. We now fix an arbitrary such
component $A_{j}\cup B_{j}$.

  * •

If $v_{p}$ has an incident edge to both $A_{j}$ and $B_{j}$, then this
component contains (if including $v_{p}$) an odd cycle of $\mathcal{G}$. This
holds since any path between a node in $A_{j}$ and a node in $B_{j}$ has odd
length.

  * •

If $v_{p}$ has incident edges with only one side, we assume without loss of
generality that this side is $A_{j}$. One could simply switch both sides in
the other case while still keeping a valid bipartition of the graph
$\mathcal{G}\setminus v_{p}$.

  * •

If $v_{p}$ does not have incident edges with either of the two sides, then
$A_{j}\cup B_{j}$ is a connected component of the original graph
$\mathcal{G}$. We call such components _dummy_ components and denote by
$A_{d}\cup B_{d}$ the bipartite graph formed by taking the union of all the
dummy components.

We denote $N_{A}(v_{p}):=N(v_{p})\cap A$ and $N_{B}(v_{p}):=N(v_{p})\cap B$.
We now split the graph into layers, where each layer corresponds to the nodes
at the same shortest path distance from $N_{A}(v_{p})$. More precisely, we
define

$\mathcal{L}_{i}:=\Big{\\{}v\in A\cup B\mid
d(N_{A}(v_{p}),v)=i\Big{\\}}\quad\text{for }i\in\\{0,\dots,q\\}$ (4.1)

where $d(N_{A}(v_{p}),v)$ represents the unweighted shortest path distance
between $v$ and a vertex in $N_{A}(v_{p})$. The parameter $q$ is defined to be
the maximal finite distance from $N_{A}(v_{p})$ in the graph $\mathcal{G}$. An
important observation is the fact that these layers are alternatingly included
in one side of the bipartition, see Figure 1 for an illustration of the
construction.

Figure 1: The layers of a bipartite graph $\mathcal{G}\setminus v_{p}=(A\cup
B,E^{\prime})$ with $\rho=4$. The blue square vertices correspond to
$N(v_{p})$, where the two left ones are $\mathcal{L}_{0}=N_{A}(v_{p})$ and the
two right ones are $N_{B}(v_{p})$.

If the graph $\mathcal{G}$ is not connected, note that
$d(N_{A}(v_{p}),v)=\infty$ for the vertices $v$ lying in dummy components. In
order to add the dummy components to the layers and keep alternation between
the two sides of the bipartition, we define the last two layers to either be
$\\{\mathcal{L}_{q+1}:=A_{d},\>\mathcal{L}_{q+2}:=B_{d}\\}$ or
$\\{\mathcal{L}_{q+1}:=B_{d},\>\mathcal{L}_{q+2}:=A_{d}\\}$, depending on
which side of the bipartition the last connected layer $\mathcal{L}_{q}$ lies.
We now have that $\mathcal{L}_{i}\subset A$ if $i$ is even, and
$\mathcal{L}_{i}\subset B$ if $i$ is odd. In fact,

$A=\bigcup_{i=0}^{\lfloor l/2\rfloor}\mathcal{L}_{2i}\quad\text{and}\quad
B=\bigcup_{i=1}^{\lceil l/2\rceil}\mathcal{L}_{2i-1},$

where the parameter $l\in\mathbb{N}$ represents the index of the last layer:
if $\mathcal{G}$ is connected, then $l=q$, otherwise $l=q+2$. Notice also that
$\mathcal{L}_{0}=N_{A}(v_{p})$. However, $N_{B}(v_{p})$ may now have several
different vertices in different layers, see Figure 1.

Let $C\subset V$ be an arbitrary odd cycle of $\mathcal{G}$. Notice that this
cycle contains $v_{p}$, a vertex from $N_{A}(v_{p})$ and a vertex from
$N_{B}(v_{p})$, since $\mathcal{G}\setminus v_{p}$ is bipartite and therefore
does not contain an odd cycle. Any odd cycle $C$ in $\mathcal{G}$ thus
corresponds to an odd path between a vertex in $N_{A}(v_{p})=\mathcal{L}_{0}$
and a vertex in $N_{B}(v_{p})$. By the assumption that the shortest odd cycle
length of $\mathcal{G}$ is $2\rho-1$, the first layer having a non-empty
intersection with $N_{B}(v_{p})$ is $\mathcal{L}_{2\rho-3}$:

$\mathcal{L}_{i}\cap N_{B}(v_{p})=\emptyset\quad\forall i<2\rho-3.$

A shortest odd cycle of length $2\rho-1$ therefore corresponds to an odd path
of length $2\rho-3$ between $\mathcal{L}_{0}$ and a vertex in
$\mathcal{L}_{2\rho-3}\cap N_{B}(v_{p})$, see Figure 1 for an illustration. We
now define edges connecting two consecutive layers $\mathcal{L}_{i}$ and
$\mathcal{L}_{i+1}$ as follows:

$E[\mathcal{L}_{i},\mathcal{L}_{i+1}]:=\\{(u,v)\in E^{\prime}\mid
u\in\mathcal{L}_{i},v\in\mathcal{L}_{i+1}\\}\qquad\forall
i\in\\{0,\dots,l-1\\}.$

We also denote by

$\delta_{A}(v_{p})=\\{(v_{p},u)\in E\mid u\in
A\\}\quad\text{,}\quad\delta_{B}(v_{p})=\\{(v_{p},u)\in E\mid u\in B\\}$

the incident edges to $v_{p}$ respectively connecting to $A$ and $B$.

######  Lemma 4.1.

Let $\mathcal{G}=(V,E)$ be a non-bipartite graph, let $v_{p}\in V$ such that
$\mathcal{G}\setminus
v_{p}=\left(\bigcup_{i=0}^{l}\mathcal{L}_{i},E^{\prime}\right)=(A\cup
B,E^{\prime})$ is bipartite, and let $(y,w)\in Q^{Y,W}$. Then,

$\displaystyle w(OPT(\mathcal{G}\setminus v_{p}))\leq
y(E^{\prime})+\min\Big{\\{}y(\delta_{A}(v_{p})),\;y(\delta_{B}(v_{p})),\;\min_{j\in[\rho-2]}y\big{(}E[\mathcal{L}_{2j-1},\mathcal{L}_{2j}]\big{)}\Big{\\}}.$

######  Remark.

When $\rho=2$, there are only two terms in the outer minimum, which are
$y(\delta_{A}(v_{p}))$ and $y(\delta_{B}(v_{p}))$.

Figure 2: An illustration of the $\rho$ feasible covers constructed in the
proof of Lemma 4.1. The square vertices correspond to $N(v_{p})$, where the
two left ones are $N_{A}(v_{p})$ and the two right ones are $N_{B}(v_{p})$.

###### Proof.

We prove this lemma by constructing $\rho$ explicit vertex covers of
$\mathcal{G}\setminus v_{p}$ and illustrate those in Figure 2. Firstly, notice
that taking one side of the bipartition is a feasible vertex cover. The cover
$A$ has weight $y(E^{\prime})+y(\delta_{A}(v_{p}))$, whereas the cover $B$ has
weight $y(E^{\prime})+y(\delta_{B}(v_{p}))$. This holds because every edge
$(u,v)\in E^{\prime}$ only has one endpoint in both these covers, meaning that
the dual on every such edge is counted exactly once, leading to a contribution
of $y(E^{\prime})$. The vertices in $N_{A}(v_{p})$ give an additional
contribution of $y(\delta_{A}(v_{p}))$ for the cover $A$. Similarly, the
vertices in $N_{B}(v_{p})$ incur an additional cost of $y(\delta_{B}(v_{p}))$
for the cover $B$. Therefore,

$w(OPT(\mathcal{G}\setminus v_{p}))\leq
y(E^{\prime})+\min\Big{\\{}y(\delta_{A}(v_{p})),\;y(\delta_{B}(v_{p}))\Big{\\}}.$
(4.2)

We now construct $\rho-2$ additional covers with the help of the layers. If
$\rho\neq 2$, fix a $j\in[\rho-2]$, and start the cover $S_{j}$ by taking the
two consecutive layers $\mathcal{L}_{2j-1}$ and $\mathcal{L}_{2j}$. Complete
this cover by taking remaining layers alternatively (hence always skipping
one) until covering every edge of the graph. Notice that this cover has an
empty intersection with $N(v_{p})$. By counting its weight in terms of the
dual values on the edges, $S_{j}$ counts every edge in $E^{\prime}$ once,
except for the edges in $E[\mathcal{L}_{2j-1},\mathcal{L}_{2j}]$, which it
counts twice. The weight of the cover is thus

$w(S_{j})=y(E^{\prime})+y(E[\mathcal{L}_{2j-1},\mathcal{L}_{2j}]).$

Since this is true for any $j\in[\rho-2]$, we get that

$w(OPT(\mathcal{G}\setminus v_{p}))\leq
y(E^{\prime})+\min_{j\in[\rho-2]}\>y\big{(}E[\mathcal{L}_{2j-1},\mathcal{L}_{2j}]\big{)}.$

Combining this with the bound (4.2) finishes the proof of the lemma. ∎

######  Theorem 4.1.

Let $\mathcal{G}=(V,E)$ be a graph and $v_{p}\in V$ such that
$\mathcal{G}\setminus v_{p}=(A\cup B,E^{\prime})$ is bipartite. For any $w\in
Q^{W}$, the approximation ratio satisfies:

$R(w)\leq 1+\frac{1}{\rho}$

where $2\rho-1$ is the odd girth of $\mathcal{G}$.

###### Proof.

Let $w\in Q^{W}$ and let $y\in\mathbb{R}^{E}_{+}$ be the corresponding dual
solution. By Lemma 3.2 and Lemma 4.1, the approximation ratio satisfies:

$\displaystyle R(w)$ $\displaystyle=\frac{w(v_{p})+w(OPT(\mathcal{G}\setminus
v_{p}))}{w(OPT(\mathcal{G}))}$ $\displaystyle\leq
y(\delta(v_{p}))+y(E^{\prime})+\min\Big{\\{}y\left(\delta_{A}(v_{p})\right),y\left(\delta_{B}(v_{p})\right),\;\min_{j\in[\rho-2]}y\big{(}E[\mathcal{L}_{2j-1},\mathcal{L}_{2j}]\big{)}\Big{\\}}$
$\displaystyle=1+\min\Big{\\{}y\left(\delta_{A}(v_{p})\right),y\left(\delta_{B}(v_{p})\right),\;\min_{j\in[\rho-2]}y\big{(}E[\mathcal{L}_{2j-1},\mathcal{L}_{2j}]\big{)}\Big{\\}}$
$\displaystyle\leq 1+\frac{1}{\rho}.$

The last equality follows from the fact that $E=E^{\prime}\cup\delta(v_{p})$
and $y(E)=1$. The last inequality follows from the following argument. Notice
that the outer minimum term can be seen as a minimum over $\rho$ values
$y(E_{i})$ for $E_{i}\subset E$. Moreover, these sets of edges
$\\{E_{i}\\}_{i\in[\rho]}$ are pairwise disjoint and sum to at most one, since
the total sum of the edges of the graph is $y(E)=1$. This minimum can thus be
upper bounded by $1/\rho$. ∎

We now prove that this bound is tight and is attained for a certain class of
weight functions. Let $\mathcal{C}=\\{C_{1},\dots,C_{k}\\}$ be all the
shortest odd cycles (of length $2\rho-1$) of the graph $\mathcal{G}$. Notice
that every odd cycle (and thus in particular every $C\in\mathcal{C}$) of the
graph $\mathcal{G}$ contains the vertex $v_{p}$, since $\mathcal{G}\setminus
v_{p}$ is bipartite. For every $C\in\mathcal{C}$, we define the following
weight function $w^{C}:V\to\mathbb{R}_{+}$, that we call the _basic weight
function corresponding to the odd cycle $C$_.

$w^{C}(v)=\begin{cases}2/\rho\quad\text{if} &v=v_{p}\\\
1/\rho\quad\text{if}&v\in C\setminus v_{p}\\\ 0\quad\quad\text{if}&v\notin
C\end{cases}$

It is not hard to see that $w^{C}\in Q^{W}$. Indeed, construct the dual
solution certifying that by setting both dual edges incident to $v_{p}$ to
$1/\rho$. After that, alternatingly set the dual edges to 0 and $1/\rho$ along
the odd cycle. For any edge outside of $C$, set its dual value to $0$. We now
define:

$\mathcal{W}:=\Big{\\{}w:V\to\mathbb{R}_{+}\mid
w=\sum_{C\in\mathcal{C}}\lambda^{C}w^{C};\quad\sum_{C\in\mathcal{C}}\lambda^{C}=1;\quad\lambda^{C}\geq
0\quad\forall C\in\mathcal{C}\Big{\\}}$

One may see this as the convex hull of the basic weight functions
corresponding to each shortest odd cycle. Since each $w^{C}\in Q^{W}$, and
$Q^{W}$ is a convex polytope, we have that $\mathcal{W}\subset Q^{W}$.

Figure 3: An example of a weight function $w\in\mathcal{W}$ obtained by a
convex combination of two basic weight functions of shortest odd cycles. The
light gray nodes are assigned weight zero.

######  Theorem 4.2.

Let $\mathcal{G}=(V,E)$ be a graph and $v_{p}\in V$ such that
$\mathcal{G}\setminus
v_{p}=\left(\bigcup_{i=0}^{l}\mathcal{L}_{i},E^{\prime}\right)=(A\cup
B,E^{\prime})$ is bipartite. For any weight function $w\in\mathcal{W}$, the
approximation ratio satisfies

$R(w)=1+\frac{1}{\rho}$

where $2\rho-1$ is the odd girth of $\mathcal{G}$.

###### Proof.

Let $\mathcal{C}$ be the set of all the shortest odd cycles (of length
$2\rho-1$) of the graph $\mathcal{G}$ and let
$w=\sum_{C\in\mathcal{C}}\lambda^{C}w^{C}\in\mathcal{W}$. Notice that, for any
subset of vertices $S\subset A\cup B$, we can count its weight as

$w(S)=\sum_{v\in S}w_{v}=\sum_{v\in
S}\sum_{C\in\mathcal{C}}\frac{\lambda^{C}}{\rho}1_{\\{v\in
C\\}}=\frac{1}{\rho}\sum_{C\in\mathcal{C}}\lambda^{C}\sum_{v\in S}1_{\\{v\in
C\\}}=\frac{1}{\rho}\sum_{C\in\mathcal{C}}\lambda^{C}|S\cap C|.$ (4.3)

Notice also that every odd cycle $C\in\mathcal{C}$ intersects each layer
$\mathcal{L}_{i}$ for $i\in\\{0,\dots,2\rho-3\\}$ exactly once. Therefore, by
(4.3),

$w(\mathcal{L}_{i})=\frac{1}{\rho}\qquad\forall i\in\\{0,\dots,2\rho-3\\}.$

We now claim that

$w(OPT(\mathcal{G}))=1.$

The fact that $w(OPT(\mathcal{G}))\geq 1$ follows from Lemma 3.2. For the
reverse inequality, notice that it is possible to take a feasible cover by
taking exactly $\rho$ layers in addition to the zero weight vertices, for
instance
$\mathcal{L}_{0}\cup\mathcal{L}_{2}\cup\mathcal{L}_{3}\cup\mathcal{L}_{5}\dots\cup\mathcal{L}_{2\rho-3}$,
showing $w(OPT(\mathcal{G}))\leq 1$. Similarly, we claim

$w(OPT(\mathcal{G}\setminus v_{p}))=\frac{\rho-1}{\rho}.$

After removal of $v_{p}$, every cycle $C\in\mathcal{C}$ becomes a path of
length $2\rho-3$ (and thus consisting of $2\rho-2$ vertices), with one vertex
in each layer $\mathcal{L}_{i}$ for $i\in\\{0,\dots,2\rho-3\\}$. By
feasibility, $OPT(\mathcal{G}\setminus v_{p})$ has to contain at least
$\rho-1$ vertices for every such path. Using (4.3), we infer
$w(OPT(\mathcal{G}\setminus v_{p}))\geq(\rho-1)/\rho$. For the reverse
inequality, taking $\rho-1$ layers alternatively, such as
$\mathcal{L}_{0}\cup\mathcal{L}_{2}\cup\mathcal{L}_{4}\dots\cup\mathcal{L}_{2\rho-4}$,
as well as the zero weight vertices, builds a feasible cover of weight exactly
$(\rho-1)/\rho$. Finally, notice that

$w(v_{p})=\frac{2}{\rho}$

because every $C\in\mathcal{C}$ contains $v_{p}$. By combining the three
equalities, we get

$R(w)=\frac{w(v_{p})+w(OPT(\mathcal{G}\setminus
v_{p}))}{w(OPT(\mathcal{G}))}=1+\frac{1}{\rho}.$

∎

###  4.2 Independent Set to Bipartite

We focus in this section on graphs $\mathcal{G}=(V,E)$ where there exists an
independent set $I\subset V$ such that
$\mathcal{G}^{\prime}:=\mathcal{G}\setminus
I=(V^{\prime},E^{\prime})=(V\setminus I,E\setminus\delta(I))$ is a bipartite
graph. The algorithm we consider is a two-step rounding process: we first
round on the nodes in $I$, remove them from the graph, and then solve the
(integral) linear program on the bipartite graph $\mathcal{G}\setminus I$.
Given a weight function $w\in Q^{W}$, the approximation ratio is defined as:

$R(w):=\frac{w(I)+w(OPT(\mathcal{G}\setminus I))}{w(OPT(\mathcal{G}))}.$

For a feasible vertex cover $U\subset V\setminus I$ of the bipartite graph
$\mathcal{G}^{\prime}=\mathcal{G}\setminus I$, we define

$E_{U}:=\Big{\\{}(u,v)\in E^{\prime}\;\big{|}\;u\in U,v\in
U\Big{\\}}\cup\Big{\\{}(u,v)\in E\;\big{|}\;u\in U,v\in I\Big{\\}}.$

Note that the second term is a subset of edges of the original graph
$\mathcal{G}$. In particular, $E_{U}$ might have a non-empty intersection with
$\delta(I)$.

######  Definition 4.1.

Let $\mathcal{G}=(V,E)$ and $I\subset V$. Two feasible vertex covers
$U_{1},U_{2}\subset V\setminus I$ of
$\mathcal{G}^{\prime}=\mathcal{G}\setminus I$ are _edge-separate_ with respect
to $\mathcal{G}$ if

$E_{U_{1}}\cap E_{U_{2}}=\emptyset.$

See Figure 5 for an illustration of three pairwise edge-separate covers. If
the graph $\mathcal{G}$ is clear from the context, we will sometimes simply
say that the covers are edge-separate.

######  Lemma 4.2.

Let $\mathcal{G}=(V,E)$ be a graph and $I\subset V$ be an independent set such
that $\mathcal{G}\setminus I$ is bipartite. If there exist $k$ pairwise edge-
separate feasible vertex covers of the graph $\mathcal{G}\setminus I$, then

$R(w)\leq 1+\frac{1}{k}$

for any weight function $w\in Q^{W}$.

###### Proof.

Let $(y,w)\in Q^{Y,W}$ be such that $w(V)=2$ and $y(E)=1$. We use the fact
that $I$ is an independent set: its weight is equal to the sum of the dual
values of the edges incident to it:

$w(I)=y(\delta(I)).$ (4.4)

Let $U\subset V\setminus I$ be a feasible cover of $\mathcal{G}\setminus I$.
We compute the weight of this cover with the help of the dual variables:

$w(U)=y(E\setminus\delta(I))+y(E_{U}).$ (4.5)

We now explain how this formula is obtained. By feasibility of $U$, it counts
the dual value of each edge in the graph $\mathcal{G}\setminus I$ at least
once, leading to a contribution of $y(E^{\prime})=y(E\setminus\delta(I))$. The
edges $(u,v)\in E^{\prime}$ which are counted twice are in fact the ones where
both endpoints lie in $U$, i.e. $u\in U$ and $v\in U$. The final quantity we
need to account for are the edges in $E\setminus E^{\prime}$ which also
contribute to the weight of the cover. These are in fact the edges $(u,v)\in
E$ incident to $I$ but with one endpoint in $U$, i.e. $u\in U$, $v\in I$, and
are counted once. Therefore, any feasible cover $U$ incurs a necessary cost of
$y(E^{\prime})=y(E\setminus\delta(I))$, with a surplus of $y(E_{U})$.

We now let $U_{1},\dots,U_{k}\subset V\setminus I$ be the $k$ pairwise edge-
separate feasible covers of $\mathcal{G}\setminus I$. Since these are all
feasible, we get an upper bound on the weight of $OPT(\mathcal{G}\setminus
I)$:

$w(OPT(\mathcal{G}\setminus
I))\leq\min_{i\in[k]}\;w(U_{i})=y(E\setminus\delta(I))+\min_{i\in[k]}\;y(E_{U_{i}})\leq
y(E\setminus\delta(I))+\frac{1}{k}.$ (4.6)

The last inequality follows from the assumption that the subsets of edges
$E_{U_{i}}$ are pairwise disjoint: suppose that $y(E_{U_{i}})>1/k$ for every
$i\in[k]$. Then, $y(E)\geq\sum_{i\in[k]}y(E_{U_{i}})>1$, which is a
contradiction. Combining Lemma 3.2, (4.4) and (4.6), we get the desired bound:

$R(w)=\frac{w(I)+w(OPT(\mathcal{G}\setminus I))}{w(OPT(\mathcal{G}))}\leq
y(\delta(I))+y(E\setminus\delta(I))+\min_{i\in[k]}\;y(E_{U_{i}})\leq
1+\frac{1}{k}.$

∎

Figure 4: An example of the graph contraction operation described in
Definition 4.2. Observe that the odd girth decreases from nine to five.

######  Definition 4.2.

Let $\mathcal{G}=(V,E)$ be a graph and $I\subset V$ be a subset of vertices.
We denote by $\tilde{\mathcal{G}}:=\mathcal{G}/I=(\tilde{V},\tilde{E})$ the
graph obtained by contracting the vertices in $I$ into a single new node
$v^{I}\in\tilde{V}$, where multiple edges are allowed, but self-loops are not.

######  Remark.

Observe that if $I$ is an independent set, the edge set $\tilde{E}$ of the
graph $\tilde{\mathcal{G}}$ has a one-to-one correspondence with the edge set
$E$ of the original graph $\mathcal{G}$.

######  Theorem 4.3.

Let $\mathcal{G}=(V,E)$ be a graph and $I\subset V$ be an independent set such
that $\mathcal{G}\setminus I=(A\cup B,E^{\prime})$ is bipartite. For any $w\in
Q^{W}$, the approximation ratio satisfies

$R(w)\leq 1+\frac{1}{\rho}$

where $2\rho-1$ is the odd girth of the vertex-contracted graph
$\tilde{\mathcal{G}}=\mathcal{G}/I$.

######  Remark.

The odd girth of $\tilde{\mathcal{G}}$ is at most the odd girth of
$\mathcal{G}$, but can be strictly smaller, see Figure 4 for an example.

###### Proof.

By Lemma 4.2, it is enough to construct $\rho$ edge-separate covers of
$\mathcal{G}\setminus I$ in order to prove the theorem. Observe that it is
enough to work in the contracted graph $\tilde{\mathcal{G}}:=\mathcal{G}/I$.
Indeed, constructing $k$ edge-separate feasible covers of
$\mathcal{G}\setminus I$ with respect to $\tilde{\mathcal{G}}$ directly
implies that one can construct $k$ edge-separate feasible covers of
$\mathcal{G}\setminus I$ with respect to $\mathcal{G}$, since the edge sets of
$\mathcal{G}$ and $\tilde{\mathcal{G}}$ are the same.

First, notice that $\tilde{\mathcal{G}}$ does indeed contain an odd cycle. Fix
an arbitrary odd cycle $C$ of $\mathcal{G}$ and observe that $C\cap
I\neq\emptyset$, since $I$ breaks all the odd cycles by assumption. Since $I$
is an independent set, there exists an odd path between two nodes of $C\cap
I$. This odd path becomes an odd cycle when the vertices in $I$ get contracted
in the graph $\tilde{\mathcal{G}}$. The odd girth is thus well-defined.

Moreover, $\tilde{\mathcal{G}}$ is now a graph which is one vertex away from
being bipartite: if we denote by $v^{I}$ the contracted vertex, then
$\tilde{\mathcal{G}}\setminus v^{I}=\mathcal{G}\setminus I=(A\cup
B,E^{\prime})$. We can thus decompose the vertex set of the graph
$\mathcal{G}\setminus I$ into the layers

$\mathcal{L}_{i}:=\Big{\\{}v\in A\cup B\mid
d\left(N_{A}\left(v^{I}\right),v\right)=i\Big{\\}}\quad\text{for
}i\in\\{0,\dots,l\\}$

as explained in (4.1). We now construct the $\rho$ edge-separate covers in the
same fashion as in the proof of Lemma 4.1, and these are illustrated in
Figures 2 and 5.

Figure 5: The $\rho=3$ edge-separate covers of $\mathcal{G}\setminus v^{I}$
constructed in the proof of Theorem 4.3. Observe that only the three bottom
edges are required to be covered. For each cover $U\subset V\setminus v^{I}$,
the blue edges correspond to $E_{U}$. Notice that they are pairwise disjoint.

The first two covers are both sides of the bipartition $A$ and $B$, where
$E_{A}=\\{(u,v^{I})\in\tilde{E}\mid a\in A\\}$ and
$E_{B}=\\{(u,v^{I})\in\tilde{E}\mid u\in B\\}$. If $\rho>2$, the remaining
$\rho-2$ covers are constructed as follows: fix a $j\in[\rho-2]$, and start
the cover $U_{j}$ by taking the two consecutive layers $\mathcal{L}_{2j-1}$
and $\mathcal{L}_{2j}$. Complete it by taking remaining layers alternatingly
(hence always skipping one) until covering every edge of the graph. In this
case,

$E_{U_{j}}=E[\mathcal{L}_{2j-1},\mathcal{L}_{2j}]=\\{(u,v)\in\tilde{E}\mid
u\in\mathcal{L}_{2j-1},v\in\mathcal{L}_{2j}\\}$

Clearly, $E_{A},E_{B},E_{U_{1}},\dots,E_{U_{\rho-2}}$ are all pairwise
disjoint, implying that the covers constructed are pairwise edge-separate. By
Lemma 4.2, this finishes the proof of the theorem. ∎

We now show that this bound is tight and is attained for a class of weight
functions $w\in Q^{W}$. Let $\tilde{\mathcal{C}}$ be all the shortest odd
cycles (of length $2\rho-1$) of the graph $\tilde{\mathcal{G}}$, each of which
is containing $v^{I}$. For every such cycle $C\in\tilde{\mathcal{C}}$, we
define the following dual function on the edges
$y^{C}:\tilde{E}\to\mathbb{R}_{+}$: set both dual edges incident to $v^{I}$ to
$1/\rho$ and then alternatively set the dual edges to 0 and $1/\rho$ along the
odd cycle, see Figure 6. For any edge outside of $C$, set its dual value to
$0$. We now take the convex hull of all these functions:

$\displaystyle\mathcal{Y}$
$\displaystyle:=\Big{\\{}y:\tilde{E}\to\mathbb{R}_{+}\mid
y=\sum_{C\in\mathcal{C}}\lambda^{C}y^{C};\quad\sum_{C\in\mathcal{C}}\lambda^{C}=1;\quad\lambda^{C}\geq
0\quad\forall C\in\tilde{\mathcal{C}}\Big{\\}}.$

Because of the one-to-one correspondence between the edge sets $\tilde{E}$ and
$E$, we can naturally define a weight function on the original vertex set once
we fix a $y\in\mathcal{Y}$:

$w(v):=y(\delta(v))\quad\forall v\in V.$

We define the space of all such weight functions as:

$\mathcal{W}:=\left\\{w:V\to\mathbb{R}_{+}\mid w(v)=y(\delta(v))\quad\forall
v\in V;\quad y\in\mathcal{Y}\right\\}.$

Figure 6: An example of a weight function attaining the $1+1/\rho$ bound and
how it translates to the original graph. The light gray edges are assigned
value zero.

######  Theorem 4.4.

Let $\mathcal{G}=(V,E)$ be a graph and $I\subset V$ be an independent set such
that $\mathcal{G}\setminus I=(A\cup B,E^{\prime})$ is bipartite. For any
$w\in\mathcal{W}$, the approximation ratio satisfies

$R(w)=1+\frac{1}{\rho}$

where $2\rho-1$ is the odd girth of the vertex-contracted graph
$\mathcal{G}/I$.

###### Proof.

The proof is essentialy the same as the one of Theorem 4.2. Using the same
arguments, we get that $w(I)=2/\rho,w(OPT(\mathcal{G}\setminus
I))=w(OPT(\tilde{\mathcal{G}}\setminus v^{I}))=(\rho-1)/\rho$ and
$w(OPT(\mathcal{G}))=1$, showing

$R(w)=\frac{w(I)+w(OPT(\mathcal{G}\setminus
I))}{w(OPT(\mathcal{G}))}=1+\frac{1}{\rho}.$

∎

###  4.3 Arbitrary Set to Bipartite

We now consider the setting where we are given an arbitrary graph
$\mathcal{G}=(V,E)$ and a subset of vertices $S\subset V$ such that
$\mathcal{G}^{\prime}=\mathcal{G}\setminus S=(A\cup B,E^{\prime})$ is a
bipartite graph. The algorithm considered is again a two-step rounding
process: first round on the vertices in $S$ and take them to the cover, remove
$S$ and solve the linear program on $\mathcal{G}\setminus S$ to get an
integral solution.

Let $(y,w)\in Q^{Y,W}$ such that $w(V)=2$ and $y(E)=1$. The approximation
ratio is

$R(w):=\frac{w(S)+w(OPT(\mathcal{G}\setminus S))}{w(OPT(\mathcal{G}))}.$

Denote the set of edges with both endpoints in the set $S$ by

$E[S]:=\Big{\\{}(u,v)\in E\mid u\in S,v\in S\Big{\\}}.$

Our guarantee on the approximation ratio will depend on the total sum of the
dual variables on these edges. We denote this sum by

$\alpha:=y(E[S]).$

In addition, the guarantee that we get on the approximation ratio depends on
whether the contracted graph $\tilde{\mathcal{G}}:=\mathcal{G}/S$ is bipartite
or not. If $\tilde{\mathcal{G}}$ contains an odd cycle, we denote its odd
girth by $2\rho-1$ and show that the approximation ratio is determined by a
linear interpolation between $1+1/\rho$ and $2$ with respect to the $\alpha$
parameter. Hence, for $\alpha=0$, we recover the bound of the previous
section, whereas for $\alpha=1$, we recover the $2$-approximation. Similarly,
if $\tilde{\mathcal{G}}$ is bipartite, we show that the approximation ratio is
determined by a linear interpolation between $1$ and $2$ with respect to
$\alpha$.

######  Theorem 4.5.

Let $\mathcal{G}=(V,E)$ be a graph and $S\subset V$ such that
$\mathcal{G}\setminus S=(A\cup B,E^{\prime})$ is bipartite. For any $w\in
Q^{W}$, the approximation ratio satisfies

$R(w)\leq\left(1+\frac{1}{\rho}\right)(1-\alpha)+2\alpha\qquad\text{with
}\alpha\in[0,1]\text{ and }\rho\geq 2$

if the contracted graph $\mathcal{G}/S$ contains an odd cycle and $2\rho-1$
denotes its odd girth.

###### Proof.

Recall that $w(V)=2$ and $y(E)=1$, meaning that $w(OPT(\mathcal{G}))\geq
y(E)=1$ by Lemma 3.2. We decompose the weight of $S$ with respect to the dual
variables. The edges in $E[S]$ are counted twice, whereas the edges in
$\delta(S)$ are counted once, giving:

$w(S)=2\alpha+y(\delta(S)).$ (4.7)

Consider the contracted graph
$\tilde{\mathcal{G}}=\mathcal{G}/S=(\tilde{V},\tilde{E})$ and denote by
$v^{S}$ the contracted node. The edge set of this graph is now

$\tilde{E}=\delta(S)\cup E^{\prime}$

since the edges in $E[S]$ have been collapsed. This graph contains by
assumption an odd cycle, but is now one vertex away from being bipartite, if
we were to remove $v^{S}$. By Lemma 4.1, we can construct $\rho$ edge-separate
covers $U_{1},\dots,U_{\rho}\subset\tilde{V}\setminus v^{S}$ on the bipartite
graph $\mathcal{G}^{\prime}$ with respect to $\tilde{\mathcal{G}}$. These
covers are still edge-separate with respect to the original graph
$\mathcal{G}$. This allows us to get an upper bound on the weight of
$OPT(\mathcal{G}\setminus S)$:

$w(OPT(\mathcal{G}\setminus
S))\leq\min_{i\in[\rho]}\;w(U_{i})=y(E^{\prime})+\min_{i\in[\rho]}y(E_{U_{i}})\leq
y(E^{\prime})+\frac{1-\alpha}{\rho}.$ (4.8)

The first inequality holds since every $U_{i}$ is a feasible cover of
$\mathcal{G}\setminus S$. The second equality holds by counting the weight of
a cover $U_{i}$ in terms of the dual edges as explained in (4.5). The last
inequality holds because the edge sets $\\{E_{U_{i}}\\}_{i\in[\rho]}$ are
pairwise disjoint, and their total dual sum is at most $1-\alpha$.

Combining Lemma 3.2, (4.7) and (4.8), and using
$y(E)=\alpha+y(\delta(S))+y(E^{\prime})=1$, we get

$\displaystyle R(w)$ $\displaystyle=\frac{w(S)+w(OPT(\mathcal{G}\setminus
S))}{w(OPT(\mathcal{G}))}\leq
2\alpha+y(\delta(S))+y(E^{\prime})+\frac{1-\alpha}{\rho}$
$\displaystyle=1+\alpha+\frac{1-\alpha}{\rho}=\left(1+\frac{1}{\rho}\right)(1-\alpha)+2\alpha.$

∎

Figure 7: The plot of the approximation ratio $R(w)$ with respect to the
parameter $\alpha\in[0,1]$.

What happens if the contracted graph $\mathcal{G}/S$ does not contain an odd
cycle and is thus bipartite? In that case, we can get an exact formula on
$w(OPT(\mathcal{G}\setminus S))$ without having the additive term
$(1-\alpha)/\rho$ in (4.8). The approximation ratio is then determined by a
linear interpolation between $1$ and $2$ with respect to the $\alpha$
parameter.

######  Theorem 4.6.

Let $\mathcal{G}=(V,E)$ be a graph and $S\subset V$ such that
$\mathcal{G}\setminus S=(A\cup B,E^{\prime})$ is bipartite. For any $w\in
Q^{W}$, the approximation ratio satisfies

$R(w)\leq 1+\alpha\qquad\text{with }\alpha\in[0,1]$

if the contracted graph $\mathcal{G}/S$ is bipartite.

###### Proof.

The only change with respect to the previous proof is the bound on
$w(OPT(\mathcal{G}\setminus S))$ in (4.8). We denote the contracted graph by
$\tilde{\mathcal{G}}=\mathcal{G}/S$ and by $v^{S}$ the contracted vertex.
Suppose $\tilde{\mathcal{G}}$ admits the bipartition
$(\tilde{A}\cup\tilde{B},\tilde{E})$ and assume without loss of generality
that $v^{S}\in\tilde{A}$. Note that $\tilde{E}=E^{\prime}\cup\delta(v^{S})$.

Any feasible cover of $\mathcal{G}\setminus S$ needs to count the dual value
of every edge in $E^{\prime}$ at least once. Taking the cover
$\tilde{A}\setminus v^{S}$ counts every edge in $E^{\prime}$ exactly once,
showing that $w(OPT(\mathcal{G}\setminus S))=y(E^{\prime})$. Hence, using
$y(E)=\alpha+y(\delta(S))+y(E^{\prime})=1$, we get

$R(w)\leq 2\alpha+y(\delta(S))+y(E^{\prime})=1+\alpha.$

∎

We now show that these two bounds are tight for any values of $\alpha\in[0,1]$
and $\rho\geq 2$.

######  Theorem 4.7.

Let $\alpha\in[0,1]$ and let $\rho\geq 2$. There exists a non-bipartite graph
$\mathcal{G}=(V,E)$, with weights $(y,w)\in Q^{Y,W}$, and a set $S\subset V$
with $y(E[S])=\alpha$, where $\mathcal{G}/S$ has odd girth $2\rho-1$ and which
satisfies

$R(w)=\left(1+\frac{1}{\rho}\right)(1-\alpha)+2\alpha.$

###### Proof.

An example of such a graph can be constructed as follows. We first construct
$\mathcal{G}/S$: take an odd cycle of length $2\rho-1$ with a distinguished
node $v^{S}$ and assign dual value $(1-\alpha)/\rho$ to both edges incident to
it. Alternatively assign dual values $0$ and $(1-\alpha)/\rho$ along the odd
cycle for the remaining edges. In order to construct $\mathcal{G}$, replace
$v^{S}$ by a triangle $S$ with dual edges set to $\alpha,0$ and $0$, where the
two previous incident edges to $v^{S}$ are adjacent to the endpoints of the
edge with value $\alpha$. Note that we replace it with a triangle instead of a
single edge in order to avoid $\mathcal{G}$ becoming bipartite. Similarly to
the proof of Theorem 4.2, one can check that

$w(S)=2\alpha+\frac{2\>(1-\alpha)}{\rho};\quad w(OPT(\mathcal{G}\setminus
S))=\frac{(1-\alpha)(\rho-1)}{\rho};\quad w(OPT(\mathcal{G}))=1.$

Therefore,

$R(w)=2\alpha+\frac{2\>(1-\alpha)}{\rho}+\frac{(1-\alpha)(\rho-1)}{\rho}=\left(1+\frac{1}{\rho}\right)(1-\alpha)+2\alpha.$

∎

######  Theorem 4.8.

Let $\alpha\in[0,1]$. There exists a non-bipartite graph $\mathcal{G}=(V,E)$,
with weights $(y,w)\in Q^{Y,W}$, and a set $S\subset V$ with $y(E[S])=\alpha$,
where $\mathcal{G}/S$ is bipartite and which satisfies

$R(w)=1+\alpha.$

###### Proof.

Let $\mathcal{G}$ be an arbitrary odd cycle. Consider an arbitrary edge
$(u,v)\in E$ and assign it dual value $\alpha$. The set $S$ is defined to be
$S=\\{u,v\\}$. Assign dual value zero to the edge $(u,w)\in E$, where $w$ is
the second neighbour of $u$ in the cycle. For the remaining edges, arbitrarily
assign dual values, while ensuring that they sum up to $1-\alpha$. The fact
that one edge is equal to zero is necessary in order to get the exact formula
$w(OPT(\mathcal{G}))=1$, a feasible cover showing $w(OPT(\mathcal{G}))\leq 1$
being the following: take both endpoints of the edge $(u,w)$ and take
remaining vertices alternatively (hence always skipping one) along the odd
cycle. All the edges are counted once, except for $(u,w)$, which is counted
twice but has value zero. Moreover, $w(S)=2\alpha+y(\delta(S))$ and
$w(OPT(\mathcal{G}\setminus S))=y(E^{\prime})$, where $E^{\prime}$ is the edge
set of the bipartite graph $\mathcal{G}\setminus S$. Therefore,

$R(w)=2\alpha+y(\delta(S))+y(E^{\prime})=1+\alpha.$

∎

##  5 Algorithmic application

A natural question to ask is what is, for a general graph, the best possible
set $S$ bipartizing the graph one can find? By best possible, we mean here a
set $S$ with a low value for the $\alpha$ parameter. In fact, once such a set
$S$ is found, there can also be freedom in the choice of the dual solution in
order to optimize the $\alpha$ parameter. This motivates the following
definition.

######  Definition 5.1.

Let $(\mathcal{G},S,y,w)$ be a graph with a bipartizing set $S\subset V$,
weights $w\in Q^{W}$ and a dual solution $y\in\mathbb{R}^{E}_{+}$. A tuple
$(\mathcal{G}^{\prime},S^{\prime},y^{\prime},w^{\prime})$ is _approximation
preserving_ if

$w(S)+w(OPT(\mathcal{G}\setminus S))\leq
w^{\prime}(S^{\prime})+w^{\prime}(OPT(\mathcal{G}^{\prime}\setminus
S^{\prime})).$

Moreover, we say that $\alpha\in[0,1]$ is _valid_ for $S\subset V$ if there
exists an approximation preserving
$(\mathcal{G}^{\prime},S^{\prime},y^{\prime},w^{\prime})$ such that
$\alpha=y^{\prime}(E[S^{\prime}]).$

Finding a valid $\alpha\in[0,1]$ would directly allow us to use it in the
bound of Theorem 4.5, where the $\rho$ parameter would correspond to the one
of the approximation preserving graph. We present here an application if a
coloring of a graph can be found efficiently.

######  Theorem 5.1.

Let $\mathcal{G}=(V,E)$ be a graph with weights $w\in Q^{W}$ that can be
$k$-colored in polynomial time for $k\geq 4$. There exists an efficiently
findable set $S\subset V$ bipartizing the graph and a valid $\alpha$ such that

$\alpha\leq 1-4/k.$

###### Proof.

Let us denote by $V_{1},\dots,V_{k}$ the $k$ independent sets defining the
color classes of the graph $\mathcal{G}$. We assume without loss of generality
that they are ordered by weight $w(V_{1})\leq w(V_{2})\dots\leq w(V_{k})$.
Since $w(V)=2$, the two color classes with the largest weights satisfy
$w(V_{k-1})+w(V_{k})\geq 4/k$. We define the bipartizing set to be the
remaining color classes: $S:=V_{1}\cup\dots\cup V_{k-2}$. We denote by
$y\in\mathbb{R}^{E}_{+}$ the dual solution satisfying complementary slackness
and $y(E)=1$.

We now define an approximation preserving tuple
$(\mathcal{G}^{\prime},S^{\prime},y^{\prime},w^{\prime})$ in the following
way. Let $\mathcal{G}^{\prime}=K_{k}$ be the complete graph on $k$ vertices,
denoted by $\\{v_{1},\dots,v_{k}\\}$. The weights are defined to be

$w^{\prime}(v_{i}):=w(V_{i})\quad\text{ and }\quad
y^{\prime}(v_{i},v_{j}):=y(E[V_{i},V_{j}])$

for every $i,j\in[k]$. These clearly satisfy the complementary slackness
condition $y^{\prime}(\delta(v_{i}))=w^{\prime}(v_{i})$ for every $i\in[k]$.
The bipartizing set is defined to be $S^{\prime}:=\\{v_{1},\dots,v_{k-2}\\}$.
This tuple is approximation preserving since $w(S)=w^{\prime}(S^{\prime})$ and
$w(OPT(\mathcal{G}\setminus S))\leq
w^{\prime}(OPT(\mathcal{G}^{\prime}\setminus S^{\prime}))$. In order to prove
the theorem, we still need to tweak the dual solution $y^{\prime}$ to ensure
$\alpha:=y^{\prime}(E[S^{\prime}])\leq 1-4/k$. Observe that
$w^{\prime}(v_{k-1})+w^{\prime}(v_{k})\geq 4/k$.

  * •

If $y^{\prime}(v_{k-1},v_{k})=0$, then the result follows since in that case
$y^{\prime}(\delta(S^{\prime}))\geq 4/k$ and thus
$y^{\prime}(E[S^{\prime}])\leq 1-4/k$.

  * •

If $y^{\prime}(E[S^{\prime}])=0$, then the result trivially follows as well.

Suppose thus that $y^{\prime}(E[S^{\prime}])>0$ and
$y^{\prime}(v_{k-1},v_{k})>0$. Pick an arbitrary edge $(v_{i},v_{j})\in
E[S^{\prime}]$ satisfying $y^{\prime}(v_{i},v_{j})>0$ and consider the 4-cycle
$(v_{i},v_{j},v_{k-1},v_{k})$. Notice that alternatively increasing and
decreasing the dual values on the edges of this cycle by a small amount
$\epsilon>0$ gives another feasible dual solution satisfying the complementary
slackness condition. More formally, we set
$\epsilon:=\min\\{y^{\prime}(v_{i},v_{j}),y^{\prime}(v_{k-1},v_{k})\\}$,
decrease $y^{\prime}(v_{i},v_{j})$ and $y^{\prime}(v_{k-1},v_{k})$ by
$\epsilon$, while increasing $y^{\prime}(v_{j},v_{k-1})$ and
$y^{\prime}(v_{k},v_{i})$ by the same amount. Observe that this leads to
either $(v_{i},v_{j})$ or $(v_{k-1},v_{k})$ dropping to dual value zero. We
can repeat this procedure until either $y^{\prime}(E[S^{\prime}])=0$ or
$y^{\prime}(v_{k-1},v_{k})=0$, finishing the proof of the theorem. ∎

Setting $\alpha\leq 1-4/k$ and $\rho\geq 2$ in the bound of Theorem 4.5
directly gives us an approximation algorithm of ratio $R(w)\leq 2-2/k$ for
this setting. This recovers a result given by Hochbaum in [27] and is in fact
best possible when working with the standard linear relaxation. This holds
since we are lower bounding $w(OPT)$ by comparing it to the value of the
optimal LP solution in Lemma 3.2, and the fact that the integrality gap of the
linear relaxation on the complete graph with $k$ vertices is $2-2/k$.

##  6 Integrality Gap and Fractional Chromatic Number

In this section, we consider as in Sections 4.1 and 4.2 graphs
$\mathcal{G}=(V,E)$ having the property that there exists an independent set
$I\subset V$ whose removal yields a bipartite graph. Equivalently, this is
simply the class of graphs with chromatic number three. For the case where
$I=\\{v_{p}\\}$ is a single vertex, we provide explicit formulas for the
integrality gap and the fractional chromatic number, and show that they are
again determined by the odd girth of the graph, generalizing a result known
for the cycle graph. For the case of an arbitrary $3$-colorable graph, we
provide tight upper bounds. A key result that we use in this section is given
by Singh in [48], which relates the integrality gap with the fractional
chromatic number of a graph.

The latter is denoted as $\chi^{f}(\mathcal{G})$ and is defined as the optimal
solution of the following primal-dual linear programming pair. We denote by
$\mathcal{I}\subset 2^{V}$ the set of all independent sets of the graph
$\mathcal{G}$. Solving these linear programs is however NP-hard because of the
possible exponential number of independent sets.

$\displaystyle\min\sum_{I\in\mathcal{I}}y_{I}$
$\displaystyle\sum_{I\in\mathcal{I},v\in I}y_{I}$ $\displaystyle\geq
1\quad\forall v\in V$ $\displaystyle y_{I}$ $\displaystyle\geq 0\quad\forall
I\in\mathcal{I}$

$\displaystyle\max\sum_{v\in V}z_{v}$ $\displaystyle\sum_{v\in I}z_{v}$
$\displaystyle\leq 1\quad\forall I\in\mathcal{I}$ $\displaystyle z_{v}$
$\displaystyle\geq 0\quad\forall v\in V$

Note that $\chi^{f}(\mathcal{G})=2$ if and only if $\mathcal{G}$ is bipartite.

######  Theorem 6.1 (Singh, [48]).

Let $\mathcal{G}=(V,E)$ be a graph. The integrality gap of the vertex cover
linear programming relaxation $P(\mathcal{G})$ is:

$IG(\mathcal{G})=2-\frac{2}{\chi^{f}(\mathcal{G})},$

where $\chi^{f}(\mathcal{G})$ is the fractional chromatic number of the graph
$\mathcal{G}$.

We first focus on graphs with the existence of a single vertex whose removal
produces a bipartite graph. The following theorem generalizes the result given
for the cycle graph in [4, 45] and turns out to be the same formula as for
series-parallel graphs [21].

######  Theorem 6.2.

Let $\mathcal{G}=(V,E)$ be a non-bipartite graph and $v_{p}\in V$ such that
$\mathcal{G}\setminus v_{p}=(A\cup B,E^{\prime})$ is bipartite. Then,

$\chi^{f}(\mathcal{G})=2+\frac{1}{\rho-1},$

where $2\rho-1$ is the odd girth of $\mathcal{G}$.

###### Proof of Theorem 6.2.

We prove this theorem by constructing feasible primal and dual solutions of
objective value $2+1/(\rho-1)$. By strong duality, these two solutions are
then optimal for their respective linear programs, hence proving the theorem.

We first construct the dual solution. Let $\mathcal{C}$ be the set of all the
shortest odd cycles of $\mathcal{G}$. For any such cycle $C\in\mathcal{C}$,
define the dual solution $z^{C}\in\mathbb{R}^{V}$ by

$z_{v}^{C}=\begin{cases}1/(\rho-1)\quad&\text{if }v\in C\\\ 0\quad&\text{if
}v\in V\setminus C\end{cases}$

This solution is feasible since any independent set in an odd cycle of length
$2\rho-1$ has size at most $\rho-1$. Indeed, fix an independent set
$I\in\mathcal{I}$, then:

$\sum_{v\in I}z_{v}^{C}=\sum_{v\in I\cap C}\;\frac{1}{\rho-1}=\frac{|I\cap
C|}{\rho-1}\leq 1.$

Moreover, the objective value of this solution is:

$\sum_{v\in V}z_{v}^{C}=\sum_{v\in
C}\;\frac{1}{\rho-1}=\frac{2\rho-1}{\rho-1}=2+\frac{1}{\rho-1}.$

Figure 8: An optimal dual solution constructed in the proof of Theorem 6.2.
Each node on a shortest odd cycle is assigned a fractional value of
$1/(\rho-1)$.

Let us now construct the primal solution. We will do so by constructing
$2\rho-1$ independent sets $I_{k}\in\mathcal{I}$ and assigning to each of them
a fractional value of $y(I_{k})=1/(\rho-1)$. All the other independent sets
are assigned value zero. We split the bipartite graph $\mathcal{G}\setminus
v_{p}$ into the layers

$\mathcal{L}_{i}:=\\{v\in A\cup B\mid d(N_{A}(v_{p}),v)=i\\}\quad\text{for
}i\in\\{0,\dots,l\\}.$

as explained in (4.1). As a reminder, any shortest odd cycle corresponds to a
path between $\mathcal{L}_{0}=N_{A}(v_{p})$ and $\mathcal{L}_{2\rho-3}\cap
N_{B}(v_{p})$. The original vertex set $V$ is thus decomposed into
$\\{v_{p}\\}\cup\mathcal{L}_{0}\cup\dots\cup\mathcal{L}_{l}$, where each layer
is an independent set and only has edges going out to $v_{p}$ or its two
neighbouring layers.

Let us first focus on the subgraph consisting of the vertices in
$\\{v_{p}\\}\cup\bigcup_{i=0}^{2\rho-3}\mathcal{L}_{i}$, where any shortest
odd cycle has exactly one vertex per layer (per abuse of notation, we say that
$\\{v_{p}\\}$ is also a layer in this situation). For convenience of indexing,
we rename these layers as
$\mathcal{\tilde{L}}_{1},\dots,\mathcal{\tilde{L}}_{2\rho-1}$ where
$\tilde{\mathcal{L}_{1}}=v_{p}$ and
$\tilde{\mathcal{L}}_{i}=\mathcal{L}_{i-2}$ for $i>1$. We now create $2\rho-1$
independent sets on this subgraph in the following way. The first independent
set is defined as
$U_{1}=\mathcal{\tilde{L}}_{1}\cup\mathcal{\tilde{L}}_{4}\cup\mathcal{\tilde{L}}_{6}\
\dots\cup\mathcal{\tilde{L}}_{2\rho-2}$, where we take the first layer
$\mathcal{\tilde{L}}_{1}$, skip two before taking the next one and then
continue by taking the remaining layers alternatingly (hence always skipping
one), see Figure 9. Note that the layer following
$\mathcal{\tilde{L}}_{2\rho-1}$ is assumed to be $\mathcal{\tilde{L}}_{1}$.
This procedure generates in fact a distinct independent set by starting at
$\mathcal{\tilde{L}}_{k}$ for any $k\in[2\rho-1]$ and we denote the
corresponding independent set by $U_{k}$. Notice that each layer is contained
in exactly $\rho-1$ of the constructed independent sets $\\{U_{k}\mid
k\in[2\rho-1]\\}$.

Figure 9: The $2\rho-1$ independent sets $I_{k}$ constructed in the optimal
primal solution. The blue nodes correspond to $\\{U_{k}\mid k\in[2\rho-1]\\}$,
whereas the orange nodes correspond to $\\{R_{1},R_{2}\\}.$

We now focus on the subgraph consisting of the vertices in
$\bigcup_{i>2\rho-3}\mathcal{L}_{i}$. We can construct two different
independent sets there by taking either the odd or even indexed layers, i.e.

$R_{1}:=\bigcup_{i\text{ odd},\;i>2\rho-3}\mathcal{L}_{i}\quad\text{and}\quad
R_{2}:=\bigcup_{i\text{ even},\;i>2\rho-3}\mathcal{L}_{i}.$

We now define our final $2\rho-1$ independent sets on the full graph as:

$I_{k}:=\begin{cases}U_{k}\cup R_{1}\quad\text{ if }v_{p}\notin U_{k}\\\
U_{k}\cup R_{2}\quad\text{ if }v_{p}\in U_{k}\end{cases}\qquad\forall
k\in[2\rho-1].$

These are in fact independent sets: in the first case, the first layer in
$R_{1}$ is $\mathcal{L}_{2\rho-1}$ whereas the last layer in $U_{k}$ has index
at most $2\rho-3$, meaning that there are no two neighbouring layers. In the
second case, since $v_{p}\in U_{k}$, we have that $\mathcal{L}_{2\rho-3}\notin
U_{k}$, by construction of $U_{k}$. The last layer in $U_{k}$ thus has index
at most $2\rho-4$, whereas the first layer in $R_{2}$ is
$\mathcal{L}_{2\rho-2}$, meaning again that there are no two neighbouring
layers. In addition, there is no edge between $v_{p}$ and $R_{2}$, because the
only even indexed layer having edges sent to $v_{p}$ is
$\mathcal{L}_{0}=N_{A}(v_{p})$.

We now define our primal solution as

$y(I_{k})=\frac{1}{\rho-1}\qquad\forall k\in[2\rho-1],$

and $y(I)=0$ for every other independent set $I\in\mathcal{I}$. We now show
this is a feasible solution, i.e. that every vertex $v\in V$ belongs to at
least $\rho-1$ independent sets in $\\{I_{k}\mid k\in[2\rho-1]\\}$. For
$v\in\\{v_{p}\\}\cup\bigcup_{i=0}^{2\rho-3}\mathcal{L}_{i}$, such a vertex
lies by construction in exactly $\rho-1$ independent sets $\\{U_{k}\mid
k\in[2\rho-1]\\}$, and thus also of $\\{I_{k}\mid k\in[2\rho-1]\\}$. For
$v\in\bigcup_{i>2\rho-3}\mathcal{L}_{i}$, if $v$ belongs to an even indexed
layer, then it is contained in $\rho-1$ of the desired independent sets. If it
belongs to an odd indexed layer, then it is contained in $\rho$ of them.
Therefore,

$\sum_{I\in\mathcal{I},v\in I}y_{I}=\sum_{k=1}^{2\rho-1}y(I_{k})\;1_{\\{v\in
I_{k}\\}}=\frac{1}{\rho-1}\sum_{k=1}^{2\rho-1}1_{\\{v\in I_{k}\\}}\geq 1.$

The objective value of this primal solution is clearly $2+1/(\rho-1)$. We have
constructed feasible primal and dual solutions with the same objective value.
By strong duality, this finishes the proof of the theorem.

∎

We now consider the case where $\mathcal{G}=(V,E)$ is a graph with chromatic
number $\chi(\mathcal{G})=3$.

######  Theorem 6.3.

Let $\mathcal{G}=(V,E)$ be a 3-colorable graph with color classes $V=V_{1}\cup
V_{2}\cup V_{3}$. Then,

$\chi^{f}(\mathcal{G})\leq 2+\min_{i\in\\{1,2,3\\}}\frac{1}{\rho_{i}-1}$

where $2\rho_{i}-1$ is the odd girth of the contracted graph
$\mathcal{G}/V_{i}$ for each $i\in\\{1,2,3\\}$. Moreover, equality holds if
one color class only contains one vertex.

###### Proof.

We prove this theorem by constructing three feasible solutions of value
$2+1/(\rho_{i}-1)$ for each $i\in\\{1,2,3\\}$ to the primal linear program of
the fractional chromatic number on the graph $\mathcal{G}$.

Fix an $i\in\\{1,2,3\\}$ and consider the graph
$\tilde{\mathcal{G}}:=\mathcal{G}/V_{i}=(\tilde{V},\tilde{E})$ with odd girth
$2\rho_{i}-1$. We denote the contracted node by $\tilde{v}\in\tilde{V}$. Since
this graph is bipartite if we were to remove $\tilde{v}$, we know that its
fractional chromatic number is equal to $2+1/(\rho_{i}-1)$ by Theorem 6.2. Let
$\\{\tilde{I}_{k},k\in[2\rho_{i}-1]\\}$ be the independent sets in the support
of the optimal primal solution of the graph $\tilde{\mathcal{G}}$ constructed
in the proof of this theorem. For each of these independent sets, we extend
them to the original graph in the following way:

$I_{k}=\begin{cases}\tilde{I}_{k}\qquad&\text{if
}\tilde{v}\notin\tilde{I}_{k}\\\ (\tilde{I}_{k}\setminus\tilde{v})\cup
V_{i}\qquad&\text{if }\tilde{v}\in\tilde{I}_{k}.\end{cases}$

In words, if $\tilde{v}$ happens to belong to $\tilde{I}_{k}$, we replace it
by $V_{i}$ to get a valid independent set in the original graph. Assigning
fractional value $y(I_{k})=1/(\rho_{i}-1)$ for every $k\in[2\rho_{i}-1]$
yields a feasible primal solution with objective value $2+1/(\rho_{i}-1)$.
Since we can do this for every $i\in\\{1,2,3\\}$, and the optimal minimum
value of the primal linear program is at most the objective value of any of
these feasible solutions, the proof is finished.

Moreover, this upper bound is in fact tight, since it holds with equality when
one of the color classes only contains one vertex by Theorem 6.2. ∎

It is now straightforward to extend this result for the integrality gap by
Theorem 6.1.

######  Corollary 6.1.

Let $\mathcal{G}=(V,E)$ be a 3-colorable graph with color classes $V=V_{1}\cup
V_{2}\cup V_{3}$. The integrality gap $IG(\mathcal{G})$ of the standard linear
programming relaxation $P(\mathcal{G})$ satisfies:

$IG(\mathcal{G})\leq 1+\min_{i\in\\{1,2,3\\}}\frac{1}{2\rho_{i}-1}$

where $2\rho_{i}-1$ is the odd girth of the contracted graph
$\mathcal{G}/V_{i}$ for each $i\in\\{1,2,3\\}$. Moreover, equality holds if
one color class only contains one vertex.

## References

  * [1] Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, and Bertrand Simon.  Online metric algorithms with untrusted predictions.  In International Conference on Machine Learning, pages 345–355. PMLR, 2020.
  * [2] Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev.  Secretary and online matching problems with machine learned advice.  Advances in Neural Information Processing Systems, 33:7933–7944, 2020.
  * [3] Kenneth I Appel and Wolfgang Haken.  Every planar map is four colorable, volume 98.  American Mathematical Soc., 1989.
  * [4] Sanjeev Arora, Béla Bollobás, and László Lovász.  Proving integrality gaps without knowing the linear program.  In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pages 313–322. IEEE, 2002.
  * [5] Stephan Artmann, Robert Weismantel, and Rico Zenklusen.  A strongly polynomial algorithm for bimodular integer linear programming.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1206–1219, 2017.
  * [6] R Balasubramanian, Michael R Fellows, and Venkatesh Raman.  An improved fixed-parameter algorithm for vertex cover.  Information Processing Letters, 65(3):163–168, 1998.
  * [7] M Balinski.  On the maximum matching, minimum covering.  In Proc. Symp. Math. Programming, pages 301–312. Princeton University Press, 1970.
  * [8] Étienne Bamas, Andreas Maggiori, and Ola Svensson.  The primal-dual method for learning augmented algorithms.  Advances in Neural Information Processing Systems, 33:20083–20094, 2020.
  * [9] Reuven Bar-Yehuda and Shimon Even.  A linear-time approximation algorithm for the weighted vertex cover problem.  Journal of Algorithms, 2(2):198–203, 1981.
  * [10] Reuven Bar-Yehuda and Shimon Even.  A local-ratio theorm for approximating the weighted vertex cover problem.  Technical report, Computer Science Department, Technion, 1983.
  * [11] Abbas Bazzi, Samuel Fiorini, Sebastian Pokutta, and Ola Svensson.  No small linear program approximates vertex cover within a factor 2- $\varepsilon$.  Mathematics of Operations Research, 44(1):147–172, 2019.
  * [12] Adrian Bock, Yuri Faenza, Carsten Moldenhauer, and Andres Jacinto Ruiz-Vargas.  Solving the stable set problem in terms of the odd cycle packing number.  In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014.
  * [13] Jonathan F Buss and Judy Goldsmith.  Nondeterminism within p.  SIAM Journal on Computing, 22(3):560–572, 1993.
  * [14] Jianer Chen, Iyad A Kanj, and Weijia Jia.  Vertex cover: further observations and further improvements.  Journal of Algorithms, 41(2):280–301, 2001.
  * [15] Jianer Chen, Lihua Liu, and Weijia Jia.  Improvement on vertex cover for low-degree graphs.  Networks: An International Journal, 35(4):253–259, 2000.
  * [16] Michele Conforti, Samuel Fiorini, Tony Huynh, Gwenaël Joret, and Stefan Weltge.  The stable set problem in graphs with bounded genus and bounded odd cycle packing number.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2896–2915. SIAM, 2020.
  * [17] Irit Dinur and Samuel Safra.  On the hardness of approximating minimum vertex cover.  Annals of mathematics, pages 439–485, 2005.
  * [18] Rodney G Downey and Michael R Fellows.  Fixed-parameter tractability and completeness.  In Complexity Theory: Current Research, pages 191–225, 1992.
  * [19] Rodney G Downey and Michael Ralph Fellows.  Parameterized complexity.  Springer Science & Business Media, 2012.
  * [20] Jörg Flum and Martin Grohe.  Parameterized complexity theory.  In Texts in Theoretical Computer Science. An EATCS Series, 2006\.
  * [21] Wayne Goddard and Honghai Xu.  Fractional, circular, and defective coloring of series-parallel graphs.  Journal of Graph Theory, 81(2):146–153, 2016.
  * [22] Jerrold W Grossman, Devadatta M Kulkarni, and Irwin E Schochetman.  On the minors of an incidence matrix and its smith normal form.  Linear Algebra and its Applications, 218:213–224, 1995.
  * [23] Ervin Györi, Alexandr V Kostochka, and Tomasz Łuczak.  Graphs without short odd cycles are nearly bipartite.  Discrete Mathematics, 163(1-3):279–284, 1997.
  * [24] Eran Halperin.  Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs.  SIAM Journal on Computing, 31(5):1608–1623, 2002.
  * [25] Johan Håstad.  Some optimal inapproximability results.  Journal of the ACM (JACM), 48(4):798–859, 2001.
  * [26] Dorit S Hochbaum.  Approximation algorithms for the set covering and vertex cover problems.  SIAM Journal on computing, 11(3):555–556, 1982.
  * [27] Dorit S Hochbaum.  Efficient bounds for the stable set, vertex cover and set packing problems.  Discrete Applied Mathematics, 6(3):243–254, 1983.
  * [28] George Karakostas.  A better approximation ratio for the vertex cover problem.  In International Colloquium on Automata, Languages, and Programming, pages 1043–1050. Springer, 2005.
  * [29] Richard M Karp.  Reducibility among combinatorial problems.  In Complexity of computer computations, pages 85–103. Springer, 1972.
  * [30] Subhash Khot and Oded Regev.  Vertex cover might be hard to approximate to within 2- $\varepsilon$.  Journal of Computer and System Sciences, 74(3):335–349, 2008.
  * [31] Stefan Kratsch and Magnus Wahlström.  Compression via matroids: a randomized polynomial kernel for odd cycle transversal.  ACM Transactions on Algorithms (TALG), 10(4):1–15, 2014.
  * [32] Harold W Kuhn.  The hungarian method for the assignment problem.  Naval research logistics quarterly, 2(1-2):83–97, 1955.
  * [33] Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii.  Online scheduling via learned weights.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1859–1877. SIAM, 2020.
  * [34] Lap Chi Lau, Ramamoorthi Ravi, and Mohit Singh.  Iterative methods in combinatorial optimization, volume 46.  Cambridge University Press, 2011.
  * [35] Thodoris Lykouris and Sergei Vassilvitskii.  Competitive caching with machine learned advice.  Journal of the ACM (JACM), 68(4):1–25, 2021.
  * [36] Burkhard Monien and Ewald Speckenmeyer.  Ramsey numbers and an approximation algorithm for the vertex cover problem.  Acta Informatica, 22(1):115–123, 1985.
  * [37] George L Nemhauser and Leslie E Trotter.  Properties of vertex packing and independence system polyhedra.  Mathematical programming, 6(1):48–61, 1974.
  * [38] George L Nemhauser and Leslie Earl Trotter.  Vertex packings: structural properties and algorithms.  Mathematical Programming, 8(1):232–248, 1975.
  * [39] Rolf Niedermeier and Peter Rossmanith.  Upper bounds for vertex cover further improved.  In Annual Symposium on Theoretical Aspects of Computer Science, pages 561–570. Springer, 1999.
  * [40] Rolf Niedermeier and Peter Rossmanith.  On efficient fixed-parameter algorithms for weighted vertex cover.  Journal of Algorithms, 47(2):63–77, 2003.
  * [41] Christos Papadimitriou and Mihalis Yannakakis.  Optimization, approximation, and complexity classes.  In Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 229–234, 1988.
  * [42] Manish Purohit, Zoya Svitkina, and Ravi Kumar.  Improving online algorithms via ml predictions.  Advances in Neural Information Processing Systems, 31, 2018.
  * [43] Bruce Reed, Kaleigh Smith, and Adrian Vetta.  Finding odd cycle transversals.  Operations Research Letters, 32(4):299–301, 2004.
  * [44] Tim Roughgarden.  Beyond the worst-case analysis of algorithms.  Cambridge University Press, 2021.
  * [45] Edward R Scheinerman and Daniel H Ullman.  Fractional graph theory: a rational approach to the theory of graphs.  Courier Corporation, 2011.
  * [46] Alexander Schrijver.  Theory of linear and integer programming.  John Wiley & Sons, 1998.
  * [47] Alexander Schrijver.  Combinatorial optimization: polyhedra and efficiency, volume 24.  Springer, 2003.
  * [48] Mohit Singh.  Integrality gap of the vertex cover linear programming relaxation.  Operations Research Letters, 47(4):288–290, 2019.
  * [49] Ulrike Stege and Michael Ralph Fellows.  An improved fixed parameter tractable algorithm for vertex cover.  Technical report/Departement Informatik, ETH Zürich, 318, 1999\.
  * [50] Leslie Earl Trotter Jr.  Solution characteristics and algorithms for the vertex packing problem. Cornell University, 1973.