<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2017-01-28T16:28:28.187Z
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?
vzn
CC BY-SA 3.0
2017-01-28T17:43:17.337Z
Unfortunately, I don't understand the algorithm well enough to answer this question.
Yuval Filmus
CC BY-SA 3.0
2017-01-28T21:44:37.000Z
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.
vzn
CC BY-SA 3.0
2017-01-28T22:35:40.607Z
Babai himself stated it – you could ask him.
Yuval Filmus
CC BY-SA 3.0
2017-01-28T23:01:01.877Z
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.
Yuval Filmus
CC BY-SA 3.0
2017-01-27T23:43:22.333Z
2017-01-27T23:43:22.333Z
Yuval Filmus
<p>Babai has reputedly repaired his proof of graph isomorphism in quasipolynomial time.[1] the proof hinges crucially on <a href="https://en.wikipedia.org/wiki/Johnson_graph" rel="nofollow noreferrer">Johnson graphs</a>.</p>
<blockquote>
<ul>
<li><p>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?</p>
</li>
<li><p>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?</p>
</li>
</ul>
</blockquote>
<p>[1] <a href="https://www.quantamagazine.org/20170114-graph-isomorphism-babai-fix/" rel="nofollow noreferrer">Graph isomorphism vanquished again</a> / Klarreich, Quanta magazine</p>

<graph-theory><graph-algorithms><time-complexity><graph-isomorphism><polynomial-time>
questions on implications Babais quasi P time graph isomorphism result
vzn
# questions on implications Babais quasi P time graph isomorphism result

(Asked by: username_0 on 2017-01-27)

Babai has reputedly repaired his proof of graph isomorphism in quasipolynomial time.[1] the proof hinges crucially on [Johnson graphs](https://en.wikipedia.org/wiki/Johnson_graph).

> * 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](https://www.quantamagazine.org/20170114-graph-isomorphism-babai-fix/) / Klarreich, Quanta magazine

**Tags:** graph-theory, graph-algorithms, time-complexity, graph-isomorphism, polynomial-time


---

## 1 answers

### Answer by username_1 on 2017-01-27. Score: 13 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: Unfortunately, I don't understand the algorithm well enough to answer this question.  
> **username_0**: 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.  
> **username_1**: Babai himself stated it – you could ask him.  
> **username_1**: 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.  

---

