The graph isomorphism problem has a long history in the fields of computer science, mathematics and chemistry. Graph isomorphism is very important due to its practical applications and its unique complexity theoretic status . Informally, graph isomorphism is to check if two graphs that look different are actually the same. More formally, given two graphs does there exist a 1-to-1 mapping of vertices in one graph onto the vertices of other such that edges and non-edges are preserved?. Example of two isomorphic graphs is given below

A more interesting example is below

Some of the applications of Graph Isomorphism are verification of computer programs, Security, for example fingerprint scanners, facial scanners etc. The problem is in class NP (nondeterministic polynomial time) mean given a solution (bijective mapping) you can verify the solution efficiently.

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestCan the graph isomorphism problem be solved in polynomial time?

Log in to reply

till now no one is able to solve the problem in polynomial time in general (For some special class of graphs it is solvable in polynomial time like for trees)

Log in to reply

Note: Laszlo Babai showed last year that Graph Isomorphism is in Quasipolynomial-time.

Log in to reply