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$ – Andrew D. King Apr 8 '15 at 21:32

Your Answer

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

Browse other questions tagged or ask your own question.