0
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ You can write "A and B must be in the same part" as $(A \lor !B) \land (!A \lor B)$ $\endgroup$
    – user114966
    Oct 26 '20 at 13:23
  • $\begingroup$ @Dmitry thank you that is correct! $\endgroup$
    – DBrons
    Oct 26 '20 at 13:34
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 26 '20 at 14:09
  • $\begingroup$ @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. $\endgroup$
    – DBrons
    Oct 26 '20 at 14:48
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Oct 26 '20 at 16:14
0
$\begingroup$

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.

$\endgroup$

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.