Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
How to provide a reduction from 3SAT to domatic number problem. Domatic number problem: Given a graph $G = (V, E)$ and an integer $k$, can we partition $V $ into at least k disjoint sets of vertices, such that each set is a dominating set of $G$?
I have made many attempts, but still have no clue.
The following is a reduction from 3-SAT to the domatic number problem:
Let $\phi: C_1 \wedge C_2 \wedge \dotsc C_m$ be an instance of 3-SAT with $n$ variables $x_1,\dotsc,x_n$. Create a graph $G = (V,E)$ such that for each clause $C_i \in \{C_1,\dotsc,C_m\}$ there is a vertex $vc_i$, and for each variable $x_j \in \{x_1,\dotsc,x_n\}$ there are three vertices $a_j$, $b_j$, and $c_j$. The three vertices $a_j$, $b_j$, and $c_j$ form a triangle in the graph as shown in the figure below:
The vertex $a_j$ corresponds to the positive literal $x_j$ and the vertex $b_j$ corresponds to the negative literal $\bar{ x_j }$. There is an edge between vertices $vc_i$ and $a_j$ iff $x_j$ appears in clause $C_i$. Similarly, there is an edge between vertices $vc_i$ and $b_j$ iff $\bar{x_j}$ appears in clause $C_i$. Moreover, there is a vertex $r$ which is connected to vertex $vc_i$ via a path $r \to s_i \to vc_i$ for each $i \in \{1,\dotsc,m\}$. Moreover, the vertex $r$ is directly connected to vertices $a_j$ and $b_j$ by an edge for each $j \in \{1,\dotsc,n\}$. This completes the construction.
Claim: $\phi$ is satisfiable iff $G$ has domatic number at least $3$.
Proof: $(\to)$ Suppose that $\phi$ has a satisfying assignment such that without loss of generality, $x_1,\dotsc,x_k$ variables are true and the remaining variables $x_{k+1},\dotsc,x_n$ are false. We show that the reduced graph $G = (V,E)$ has domatic number $3$. The vertex set $V$ can be partitioned into three sets $V_1 = \{ a_1,\dotsc,a_k,b_{k+1},\dotsc,b_n\} \cup \{r\}$, $V_2 = \{ b_1,\dotsc,b_k,a_{k+1},\dotsc,a_n,vc_{1},\dotsc,vc_m\}$, and $V_3 = \{c_1,\dotsc,c_n, s_1,\dotsc,s_m\}$. It is easy to see that each of these vertex sets is a dominating set of graph $G$.
$(\gets)$ Suppose the graph $G = (V,E)$ has domatic number at least $3$. Note that the domatic number can not be greater than $3$ since $c_i$ has degree two and it can be dominated by at most three distinct sets. Therefore, let $V_1$, $V_2$, $V_3 \subseteq V$ be a partition of the vertex set $V$ such that each vertex set is a dominating set. Without loss of generality, assume that $r \in V_1$. Then there are only two possibilities for each $i \in \{1,\dotsc,n\}$ as stated below:
$(1)$ $vc_i \in V_2$ and $s_i \in V_3$
$(2)$ $vc_i \in V_3$ and $s_i \in V_2$
Otherwise, $s_i$ can not be dominated by one of the sets $V_2$ or $V_3$. Without loss of generality, consider a particular vertex $vc_i$ and suppose that $vc_i \in V_2$. Therefore, $s_i \in V_1$. Now note that $vc_i$ must be dominated by some vertex in $V_1$. Therefore, at least one of the $a_j/b_j$'s connected to $vc_i$ must be in $V_1$. Therefore, the vertex set $V_1 \cap \{a_1,\dotsc,a_n,b_1,\dotsc,b_n\}$ is a satisfying assignment for $\phi$. Note that for any $j$, both $a_j$ and $b_j$ can not be picked into $V_1$ otherwise $c_j$ won't get dominated by either $V_2$ and $V_3$. Therefore, the assignment is a valid assignment. This completes the proof of the claim.
