Linear time complexity algorithm for building the intersection graph

Question

We would appreciate help in determining a linear time complexity algorithm for building the intersection graph of a set of subsets of a finite set of elements U.

For example, let U = {a,b,c,d,e,f,g,h}. Consider the set S = { {{a,b}, {c,d}, {a,e,h}, {e,f,g} } of U. We need to build the intersection graph G of S in linear time, if possible. Each element in S is a node of G. Two nodes N1 and N2 in G have a edge between them if and only if N1 and N2 have at least one element in common.

For example, the intersection graph G of S above would have four nodes, namely, {a,b}, {c,d}, {a,e,h}, and {e,f,g}. G would have 2 edges of G, i.e. {a,b}-{a,e,h} and {a,e,h}-{e,f,g}.

Is there a linear algorithm for building the intersection graph from a set of subsets of a finite set of elements?

Do you mean linear in the size of the input or linear in the size of the output? In general, linear in the size of the input isn't possible, since the output graph could have size quadratic in the size of the input. — templatetypedef
– templatetypedef, Commented Aug 23, 2016 at 1:07
Can you show any work on this algorithm? Perhaps one that is correct but too slow? As it is, you are not so much asking for help as asking for someone to do it for you. — Scott Hunter
– Scott Hunter, Commented Aug 23, 2016 at 1:10
@templatetypedef obviously, no algorithm can be faster than the size of the output. In general, by "linear" people mean "linear by the size of the input + size of the output". This makes sense as reading the input / writing the output are part of the algorithm (sometimes you don't actually have to read all the input though, but you always have to write the output) — rabensky
– rabensky, Commented Aug 23, 2016 at 3:49

rabensky · Accepted Answer · 2016-08-23 03:41:49Z

2

I can do it in O(E * M), where E is the number of edges in the resulting graph, and M is the average number of common elements between nodes that have a common element.

Sure. First, I will give an arbitrary order for the elements of S, and name the elements of S by their index in that order. I also give an arbitrary order to the elements of U and name each of the elements by it's index in that order.

That was all a fancy way of saying "I can now say I want the 4rd element in U and the 2nd element in S", and it's O(1) to do so.

I create the following data structure:

table: 1...|U| -> list of numbers in range 1...|S|

Now I go over all elements N in S, for such N I go over all u in N, then I look at the list of nodes in table[u], and add a graph edge between N and all the nodes in table[u]. Finally, add the current N to table[u]

Pseudo code:

for N1 in S:
  for u in N1:
    for N2 in table[u]:
      Create edge N1-N2
    add N1 to table[u]

answered Aug 23, 2016 at 3:41

rabensky

2,93415 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

jhonatanoliveira Over a year ago

Hi @rabensky, I like you solution, thank you. I am curious though, given your pseudo code, how M, average number of common elements, plays a role in the complexity O(E * M). Can you, please, elaborate a bit more on this?

user3386109 Over a year ago

@jhonatanoliveira For each edge, this algorithm will attempt to create the edge M times on average. For example, if N1={a,b,c} and N2={a,b,d}, then this algorithm will create edge N1-N2 twice. So (depending on how the edges are stored) the implementation may have to check if the edge already exists before creating it. If the edges are stored in an adjacency matrix, then no check is necessary (the new edge overwrites the old edge). But if the edges are stored in adjacency lists, then checking for duplicates is necessary, and the time complexity increases accordingly.

rabensky Over a year ago

@user3386109 in any reasonable implementation of a graph, checking if an edge N1-N2 exists is O(1). So the time complexity isn't increased because of the need to check. It's increased, like you said, because each edge is added M times on average.

Collectives™ on Stack Overflow

Linear time complexity algorithm for building the intersection graph

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related