# Questions tagged [graph-isomorphism]

The tag has no usage guidance.

71 questions
Filter by
Sorted by
Tagged with
0answers
106 views

### Isomorphic induced subgraph problem using Courcelle's theorem

The isomorphic induced subgraph problem, is the problem of deciding whether, given two graphs $G$ and $H$, $G$ contains an induced subgraph isomorphic to $H$. Is there a proof using ...
2answers
3k views

### Can the isomorphic graph problem be solved in deterministic polynomial time?

Here is a recent homework problem of mine: Call graphs G and H isomorphic if the nodes of G may be reordered so that it is identical to H. Let ISO = {⟨G,H⟩| G and H are isomorphic graphs}. Show ...
0answers
585 views

### Implications of Babai's Proof that Graph Isomorphism is Quasi Polynomial Time [closed]

In the context of the very recent talk by Lazlo Babai outlining that Graph Isomorphism (GI) is Quasi Polynomial Time, what are the broader implications of this result? (I'm assuming the claim will ...
0answers
270 views

### Enumerate all non-isomorphic graphs of size n

I am trying to enumerate all non-isomorphic graphs of size n and found this question: Enumerate all non-isomorphic graphs of a certain size The accepted answer ...
0answers
94 views

### Complexity lower bounds via Cook reductions

Karp reduction (polynomial-time many one) is used in complexity theory to define NP-completeness. However, Cook reductions (polynomial-time Turing) is more powerful and intuitive from information ...
1answer
37 views

3answers
3k views

### Finding an isomorphism between finite automata

Im having trouble figuring out how to determine if two finite automata are the same apart from renumbered states. More specifically, heres an example: It's easy to generate a regular expression ...