2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Hi Hughson. Did you made any attempt to do literature survey? It seems pretty standard. $\endgroup$ Jun 9, 2023 at 21:19
  • 1
    $\begingroup$ @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” $\endgroup$
    – Dmitry
    Sep 2, 2023 at 14:23
  • $\begingroup$ @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. $\endgroup$ Sep 9, 2023 at 22:04
  • 1
    $\begingroup$ @InuyashaYagami, thanks, looks great! $\endgroup$
    – Dmitry
    Sep 12, 2023 at 22:15

1 Answer 1

2
$\begingroup$

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:

enter image description here

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.