Planar Graph Isomorphism Is in Log-Space
| Autor: | Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
Discrete mathematics
Block graph Logspace SPQR tree Planar straight-line graph Biconnected component Biconnected graph Graph canonization Theoretical Computer Science Planar graph Combinatorics symbols.namesake Planar Graphs Computational Theory and Mathematics Outerplanar graph Graph Isomorphism symbols MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Datta, S, Limaye, N, Nimbhorkar, P, Thierauf, T & Wagner, F 2022, ' Planar Graph Isomorphism Is in Log-Space ', ACM Transactions on Computation Theory, vol. 14, no. 2, pp. 1-33 . https://doi.org/10.1145/3543686 IEEE Conference on Computational Complexity |
| Popis: | Graph Isomorphism is the prime example of a computational problem with a wide difference between the best known lower and upper bounds on its complexity. There is a significant gap between extant lower and upper bounds for planar graphs as well. We bridge the gap for this natural and important special case by presenting an upper bound that matches the known log-space hardness [JKMT03]. In fact, we show the formally stronger result that planar graph canonization is in log-space. This improves the previously known upper bound of AC1 [MR91]. Our algorithm first constructs the biconnected component tree of a connected planar graph and then refines each biconnected component into a triconnected component tree. The next step is to log-space reduce the biconnected planar graph isomorphism and canonization problems to those for 3-connected planar graphs, which are known to be in log-space by [DLN08]. This is achieved by using the above decomposition, and by making significant modifications to Lindell’s algorithm for tree canonization, along with changes in the space complexity analysis. The reduction from the connected case to the biconnected case requires further new ideas, including a non-trivial case analysis and a group theoretic lemma to bound the number of automorphisms of a colored 3-connected planar graph. This lemma is crucial for the reduction to work in log-space. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|