1
$\begingroup$

Suppose we have a set of variables $V$. We also have a set of equations $E$, which are sets of at least two variables. We don't know anything about these equations, except if we know all but one of the variables in an equation, we can deduce the missing one.

Does there exist a set of variables $R \subseteq V$ with $|R| \leq k$ such that revealing these variables allows us to deduce all variables?

Is this problem NP-complete? What if all equations have degree $\leq d$?

I'm ultimately interested in the search version of this problem (where we actually need to find minimal $R$).

$\endgroup$
1
$\begingroup$

Yes, it is $NP$-complete even if $d=4$.

Note that unless $P=NP$, we cannot prove $NP$-completeness for $d=2$ because it is merely the problem of counting the number of connected components of a given graph.

Reduce from Exact-Cover-by-$3$-sets (X3C).

Given an instance of X3C, we construct an instance of our problem as follows.

The set of elements is $E=\{e_1,e_2,\dots,e_n\}$.
The set of $3$-sets is $C=\{s_1,s_2,\dots,s_m\}$.

This will be a YES instance (of X3C) iff there exists $C'\subseteq C$ with $|C'|=\frac n3$ that cover each element exactly once.

Now, set the set of variables $V=C\cup E\cup C^{up}$ where $C^{up}=\{s_j^{up}|s_j\in C\}$, that means each element is a varialbe and each $3$-set is also a variable. And for each set $s_j$, we add a new variable $s_j^{up}$.

Note that, X3C remains $NP$-complete even when each element belongs to at most $2$ sets and each pair of $3$-sets shares at most one element.

So, here come the equations.

For each $3$-set $s_j\in C$ where $s_j=\{e_a,e_b,e_c\}$, add the following equations:

  • $\{s_j,e_a,e_b,e_c\}$
  • $\{s_j,s_j^{up}\}$
  • $\{s_j,s_j^{up},e_a\}, \{s_j,s_j^{up},e_b\}, \{s_j,s_j^{up},e_c\}$

Finally, set $k=\frac n3$.

We have done with our reduction. Now we have to prove its correctness.

Proof of correctness: (sketchy)

For one direction, if we have a solution $C'$ to our given X3C, it is obvious that $C'$ is also a solution to our instance.

For the other direction, note that it is w.l.o.g to assume that a (minimal) solution contains only variable in $C$. Because if it contains an element (in $E$), we can safely remove it from the solution and add one of the containing $3$-sets (that the element belongs to) to the current solution (if that set has not already been present in the current solution).

So, now a subcollection $C'\subseteq C$ is a solution to our problem. We show that it is also a solution to the original X3C instance.

For each $s_j\notin C'$, it must be the case that all $3$ contained elements of $s_j$ must be deducible. For otherwise, $s_k$ becomes unreachable.

For each element $e_i\in E$, it must be the case that one of the $2$ sets containing it must be included in $C'$.$\blacksquare$


Take @xskxzr's example: The given X3C instance is $E=\{e_1,\dots,e_9\}$, $C=\{s_1,\dots,s_5\}$ where $s_1=\{e_1,e_2,e_3\}$, $s_2=\{e_4,e_5,e_6\}$, $s_3=\{e_2,e_5,e_8\}$, $s_4=\{e_6,e_7,e_9\}$, $s_5=\{e_1,e_4,e_7\}$.

Our set of variables will be $V=C\cup C^{up}\cup E=\{s_1,\dots,s_5,s_1^{up},\cdots,s_5^{up},e_1,\dots,e_9\}$.

