Suppose I want to test an algorithm for graph isomorphism check.

Starting from a given graph, I would do a random permutation of vertices to build the second graph.

Is there a way of making another isomorphic graph that is "more difficult" to check?

  • 4
    $\begingroup$ No, because given any labelling of a graph you can make a random labelling of that. So every labelling is equally difficult. That doesn't mean a particular algorithm will take the same time for each labelling. $\endgroup$ Sep 11 at 14:51
  • 1
    $\begingroup$ Maybe it's more interesting to ask for a non-isomorphic graph that is difficult to check? $\endgroup$ Sep 12 at 1:38
  • 1
    $\begingroup$ @Gerry Myerson yes, right. $\endgroup$
    – BillyJoe
    Sep 12 at 6:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.