Given N finite subsets of the finite universe set E, it is necessary to find the intersection which contains maxumum number of subsets. Let call this problem MSI (Maximum Subset Intersetion).
Firstly I had thought that it is variation of well-known Maximum Clique Problem where vertices are subsets and edges are relations of intersection, so the classic Bron-Kerbosch algorithm or Tomita et al. algorithm can be easily used. But the k-size clique is certainly not the same that the mutual intesection of k subsets (cause subset A can intersect B, B can intersect C, A can intersect C, but at the same time A, B and C may not have common points of intersection).
Actually the multiple intersections form edges in hypergraph, so the main task is to find edge of maximal cardinality.
I found an article by Eduardo C. Xavier A Note on a Maximum k-Subset Intersection Problem where he proves that the MSI-problem is a variation of Maximum Edge Biclique (MEB) problem which is in turn NP-hard.
My naive solution is to implement branch and bound greedy algorithm (in other words, to adopt Bron-Kerbosch algorithm to this domain).
May be there are already any implementations or acadimic paper on that problem?
Actually the exact problem I met in my work is the following:
Suppose that I can run some function which returns the cardinality of one subset or N subsets intersection. The function is time-consuming. I am interested in finding optimal or approximately optimal argorithm to find the intersection of maximum number of subsets (next thing is to find the whole set of such intersections in cardinality decreasing order). Working on element-level is even more costly from the time consumption point of view.
I thought firstly to take cardinalities of all subsets (N operations) and then run Bron-Kerbosh kind of search for subsets sorted by cardinality decreasing order. So I will start with the largest subset, check if it intersects with the 2nd largest subset and so on.