Babai has reputedly repaired his proof of graph isomorphism in quasipolynomial time.[1] the proof hinges crucially on Johnson graphs.

  • based on the proof, does this mean now that if Johnson graphs can be recognized in P-time, then graph isomorphism is also in P-time?

  • is the proof also essentially showing that recognizing Johnson graphs can be done in at least quasipolynomial time? and presumably this improved on prior results... what was known previously, has it changed? has the recognition time for Johnson graphs been studied in particular? is it now likely to be an area of focus after the proof, or might future research go in some other direction?

[1] Graph isomorphism vanquished again / Klarreich, Quanta magazine


1 Answer 1


Johnson graphs are actually easy to recognize. In particular, you can recognize whether an input graph is a Johnson graph in polynomial time, and you can construct an isomorphism between two isomorphic Johnson graphs in polynomial time.

Johnson graphs come into the proof in a different way. Very roughly speaking, the proof juggles between group-theoretic reductions and combinatorial reductions based on individualization/refinement. Johnson graphs are an obstacle for combinatorial reductions but amenable to group-theoretic ones. The Johnson graphs in question are not the actual input graphs – in fact the problem solved by the algorithm is more general than graph isomorphism – but rather, they show up after a series of reductions during the algorithm.

  • $\begingroup$ ok, thx helpful, realize then somewhat mis-asked the question. what are the "hard" input graphs for the algorithm? the algorithm takes g1, g2, and are you saying that hard cases may involve neither g1, g2 as johnson graphs? $\endgroup$
    – vzn
    Jan 28, 2017 at 16:28
  • $\begingroup$ Unfortunately, I don't understand the algorithm well enough to answer this question. $\endgroup$ Jan 28, 2017 at 17:43
  • 1
    $\begingroup$ ok. a ref for the P-time Johnson algorithm recognition if known/ exists would be helpful/ more complete, wikipedia doesnt seem to cite it. doesnt seem obvious how to do it. $\endgroup$
    – vzn
    Jan 28, 2017 at 21:44
  • $\begingroup$ Babai himself stated it – you could ask him. $\endgroup$ Jan 28, 2017 at 22:35
  • 3
    $\begingroup$ Graph isomorphism for Johnson graphs reduces to identification of Johnson graphs – given a graph, determine whether it's a Johnson graph, and identify its parameters. I don't know what procedure Babai had in mind, but it seems you can guess the parameters, and then uncover the "identity" of the vertices (thus verifying that the guessed parameters are correct) by traversing the graph starting from some arbitrary vertex. Details left to the reader. $\endgroup$ Jan 28, 2017 at 23:01

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.