13.1. Half-Integrality

As already said in the introduction of this chapter, half-integrality is the property of an ILP that its LP relaxation has optimal solutions where every variable's value is a multiple of \(\frac{1}{2}\). As we will see, these solutions are really easy to round, to obtain \(2\)-approximations of optimal solutions. We illustrate this using the vertex cover and multiway vertex cut problems as examples.

For the vertex cover problem, we are able to prove that essentially every optimal solution of the LP relaxation is half-integral. Specifically, we prove that every solution of the type found by the Simplex Algorithm is half-integral for the vertex cover problem. Thus, the algorithm for finding a \(2\)-approximation of an optimal integral solution is simple: Compute an arbitrary optimal fractional solution and then round it.

For the multiway vertex cut problem we can only show that there exists and optimal fractional solution that is half-integral. Thus, we also need to worry about constructing such a solution from an arbitrary optimal fractional solution before rounding. (Actually, we will combine the transformation into a half-integral solution and the rounding step into a single step.)