Consider the following decision problem. Given $m$ subsets $A_{1}, \dots , A_{m} \subset \{1 , \dots , n \}$.
Does there exist a subset $S \subset \{ 1, \dots ,n \}$ such that the cardinality of the intersections $| S \cap A_{i}| = 1 $ for all $1 \leq i \leq m$?
Write a boolean formula for this problem and show that 2-Colorability can be cast as this problem.
Possible typo on the question: The problem states on the second line, "cardinality of intersections" I am not really sure what is meant. The words and notation are contradictory; however, the problem has been considered as a 'mini-Sudoku' problem. I recently played Sudoku and supposedly we are only allowed to have one symbol match per row and column. So, I guess the correct notation would be $\cap $.
I know that 2-colorability problem is reducible to a decision problem to determine if a graph is bi-partite. Supposedly, the boolean formula for 2-colorability is:
$\wedge_{(i,j) \in Edges} (x_{i} \oplus x_{j} ) = \wedge_{(i<j) \in Edges } ((x_{i} \vee x_{j} ) \wedge (\bar{x_{i}} \vee \bar{x_{j}}))$
How should I proceed?
For a subset $A_k$, if $i, j \in A_k$ then either $i \in S$ or $j \in S$, but not both which translate to the following formula $f_k$ = $\wedge_{i \lt j \in A_k} (x_{i} \oplus {x_{j}})$. Since this true for all $A_k$, putting those formulae together, you get $f_S = \wedge_{k=1}^{m}f_k$. So the problem is equivalent to $f_S$ being satisfiable. As you can see, that is very similar to the formula for 2-colorability.