Dynamic complexity of planar 3-connected graph isomorphism

DOI10.1007/978-3-319-06686-8_21MaRDI QIDQ4981166zbMATH OpenOpenAlexFDO

Authors Jenish C. Mehta

Publication date 24 June 2014

Published in Computer Science - Theory and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.2141

Mathematics Subject Classification ID

Logic in computer science (03B70) Planar graphs; geometric and topological aspects of graph theory (05C10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Data structures (68P05) Database theory (68P15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Dynamic Complexity (as introduced by Patnaik and Immerman) tries to express how hard it is to update the solution to a problem when the input is changed slightly. It considers the changes required to some stored data structure (possibly a massive database) as small quantities of data (or a tuple) are inserted or deleted from the database (or a structure over some vocabulary). The main difference from previous notions of dynamic complexity is that instead of treating the update quantitatively by finding the the time/space trade-offs, it tries to consider the update qualitatively, by finding the complexity class in which the update can be expressed (or made). In this setting, DynFO, or Dynamic First-Order, is one of the smallest and the most natural complexity class (since SQL queries can be expressed in First-Order Logic), and contains those problems whose solutions (or the stored data structure from which the solution can be found) can be updated in First-Order Logic when the data structure undergoes small changes. Etessami considered the problem of isomorphism in the dynamic setting, and showed that Tree Isomorphism can be decided in DynFO. In this work, we show that isomorphism of Planar 3-connected graphs can be decided in DynFO+ (which is DynFO with some polynomial precomputation). We maintain a canonical description of 3-connected Planar graphs by maintaining a database which is accessed and modified by First-Order queries when edges are added to or deleted from the graph. We specifically exploit the ideas of Breadth-First Search and Canonical Breadth-First Search to prove the results. We also introduce a novel method for canonizing a 3-connected planar graph in First-Order Logic from Canonical Breadth-First Search Trees.

Recommendations

• Dyn-FO: A parallel, dynamic complexity class
• STACS 2005
• Dynamic complexity of directed reachability and other problems
• Reachability is in DynFO
• Dynamic complexity theory revisited

Cited in

(3)

• 3-connected Planar Graph Isomorphism is in Log-space
• scientific article; zbMATH DE number 5777931 (Why is no real title available?)
• scientific article; zbMATH DE number 6146491 (Why is no real title available?)

This page was built for publication: Dynamic complexity of planar 3-connected graph isomorphism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4981166)