3-SAT to Dominating Set (Karp Reduction)

Definition

3-SAT to Dominating Set

There is a polynomial-time many-one reduction

$$3\text{-}\mathrm{SAT}{\le }_m^p\mathrm{DOMINATING}\mathrm{SET}.$$

A 3-SAT formula $F$ with $n$ variables and $m$ clauses is mapped to a Dominating Set instance $(G,n)$ with $4n+m$ vertices, such that

$$F\text{ is satisfiable}⟺G\text{ has a dominating set of size at most }n.$$

Construction

Write $F={\bigwedge }_{j=1}^m{C}_j$, where each clause contains at most three literals over variables $x_1,\dots ,x_n$. All graphs below are simple and undirected. A selected vertex dominates itself and its neighbours, not vertices at distance two.

Give each variable two truth choices

For variable $x_i$, introduce four distinct vertices

$$B_i=\{t_i,f_i,a_i,b_i\}.$$

The vertices $t_i$ and $f_i$ represent setting $x_i$ to true and false. Add the five edges

$$E_i=\{\{t_i,f_i\},\{t_i,a_i\},\{f_i,a_i\},\{t_i,b_i\},\{f_i,b_i\}\}.$$

These are two triangles sharing the edge $\{t_i,f_i\}$. There is no edge between $a_i$ and $b_i$, and these two auxiliary vertices will have no neighbours outside $B_i$.

Selecting either $t_i$ or $f_i$ dominates all four vertices. Selecting only $a_i$ does not dominate $b_i$, and selecting only $b_i$ does not dominate $a_i$. Thus a single selection can handle this gadget only by choosing a truth-value vertex. The second auxiliary vertex is what prevents a one-vertex auxiliary choice.

Make each clause demand a true literal

For each clause $C_j$, add one vertex $c_j$. Join it to $t_i$ if $x_i$ occurs in $C_j$, and to $f_i$ if $\neg x_i$ occurs in $C_j$. No other edges are added: in particular, clause vertices are not adjacent to one another or to auxiliary vertices.

If $c_j$ is not itself selected, it is dominated exactly when at least one of its literal-vertices is selected. This is the disjunction in $C_j$. We still need to prohibit selecting $c_j$ directly; that is the purpose of the budget.

Allow exactly one selection per variable

Output $(G,k)$ with $k=n$. Every gadget needs at least one internal selection, since $a_i$ cannot be dominated from outside $B_i$. There are $n$ disjoint gadgets, so these selections exhaust the budget. There is no room for a clause vertex or a second choice in any gadget.

Consequently, each gadget must be dominated using exactly one internal vertex. By the variable gadget construction, that vertex must be $t_i$ or $f_i$.

This is the complete graph for the displayed formula. Orange vertices are selected; orange clause edges witness satisfied literals. Edge crossings are not vertices. The budget forces a truth assignment, and domination of the clause vertices checks that assignment.

For reference, the full construction is

$$\begin{array}{rl}V(G)& =\bigcup _{i=1}^n{B}_i\cup \{c_1,\dots ,c_m\},\\ E(G)& =\bigcup _{i=1}^n{E}_i\\ & \cup \{\{c_j,t_i\}:x_i\in C_j\}\\ & \cup \{\{c_j,f_i\}:\neg x_i\in C_j\},\\ k& =n.\end{array}$$

Here $x_i\in C_j$ means that the literal occurs in the clause; it does not assert that the literal is true.

Correctness

Satisfiability is equivalent to domination within the budget

Forward: turn an assignment into a dominating set

Let $\alpha :\{x_1,\dots ,x_n\}\to \{\top ,\perp \}$ satisfy $F$. Select

$$D=\{t_i:\alpha (x_i)=\top \}\cup \{f_i:\alpha (x_i)=\perp \}.$$

There is exactly one selected vertex per variable, so $|D|=n=k$. Each selected truth-value vertex dominates its entire gadget. Each clause $C_j$ has a true literal; the corresponding selected vertex is adjacent to $c_j$. Thus every vertex of $G$ is dominated.

Backward: recover a satisfying assignment

Let $D$ dominate $G$ with $|D|\le n$.

Count the selections forced inside gadgets

The only vertices that can dominate $a_i$ are $a_i,t_i,f_i$, all in $B_i$. Hence $|D\cap B_i|\ge 1$ for every $i$. Since the gadgets are disjoint,

$$n\le \underset{\text{selected gadget vertices}}{\underbrace{\sum _{i=1}^n|D\cap B_i|}}\le |D|\le n.$$

All inequalities are equalities. Thus every gadget contains exactly one selected vertex, and no clause vertex is selected.

Exclude auxiliary selections

If $D\cap B_i=\{a_i\}$, then $b_i$ is undominated: it is not selected, its only neighbours are $t_i,f_i$, and neither is selected. The case $D\cap B_i=\{b_i\}$ is symmetric. Therefore

$$D\cap B_i\in \{\{t_i\},\{f_i\}\}.$$

Define $\alpha (x_i)=\top$ when $t_i\in D$, and $\alpha (x_i)=\perp$ when $f_i\in D$. Exactly one of these cases holds for each variable.

Read domination of each clause as satisfaction

Fix any clause $C_j$. Since $c_j\notin D$, it must have a selected neighbour. Such a neighbour is either $t_i$ with $x_i\in C_j$, or $f_i$ with $\neg x_i\in C_j$. By the definition of $\alpha$, that literal is true. Thus every clause is satisfied, so $\alpha \models F$.

Size and running time

Let $L$ count distinct literal occurrences within clauses, so $L\le 3m$. The construction creates

$$\begin{array}{rl}N:=|V(G)|& =\underset{\text{variable gadgets}}{\underbrace{4n}}+\underset{\text{clause vertices}}{\underbrace{m}},\\ M:=|E(G)|& =\underset{\text{gadget edges}}{\underbrace{5n}}+\underset{\text{literal incidences}}{\underbrace{L}}\le 5n+3m.\end{array}$$

It takes $O(n+m)$ vertex/edge operations, hence polynomial time in the encoded input length. Repeated literals in a clause create only one edge. An empty clause creates an isolated clause vertex, which cannot fit into the exhausted budget; thus unsatisfiable empty clauses are handled correctly too.