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


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 '17 at 16:28
  • $\begingroup$ Unfortunately, I don't understand the algorithm well enough to answer this question. $\endgroup$ – Yuval Filmus Jan 28 '17 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 '17 at 21:44
  • $\begingroup$ Babai himself stated it – you could ask him. $\endgroup$ – Yuval Filmus Jan 28 '17 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$ – Yuval Filmus Jan 28 '17 at 23:01

Your Answer

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

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