2
$\begingroup$

Background/Motivation

I'm working on algorithms for canonical labeling of a certain class of graphs (motivated by biology). The "difficult" instances of this problem can be reduced to graphs of the type mentioned in the title.

Rigid refers to graphs having only the trivial automorphism, i.e. no symmetry.

Chromatic index refers to the smallest number of colors needed for an edge coloring of the graph, i.e. a coloring such that no node is incident to two edges of the same color.

So, all nodes in these graphs have the same "local view", i.e. exactly one incident edge for each of the N distinct colors.

I'm interested in undirected graphs in the first instance, but ultimately also in directed graphs; in the latter case, I allow the same color be used for two edges incident to a given node if one is outgoing and the other is incoming.

Edit: To motivate the chromatic index property, I am in fact working with graphs which have colors assigned to edges, and these happen to constitute edge colorings. So I get edge colorings for free - I'm not computing them.

Edit: An outline of the canonical labeling algorithm we are looking at, in case that is relevant or of interest. Edges are colored, and isomorphism must preserve edge colors. We assume a total ordering of colors. This ordering then induces a total ordering on nodes, based on e.g. depth first searches which follow edges according to the color ordering. The fact that each node has at most one edge of a given color means that a node uniquely determines a depth first search from that node. One can then pick a "least" node, and construct a canonical labeling based on a search from that node. If there are "many" automorphisms, one can quickly reduce the number of nodes under consideration. The problem arises when there are "few" automorphisms - e.g. just the trivial one - which was the original motivation for this question.

The question

I'm trying to better understand this class of connected, rigid, N-regular graphs with chromatic index N. Specifically:

1) Are there any well-known or extensively studied examples of such graphs?

2) Are there any established results relating to such graphs, e.g. on existence?

3) Are there existing results on the complexity of isomorphism or canonical labeling for this class of graphs?

I'm not very hopeful, since I have done my best to search the literature. But I'm not an expert in graph theory, and I'd be grateful for any pointers.

Many thanks, Michael

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ You won't find much with that particular combination of properties, because "most" regular graphs are rigid and "most" graphs are Class 1 (have chromatic index equal to maximum degree). $\endgroup$
    – Gordon Royle
    Commented Dec 17, 2012 at 22:10
  • $\begingroup$ I second Gordon's remark, but I am also puzzled by relevance of the chromatic index. The chromatic index are harder to compute than a canonical labeling. Thus, unless you get the index cheaply, it is not clear why it helps. $\endgroup$
    – Dima Pasechnik
    Commented Dec 17, 2012 at 23:21
  • $\begingroup$ Thanks Gordon and Dima - yes, I suppose there isn't much to go on with these properties. I added some additional motivation for edge colorings in the question (so Dima, yes: we get these for free). Apart from that, the colorings are in fact hugely helpful for efficient canonical labelings - we have a simple algorithm with worst case time O(e^2) where e is the number of edges - but we are hoping for a better bound. Perhaps I'll post a separate question directly related to the canonical labeling problem if we don't make further progress. $\endgroup$
    – Michael Pedersen
    Commented Dec 18, 2012 at 10:04
  • $\begingroup$ Please clarify the relevance of the edge colouring to the canonical labelling. Is the particular edge colouring you have a property that must be preserved by isomorphisms? $\endgroup$
    – Brendan McKay
    Commented Dec 18, 2012 at 10:16
  • $\begingroup$ Brendan, yes, isomorphisms must preserve edge coloring. I've added a brief description of our approach in the question (second Edit). It may of course be that general graph isomorphism algorithms (including yours, McKay), already handle this class of graphs effectively - its just not obvious to me. $\endgroup$
    – Michael Pedersen
    Commented Dec 18, 2012 at 10:51

1 Answer 1

Reset to default
0
$\begingroup$

Based on the further information, I am addressing the question of canonical labelling of connected, edge-coloured, regular graphs. I don't recall any literature on this. Let $n$ be the number of vertices and $d$ the degree.

As you noted, DFS (or BFS, etc) can be used to make a unique labelling for each starting vertex. Then you can choose a "best" starting vertex according to some ordering on labelled graphs. This gives an $O(n^2d)$ canonical labelling algorithm. In practice you can do two things to make it faster.

(1) Compute some invariant of the vertices and only consider starting vertices that that have the rarest value of the invariant. Think of the number of triangles at a vertex, the number of vertices at distance two from a vertex, etc. Probably in your case some use of colours is best. The length of the cycles formed by two colours might be useful. You need to experiment to find the most efficient invariant for your application.

(2) Don't compute complete labellings before comparing them. Keep the best labelling seen so far and compare other labelings to it as they are being computed. Most labellings will be aborted early.

I don't see a fundamental reason why O(nd) is impossible, but I don't see an algorithm achieving that either. Knowing in advance that the automorphism group is trivial will not help.

Regarding the existence problem, the complete graph on an even number of vertices can be properly edge coloured (look up perfect factorizations, also called 1-factorization, of complete graphs). Just take the edges with some set of colours to get examples of any plausible degree. (However, this does not get all possible examples.)

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for your comments Brendan. Regarding 1: We are already exploiting cycles of various colors; we associate a "cycle characterisation" with nodes; then we do partition refinement, and finally carry out searches from all nodes in an appropriately chosen class. Regarding 2: We are also investigating this parallel algorithm; indeed the intuition is that this should discover asymmetry early when there is asymmetry. We are working on understanding the time complexity in these cases, hence starting with graphs with no non-trivial automorphisms. $\endgroup$
    – Michael Pedersen
    Commented Dec 18, 2012 at 13:16
  • $\begingroup$ Another point: as hinted in the question, the pairwise comparison (non-parallel) approach works well when there are "many" automorphisms: these are likely to be discovered early, and whenever one is discovered, the number of pending nodes is greatly reduced (at least halved), improving on the quadratic time. Our hope is that the parallel approach will be better than quadratic when there a "few" automorphisms. We can then run the two approaches simultaneously. $\endgroup$
    – Michael Pedersen
    Commented Dec 18, 2012 at 13:24
  • $\begingroup$ Btw, we have some slides on this approach here: people.ds.cam.ac.uk/mdp40/site_graph_iso.pptx They are informal and not very self contained, but maybe of help to anybody stumbling on this question. $\endgroup$
    – Michael Pedersen
    Commented Dec 18, 2012 at 13:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .