Search

Canonical orderings [STOC’88, FOCS’92] have been used as a key tool in graph drawing, graph encoding and visibility representations for the last decades. We study a far-reaching generalization of canonical orderings to non-planar graphs that was published by Lee Mondshein in a PhD-thesis at M.I.T. as early as 1971.

We study the graph isomorphism problem for graph classes defined by sets of forbidden subgraphs. We show that there is a complexity dichotomy in case the set of forbidden subgraphs is finite. More precisely, we show that the problem is polynomial-time solvable if the forbidden set contains a forest of subdivided stars and is graph isomorphism complete otherwise. We also show that, assuming that the graph isomorphism problem is not polynomial-time solvable in general, there is no such dichotomy for the cases of infinite sets of forbidden subgraphs. To this end, we conditionally show that there exists a graph class closed under taking subgraphs with intermediate isomorphism problem, i.e., a class on which the isomorphism problem is neither polynomial-time solvable nor graph isomorphism complete.

The fixed-parameter tractability of graph isomorphism is an open problem with respect to a number of natural parameters, such as tree-width, genus and maximum degree. We show that graph isomorphism is fixed-parameter tractable when parameterized by the tree-depth of the graph. We also extend this result to a parameter generalizing both tree-depth and max-leaf-number by deploying new variants of cops-and-robbers games.

We study the problem of canonizing hypergraphs under Abelian group action and show tight complexity bounds. Our approach is algebraic. We transform the problem of graph canonization to the problem of canonizing associated algebraic structures for which we develop a parallel algorithm. Specifically, we show that the problem of computing canonical labelings for hypergraphs of color class size 2 is computable in FL⊕L. For general hypergraphs, under Abelian permutation group action, for the canonization problem we show an upper bound of randomized FLGapL (which is contained in randomized NC2). This is a nearly tight characterization since the problem is hard for the complexity class FLGapL. The problem is also in deterministic NC3.

For similarity measures of labeled and unlabeled graphs, we study the complexity of the graph isomorphism problem for pairs of input graphs which are close with respect to the measure. More precisely, we show that for every fixed integer k we can decide in quadratic time whether a labeled graph G can be obtained from another labeled graph H by relabeling at most k vertices. We extend the algorithm solving this problem to an algorithm determining the number l of vertices that must be deleted and the number k of vertices that must be relabeled in order to make the graphs equivalent. The algorithm is fixed-parameter tractable in k + l. Contrasting these tractability results, we also show that for those similarity measures that change only by finite amount d whenever one edge is relocated, the problem of deciding isomorphism of input pairs of bounded distance d is equivalent to solving graph isomorphism in general.

Given a pattern graph H of fixed size, and a host graph G guaranteed to contain at most one occurrence of a subgraph isomorphic to H, we show that both the problem of finding such an occurrence (if any) as well as the decision version of the problem are as hard as in the general case when G may contain several occurrences of H.

Measures of vertex similarity have been incorporated in graph matching algorithms. Graph matching tries to retrieve a 1-1 correspondence between vertices of two given graphs. In this paper, the vertex similarity measure of Blondel et al. is studied for its usefulness in detecting graph isomorphism. Firstly, the applicability of this measure to distinguish similar pairs from dissimilar pairs is shown to be limited in scope even for small graphs. In a preliminary experiment, we show that Blondel’s vertex similarity measure does not retrieve the isomorphism within a graph of 14 nodes. We propose a refinement of Blondel’s measure. Zager et al. also refine Blondel’s measure and further propose a graph matching algorithm. We propose a graph matching algorithm based on the lines of Zager et al. and test our algorithm against Zager’s as well as Blondel’s and show that the proposed refinement performs better than both the measures with regard to graph isomorphism problem. The performance is evaluated systematically on a large bench mark data set made available by Foggia et al. The proposed algorithm performs with 90.10% accuracy on all of the 18,200 pairs of isomorphic graphs available in the benchmark dataset.

