1
$\begingroup$

Can anyone help me with the following exercise?

STASI problem (graph domination problem) is following: we have an undirected graph and number K. Is it possible to place K spies on graph's vertices in order that each vertex without spy has at least one spy in the neighborhood?

I know that I have to show that 3SAT <=p STASI, but I have a problem with it. I will be grateful for any solution or tip.

$\endgroup$
  • $\begingroup$ Going from 3SAT to Dominating Set, think of the literals and clauses as vertices, add an edge between a literal and a clause if the literal satisfies the clause. And finding a satisfying assignment is like dominating all the clauses by choosing literals. You have to ensure that a literal and its negation don't both get chosen though. $\endgroup$ – Manuel Lafond Jun 5 '17 at 3:35
0
$\begingroup$

Given an instance 3-SAT with $n$ variables $x_1, x_2, ..., x_n$ and $m$ clauses $c_1, c_2, ..., c_m$ construct the following instance of $DOMSET<G, k>$

1) Set k = n
2) Construct the following graph G with vertices
$\quad u_1, u_2, ..., u_n$
$\quad x_1, x_2, ..., x_n$
$\quad \overline x_1, \overline x_2, ..., \overline x_n$
$\quad c_1, c_2, ..., c_m$.

3) Create the following edges $(u_i, x_i), (u_i, \overline x_i)$ and $(x_i, \overline x_i)$ to form a triangle of vertices.

4) For each clause $c_j$ create edge $(c_j, x_i)$ if $c_j$ contains $x_i$ and edge $(c_j, \overline x_i)$ if $c_j$ contains $\overline x_i$

The diagram below illustrates the construction for a clause $c_i = x_1 + \overline x_2 + x_3$

enter image description here

Suppose there is a satisfying assignment.
Form a set S that includes $x_i$ if $x_i$ is true and $\overline x_i$ if $x_i$ is false.
S contains exactly n vertices and includes all variables that are true.
Every $x_i$ not in S is adjacent to $\overline x_i$ in S
Every $\overline x_i$ not in S is adjacent to $x_i$ in S
Since every clause is true, every clause must include at least one variable that is true.
Since S contains all variables that are true, every clause is adjacent to at least one variable in S.
So, S is a dominating set of n vertices.

Suppose S is a dominating set of at most n vertices.
Note that at least one of $u_i, x_i$ or $\overline x_i$ must be in S for $i=1,2,..., n$
Since S has at most n vertices and must include at least one vertex from each of the n triangles, S can only include exactly one vertex from each triangle.
If $u_i$ is in S, we can always replace it with either $x_i$ or $\overline x_i$ and S would still be a dominating set.
So, we can assume that S contains only $x_i$ or $\overline x_i$ without loss of generality.
If $x_i$ is in S, assign true to x_i and if $\overline x_i$ is in S, assign false to$
This means all variables in S are true.
Since S is a dominating set, all clauses are adjacent to some variable in S that has been assigned true.
So, all clauses are true and there is a satisfying assignment.

$\endgroup$

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.