The graph isomorphism problem: its structural complexity
The aim of this book is two-fold: On the one hand, the authors want to give an almost complete overview on interesting developments regarding the complexity of the graph isomorphism problem. But on the other hand they use the opportunity to introduce the reader to the field of structural complexity theory. The light and fluent style, as well as the many well-chosen examples make it a real pleasure to work with this book. The book consists of four chapters: 1) Decision Problems, Search Problems, and Counting Problems, 2) Quantifiers, Games, and Interactive Proofs, 3) Circuits and Sparse Sets, 4) Counting Properties. In my opinion, the first two chapters are the most important ones, which should be interesting and understandable to all readers. Chapters 3) and 4) use advanced methods and constructions, which are suitable for the more interested reader only. In the first chapter first an introduction is given to the central complexity classes \(P\) and \(NP\), as well as to various reducibility notions used throughout the book. Then the authors define the three main types of problems to be considered: Decision problems, where the expected answer to a given input is YES (accept the input) or NO (reject the input); Search problems, where the expected answer to a given input is a SOLUTION (if there is one) or the answer NO (if no solution is possible); Counting problems, where the expected answer to a given input is a natural number, namely the number of different solutions to the problem described by the input. The second chapter introduces the polynomial time hierarchy first. Then the topic of interactive proof systems is treated in detail. Especially, interactive proof systems are given for the graph isomorphism problem itself (which is easy), but also for the complementary problem of graph nonisomorphism. Moreover, a zero-knowledge proof for graph isomorphisms is described. The remainder of this chapter is devoted to the concepts of probabilism and lowness. In the third chapter the class of problems decidable by polynomial size circuits is introduced. This class is equal to the closure of the class of sparse sets under Turing-reduction. The authors prove a consequence of the hypothesis that graph isomorphism have polynomial size circuits, namely then graph isomorphism is low for the class MA. Unfortunately, I cannot estimate how likely or unlikely this consequence is. On the other hand in this chapter it is shown that the presence of a sparse oracle is enough to put graph isomorphism into the class coNP, and thus (since it is certainly in NP) we can conclude that graph isomorphism is not much harder than \(NP \cap \text{NP}\). The final chapter introduces the counitng classes \(\#P\), \(PP\), \(\oplus P\), \(\text{Gap}P\) and others. A lot of interesting relations between these classes are shown, like the result of Toda that the polynomial time hierarchy is contained in \(BP \cdot \oplus P\). To summarize, I think the authors achieve both of the above mentioned aims; they wrote a wonderful book, which is at the same time very readable and extremely informative.
- On the pseudo-achromatic number problem
- Computational complexity of computing a partial solution for the graph automorphism problems
- Laminar structure of ptolemaic graphs with applications
- \texttt{SymChaff}: Exploiting symmetry in a structure-aware satisfiability solver
- Graph isomorphism is in the low hierarchy
- Parameterized circuit complexity and the \(W\) hierarchy
- How to define a linear order on finite models
- Completeness results for graph isomorphism.
- Almost complete sets.
- The computational complexity of equivalence and isomorphism problems
- A method for agent-based models validation
- Polynomial time algorithms for variants of graph matching on partial k-trees
- Towards an isomorphism dichotomy for hereditary graph classes
- On the reducibility of sets inside NP to sets with low information content
- Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
- The complexity of homomorphisms and renamings for minimal unsatisfiable formulas
- New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
- The complexity of Boolean matrix root computation
- Algorithms for highly symmetric linear and integer programs
- The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
- Graph isomorphism and identification matrices: Sequential algorithms
- On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions
- Parameterized complexity of small weight automorphisms and isomorphisms
- Practical post-quantum signature schemes from isomorphism problems of trilinear forms
- Computational complexity of k-block conjugacy
- Colored hypergraph isomorphism is fixed parameter tractable
- Isomorphic implication
- Computing graph automorphism from partial solutions
- Computational aspects of the Gromov-Hausdorff distance and its application in non-rigid shape matching
- Zero knowledge and circuit minimization
- Graph isomorphism, color refinement, and compactness
- G-Tries: a data structure for storing and finding subgraphs
- The graph isomorphism problem and approximate categories
- Graph Isomorphism is in SPP
- Compatible topologies on graphs: an application to graph isomorphism problem complexity
- The complexity of equivalence and isomorphism of systems of equations over finite groups
- Linear time algorithms for Abelian group isomorphism and related problems
- Isomorphism testing of read-once functions and polynomials
- Quantum public-key signature scheme based on asymmetric quantum encryption with trapdoor information
- Solution-Graphs of Boolean Formulas and Isomorphism
- Permutation Groups and the Graph Isomorphism Problem
- The decidability of the structural congruence for beta-binders
- Complexity and algorithms for computing Voronoi cells of lattices
- Do there exist complete sets for promise classes?
- Minimum circuit size, graph isomorphism, and related problems
- The Isomorphism Problem for k-Trees Is Complete for Logspace
- Promise problems on probability distributions
- On the Complexity of Matroid Isomorphism Problems
- Graph isomorphism for graph classes characterized by two forbidden induced subgraphs
- A Logspace Algorithm for Partial 2-Tree Canonization
- From Invariants to Canonization in Parallel
- On Toda’s Theorem in Structural Communication Complexity
- On distance between graphs
- The parallel complexity of graph canonization under abelian group action
- Structural complexity II
- scientific article; zbMATH DE number 512806 (Why is no real title available?)
- Computational indistinguishability between quantum states and its cryptographic application
- On complete systems of invariants for small graphs
- A large database of graphs and its use for benchmarking graph isomorphism algorithms
- Restrictive Acceptance Suffices for Equivalence Problems
- New collapse consequences of NP having small circuits
- The module isomorphism problem reconsidered.
- Exploring the tractability border in epistemic tasks
- Minimum circuit size, graph isomorphism, and related problems
- Spectrally robust graph isomorphism
- Solution-Graphs of Boolean Formulas and Isomorphism1
- Graph isomorphism is low for PP
- GROUP, GRAPHS, ALGORITHMS: THE GRAPH ISOMORPHISM PROBLEM
- scientific article; zbMATH DE number 7310264 (Why is no real title available?)
- Algorithms for group isomorphism via group extensions and cohomology
- Neighborhood hypergraphs of bipartite graphs
- Succinct Encodings of Graph Isomorphism
- Reductions to Graph Isomorphism
- Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
- Applications of dimensionality reduction and exponential sums to graph automorphism
- Linear and sublinear time algorithms for the basis of abelian groups
- A global constraint for graph isomorphism problems
- On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness
- Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
- Dot operators
- An Isomorphism-Invariant Distance Function on Propositional Formulas in CNF
- Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas
- Computational complexity of reconstruction and isomorphism testing for designs and line graphs
- On the complexity of deciding whether the distinguishing chromatic number of a graph is at most two
- On the complexity of matroid isomorphism problem
- Containment of conjunctive queries on annotated relations
- Computing cyclic invariants for molecular graphs
- The complexity of game isomorphism
- Exploiting the symmetry of \(\mathbb{Z}^n\): randomization and the automorphism problem
- On the power of counting the total number of computation paths of NPTMs
- On the acceptance power of regular languages
- Computing functions with parallel queries to NP
- The reachability problem for finite cellular automata
- If NP has polynomial-size circuits, then MA=AM
- A language-dependent cryptographic primitive
- Graph symmetry detection and canonical labeling: differences and synergies
- On the complexity of isomorphism problems for tensors, groups, and polynomials III: actions by classical groups
- Exploiting the symmetry of \(\mathbb{Z}^n\): randomization and the automorphism problem
- Topological scale framework for hypergraphs
- On p-group isomorphism: search-to-decision, counting-to-decision and nilpotency class reductions via tensors
This page was built for publication: The graph isomorphism problem: its structural complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4273947)