# Comparing two graphs [closed]

I want to compare the vertices of two graphs. Given two graphs, $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$, I want to compare $u_n$ and $v_m$ for $u \in V_1$ and $v \in V_2$. I came up with double loops for doing this:

for all u in G1
for all v in G2
if u.label == v.label then
do something here
end if
end for
end for


Now the above two loops have the time complexity of $O(n) = n^2$. Is there a better way of doing this , i.e. a more efficient algorithm, assuming that no other information is available?

I looked at the raph isomorphism problem (https://en.wikipedia.org/wiki/Graph_isomorphism_problem). But here I am not trying to find out if the two graphs are isomorphic.

Is there a better/more efficient approach for doing this?

• Well, you are just comparing two sets. The fact that the elements of those sets are also vertices in some graphs doesn't play a role. As for this operation, you'd be better off if you first sorted both sets and then compared them, it would give you $O(n \log n)$ since sorting would dominate the comparison. Provided you don't care about repetitions. – wvxvw Oct 5 '15 at 15:45
• What do you know about the distribution of labels? What is the do something? The answer will depend on these two. For instance, if each label is a single bit and do something is print u,v, then there's no asymptotically faster solution, as you need to print $\Theta(n^2)$ lines of output no matter what. Have you considered using a hash table to hash vertices by label, or sorting vertices by label? – D.W. Oct 5 '15 at 15:45
• @wvxvw - thanks for giving me a perspective on this – Jake Clawson Oct 25 '15 at 0:34
• @D.W. - thanks for elaborating on this. It helped me to think clearly on this question. – Jake Clawson Oct 25 '15 at 0:34

A more efficient approach would be to group the vertices according to their labels, and only run the double loop for vertices in the same group. In the worst case (if all vertices have the same label) this is still $\Omega(n^2)$, but if there are relatively few vertices sharing the same label this is much more efficient.