Reduce from 3-SAT to the dominating set problem

[GiggleLiu]

No description provided.

[SciCodePhy]

Reduce 3-SAT to the Dominating Set Problem

I. Definitions and Background

I-A. SAT

• Boolean Algebra [see 'Reduce k-SAT to 3-SAR' issue]
• Cook-Levin Theorem: 3-SAT is NP-complete.

I-B. Dominating Set Problem

Given a graph $G=(V,E)$:

• Dominating Set: a subset $D \subset V$ is a dominating set if: all the vertices in $G$ is either in $D$ or the neighbor of $D$.
• Domination Number: The size of the smallest dominating set (denoted by $\gamma(G)$.
• Dominating Set Problem: For a graph $G$ and an integer $k$, do we have a dominating set of size $k$. This is equivalent to check whether $\gamma(G) \leq k$.

II. Proof (3-SAT <= Dominating Set)

Input: An instance of 3-SAT problem -> A 3-SAT CNF.

Output: A Graph $G$ and an integer $k$.

• Step-0: $k$ = number of literals in this CNF;
• Step-1-a: Add all the $k$ literals ${x_{i\leq k} }$ and their $k$ negations ${\bar{x}_{i\leq k} }$ to the vertices;
• Step-1-b: Add all the $m$ clauses ${c_{i\leq m}}$ to the vertices;
• Step-1-c: Add $k$ dummy variables to the vertices;
• Step-2-a: Assign a dummy variable to each literal so we can attach an index to each dummy variable ${u_{i\leq k}}$. Connect $(u_i, x_i)$, $(u_i, \bar{x}_i)$ and $(x_i, \bar{x}_i)$;
• Step-2-b: If a clause $c$ has three literals, connect all of them to $c$.

It can be proven that:

• All the yes-instances exactly match.
• The transformation is within polynomial time.

III. References

Core References:

1. https://math.stackexchange.com/questions/2307920/np-hardness-polynomial-time-reduction-graph-domination-problem-stasi-problem