Constraint satisfaction problem on a graph

Question

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.

Answer 1

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.