Given a graph G and an integer k , recognize whether G contains dominating set X with no more than k vertices. And that is by finding a propositional formula ϕG,k that is only satisfiable if and only if there exists a dominating set with no more than k vertices, so basically reducing it to SAT-Problem.

The solution to this problem is supposed to be similar to reducing clique to SAT. Here is how that looks like: https://blog.computationalcomplexity.org/2006/12/reductions-to-sat.html

  • 1
    $\begingroup$ What is your question? $\endgroup$
    – Nathaniel
    Jun 11 at 13:32
  • $\begingroup$ We are a question-and-answer site, so we require you to articulate a specific question about your situation. It might also be helpful to share with us the context where you encountered this task. Finally, we discourage questions that simply state an exercise-style task out of context and expect us to solve it. You might find this page helpful in improving your question. $\endgroup$
    – D.W.
    Jun 11 at 20:20
  • $\begingroup$ Right, sorry. The question is how to do it? How to reduce the dominating set problem to SAT $\endgroup$
    – Matjaž
    Jun 11 at 21:07

Take a look at the Cook Levin theorem, that shows a reduction from any $NP$ problem to $SAT$. Since $Dominating-Set\in NP$, this is a reduction $Dominating-Set\le_p SAT$.

In the case I didn't understand your question and you wanted a reduction $SAT\le_p Dominating-Set$, consider creating the following graph: add a node for each variable $x_i$ and add another node for its negation $\overline{x_i}$, and add an edge between the two nodes. For each such variable, add another node $h_i$ that has an edge to $x_i$ and $\overline{x_i}$.

Additionally, for each clause add a node $c_j$ and add an edge between it to any literal in it.

Now we want to find a dominating set of size $k$, where $k$ is the number of variables in the SAT instance.

For more information on this, take a look here.

I hope this helped!

  • $\begingroup$ Right, I actually somehow missed that. Thanks! $\endgroup$
    – Juho
    Jun 12 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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