patternMinor
For how large graphs can we still check for isomorphism?
Viewed 0 times
cangraphslargeforhowstillcheckisomorphism
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#18358, answer score: 7
Revisions (0)
No revisions yet.