<p>1 in 3 Sat reduces to this problem.
<a href="http://en.wikipedia.org/wiki/One-in-three_3SAT">http://en.wikipedia.org/wiki/One-in-three_3SAT</a></p>

<p>Set d=3, each k_i = 2 and each l_i=1</p>

<p>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.</p>

CC BY-SA 3.0
2012-11-10T01:25:37.550Z
2012-11-10T01:41:21.993Z
2012-11-10T01:41:21.993Z
Martin Vatshelle
<p>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?</p>

<p>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.</p>

<cc.complexity-theory><graph-theory><sat><csp>
Constraint satisfaction problem on a graph
Marcin Kotowski
# Constraint satisfaction problem on a graph

(Asked by: username_0 on 2012-11-10)

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.

**Tags:** cc.complexity-theory, graph-theory, sat, csp


---

## 1 answers

### Answer by username_1 on 2012-11-10. Score: 9 | Accepted answer

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.


---

