4
$\begingroup$

I am trying to find a polynomial time reduction from the colored graph isomorphism to the regular graph isomorphism. Doing a search on this problem, I found this article and it seems like theorem 1 is the solution I am looking for, however I don't fully understand it. Could someone please explain how the reduction works?

$\endgroup$
1
3
$\begingroup$

"a polynomial time reduction from the colored graph isomorphism to the regular graph isomorphism" ....

the below proof is due to Pascal Schweitzer,

Theorem 1 (reduction of colored to uncolored graph isomorphism). The graph isomorphism problem for colored graphs polynomial-time reduces to the uncolored graph isomorphism problem.

Proof: Assume we are given two colored graphs $G_1, G_2$ on $n$ vertices. If the sets of colors used for the graphs are not equal, we reduce the problem to a No-instance of uncolored graph isomorphism, i.e., some fixed pair of non-isomorphic graphs.

If the graphs use the same color set, we attach to every vertex a rooted tree, whose isomorphism type is in one-to-one correspondence with the color of the vertex: We choose a canonical bijection of the color set to the set of rooted trees for which every leaf is at height $⌈log2(n)⌉$ and which has a maximum degree of $3$. Such a bijection is given by the following method: We number the colors with integers in $\{0, . . . , n − 1\}$. To a color with binary encoding $ a_0 a_1 . . . a_{⌈log2 n−1⌉}$ we assign the tree for which every vertex on height $i$ has exactly $a_i + 1$ children. We obtain two new graphs $G′_ 1$, $G′ _2$ of size at most $O(n^2)$. By induction on the height, it is easy to show that these new graphs are isomorphic if and only if the original graphs are.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.