Vertex Cover to Integer Linear Programming (Karp Reduction)

Definition

Vertex Cover to Integer Linear Programming

There is a polynomial-time many-one reduction from the Vertex Cover problem to the decision version of integer linear programming:

$$\mathrm{VERTEX}\mathrm{COVER}{\le }_m^p{\mathrm{ILP}}_{\mathrm{decision}}.$$

Construction

Given a Vertex Cover instance $(G,k)$ with $G=(V,E)$, create one integer variable $x_v$ for every vertex $v\in V$. Force every variable to be binary using

$$-x_v\le 0,x_v\le 1(v\in V).$$

Interpret $x_v=1$ as selecting $v$. Bound the number of selected vertices by

$$\sum _{v\in V}{x}_v\le k.$$

For every edge $\{u,v\}\in E$, require at least one selected endpoint:

$$-x_u-x_v\le -1⟺x_u+x_v\ge 1⟺(x_u=1)\vee (x_v=1).$$

Finally, use the zero objective and target

$$c=(0,\dots ,0),t=0.$$

The objective is irrelevant: the reduction asks only whether a feasible assignment exists, corresponding to a vertex cover of size at most $k$.

Correctness

The Vertex Cover instance is a yes-instance if and only if the constructed ILP instance is a yes-instance.

Correctness

Forward

Let $C\subseteq V$ be a vertex cover with $|C|\le k$. Set $x_v=1$ for $v\in C$ and $x_v=0$ otherwise. The budget constraint holds, and every edge has an endpoint in $C$, so every edge constraint holds. The objective reaches $t=0$.

Backward

Any feasible integer assignment satisfies $x_v\in \{0,1\}$. Define

$$C=\{v\in V:x_v=1\}.$$

The budget constraint gives $|C|\le k$. For every edge $\{u,v\}\in E$, the edge constraint implies $x_u+x_v\ge 1$, so at least one endpoint belongs to $C$. Hence $C$ is a vertex cover.

Running time

The reduction creates $|V|$ variables and $2|V|+|E|+1$ inequalities. Its running time and output encoding size are polynomial in $|V|+|E|$.

NP-hardness

Vertex Cover is NP-hard without large numerical parameters. The reduction uses only coefficients from $\{-1,0,1\}$, and one may assume $k\le |V|$. It therefore proves that ILP is strongly NP-hard. Together with membership in NP, the ILP decision problem is strongly NP-complete.