# 2-Colorable & Decision Problem

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.
• I don't understand why is that $S$ exists if and only if $G$is 2-colorable. Why does the intersection of $S$ and $A_{k}$ tell you this? – knowKnothing Dec 19 '13 at 14:29
• I don't know much, but I don't think you need the bar on top of $x_{j}$ on your $f_{k}$. Thank you for helping, though. – knowKnothing Dec 19 '13 at 18:06