0
$\begingroup$

Given an undirected graph $G=(V,E)$ where $V$ is a set of vertices, and $E$ is a set of edges and
given a set $D$ where $D \subseteq V $ and $ \forall v \in V \setminus D \: \mid \: \exists w \in D : \{v,w\} \in E$

INPUT an undirected graph $G=(V,E)$ and a number $k \in \mathbb{N}$
PROBLEM $X$ : Does a set $D \subseteq V$ exist where $ |D| \leq k$ ?

I'm asked to prove that $\text{3-SAT} \leq_p X$.
I thought about using the $\text{CLIQUE}$ problem to prove it, since they seem to be related, though I'm not sure about it.
Or could I use the $\text{VERTEX-COVER}$ problem and reduce it to problem $X$?

Improve this question
$\endgroup$
5
  • $\begingroup$ If you already know that min-vertex-cover ist NP-complete then you should proof: $\text{3-SAT} \leq_p \text{MIN-VERTEX-COVER} \leq_p \text{X}$. $\endgroup$
    – plshelp
    Jul 10, 2022 at 15:52
  • $\begingroup$ In the title you ask for a polynomial reduction to 3-SAT. In the body you ask for a polynomial reduction from 3-SAT... $\endgroup$
    – Steven
    Jul 10, 2022 at 17:24
  • $\begingroup$ Hint: you want the vertices in the dominating set $D$ to correspond to a truth assignment of the variables. Each variable is represented by 2 vertices. Clauses are vertices that are dominated iff at least one of their literals is true. To ensure that it is never convenient to directly add clauses to $D$ you can create sufficiently many copies of the clause vertices. To force the choice of at least one truth value for each variable you can add an edge between its two vertices. To ensure that at most one truth value is chosen you can play with $k$. You should be able to fill in the details. $\endgroup$
    – Steven
    Jul 10, 2022 at 17:30
  • $\begingroup$ @Steven My bad, changed the title. Thank you for mentioning it. $\endgroup$
    – Emily
    Jul 10, 2022 at 17:31
  • 1
    $\begingroup$ Your problrm is a dominating set problem. See en.m.wikipedia.org/wiki/…. $\endgroup$
    – Majid Zohrehbandian
    Jul 11, 2022 at 8:13

0

Reset to default

Your Answer

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