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.

  • $\begingroup$ 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? $\endgroup$ – knowKnothing Dec 19 '13 at 14:29
  • $\begingroup$ Sorry, I was totally off base. But now it should be OK. $\endgroup$ – hbm Dec 19 '13 at 15:56
  • $\begingroup$ 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. $\endgroup$ – knowKnothing Dec 19 '13 at 18:06
  • $\begingroup$ You are right again. $\endgroup$ – hbm Dec 19 '13 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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