3 ms·
For context, determining if two graphs are isomorphic is NP-complete.
by jboggan 7y ago
For context, determining if two graphs are isomorphic is NP-complete.
- firebatpi 7y agoGraph isomorphism is actually not known to be NP-complete. Many complexity theorists believe it isn't, since if it is, then the polynomial hierarchy collapses.
- dnlgl 7y agoIt is already all but known to be quasi-polynomial, thanks to László Babai: https://www.quantamagazine.org/graph-isomorphism-vanquished-again-20170114/ https://www.quantamagazine.org/graph-isomorphism-vanquished-...
- salty_biscuits 7y agoAlso approximate matching via spectral methods is polynomial. You basically take eigendecomposition of graph adjacency matrix and take inner product of eigenvectors, because spectrum is invariant under permutation of node labels. Works well on noise free and large graphs, because you are unlikely to be unlucky enough to land on isospectral graphs.
- jcims 7y agoI'm imagining a number of use cases for something like this in the information security domain but don't know enough about graph theory to chew into this paper. Would it be possible to do something like k-means with this to identify patterns in existing graphs as well?