Maximum Cardinality Intersection of Every Pair of Equal-Size Sets

Viewed 351

We have N sets, each having N integers.

We take every pair of sets, and find their intersection set, S.

Now, we are interested to find the cardinality of the intersection set S that has maximum cardinality.


Example

For example, let N be 4 and we have 4 sets each of 4 elements:

A= {1,2,5,6}, B= {2,5,7,6}, C= {3,4,2,6}, D= {1,4,7,8}

Now we take pairwise intersection of these sets and an intersection set having maximum cardinality= {2,5,6}

So, we return 3.


A brute force solution can be done with Θ(N3) time. Can we do it more efficiently with an other method ?

1 Answers
Related