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.
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$
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 $x_i$.
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.