Dominating Set to Integer Linear Programming (Karp Reduction)

Definition

Dominating Set to Integer Linear Programming

There is a polynomial-time many-one reduction

from the Dominating Set decision problem to the integer linear programming decision problem. A graph and threshold are mapped to an integer constraint system feasible exactly when has a dominating set of size at most .

Construction

Let be a simple undirected graph. Write for the neighbours of and for its closed neighbourhood.

Represent selection by binary integer variables

Introduce one integer variable per vertex and impose

Integrality forces : means selected and means unselected. Enforce the size bound by

The sum counts selected vertices exactly because each variable is binary. Bounds alone without integrality would allow fractional choices and would not encode a dominating set.

Turn each closed neighbourhood into one constraint

A vertex is dominated if it is selected itself or some neighbour is selected. Require

Each summand is or , so the inequality says that at least one vertex in is selected.

These are the three domination rows for the path above. The choice makes all three left-hand sides equal to . An isolated vertex has constraint , correctly forcing its selection.

Express feasibility in the target decision format

In the ILP decision format , rewrite lower bounds by multiplying by :

Set the objective vector to and threshold to . Then is always true, so the target asks only whether the constraints admit an integer solution. No optimisation needs to be performed by the reduction.

Correctness

Selections and feasible integer vectors correspond

Forward: encode a dominating set

Suppose dominates and . Set for and otherwise. These values are integral and satisfy the domain bounds. Their sum is . For every , domination gives , so . The zero objective reaches its zero threshold. Thus the target is a yes-instance.

Backward: decode a feasible integer vector

Suppose the target has a feasible integer vector . Domain bounds imply . Define . The budget row gives . For each , the domination row forces at least one with . Hence every vertex lies in or has a neighbour in . Thus is a dominating set of the required size.

Size and running time

For and , there are integer variables and constraint rows. The domination rows contain

nonzero coefficients: each vertex contributes its own variable, and each undirected edge contributes to two rows. Including domain coefficients and budget coefficients gives nonzero coefficients in total.

All coefficients are , or ; the only potentially large right-hand side is the copied threshold . A sparse representation can be built in coefficient operations, plus the cost of copying and encoding indices. A dense matrix uses entries. Both representations have polynomial encoding length and can be produced in polynomial time.