# Algorithm to find largest intersection of sets

This is a cross-posting from here, on the mathematics Stack Exchange. I thought this might be a more appropriate venue.

The problem is this:

I have a list of sets $$S_1, S_2,... S_N$$ where each set contains $$m$$ elements, all drawn from some larger set $$A$$. The challenge is to find the largest set $$K\subseteq A$$ such that every subset $$k_i\in K$$ of size $$|k_i|=m$$, there exists a matching $$S_j == k_i$$. such that every set of size $$m$$ which can be made from the elements of $$K$$ matches one of the original sets $$S_i$$. To make this clearer, here are two examples

## Example 1

If we have a small alphabet $$A = (a, b, c, d)$$ with $$m=2$$ and sets \begin{aligned} S_1 &= (a, b)\\ S_2 &= (a, c)\\ S_3 &= (b, c)\\ S_4 &= (c, d) \end{aligned} then $$K = (a, b, c)$$. All combinations of $$K$$ which are size $$m=2$$ appear in our list of sets $$S_i$$ (specifically $$S_1, S_2, S_3$$ contain every combination, length 2, of the elements of $$K$$). On the other hand, $$d$$ only appears in $$S_4$$ with $$c$$. We cannot include it in $$K$$ because then there would be pairs of elements of $$K$$ which do not match any $$S$$, such as $$(a, d)$$.

## Example 2

If $$A$$ is a small alphabet $$A = (a, b, c, d, e, f)$$ and we have that $$m$$ = 3 and sets \begin{aligned} S_1 &= (a, b, c)\\ S_2 &= (b, c, d)\\ S_3 &= (c, d, e)\\ S_4 &= (a, c, f) \\ S_5 &= (b, d, f) \\ S_6 &= (b, c, e)\\ S_7 &= (c, e, f)\\ S_8 &= (b, c, f)\\ S_9 &=(c, d, f) \end{aligned} So, in this example, the largest set would be $$K = (b, c, d, f)$$, here every triple which we can form from $$K$$ has a corresponding set (these being $$S_2, S_5, S_8, S_9)$$.

I'm trying to find an algorithm which can solve this task with minimal scaling in both $$|A|$$ and $$m$$. The closest related problem is probably this, though mine is meaningfully different.

My current solution, which I'm sure is terrible, does this:

for i = m to |A|
outer_sets = make combinatoric sets of size i using A
for outer_set in outer_sets:
inner_set = make combinatoric sets of size i using outer_set
for inner_set in inner_sets:
check if there exists an S_i == inner_set
if all checks positive:
max = i
K = outer_set


As you can see, very inelegant and with terrible scaling.

Any help much appreciated!

• When $m=2$ this problem is equivalent to Maximum Clique ($A$ are the vertices, the $S_i$ are the edges), which is NP-complete -- so this problem is too, meaning it's extremely unlikely that any polynomial-time algorithm exists. BTW there are a few mistakes in your problem statement -- I suggest: "Given $A$, $S_1, \dots, S_n$ and an integer $m$, the challenge is to find the largest set $K \subseteq A$ such that every $m$-sized subset of $K$ appears as one of the $S_i$." Jul 21 at 9:34
• Ah, thank you - that is indeed much clearer Jul 21 at 11:52