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 &amp; B, B &amp; 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 &quot;favorite&quot; 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 &quot;favorite&quot; assignment.
There's a simpler approach, without using 2CNF.  Instead, build an undirected graph with edges between pairs of items that must be together, then find connected components (e.g., using DFS).  Now you can freely choose, for each component, which set it is associated with, and add all of its elements to that set; the result will be valid regardless of how you make those free choices.