# Graph isomorphism with equivalence relation on the vertex set

A colored graph can be described as tuple $(G,c)$ where $G$ is a graph and $c : V(G) \rightarrow \mathbb{N}$ is the coloring. Two colored graphs $(G,c)$ and $(H,d)$ are said to be isomorphic if there exists an isomorphism $\pi : V(G) \rightarrow V(H)$ such that the coloring is obeyed, i.e. $c(v) = d(\pi(v))$ for all $v \in V(G)$.

This notion captures the isomorphism of colored graphs in a very strict sense. Consider the case where you have two political maps of the same region but they use different color sets. If one asks if they are colored in the same fashion one would assume this to mean whether there exists a bijective mapping between the two color sets such that the colors of both maps coincide via this mapping. This notion can be formalized by describing colored graphs as tuple $(G,\sim)$ where $\sim$ is an equivalence relation on the vertex set of $G$. We can then say two such graphs $(G,\sim_1)$ and $(H,\sim_2)$ are isomorphic if there exists an isomorphism $\pi : V(G) \rightarrow V(H)$ such that for all pairs $v_1,v_2 \in V(G)$ it holds that $$v_1 \sim_1 v_2 \text{ iff } \pi(v_1) \sim_2 \pi(v_2)$$

My question is whether this concept has been studied previously w.r.t. finding canonical forms etc. and if so under what name it is known?

• Please don't use the notation "$=$" for anything other than the equality relation! – David Richerby Sep 17 '14 at 8:30

The problem you describe has definitely been considered (I remember discussing it in grad school, and at the time already it had been discussed long before then), though I can't point to any particular references in the literature. Possibly because it is linearly equivalent to uncolored graph isomorphism, as follows (this is true even for canonical forms). Call the problem you describe EQ-GI.

GI is just the special case of EQ-GI where each graph has just one equivalence class consisting of all vertices.

In the other direction, to reduce EQ-GI to GI, let $(G, \sim_G)$ be a graph with equivalence relation with $n$ vertices, $m$ edges, and $c$ equivalence classes. Construct a graph $G'$ whose vertex set consists of the vertices of $G$, together with new vertices $v_1, \dotsc, v_c$, one for each equivalence class in $=_G$, as well as $n+c+1$ new vertices $w_0, \dotsc, w_{n+c}$. Connect the $w_i$'s in a path $w_0 - w_1 - w_2 - \dotsb - w_{n+c}$, connect each $v_i$ to $w_0$, and for every vertex in $G$, connect it to the corresponding equivalence class vertex $v_i$. Then $G'$ has at most $n + 2c + n +1 \leq O(n)$ vertices and can be constructed in essentially the same time bound. (It also has at most $m + n + c + (n+c+1) \leq m + 4n + 1 \leq O(m+n)$ edges - which is $O(m)$ for connected graphs - but that's somewhat less relevant since most GI algorithms have running times that essentially only depend on $n$.)

Update: Since there was some confusion in the comments, I'm adding here a sketch of the correctness of the above argument. Given $(G_1, \sim_1)$ and $(G_2, \sim_2)$, let $G_1'$ and $G_2'$ be the graphs constructed as above; let $v_{i,1}$ denote the vertex $v_i$ from above in $G_1'$, and $v_{i,2}$ the one in $G_2'$, and similarly for $w_{i,1}$ and $w_{i,2}$. If there is an isomorphism $G_1' \cong G_2'$, it must send $w_{i,1}$ to $w_{i,2}$ for all $i$, since in each graph $w_{n+c}$ is the unique vertex that is the endpoint of any path of length at least $n+c+1$. In particular, $w_{0,1}$ maps to $w_{0,2}$. Since the neighbors of $w_0$ that aren't $w_1$ are exactly the $v_i$, the isomorphism must map the set $\{v_{1,1},\dotsc,v_{c,1}\}$ to the set $\{v_{1,2},\dotsc,v_{c,2}\}$ (and in particular both $\sim_1$ and $\sim_2$ must have the same number, $c$, of equivalence classes). Note that the isomorphism need not send $v_{i,1}$ to $v_{i,2}$ for all $i$, but is allowed to permute the indices of the $v$'s so long as the corresponding equivalence classes can be mapped to one another. Conversely, based on this description of how isomorphisms between $G_1'$ and $G_2'$ can look, it is easy to see that if $(G_1, \sim_1) \cong (G_2, \sim_2)$ then this gives an isomorphism $G_1' \cong G_2'$.

• As far as I understand there is a fundamental problem with your reduction. You basically enforce a unique invariant property on the set of vertices of every equivalence class. In this case you chose the eccentricity of a vertex as invariant property. For a graph $G$ let $f$ be a coloring. Let us say $=_f$ is the equivalence relation induced by $f$, i.e. $u =_f v$ iff $f(u) = f(v)$. – John D. Sep 17 '14 at 6:24
• Now, consider reducing EQ-GI to colored GI. By your argument for an input $(G,=_1),(H,=_2)$ it should suffice to pass $G,H$ and choose colorings $c_1,c_2$ which induce $=_1,=_2$. The problem here is that $(G,c) \cong (H,d)$ implies $(G,=_c) \cong (H,=_d)$ but the other direction is not necessarily true because we don't know the correspondence between the two sets of equivalence classes a priori. – John D. Sep 17 '14 at 6:24
• Stated differently, I fail to see how it would be possible for a mere graph transformation to reduce EQ-GI to colored GI at all because of the more complex constraints. It is clear however that your construction would work to reduce colored GI to GI. – John D. Sep 17 '14 at 6:25
• @user17410 EQ-GI is coloured GI. "Call the problem you describe EQ-GI." It's certainly possible for a graph transformation to reduce EQ-GI to GI: in fact this can be done for any isomorphism problem on relational structures to GI. Joshua's reduction looks correct to me; I had thought of a slightly simpler one that adds rather more vertices. – David Richerby Sep 17 '14 at 7:42
• Your correctness argument has convinced me. I jumped to conclusions to fast before taking the time to analyze your reduction, I apologize. – John D. Sep 18 '14 at 19:14

I read your last comment in the Joshua's correct answer; if you need to transform EQ-GI to colored GI (i.e. you are in trouble with the colors assigned to the equivalence classes) you can use the following reduction:

Suppose that the starting graphs are $G_1 = (V_1, E_1)$, $G_2 = (V_2, E_2)$ and there are $q$ equivalence classes; then you can add to each graph a "permutator", i.e. a complete graph on $|V_1|+1=|V_2|+1$ nodes ($K'_{|V_1|+1}$,$K''_{|V_2|+1}$) and use $q+1$ colors $c_1,...,c_q,c_{q+1}$.

In both $K'$ and $K''$, $q$ nodes are distinguished and colored with $c_1,...,c_q$ the remaining nodes are colored with $c_{q+1}$. The nodes of $G_1$ are colored with color $c_{q+1}$ and nodes in the same equivalence class are linked to the corresponding color in $K'$; the nodes of $G_2$ are colored with color $q+1$ and nodes in the same equivalence class are linked to the corresponding color in $K''$.

Also note that you can drop the colors and get an equivalent GI instance :-)

The reduction coresponding to the example in your comment

• This looks promising. I will check the correctness later on. – John D. Sep 17 '14 at 18:17
• @user17410: ok, let me know if you need more clarifications – Marzio De Biasi Sep 18 '14 at 9:38