We show that k-tree isomorphism can be decided in logarithmic space by giving a logspace canonical labeling algorithm. This improves over the previous StUL upper bound and matches the lower bound. As a consequence, the isomorphism, the automorphism, as well as the canonization problem for k-trees are all complete for deterministic logspace. We also show that even simple structural properties of k-trees are complete for logspace.

In frequent subgraph mining one tries to find all subgraphs that occur with a userspecified minimum frequency in a given graph database. The basic approach is to grow subgraphs, adding an edge and maybe a node in each step, to count the number of database graphs containing them, and to eliminate infrequent subgraphs. The predominant method to avoid redundant search (the same subgraph can be grown in several ways) is to define a canonical form that uniquely identifies a graph up to automorphisms. The obvious alternative, a repository of processed subgraphs, has received fairly little attention yet. However, if the repository is laid out as a hash table with a carefully designed hash function, this approach is competitive with canonical form pruning. In experiments we conducted, the repository-based approach could sometimes outperform canonical form pruning by 15%.

We investigate the Induced Subgraph Isomorphism problem with non-standard parametrization, where the parameter is the difference |V (G )| *** |V (H )| with H and G being the smaller and the larger input graph, respectively. Intuitively, we can interpret this problem as "cleaning" the graph G , regarded as a pattern containing extra vertices indicating errors, in order to obtain the graph H representing the original pattern. We show fixed-parameter tractability of the cases where both H and G are planar and H is 3-connected, or H is a tree and G is arbitrary.

A tournament is a graph in which each pair of distinct vertices is connected by exactly one directed edge. Tournaments are an important graph class, for which isomorphism testing seems to be easier to compute than for the isomorphism problem of general graphs. We show that tournament isomorphism and tournament automorphism is hard under DLOGTIME uniform AC0 many-one reductions for the complexity classes NL, C=L, PL (probabilistic logarithmic space), for logarithmic space modular counting classes ModkL with odd k = 3 and for DET, the class of problems, NC1 reducible to the determinant. These lower bounds have been proven for graph isomorphism, see [21].

We show that several reducibility notions coincide when applied to the Graph Isomorphism (GI) problem. In particular we show that if a set is many-one logspace reducible to GI, then it is in fact many-one AC0 reducible to GI. For the case of Turing reducibilities we show that for any k ≥ 0 an NCk+1 reduction to GI can be transformed into an ACk reduction to the same problem.

A core problem of approaches to frequent graph mining, which are based on growing subgraphs into a set of graphs, is how to avoid redundant search. A powerful technique for this is a canonical description of a graph, which uniquely identifies it, and a corresponding test. I introduce a family of canonical forms based on systematic ways to construct spanning trees. I show that the canonical form used in gSpan ([Yan and Han (2002)]) is a member of this family, and that MoSS/MoFa ([Borgelt and Berthold (2002), Borgelt et al. (2005)]) is implicitly based on a different member, which I make explicit and exploit in the same way.

The need to perform isomorphism testing is emerging recently in many application domains such as graph-based data mining for discovering frequent common patterns in a graph database. Due to the complex nature of graph representations, the isomorphism testing between labeled graphs is one of the most time-consuming phases during the mining process. The canonical form of a graph that serves as the isomorphism certificate needs O(n!) to produce for a graph of order n, or Θ(Πi=1c(|πi|!)) if vertex invariants are employed to divide n vertices into c equivalence classes with |πi| vertices in each class i. In this paper, we propose a new algorithm to perform isomorphism testing of labeled graphs with worst case time complexity O(Σi=1c(|πi|!)), in which the product of all |πi|! terms is replaced by the sum of the terms and the asymptotic notation is changed from big theta to big oh. To the best of our knowledge, this proposed model is the latest work that focuses on the dealing of the isomorphism testing of labeled graphs. The result of this algorithm is directly applicable to the fields of graph isomorphism testing for labeled graphs.

We give a polynomial-time oracle algorithm for Tournament Canonization that accesses oracles for Tournament Isomorphism and Rigid-Tournament Canonization. Extending the Babai-Luks Tournament Canonization algorithm, we give an nO(k+logn) algorithm for canonization and isomorphism testing of k-hypertournaments, where n is the number of vertices and k is the size of hyperedges.

