Proving NP-completeness of a surveilled graph problem 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!
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$.