= Solution
A <vertex cover> of an <undirected graph> $G=(V,E)$ is a <subset> $C\subseteq V$ containing at least one endpoint of every <edge>. The optimization version of the <vertex cover> problem minimizes $|C|$; the <vertex cover decision problem> asks whether a cover of size at most a given bound exists.
Let $x_v=1$ mean that <vertex> $v$ is selected. An <integer program> for minimum-size <vertex cover> is
$$
\boxed{
\begin{aligned}
\min\quad&\sum_{v\in V}x_v\\
\text{subject to}\quad&x_u+x_v\geq1&& (uv\in E),\\
&x_v\in\{0,1\}&& (v\in V).
\end{aligned}}
$$
The <linear programming relaxation> replaces $x_v\in\{0,1\}$ by $0\leq x_v\leq1$. The <edge> inequalities enforce coverage, and the <objective function> counts selected <vertices> in the <integer program>.
For a <graph triangle> with <vertices> $1,2,3$, the three covering constraints are
$$
x_1+x_2\geq1,\qquad x_2+x_3\geq1,\qquad x_3+x_1\geq1.
$$
Adding them gives $2(x_1+x_2+x_3)\geq3$. Therefore the relaxed <objective function> is at least $3/2$. The <feasible solution> $x_1=x_2=x_3=1/2$ attains that lower bound, so
$$
\boxed{\operatorname{OPT}_{\mathrm{LP}}=\frac32.}
$$
In contrast, one <vertex> leaves the opposite <edge> uncovered and any two <vertices> cover all three <edges>, giving integer optimum $2$. The example exhibits a genuinely non-integer optimal value, rather than merely a fractional <feasible solution>.
Back to article page
