graph isomorphism

Graph isomorphism is a weird sort of central problem in CS theory. An efficient algorithm would be quite nice. It would also be an achievement of some note – quite a few people have been stymied by this problem over the years. It also has the interesting property that if graph isomorphism is NP-complete, then the polynomial heirarchy collapses to level Π₂, which most people don’t think is likely. There are also some surprising things that happen if GI is in P, but I can’t think of them offhand. So, on to the show…

Okay, first, make sure the # of nodes and edges is the same. Second, make sure the spectra are the same

Now we need to disambiguate graphs that have the same spectra. … I got nothing.

Is there perhaps some kind of transform that would transform different graphs with the same spectra into larger graphs that have different spectra? the only way I can see of doing this is by rewriting constant sized subgraphs into larger constant sized subgraphs. My intuition says that the things that make graph isomorphism hard is the non-locality of features. So my intuition further says that graph ismorphism should be FPT where the parameter is the chordality or treewidth or whatever of the graph.

What we really need are two distinct algorithms – one for a parameter, and one for its “inverse”, so that as soon as the algorithm started getting really inefficient, we could switch to the other.

This would also be a trivial problem if there were some sort of graph theoretic analog to the classification of finite simple groups, where we could provide a finite number of graph families whose union is the set of all graphs. Then, all we would have to do is to write a disambiguation algorithm for each family.

Alternatively, any graph can be transformed into a bipartite graph such that if the bipartite analogs of two graphs are the same, then the graphs are isomorphics. Thus, the graph isomorphism problem is really just bipartite graph isomorphism.

How can we rank the vertices of a bipartite graph so that they are in a canonical order on each side? Finding a canonical representation is possibly a harder problem than graph isomorphism, but it seems like if we could do it, then we would be very happy. And canonical representations of these graphs initially seems like it should be easy…

Grrr. This is one to keep thinking on and coming back to.

Published 27 October 2006

Filed in

spicedABLISSham

A related question I have often wondered about, but never had the motivation to really look into:
A. Given two weighted complete graphs, determine whether they are isomorphic.
Since we can just assign 1/0 weights, this is a superproblem of GI, though I suspect it may not be any harder. But what if we restrict it, as
B. Assume every weight is the square root of an integer, and the triangle inequality holds.
Does the problem get any easier then? Surely it must get easier if we consider the real problem that made me think of these problems in the first place, which is
C. Given two n-dimensional simplices with integer coordinates, determine if they are congruent.
Or more specifically,
D. Given two n-dimensional simplices with vertices taken from the unit n-cube, determine if they are congruent.
Which is really just a necessary condition for the real problem I want solved,
E. Given two simplices as in F, determine whether any of the (2^n * n!) automorphisms of the n-cube map one simplex onto the other.
If anyone has insight into solving any of these problems in less than n! time, I'd love to hear about it.
coldtortuga

How about...
1) modular decomposition -- which produces a tree-structure in poly-time
2) tree-isomorphism testing -- which I think should be poly-time?
The tricksie bit might be general graph isomorphism between pairs of prime modules. But prime modules may be sufficiently "weird" -- weird enough so that simpler tests, e.g. spectral analysis, can determine graph isomorphism in poly-time.
Of course, I am just talking out of my a** :-) But I've always wanted to do SOMETHING with modular decompositions: it's the "nicest" poly-time graph algorithm which nobody seems to implement or use.

blog comments powered by Disqus

data structures »
« wiki

Impromptus

graph isomorphism

About Peter

Photostream

Bookmarks feed

Twitter

Meta