Proving NP-completeness of a surveilled graph problem

Question

So suppose I have a graph consisting of a tuple $(V,E,A,g)$ where $V$ denotes vertices, $E$ denotes edges, $A$ denotes a subset of $V$ (i.e. $A \subseteq V$), and $g:A\rightarrow\mathbb{N}$ is a function.

We can call this graph instance $\textit{consistent}$ if we can find a subset $B \subseteq V$ \ $A$ such that for any $u \in A$, $ g(u) = |N(u)\cap B|$ (in which $N(u)$ obviously denotes the neighbourhood of vertex $u$).

How would one go about proving that the problem of determining consistency of a graph $(V,E,A,g)$ is NP-complete? Would a reduction from SUBSET-SUM using slack variables of some type work?

Thanks!

Answer 1

Let $\langle \mathcal{S}, \mathcal{I} \rangle$ be an instance of exact cover. Here $\mathcal{I}$ is a set of items and $\mathcal{S} \subseteq 2^\mathcal{I}$ is a collection of subsets of $\mathcal{I}$.

The goal is to decide whether there is a subset $S$ of $\mathcal{S}$ such that every item in $\mathcal{I}$ belongs to exactly one set in $S$. This is a well-known NP-complete problem.

To reduce exact cover to your problem create a graph $G = (V, E, A, g)$ as follows:

• $V = \mathcal{S} \cup \mathcal{I}$.
• $E = \{ (u,v) \in \mathcal{S} \times \mathcal{I} \mid v \in u \}$.
• $A = \mathcal{I}$
• $\forall u \in a, g(u)=1$.

If $S$ is an exact cover for $\langle \mathcal{S}, \mathcal{I} \rangle$, then $B=S$ is a solution for your original problem since $S \cap \mathcal{I} = B \cap A = \emptyset$ and each item in $\mathcal{I}=A$ has exactly one neighbor in $S = B$.

On the other hand, a solution $B$ to your original problem is such that $B \cap A = B \cap \mathcal{I} = \emptyset$. Hence $B \subseteq \mathcal{S}$ and eacn item in $A = \mathcal{I}$ has exactly one neighbor in $B$. Therefore $B$ is an exact cover for $\langle \mathcal{S}, \mathcal{I} \rangle$.

Answer 2

Here is a sketch of a direct reduction from 3-SAT to your problem.

Given a formula $\phi$, create a graph that contains:

• For each variable $x_i$ of $\phi$: a path of length 2 traversing vertices $x_i, u_i, \overline{x}_i$. Vertex $u_i$ is in $A$ and $g(u_i)=1$.

• For each clause $C_j$ of $\phi$, a path of length 2 traversing vertices $v_j, w_j, z_j$. Vertex $w_j$ is in $A$ and $g(w_j)=3$.

• For each variable-clause pair $(x_i, C_j)$ such that $x_i$ is a literal in $C_j$, add the edge $(x_i, w_j)$.

• For each variable-clause pair $(x_i, C_j)$ such that $\overline{x}_i$ is a literal in $C_j$, add the edge $(\overline{x}_i, w_j)$.

If there is a solution to the SAT instance, you can obtain a solution to your problem by selecting a set $B$ that contains all true literals (i.e., if $x_i$ is true, add $x_i$ to $B$, otherwise add $\overline{x}$ to $B$). Now all vertices $u_i$ have exactly one neighbor in $B$, while each vertex $w_j$ has $\eta_i \in \{1,2,3\}$ neighbors in $B$. By adding $3-\eta_i$ vertices from $\{v_j, z_j\}$ to $B$ you can also satisfy the condition on $w_j$.

The reverse direction is also true. For each variable $x_i$ exactly one vertex in $\{x_i, \overline{x}_i \}$ is in $B$ and this determines the truth value of $x_i$ in the satisfying assignment. Each vertex $w_j$ must have at least one neighbor in $B$, showing that clause $C_j$ is satisfied by the truth assignment.

See the following figure for an example: