# NP Reduction - Dominating set to SAT

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

• What is your question? Jun 11 at 13:32
• 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.
– D.W.
Jun 11 at 20:20
• Right, sorry. The question is how to do it? How to reduce the dominating set problem to SAT 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.
The text passage discusses a computational problem related to reducing the dominating set problem to the satisfiability (SAT) problem. It includes a question about how to perform this reduction and provides a potential method for doing so.
single_question_with_answer
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# NP Reduction - Dominating set to SAT

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

• What is your question? Jun 11 at 13:32
• 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.
– D.W.
Jun 11 at 20:20
• Right, sorry. The question is how to do it? How to reduce the dominating set problem to SAT 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.
user
The text passage discusses a computational problem related to reducing the dominating set problem to the satisfiability (SAT) problem. It includes a question about how to perform this reduction and provides a potential method for doing so.

TYPE: SINGLE_QUESTION_WITH_ANSWER