# On Graph Isomorphism for Restricted Graph Classes

@inproceedings{Kbler2006OnGI, title={On Graph Isomorphism for Restricted Graph Classes}, author={Johannes K{\"o}bler}, booktitle={CiE}, year={2006} }

Graph isomorphism (GI) is one of the few remaining problems in NP whose complexity status couldn't be solved by classifying it as being either NP-complete or solvable in P. Nevertheless, efficient (polynomial-time or even NC) algorithms for restricted versions of GI have been found over the last four decades. Depending on the graph class, the design and analysis of algorithms for GI use tools from various fields, such as combinatorics, algebra and logic.
In this paper, we collect several… Expand

#### Figures and Topics from this paper

#### 29 Citations

Computational complexity of reconstruction and isomorphism testing for designs and line graphs

- Computer Science, Mathematics
- J. Comb. Theory, Ser. A
- 2011

This paper studies the computational complexity of isomorphism testing for line graphs of t-(v,k,@l) designs and shows that t-designs can be reconstructed from their line graphs in polynomial-time. Expand

Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs

- Mathematics, Computer Science
- SODA
- 2014

It is shown that there are pairs of nonisomorphic n-vertex graphs G and H such that any sum-of-squares (SOS) proof of non isomorphism requires degree Ω(n), and an O(n)-round integrality gap for the Lasserre SDP relaxation is shown. Expand

Attacks on difficult instances of graph isomorphism: sequential and parallel algorithms

- Mathematics
- 2009

The graph isomorphism problem has received a great deal of attention on both theoretical and practical fronts. However, a polynomial algorithm for the problem has yet to be found. Even so, the best… Expand

Isomorphism for Graphs of Bounded Connected-Path-Distance-Width

- Mathematics, Computer Science
- ISAAC
- 2012

We show that Graph Isomorphism problem (GI) can be solved in \(\mathcal{O}(n^{2})\) time for graphs of bounded connected-path-distance-width, and more generally, in \(\mathcal{O}(n^{c + 1})\) time… Expand

Scalable Graph Isomorphism: Combining Pairwise Color Refinement and Backtracking via Compressed Candidate Space

- Computer Science
- 2021 IEEE 37th International Conference on Data Engineering (ICDE)
- 2021

A new approach to graph isomorphism is proposed, which is the framework of pairwise color refinement and binary cell mapping, and compressed CS (candidate space), and partial failing set, which together lead to a much faster and scalable algorithm. Expand

An enhanced classical approach to graph isomorphism using continuous-time quantum walk

- Mathematics
- 2012

Studies on graph isomorphism play an important role in graph research, and graph isomorphism algorithms have a wide range of applications in image matching, pattern recognition, computer vision,… Expand

On the Complexity of Matroid Isomorphism Problems

- Mathematics, Computer Science
- CSR
- 2009

For linear and graphic matroids, it is proved that the automorphism problem is polynomial time equivalent to the corresponding isomorphism problems. Expand

Around and Beyond the Isomorphism Problem for Interval Graphs

- Computer Science, Mathematics
- Bull. EATCS
- 2012

The class of problems solvable in logarithmic space has recently replenished with the isomorphism testing for interval graphs, and prospects of its extension to larger classes of graphs are discussed. Expand

FAST PRACTICAL ALGORITHM BASED ON WEISFEILER-LEHMAN METHOD FOR GRAPH ISOMORPHISM

- 2006

Graph isomorphism problem is to determine whether two given graphs are isomorphic. It is a particular type of a more general problem “the isomorphism of incidence system”. I propose some new… Expand

Colored Hypergraph Isomorphism is Fixed Parameter Tractable

- Computer Science, Mathematics
- Algorithmica
- 2013

We describe a fixed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism, denoted CHI, which has running time (2bN)O(1), where the parameter b is the maximum size of the color… Expand

#### References

SHOWING 1-10 OF 69 REFERENCES

Moderately Exponential Bound for Graph Isomorphism

- Mathematics, Computer Science
- FCT
- 1981

The first significant complexity result in graph isomorphism testing was the linear time canonical labeling of trees, found by Hopcroft and Tarjan [16~, and independently by V.N. Zemlyachenko [29].… Expand

Parallel algorithms for permutation groups and graph isomorphism

- Computer Science
- 27th Annual Symposium on Foundations of Computer Science (sfcs 1986)
- 1986

It is shown that NC contains isomorphism-testing for vertex-colored graphs with bounded color multiplicity, a problem not long known to be in polynomial time. Expand

On the hardness of graph isomorphism

- Mathematics, Computer Science
- Proceedings 41st Annual Symposium on Foundations of Computer Science
- 2000

This paper shows that the graph isomorphism problem is hard under logarithmic space many-one reductions for the complexity classes NL, PL, and Mod/sub k/L and for the class DET of problems NC/sup 1/ reducible to the determinant. Expand

Isomorphism for graphs embeddable on the projective plane

- Mathematics, Computer Science
- STOC '80
- 1980

A generalization of the third theorem to the projective plane is presented, allowing a straightforward adaptation of the planar algorithm to theprojective plane. Expand

Isomorphism of graphs of bounded valence can be tested in polynomial time

- Computer Science, Mathematics
- 21st Annual Symposium on Foundations of Computer Science (sfcs 1980)
- 1980

Testing isomorphism of graphs of valence ≤ t is polynomial-time reducible to the color automorphism problem for groups with small simple sections, and some results on primitive permutation groups are used to show that the algorithm runs inPolynomial time. Expand

An optimal lower bound on the number of variables for graph identification

- Mathematics, Computer Science
- Comb.
- 1992

It is shown that Ω(n) variables are needed for first-order logic with counting to identify graphs onn vertices, equivalent to the (k−1)-dimensional Weisfeiler-Lehman method, and the lower bound is optimal up to multiplication by a constant. Expand

A Note on the Graph Isomorphism counting Problem

- Mathematics, Computer Science
- Inf. Process. Lett.
- 1979

Bounded color multiplicity graph isomorphism is in the #L hierarchy

- Computer Science, Mathematics
- 20th Annual IEEE Conference on Computational Complexity (CCC'05)
- 2005

This paper shows that BCGI/sub b/ is in the #L hierarchy (more precisely, the Mod/sub k/L hierarchy for some constant k depending on b), and gets a tight classification of the problem using logspace-bounded counting classes. Expand

Canonical labeling of graphs

- Computer Science, Mathematics
- STOC
- 1983

An algebraic approach to the problem of assigning canonical forms to graphs by computing canonical forms and the associated canonical labelings in polynomial time is announced. Expand

Graph isomorphism problem

- Mathematics
- 1985

The article is a creative compilation of certain papers devoted to the graph isomorphism problem, which have appeared in recent years. An approach to the isomorphism problem is proposed in the first… Expand