How can I produce 'canonical' forms for rooted bipartite graphs? - MathOverflow

How can I produce 'canonical' forms for rooted bipartite graphs?

2010-03-02T04:49:43Z

The graphs I'm interested in are bipartite graphs with a specified root vertex. Because there's a root, all the vertices are 'graded' by their distance from the root. Because the graph is bipartite, vertices at depth $d$ are only ever connected to other vertices at depths $d \pm 1$ (and in particular not depth $d$).

When I represent these graphs, I order the vertices at each depth, and record the edges by a series of matrices, essentially the list of adjacency matrices from each depth to the next. (That is, the full adjacency matrix is symmetric and block tridiagonal, with zero diagonal blocks. I just write down the superdiagonal blocks.)

Now, if I reorder the vertices at some depth (this just permutes the rows of one matrix and the columns of the next), obviously I have the same underlying graph. I'd like an algorithm that picks a particular ordering at each depth, for each such graph, producing a 'canonical form', with the following properties:

the algorithm is idempotent; applying it a second time does nothing,
the algorithm is stable, in the sense that if you just look at the first $d$ depths of a graph, and see that that graph is already 'in canonical form', then when you produce a canonical form for the whole graph those first $d$ depths aren't changed, and
as many isomorphic graphs as possible are identified!

It may not be possible to satisfy 3. completely; for example the identity operation satisfies 1. and 2., but does a very bad job at 3. It's not essential for my application that every isomorphic pair of graphs are identified. (I'd be using this algorithm to speed up a combinatorial search of certain types of graphs, where I know that I'm unnecessarily producing many isomorphic copies of the same graph, but the details of the search require that I use this representation.)

Does anyone know of such an algorithm? Can anyone suggest something good?

Answer by Suresh Venkat for How can I produce 'canonical' forms for rooted bipartite graphs?

2010-03-02T05:32:59Z

I don't know of any definite answer to your question, but one idea would be to sort each level by increasing degree ? that gets you a little closer (though not that much) to isomorphism

Answer by domotorp for How can I produce 'canonical' forms for rooted bipartite graphs?

2010-03-02T09:26:49Z

I think that the best way to do is the following trivial algorithm. Whenever you want to order the vertices at depth d+1, look at the already ordered level d and associate with every vertex on level d+1 the string whose ith bit is 1 if it is connected to the ith vertex on level d and 0 if it is not. Then order the vertices on the d+1st level according to the lexicographic order of the strings, deciding equalities according to the original order of the vertices in the adjecency matrix (or any other way). I think it is clear that it is impossible to do any better if you insist on property 2, since in this algorithm we differentiate all the vertices that we can.

Answer by grshutt for How can I produce 'canonical' forms for rooted bipartite graphs?

2010-03-02T09:32:05Z

You may find Mugnier and Chein's paper "Characterization and algorithmic recognition of canonical conceptual graphs" (1993) useful.

See http://www.springerlink.com/content/77342v2587l40qtn/

Answer by Brendan McKay for How can I produce 'canonical' forms for rooted bipartite graphs?

2011-09-24T13:06:11Z

This problem is algorithmically equivalent to the general problem of finding a canonical labelling for a graph. To see that, take an arbitrary graph, add a new vertex adjacent to everything and call it the root, then subdivide every edge with a new vertex. The result is a rooted bipartite graph. Going back to the original is easy. Canonical labelling has unknown worst case complexity, though there are effective programs like nauty, bliss and Traces that can handle graphs with thousands of vertices.