Linear algebra formulation for colored node graph isomorphism

Question

(Please see a few paragraphs below by what I mean by “colored node graph isomorphism”.)

Some basic definitions for completeness:

Given two graphs $G_1=(V_1, E_1)$ and $G_2=(V_2, E_2)$ the graph isomorphism problem (GI) asks whether there exists a one-to-one mapping $\sigma: V_1 \rightarrow V_2$ such that $(a, b) \in E_1 \Rightarrow (\sigma(a), \sigma(b)) \in E_2$ for $a,b \in V_1$.

This can equivalently be stated using linear algebra as follows: Given two graphs $G_1$ with adjacency matrix $A$ and $G_2$ with adjacency matrix $B$, is there a permutation matrix $P$ that satisfies the following: $$ P A P^T = B $$

Now consider a generalized version of GI where each node can have a color (given by $color(a))$ and multiple nodes can share the same color i.e. number of colors $k$ can be less than the total number of vertices $n$. We can think of $color$ as a mapping $V \rightarrow \{1,...,k\}$ where $k \leq n$. Each graph can have its own color mapping so lets denote the colors for $G_i$ by $color_i$. In this setting, besides the required edge mapping by GI (as specified in the first paragraph above), we have the following additional restriction on $\sigma$:

$$ color_1(a) = color_1(b) \Rightarrow color_2(\sigma(a)) = color_2(\sigma(b)) $$

Notice that nodes can be mapped to a color different than their original one, but the restriction is that same color nodes should always be mapped to the same target color.

Clearly this problem is at least as hard as GI, because GI is the special case where each node has its own unique color in both graphs.

My question is, can this problem also be formulated using permutation matrices (and/or some other linear algebra tools) similar to GI above?

I’m probably missing some very simple formulation right now.

Thanks in advance!

Answer 1

It is equivalent (up to polynomials). Given a coloured graph $G_1$, add a new node (a colour vertex) for each colour and add edges from it to all vertices with that colour. Next add one more new node (the supernode) that is adjacent to all the colour vertices. Finally, attach to the supernode a clique that is so big that the supernode can't possibly be confused with any other node. Remove all colours from the result and call it $C(G_1)$. Then uncoloured graphs $C(G_1), C(G_2)$ are isomorphic iff the coloured graphs $G_1,G_2$ are colour-isomorphic in your sense.

I'm not sure what counts as a linear algebra formulation, so I haven't really answered the question. You need to represent the colours somehow. If colours have to be preserved you can use the diagonal, but since you allow permutation of colours I don't see how to avoid making the matrix larger (as in my construction) or adding a second matrix to represent the colours somehow.

If you are allowed to go to some other ring, you can use a matrix of the same size. Choose an extension of the rationals by the roots of a polynomial with symmetric Galois group. Use the roots on the diagonal to represent the colours. Then widen the rules for $P$ to allow permuting the roots as well as permuting the rows and columns. I didn't work out the details...

There is an interesting variant. Designate one colour as "wild", and define the comparison of two colours as "equal" if they are the same colour or at least one of them is wild. Now the problem is NP-complete (reduction from CLIQUE).