# How to provide a reduction from 3SAT to domatic number problem

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.

• Hi Hughson. Did you made any attempt to do literature survey? It seems pretty standard. Jun 9 at 21:19
• @InuyashaYagami, if you know a reference which actually has a proof, please share. Everyone cite “ Computers and Intractability: A Guide to the Theory of NP-Completeness”, which then refers to “unpublished results” Sep 2 at 14:23
• @Dmitry Thanks for checking closely. I could not find the result myself as well. However, I have added an answer. I would be grateful, if you could verify it once. Sep 9 at 22:04
• @InuyashaYagami, thanks, looks great! Sep 12 at 22:15

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.