# Shared Elements Algorithm

I have a problem that I am working on an algorithm for:
I have $$k$$ sets of distinct positive integers (each set is distinct, not necessarily across sets)
$$S=\{A_1,A_2,A_3,...,A_k\}$$ where $$\forall A_i\in S,\ A_i=\{a_{i1},a_{i2},a_{i3},...,a_{in_i}\},\ a_{ik}\in \mathbb{Z}^+, a_{ip}=a_{iq}\iff\ p=q$$
(so $$n_i$$ would be the amount of numbers in each set)

The algorithm should find 5 sets in $$S$$ I will call $$B_1,B_2,B_3,B_4,B_5$$ where the following pairs of sets share an element:
$$B_1,B_2$$
$$B_1,B_3$$
$$B_1,B_4$$
$$B_1,B_5$$
$$B_2,B_3$$
$$B_3,B_4$$
$$B_4,B_5$$
$$B_5,B_2$$
where the element each of these pairs share is distinct

So if $$A_2=\{4,5,7,37\},\ A_5=\{8,11,37\},\ A_7=\{4,11,21\},\ A_{12}=\{7,21,131\},\ A_{19}=\{5,8,131\}$$
Then those 5 sets would be a potential output of the algorithm. The way I would do it currently would seem very inefficient which would be to iterate through the sets of $$S$$. I would take $$A_1$$ and find all the sets in S that share an element with it. I would take one of those sets, $$A_m$$, find the sets that share an element with it that isn't that element that $$A_1$$ and $$A_m$$ shared. And continue that until I found 5 sets that worked.

There must be a more efficient solution but I am unaware of this type of problem and googling didn't help much. So if anyone knows a good way to do this or can point me in the right direction with analogous problems or topics I should learn about that would be very appreciated.

• This problem actually looks very hard.
– orlp
Mar 29, 2021 at 0:31
• This problem has different aspects depending on where in the problem space you are. In other words, there are several numbers here that can be big independently of each other: k, n_i, max a_{in_i}. I suspect the best algorithm depends on which parameter(s) is large. Mar 29, 2021 at 9:52

Construct an undirected graph with $$k$$ vertices, where each vertex represents a set $$A_i$$, and you draw an edge between two vertices if their sets share an element. Now you have an instance of subgraph isomorphism: you have a graph $$H$$ on five vertices (of the shape shown in your question), and you want to enumerate all subgraphs of $$G$$ that are isomorphic to $$G$$. You do have an additional distinctness condition, but if you can enumerate all isomorphic subgraphs, you can check whether they satisfy that additional condition in post-processing (and in most cases I expect they typically will).
This subgraph isomorphism problem looks challenging. A naive approach has $$O(k^5)$$ running time: enumerate all 5-tuples of vertices. You can improve this slightly, to $$O(k^2m^{1.5})$$ time, where $$m$$ counts the number of edges in the graph (note that $$m\le k^2$$, and might be much smaller, so this might be better). First, enumerate all 3-cliques (triangles). This can be done in $$O(m^{1.5})$$ time (see http://complexnetworks.fr/wp-content/uploads/2011/01/triangles.pdf and https://users.soe.ucsc.edu/~sesh/pubs/conf-triangle-enum.pdf). These will be your candidates for $$A_1,A_2,A_3$$. Next, enumerate all possible candidates for $$A_4,A_5$$ and check to see if they meet the requirements. This might not be much faster, but maybe it would help a little bit.
• It's not quite subgraph isomorphism because, e.g., the only element shared by two sets $A_i$ and $A_j$ may be the only element $A_i$ shares with $A_k$, so we cannot choose all 3 sets simultaneously to be $B_1, B_2, B_3$. Still a useful approach since SI is a relaxation, so all solutions to it can be checked for the distinctness property. Mar 29, 2021 at 3:55