Past exam of the computer science course of the University of Oxford / 2015 / Advanced data structures and algorithms / 3 / b

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 isThe linear programming relaxation replaces $x_v\in \{0,1\}$ by $0\le x_v\le 1$. 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 areAdding them gives $2(x_1+x_2+x_3)\ge 3$. 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, soIn 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.