Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 7 down vote accepted

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.

share|improve this answer
    
Thanks for quick answer! –  Marcin Kotowski Nov 10 '12 at 1:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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