4
$\begingroup$

Consider the set $S = \{1, \dots, n\}$ and $n$ subsets $S_i \subseteq S$ of size $d$ each (think of $S_i$ as neighborhoods of vertex $i$ in some $d$-regular graph, although the graph structure is not important here). Each vertex can have label $0$ or $1$. Each set $S_i$ comes with 2 constraints: there can be at most $k_i$ zeroes in $S_i$ and at most $l_i$ ones in $S_i$ (assume that $k_i + l_i \geq d$, otherwise constraints are clearly inconsistent). The problem - is it possible to check in time $\mathrm{poly}(n)$ (with fixed $d$) whether this constraint problem is satisfiable by at least one labelling of vertices?

It smells like something NP-hard, but I don't see an obvious reduction e.g. from $d-SAT$ since it's not clear you can implement negation by only this type of constraints.

$\endgroup$
9
$\begingroup$

1 in 3 Sat reduces to this problem. http://en.wikipedia.org/wiki/One-in-three_3SAT

Set d=3, each k_i = 2 and each l_i=1

To implement negation add $x,\overline{x},a$ and $x,\overline{x},b$ and $a,b,c$. The only possible assignment is a=0,b=0 and c=1, so $x$ and $\overline{x}$ must be different.

$\endgroup$

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.