# Algorithm for assigning items to one of two sets (2-CNF?)

I have a set of items (A, B, C, D, ...) which I want to assign to one of two sets (set1, set2). Trying all possible assignments and selecting my favorite has complexity $$O(2^n)$$, so I am trying to prune the number of assignments evaluated. I want to do this based on available knowledge that certain pairs MUST be present in the same set.

For instance: given A, B, C, D, and knowing that the following pairs must be together: A & B, B & C a solution would be set1 = {A,B,C}, set2 = {D}. Knowing that A, B, C must be together drastically reduces the number of assignments which have to be evaluated.

Note that there are pairs of items that may not occur in the same set. These relations however, are less obvious, which is why I restricted myself to finding the pairs listed above.

This already kind of looks like a satisfiability problem, which is good, as 2-CNF can be solved in linear time. In satifiablity, setting the variables to true / false could mean assigning the items to set1 / set2 respectively. However, expressing items must be in the same set looks like this: (A /\ B) V (!A /\ !B), which is 2-DNF.

2-DNF can be converted to 2-CNF in polynomial time, but would it be possbile to translate my problem directly to 2-CNF? This would allow me to keep the linear time complexity.

EDIT: As explained in the comments, 2-CNF would be satisfied by placing all items in the same set, which would defeat the purpose as this may not result in a "favorite" assignment. A better solution is the answer by @D.W., where for each connected component (which represents a cluster of items that must appear together), we can choose in which set to place it. This reduces the number of assignments that have to be evaluated, and allows us to find our "favorite" assignment.

• You can write "A and B must be in the same part" as $(A \lor !B) \land (!A \lor B)$
– user114966
Commented Oct 26, 2020 at 13:23
• @Dmitry thank you that is correct! Commented Oct 26, 2020 at 13:34
• Why don't you put all items in one of the sets? This will satisfy all constraints. More generally, all solutions are given by all 2-colorings of the connected components of your constraint graph. Commented Oct 26, 2020 at 14:09
• @YuvalFilmus this is only part of a larger problem. There are also items that may NOT be placed in the same set. I am in the process of working out how these pairs can be identified and then be added in this method. If these pairs cannot be properly identified, all items could indeed be placed in one set, and the information that gives may not be worthwhile. Commented Oct 26, 2020 at 14:48
• Please list all requirements. Don't just add clarifications in the comments - we prefer that you edit the question so that people have all the information needed to answer in a useful way in the question itself.
– D.W.
Commented Oct 26, 2020 at 16:14