5
$\begingroup$

Let $G_1,$ $G_2$ be two arbitrary graphs with $n$ vertices and we want to check if they are isomorphic.

Question 1. For what maximal value of $n$ we ​​can actually perform such verification?

Question 2. Is there any result like as a list of all non-isomorphic graphs up to $n$, and what is the value of $n$ — 10, 20?

$\endgroup$
3
  • $\begingroup$ related, number of graphs: 1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, 12005168, 1018997864, 165091172592, 50502031367952, 29054155657235488, 31426485969804308768, ... oeis.org/A000088 $\endgroup$
    – A.Schulz
    Nov 26, 2013 at 8:54
  • $\begingroup$ It is an answer on another question $\endgroup$
    – Leox
    Nov 26, 2013 at 9:19
  • $\begingroup$ Thats why I said, related. You might find references that help you with your question in the link though $\endgroup$
    – A.Schulz
    Nov 26, 2013 at 9:47

2 Answers 2

7
$\begingroup$

The number of non-isomorphic graphs on $n$ nodes is given by https://oeis.org/A000088. If you only care about connected graphs then it's https://oeis.org/A001349. Programs like nauty can enumerate these graphs for you. That answers your second question.

For your first question, it depends on the meaning on actually. There are algorithms which work for fairly large number of vertices, but fail (take a long time) on some bad examples that supposedly don't happen (or are rare) in practice. The worst-case asymptotic complexity of graph isomorphism is still open. The Wikipedia page has an old (2001) reference which compares real-world algorithms for graph isomorphism. Perhaps you could find a more recent one and update the page.

$\endgroup$
6
$\begingroup$

this is a nice recent survey incl empirical comparisons by a leading researcher who has worked decades in the field & can answer the question about state of the art/performance of best-optimized algorithms.

We report the current state of the graph isomorphism problem from the practical point of view. After describing the general principles of the refinement-individualization paradigm and proving its validity, we explain how it is implemented in several of the key programs. In particular, we bring the description of the best known program nauty up to date and describe an innova- tive approach called Traces that outperforms the competitors for many difficult graph classes. Detailed comparisons against saucy, Bliss and conauto are presented.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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