[PDF][PDF] A decomposition-compatible canonization framework for the graph isomorphism problem
D Wiebking - 2021 - publications.rwth-aachen.de
D Wiebking
2021•publications.rwth-aachen.deAbstract The Graph Isomorphism Problem is one of a few famous problems in NP that is
neither known to be solvable in polynomial time nor to be NP-complete. The problem asks
whether two given input graphs are structurally equivalent, which means that both graphs
coincide up to a renaming of the vertices. With Babai's celebrated breakthrough (STOC
2016) it was shown that the problem can be decided in quasipolynomial time. One way of
solving the Graph Isomorphism Problem is by applying a canonization approach. Graph …
neither known to be solvable in polynomial time nor to be NP-complete. The problem asks
whether two given input graphs are structurally equivalent, which means that both graphs
coincide up to a renaming of the vertices. With Babai's celebrated breakthrough (STOC
2016) it was shown that the problem can be decided in quasipolynomial time. One way of
solving the Graph Isomorphism Problem is by applying a canonization approach. Graph …
Abstract
The Graph Isomorphism Problem is one of a few famous problems in NP that is neither known to be solvable in polynomial time nor to be NP-complete. The problem asks whether two given input graphs are structurally equivalent, which means that both graphs coincide up to a renaming of the vertices. With Babai’s celebrated breakthrough (STOC 2016) it was shown that the problem can be decided in quasipolynomial time.
One way of solving the Graph Isomorphism Problem is by applying a canonization approach. Graph canonization is the task of transforming a graph into a canonical form, that is, a graph representation that coincides for structurally equivalent graphs. As far as we know, graph canonization might be harder than the Graph Isomorphism Problem. In particular, there are isomorphism tests for various graph classes and objects for which to date no canonization algorithm with the same asymptotic running time is known.
publications.rwth-aachen.de