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.

Improve this question
$\endgroup$
2
  • $\begingroup$ This problem actually looks very hard. $\endgroup$ Commented Mar 29, 2021 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$ Commented Mar 29, 2021 at 9:52

1 Answer 1

Reset to default
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.

Improve this answer
$\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$ Commented Mar 29, 2021 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$ Commented Mar 29, 2021 at 7:51

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.