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:

Construction

Given a Vertex Cover instance with , create one integer variable for every vertex . Force every variable to be binary using

Interpret as selecting . Bound the number of selected vertices by

For every edge , require at least one selected endpoint:

Finally, use the zero objective and target

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

Correctness

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

Correctness

Forward

Let be a vertex cover with . Set for and otherwise. The budget constraint holds, and every edge has an endpoint in , so every edge constraint holds. The objective reaches .

Backward

Any feasible integer assignment satisfies . Define

The budget constraint gives . For every edge , the edge constraint implies , so at least one endpoint belongs to . Hence is a vertex cover.

Running time

The reduction creates variables and inequalities. Its running time and output encoding size are polynomial in .

NP-hardness

Vertex Cover is NP-hard without large numerical parameters. The reduction uses only coefficients from , and one may assume . It therefore proves that ILP is strongly NP-hard. Together with membership in NP, the ILP decision problem is strongly NP-complete.