1
$\begingroup$

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?

EDIT:

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.

$\endgroup$
  • $\begingroup$ In the "A Note on a Maximum k-Subset Intersection Problem" it is a slightly different problem which is to find $k$ subsets with maximum intersection. You certainly mean this problem otherwise your problem would be easy. $\endgroup$ – Parham Nov 21 '13 at 16:41
  • $\begingroup$ @MahmoudA. You are right, but actually both kind of problems are interesting for me? So what is the solution for mine problem (maximum intersecting subsets)? $\endgroup$ – zavg Nov 21 '13 at 16:56
  • 1
    $\begingroup$ Just find the most frequent element in $E$, i.e. the one that occurs the most in those sets. In the NP-hard problem we want the maximum cardinality subset of $E$ with frequency at least/exactly $k$. This makes the problem much harder. $\endgroup$ – Parham Nov 21 '13 at 17:05
  • $\begingroup$ @MahmoudA. But to find the most frequent element I need to check for EVERY element if it belongs to EVERY set, isn't it? $\endgroup$ – zavg Nov 21 '13 at 17:07
  • $\begingroup$ yes, but what's the problem in checking every element as long as it takes polynomial time? The number of elements is bounded by the size of problem, isn't it? $\endgroup$ – Parham Nov 21 '13 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.