I'm wondering if someone can provide a good algorithm for the following problem.

If we take 3-SAT in conjunctive normal form, we can partition some or all of the variables (not the literals) into sets. I'm interested in finding a collection of sets such that at least two of the variables in every 3-SAT clause are in the same set. We can call this a 2-partitioning.

In order to really solve the problem I'm working on, I need to assign weights to the sets. If there are $\alpha$ variables in a set, we assign the weight $2^\alpha$ to the set. We can then total all of the weights of the sets. For example, if we can find three sets that have sizes $\alpha_1, \alpha_2, \alpha_3$, then the total weight is $2^{\alpha_1} + 2^{\alpha_2} + 2^{\alpha_3}$. I'm looking for an algorithm that finds a 2-partitioning in time/space less than the total weight. So, how fast can we make this algorithm?


If we have the formula:

$$(\underbrace{x_1 \lor \neg x_2}_\text{set 1} \lor x_3) \land (\underbrace{\neg x_4 \lor x_5}_\text{set 2} \lor x_6) \land (\underbrace{\neg x_1 \lor \neg x_6}_\text{set 1} \lor \neg x_7)$$

We can create sets $\{x_1, x_2, x_6\}$ and $\{x_4, x_5\}$ so that at least two of the variables in each clause are part of the same set, as shown above. The total weight is therefor $2^3 + 2^2 = 12$.

  • $\begingroup$ This is really a problem on 3-uniform hypergraphs. What you want is a colouring of the vertices so that no edge contains three colours: a "non-rainbow" colouring. The best I could do with a quick search is a statement of the question of whether or not you can find three nonempty subsets. lix.polytechnique.fr/~bodirsky/no-rainbow.html $\endgroup$ Commented Apr 8, 2015 at 21:32


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.