1
$\begingroup$

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!

$\endgroup$
0

2 Answers 2

1
$\begingroup$

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

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

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:

reduction example

$\endgroup$
3
  • $\begingroup$ That's fantastic...thanks a lot! $\endgroup$
    – user119110
    Apr 8, 2020 at 20:27
  • $\begingroup$ 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. $\endgroup$
    – Steven
    Apr 8, 2020 at 20:32
  • $\begingroup$ 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$. $\endgroup$
    – Steven
    Apr 8, 2020 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.