Dominating Set to Integer Linear Programming (Karp Reduction)

Definition

Dominating Set to Integer Linear Programming

There is a polynomial-time many-one reduction

$$\mathrm{DOMINATING}\mathrm{SET}{\le }_m^p\mathrm{INTEGER}\mathrm{LINEAR}\mathrm{PROGRAMMING}$$

from the Dominating Set decision problem to the integer linear programming decision problem. A graph $G=(V,E)$ and threshold $k$ are mapped to an integer constraint system feasible exactly when $G$ has a dominating set of size at most $k$.

Construction

Let $G$ be a simple undirected graph. Write $N(v)=\{u:\{u,v\}\in E\}$ for the neighbours of $v$ and $N[v]=N(v)\cup \{v\}$ for its closed neighbourhood.

Represent selection by binary integer variables

Introduce one integer variable $x_v$ per vertex and impose
$0\le x_v\le 1(v\in V).$
Integrality forces $x_v\in \{0,1\}$: $1$ means selected and $0$ means unselected. Enforce the size bound by
${\sum }_{v\in V}{x}_v\le k.$

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 $v$ is dominated if it is selected itself or some neighbour is selected. Require

$$\sum _{u\in N[v]}{x}_u=x_v+\sum _{u\in N(v)}{x}_u\ge 1(v\in V).$$

Each summand is $0$ or $1$, so the inequality says that at least one vertex in $N[v]$ is selected.

These are the three domination rows for the path above. The choice $(x_a,x_b,x_c)=(0,1,0)$ makes all three left-hand sides equal to $1$. An isolated vertex has constraint $x_v\ge 1$, correctly forcing its selection.

Express feasibility in the target decision format

In the ILP decision format $Ax\le b$, rewrite lower bounds by multiplying by $-1$:

$$\begin{array}{rlrl}-x_v& \le 0& & (v\in V),\\ x_v& \le 1& & (v\in V),\\ \sum _{v\in V}{x}_v& \le k,& & \\ -\sum _{u\in N[v]}{x}_u& \le -1& & (v\in V).\end{array}$$

Set the objective vector to $c=0$ and threshold to $t=0$. Then $c^{\top }x\ge t$ 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 $D\subseteq V$ dominates $G$ and $|D|\le k$. Set $x_v=1$ for $v\in D$ and $x_v=0$ otherwise. These values are integral and satisfy the domain bounds. Their sum is $|D|\le k$. For every $v$, domination gives $D\cap N[v]\ne \varnothing$, so ${\sum }_{u\in N[v]}{x}_u\ge 1$. 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 $x$. Domain bounds imply $x_v\in \{0,1\}$. Define $D=\{v:x_v=1\}$. The budget row gives $|D|={\sum }_v{x}_v\le k$. For each $v$, the domination row forces at least one $x_u=1$ with $u\in N[v]$. Hence every vertex lies in $D$ or has a neighbour in $D$. Thus $D$ is a dominating set of the required size.

Size and running time

For $n=|V|$ and $m=|E|$, there are $n$ integer variables and $3n+1$ constraint rows. The domination rows contain

$$\sum _{v\in V}|N[v]|=\sum _{v\in V}(1+\mathrm{deg}(v))=n+2m$$

nonzero coefficients: each vertex contributes its own variable, and each undirected edge contributes to two rows. Including $2n$ domain coefficients and $n$ budget coefficients gives $4n+2m$ nonzero coefficients in total.

All coefficients are $-1$, $0$ or $1$; the only potentially large right-hand side is the copied threshold $k$. A sparse representation can be built in $O(n+m)$ coefficient operations, plus the cost of copying $k$ and encoding indices. A dense matrix uses $O(n^2)$ entries. Both representations have polynomial encoding length and can be produced in polynomial time.