I'm trying to write an algorithm that detects the most common subset of at least size $k$, from a collection of sets. If there are ties for the most common subset, I want the one of them whose size is as large as possible.
For example if I have:
s1 = {A, B, C }
s2 = {A, B, C, D}
s3 = { B, C, D}
Then the most common subset of size $\ge k=2$ is {B, C}. As another example, if I have:
s1 = {A, B, C D}
s2 = {A, B, C, D}
s3 = { B, C, D}
Then the most common subset of size $\ge k=2$ is {B, C, D}. It's important that in this instance the algorithm would give me {B, C, D} and not {B, C}, {B, D} etc. Note that I'm not interested in the longest common subset (a different problem), I'm interested in the longest most common subset if you will. I also don't care about enumerating all the different subsets, I just want to find the most common.
Is there an efficient algorithm for this problem?
I have an algorithm for this problem, but I don't think it's very efficient. For $k=2$ I enumerate all subsets of size 2 and count how many times each one appears in the collection. If the most-frequently occurring pair is more frequently occurring than any other pair then that must be the most common subset. If there is more than one with the same (maximum) frequency then I look at the sets they are contained in. If these overlap exactly then I take the union of the pairs and that gives me the most common subset (with size > 2).
I think this could be related to the maximum clique problem but I'm not certain.
Note that just taking the intersection does not give the correct answer. For instance, if I have
s1 = {A, B }
s2 = { C, D}
s3 = {A, C, D}
then the intersection is the empty set, but the most common subset is {C, D}.
