6
$\begingroup$

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.
visualization of output

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.

$\endgroup$
2
  • $\begingroup$ This problem actually looks very hard. $\endgroup$
    – orlp
    Mar 29 at 0:31
  • $\begingroup$ 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. $\endgroup$ Mar 29 at 9:52
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Mar 29 at 3:55
  • $\begingroup$ @j_random_hacker, yes, not quite, but I imagine that in practice it will be quite close. If you can enumerate all isomorphic subgraphs, then you can check which ones satisfy that additional condition (and I expect most will, typically). $\endgroup$
    – D.W.
    Mar 29 at 7:51

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.