Our starting point is the observation that if graphs in a class C have low descriptive complexity, then the isomorphism problem for C is solvable by a fast parallel algorithm. More precisely, we prove that if every graph in C is definable in a finite-variable first order logic with counting quantifiers within logarithmic quantifier depth, then Graph Isomorphism for C is in ${\rm TC^1}\subseteq\mbox{\rm NC\ensuremath{^{2}}}$. If no counting quantifiers are needed, then Graph Isomorphism for C is even in AC1. The definability conditions can be checked by designing a winning strategy for suitable Ehrenfeucht-Fraisse games with a logarithmic number of rounds. The parallel isomorphism algorithm this approach yields is a simple combinatorial algorithm known as the Weisfeiler-Lehman (WL) algorithm. Using this approach, we prove that isomorphism of graphs of bounded treewidth is testable in TC1, answering an open question from [9]. Furthermore, we obtain an AC1 algorithm for testing isomorphism of rotation systems (combinatorial specifications of graph embeddings). The AC1 upper bound was known before, but the fact that this bound can be achieved by the simple WL algorithm is new. Combined with other known results, it also yields a new AC1 isomorphism algorithm for planar graphs.

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 complexity results on graph isomorphism testing and related algorithmic problems for restricted graph classes from the literature. Further, we provide some new complexity bounds (as well as easier proofs of some known results) and highlight some open questions.

We consider the Boolean constraint isomorphism problem, that is, the problem of determining whether two sets of Boolean constraint applications can be made equivalent by renaming the variables. We show that depending on the set of allowed constraints, the problem is either coNP-hard and GI-hard, equivalent to graph isomorphism, or polynomial-time solvable. This establishes a complete classification of the complexity of the problem, and moreover, it identifies exactly all those cases in which Boolean constraint isomorphism is polynomial-time many-one equivalent to graph isomorphism, the best-known and best-examined isomorphism problem in theoretical computer science.

We propose a graphical implementation for (possibly) recursive processes of the π-calculus, encoding each process into a term graph. Our implementation is sound and complete with respect to the standard structural congruence for the calculus: Two processes are equivalent if and only if they are mapped into isomorphic term graphs. Most importantly, the encoding allows for using standard graph rewriting mechanisms in modelling the reduction semantics of the calculus.

We present a neural network approach to solve exact and inexact graph isomorphism problems for weighted graphs. In contrast to other neural heuristics or related methods our approach is based on approximating the automorphism partition of a graph to reduce the search space followed by an energy-minimizing matching process. Experiments on random graphs with 100-5000 vertices are presented and discussed.

The following results suggest that the Graph Isomorphism problem is not NP-complete, since, unlike the known NP-complete problems, Graph Isomorphism belongs to a class that can be defined by means of the BPoperator, an operator that has proven useful in many other applications as well.

In this paper we present a fast algorithm for the computation of error-correcting graph isomorphisms. The new algorithm is an extension of a method for exact subgraph isomorphism detection from an input graph to a set of a priori known model graphs, which was previously developed by the authors.

The isomorphism problem is neither known to be NP-complete nor polynomial. Yet it is crucial for managing large conceptual graph sets. In order to speed up the conceptual graph isomorphism test, we associate to graphs a textual code that is invariant under isomorphism: a structural or filtering code. The structural code of a given graph is based on the computation by a structural function of an intrinsic total preorder on its conceptual vertices. Moreover for graphs for which the structural function produces a total order on conceptual vertices, two graphs which have the same code are isomorphic. Then, we present a conceptual graph set managing system based on the specialization relation and on a hashing function on the code induced by a structural C-preordering function. This system allows an effective search for a given conceptual graph according to its structure and so determines its specialization / generalization graphs without any projection test.

