Shared Elements Algorithm

Question

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.

Answer 1

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.