Our set of equations will be:

  • $\{s_1,s_1^{up}\},\dots,\{s_5,s_5^{up}\}$
  • $\{s_1,e_1,e_2,e_3\}$, $\{s_2,e_4,e_5,e_6\}$, $\{s_3,e_2,e_5,e_8\}$, $\{s_4,e_6,e_7,e_9\}$, $\{s_5,e_1,e_4,e_7\}$
  • $\{s_1,s_1^{up},e_1\},\{s_1,s_1^{up},e_2\},\{s_1,s_1^{up},e_3\}$
  • $\{s_2,s_2^{up},e_4\},\{s_2,s_2^{up},e_5\},\{s_2,s_2^{up},e_6\}$
  • $\{s_3,s_3^{up},e_2\},\{s_3,s_3^{up},e_5\},\{s_3,s_3^{up},e_8\}$
  • $\{s_4,s_4^{up},e_6\},\{s_4,s_4^{up},e_7\},\{s_4,s_4^{up},e_9\}$
  • $\{s_5,s_5^{up},e_1\},\{s_5,s_5^{up},e_4\},\{s_5,s_5^{up},e_7\}$

And $k=\frac n3=3$.

$\endgroup$
  • $\begingroup$ I find your construction a bit confusing :( Could you add some examples? $\endgroup$ – orlp Aug 25 '19 at 5:45
  • $\begingroup$ Isn't the normal X3C, or more simple, set cover sufficient? $\endgroup$ – xskxzr Aug 25 '19 at 10:44
  • $\begingroup$ I don't know how to make the above reduction any simpler. $\endgroup$ – Thinh D. Nguyen Aug 25 '19 at 11:09
  • $\begingroup$ @xskxzr I think using Thinh D. Nguyen's trick I've made a reduction to set cover. $\endgroup$ – orlp Aug 25 '19 at 16:23
1
$\begingroup$

Based on Thinh D. Nguyen's answer I think I have a simpler (to understand) reduction showing the problem is at least as hard as SET COVER.

The core of the construction is a one-way deduction relationship $a \to b$. Split $a$ into two variables, $a$ an $a'$ and add equations:

$$\{a, a'\}, \{a, a', b\}$$

Then given either $a$ or $a'$ we can deduce $b$, but not the other way around. Given $b$ we can not deduce either $a$ or $a'$ unless we already knew one of them, in which case we already knew both of them and thus we deduced no new information. This can be generalized, e.g. $a \wedge b \to c$:

$$\{a, a'\}, \{b, b'\}, \{a, a', b, b', c\}$$

Now in SET COVER we have a universe $U$ and some collection of sets $S$ all with elements from $U$. Can we find $k$ sets in $S$ such that their union is the universe?

Let the universe of elements be $U = \{e_1, e_2, \dots, e_n\}$ and our collection of sets $S = \{s_1, s_2, \dots, s_m\}$. For each element $e_i \in U$ add variables $e_i, e_i'$ and equation $\{e_i, e_i'\}$, and for each $s_i \in S$ add variables $s_i, s_i'$ and equation $\{s_i, s_i'\}$.

We want to add the one-way reduction from the sets to their elements. For all $e_j \in s_i$ add equation $\{s_i, s_i', e_j\}$.

Note that a minimal YES instance only ever has to pick out of the $s$ variables, as the $e$ variables are all implied by an $s$ variable and not the other way around. Thus we pick our $k$ sets from the $s$ variables.

To set up a one-to-one correspondence between SET COVER and the above we want to deduce everything if we manage to deduce the universe from our $k$ set choices. To do that we add equations

$$\{e_1, e_1', e_2, e_2', \dots, e_n, e_n', s_i\}$$

for all $s_i$. As we've seen before this equation is a one-way deduction from $e_1 \wedge \dots \wedge e_n \to s_i$, and thus does not provide any information if you hadn't already deduced the entire universe of elements from your initial $k$ set choices. However if you did manage to do that, now we we can deduce every single variable and our instance is YES iff the SET COVER instance is YES.

$\endgroup$
  • $\begingroup$ Why do we need $e_i'$? $\endgroup$ – xskxzr Aug 25 '19 at 16:29
  • $\begingroup$ @xskxzr I'm not convinced they are necessary, but they can't hurt and allows us to cleanly separate the construction in two parts without having to worry about spurious solutions being introduced by reverse deductions in the direction we don't want them. The first part picks the $k$ sets (and possibly deduces the universe) and the second part deduces everything if and only if we already deduced the universe from those $k$ picks. $\endgroup$ – orlp Aug 25 '19 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.