A computer package is being developed at Bayreuth for the generation and investigation of discrete structures. The package is a C and C++ class library of powerful algorithms endowed with graphical interface modules. Standard applications can be run automatically whereas research projects mostly require small C or C++ programs. The basic philosophy behind the system is to transform problems into standard problems of e.g. group theory, graph theory, linear algebra, graphics, or databases and then to use highly specialized routines from that field to tackle the problems. The transformations required often follow the same principles especially in the case of generation and isomorphism testing.

The directed graph isomorphism problem is a natural extension of the subtree isomorphism problem and has applications to type systems, functional languages and cyclic term graph rewriting systems. In this paper, we present an efficient algorithm for the ordered labeled directed graph isomorphism problem. Once the pattern graph is preprocessed, the matching process of our algorithm runs in time O(¦ET¦), where ¦ET¦ is the number of edges in the target graph. Our algorithm is particularly useful when the same pattern graph is used many times or the size of the pattern graph is small, which is typically the case in the above applications.

This paper deals with the isomorphism problem of directed path graphs and rooted directed path graphs. Both graph classes belong to the class of chordal graphs, and for both classes the relative complexity of the isomorphism problem is yet unknown. We prove that deciding isomorphism of directed path graphs is isomorphism complete, whereas for rooted directed path graphs we present a polynomial-time isomorphism algorithm.

This paper studies canonical graphs, which are conceptual graphs derivable from a canonical basis. We provide several characterizations of canonical graphs and prove that the correspondence between notions of a projection and a derivation sequence (specialization) holds true for canonical graphs. We propose an algorithm for deciding whether a conceptual graph is canonical relative to a given canonical basis. The complexity of this algorithm is polynomially related to the complexity of computing a projection between two conceptual graphs. When the canonical basis is a set of trees, it is polynomial.

Recent progress in topological graph theory has shown potential applicability of average genus to graph isomorphism testing. The present paper describes an initial effort at combining topological invariants with combinatorial analysis to design efficient graph isomorphism algorithms. In particular, a linear time algorithm for isomorphism of graphs of bounded average genus is presented.

We show that the graph isomorphism problem is low for PP and for C=P, i.e. it does not provide a PP or C=P computation with any additional power when used as oracle. Furthermore, we show that graph isomorphism belongs to the class LWPP (see Fenner, Fortnow, Kurtz [FeFoKu 91]). A similar result holds for the (apparently more difficult) problem Group Factorization. The problem of determining whether a given graph has a nontrivial automorphism, Graph Automorphism, is shown to be in SPP, and is therefore low for PP, C=P, and ModkP, k≥2.

In this paper we show that Graph Isomorphism and Chromatic Index are solvable in polynomial time when restricted to the class of graphs with treewidth ≤k (k a constant) (or equivalently, the class of partial k-trees). Also, we show that there exist algorithms that find tree-decompositions with treewidth ≤k of graphs with treewidth ≤k, in O(n3) time, (k constant).

We regard several classes of acyclic digraphs forming a hierarchy, which represents the present complexity gap in the isomorphism problem for acyclic digraphs. The classes at the lowest level of the hierarchy have a polynomially solvable isomorphism problem, whereas the more general ones have an isomorphism complete one. For all classes we develop graph grammars and examine them for properties reflecting the complexity of the corresponding isomorphism problem.

Some remarks about the problem of graph identification.- Motivation.- A construction of a stationary graph.- Properties of cells.- Properties of cellular algebras of rank greater than one.- Cellular algebras arising in the theory of permutation groups.- Some classes of cellular algebras.- Imprimitive cells and construction of factor-cells.- Construction of the quotient in the case of cellular algebras of rank greater than one.- On the structure of correct stationary graphs and cells having more than one normal subcell.- Properties of primitive cells.- Algebraic properties of cellular algebras.- Some modifications of stabilization.- Kernels and stability with respect to kernels.- Deep stabilization.- Examples of results using the stability of depth 1.- Some definitions and explanations about exhaustive search.- An algorithm of graph canonization.- A practical algorithm of graph canonization.- An algorithm of construction of strongly regular graphs.- Tables of strongly regular graphs with n vertices, 10?n?28.- Some properties of 25- and 26- families.