scientific article; zbMATH DE number 1004939
Determination of graph isomorphism is a well-known unsettled problem in computational complexity. A fashionable line of approach is to bound some graph parameter (like vertex degree) to obtain polynomial time algorithms for specific classes of graphs. But there are also instances where even the fastest algorithms take exponential time. The author examines McKay's algorithm in this context. A \(k\)-colouring of a graph is taken to mean a partition of its vertex set into \(k\) colour classes, and starting with a given colouring \(\phi: V\to\Omega= \{1,2,\dots,n\}\), this algorithm proceeds to obtain a refined colouring \(\phi'\) based on lexicographically ordering of the vertices \(v\) by the tuples \(D(v)=\{\phi(v), d_1(v),\dots, d_n(v)\}\), where \(d_i(v)\) is the number of the neighbours of \(v\) in the \(i\)th colour class. This refinement is repeated till for some \(r<n\), \(\phi^{(r)}= \phi^{(r+1)}\), and \(\phi^{(r)}=\overline\phi\) is defined to be the stable refinement of \(\phi\). The algorithm uses a backtrack procedure in a search tree whose nodes are stable vertex colourings. Two devices are used to prune traversal in this tree. One uses discovered automorphisms and the other uses hashing partial information of vertex labellings. This is implemented by the nauty package. The algorithm which uses only the first device is denoted ``nauty by the author. The main results of the author are that (1) there are vertex colour orderings for which nauty runs in polynomial time, (2) there are instances which need exponential time, and (3) even the refinement obtained by using the hasing technique does not improve matters. The author reports on his extensive experimentation with nauty. The technique used by the author to construct candidate graphs for the algorithms is the use of the Fürer gadgets, see \textit{M. Fürer}, A counterexample in graph isomorphism testing, Tech. Rep. CS-87-36, Department of Computer Science, The Pennsylvania State University, University Park, PA, 1987. For the entire collection see [Zbl 0861.00012].
- Graph matching using the interference of continuous-time quantum walks
- The computational complexity of cordial and equitable labelling
- Gathering robots in graphs: the central role of synchronicity
- Novel techniques to speed up the computation of the automorphism group of a graph
- New invariants for the graph isomorphism problem
- Information theoretic measures of UHG graphs with low computational complexity
- Tight lower and upper bounds for the complexity of canonical colour refinement
- Practical graph isomorphism. II.
- Symmetry breaking constraints for the minimum deficiency problem
- Efficient isomorphism of Miyazaki graphs
- McKay's canonical graph labeling algorithm
- Benchmark Graphs for Practical Graph Isomorphism
- Dörfler marking with minimal cardinality is a linear complexity problem
- Algorithms for the graph isomorphism problem based on graph deregularisation
- An exponential lower bound for individualization-refinement algorithms for graph isomorphism
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4335302)