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

• Awesome, thank you for the detailed response. I am guessing there is no way to reduce 3-SAT directly to this problem? – user119110 Apr 8 at 19:34
• See my other answer. – Steven Apr 8 at 20:14

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:

• That's fantastic...thanks a lot! – user119110 Apr 8 at 20:27
• You're welcome. A slight modification of this reduction shows that it also holds for the special case in which the function $g(u)$ is identically $1$. This and the modified version also show that the problem remains hard on planar graphs. – Steven Apr 8 at 20:32
• Replace each edge from a literal $x_i$ to $w_j$ with a path $\langle x_i, a, b, c, d, w_j \rangle$, and append a vertex $y$ to $c$. Vertices $a$ and $c$ belong to $A$. Now, if $x_i$ is selected in $B$, vertex $d$ can either belong or not belong to $B$ (depending on whether we add $y$ to $B$). If $x_i$ is not selected in $B$, then $d$ cannot possibly belong to $B$. Do the same for $\overline{x}_i$. In this way if a clause $C_j$ is satisfied by $k$ literals, we can always select any number $k' \le k$ of neighbors of $w_j$ in $B$. In particular, we can choose $k'=1$. – Steven Apr 8 at 20:45