Is finding a minimal set of seed variables for a complete deduction of a system of equations NP-complete? 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$).
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$.