Polynomial isomorphism algorithm for graphs which do not pinch to K3,g

In this paper we construct a polynomial algorithm for verifying the isomorphism of graphs which do not pinch to K_3,g. In the construction we use properties of colored graphs from this class and results of Babai-Luks on canonization of graphs. The class cited contains the class of graphs of genus not exceeding g, and we apply the algorithm constructed to the recognition of isomorphism of graphs of bounded valence. The method given is a generalization of the combinatorial and group-theoretic approach to the isomorphism problem.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 137, pp. 99–114, 1984.     

Star partitions and the graph isomorphism problem

A canonical basis of Rⁿ associated with a graph G on n vertices has been defined in [15] in connection with eigenspaces and star partitions of G. The canonical star basis together with eigenvalues of G determines G to an isomorphism. We study algorithms for finding the canonical basis and some of its variations. The emphasis is on the following three special cases; graphs with distinct eigenvalues, graphs with bounded eigenvalue multiplicities and strongly regular graphs. We show that the procedure is reduced in some parts to special cases of some well known combinatorial optimization problems, such as the maximal matching problem. the minimal cut problem, the maximal clique problem etc. This technique provides another proof of a result of L. Babai et al. [2] that isomorphism testing for graphs with bounded eigenvalue multiplicities can be performend in a polynomial time. We show that the canonical basis in strongly regular graphs is related to the graph decomposition into two strongly regular induced subgraphs. Examples of distinguishing between cospectral strongly regular graphs by means of the canonical basis are provided. The behaviour of star partitions of regular graphs under operations of complementation and switching is studied.     

Isomorphism Testing via Polynomial-Time Graph Extensions

This paper deals with algorithms for detecting graph isomorphism (GI) properties. The GI literature consists of numerous research directions, from highly theoretical studies (e.g. defining the GI complexity class) to very practical applications (pattern recognition, image processing). We first present the context of our work and provide a brief overview of various algorithms developed in such disparate contexts. Compared to well-known NP-complete problems, GI is only rarely tackled with general-purpose combinatorial optimization techniques; however, classical search algorithms are commonly applied to graph matching (GM). We show that, by specifically focusing on exploiting isomorphism properties, classical GM heuristics can become very useful for GI. We introduce a polynomial graph extension procedure that provides a graph coloring (labeling) capable of rapidly guiding a simple-but-effective heuristic toward the solution. The resulting algorithm (GI-Ext) is quite simple, very fast and practical: it solves GI within a time in the region of O(|V|³) for numerous graph classes, including difficult (dense and regular) graphs with up to 20.000 vertices and 200.000.000 edges. GI-Ext can compete with recent state-of-the-art GI algorithms based on well-established GI techniques (e.g. canonical labeling) refined over the last three decades. In addition, GI-Ext also solves certain GM problems, e.g. it detects important isomorphic structures induced in non-isomorphic graphs.     

On natural isomorphisms of cycle permutation graphs

Two problems are approached in this paper. Given a permutation onn elements, which permutations onn elements yield cycle permutation graphs isomorphic to the cycle permutation graph yielded by the given permutation? And, given two cycle permutation graphs, are they isomorphic? Here the author deals only with natural isomorphisms, those isomorphisms which map the outer and inner cycles of one cycle permutation graph to the outer and inner cycles of another cycle permutation graph. A theorem is stated which then allows the construction of the set of permutations which yield cycle permutation graphs isomorphic to a given cycle permutation graph by a natural isomorphism. Another theorem is presented which finds the number of such permutations through the use of groups of symmetry of certain drawings of cycles in the plane. These drawings are also used to determine whether two given cycle permutation graphs are isomorphic by a natural isomorphism. These two methods are then illustrated by using them to solve the first problem, restricted to natural isomorphism, for a certain class of cycle permutation graphs.     

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

Graphs with high symmetry or regularity are the main source for experimentally hard instances of the notoriously difficult graph isomorphism problem. In this paper, we study the computational complexity of isomorphism testing for line graphs of t-(v,k,λ) designs. For this class of highly regular graphs, we obtain a worst-case running time of O(vlogv+O(1)) for bounded parameters t, k, λ.In a first step, our approach makes use of the Babai-Luks algorithm to compute canonical forms of t-designs. In a second step, we show that t-designs can be reconstructed from their line graphs in polynomial-time. The first is algebraic in nature, the second purely combinatorial. For both, profound structural knowledge in design theory is required. Our results extend earlier complexity results about isomorphism testing of graphs generated from Steiner triple systems and block designs.     

Parameter testing in bounded degree graphs of subexponential growth

Parameter testing algorithms are using constant number of queries to estimate the value of a certain parameter of a very large finite graph. It is well‐known that graph parameters such as the independence ratio or the edit‐distance from 3‐colorability are not testable in bounded degree graphs. We prove, however, that these and several other interesting graph parameters are testable in bounded degree graphs of subexponential growth. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Inferring a graph from path frequency

This paper considers the problem of inferring a graph from the number of occurrences of vertex-labeled paths, which is closely related to the pre-image problem for graphs: to reconstruct a graph from its feature space representation. It is shown that both exact and approximate versions of the problem can be solved in polynomial time in the size of an output graph by using dynamic programming algorithms if the graphs are trees whose maximum degree is bounded by a constant and the lengths of given paths and alphabet size are bounded by constants. On the other hand, it is shown that this problem is strongly NP-hard even for trees of bounded degree if the maximum length of paths is not bounded. The problem of inferring a string from the number of occurrences of fixed size substrings is also studied.     

A graph isomorphism algorithm using pseudoinverses

For a graph ofm nodes andn edges, an algorithm for testing the isomorphism of graphs is given. The complexity of the algorithm is a maximum ofO(mn ²) in almost all cases, with a considerable reduction if sparsity is exploited. If isomorphism is present, the pseudoinverses of the Laplace matrices of the graphs will be row and column permutations of each other. Advantage can be taken of certain features of the incidence matrices or of properties of the graphs to reduce computation time.     

Linear-time computation of optimal subgraphs of decomposable graphs

A general problem in computational graph theory is that of finding an optimal subgraph H of a given weighted graph G. The matching problem (which is easy) and the traveling salesman problem (which is not) are well-known examples of this general problem. In the literature one can also find a variety of ad hoc algorithms for solving certain special cases in linear time. We suggest a general approach for constructing linear-time algorithms in the case where the graph G is defined by certain rules of composition (as are trees, series-parallel graphs, and outerplanar graphs) and the desired subgraph H satisfies a property that is “regular” with respect to these rules of composition (as do matchings, dominating sets, and independent sets for all the classes just mentioned). This approach is applied to obtain a linear-time algorithm for computing the irredundance number of a tree, a problem for which no polynomial-time algorithm was previously known.     

Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs

We present subexponential parameterized algorithms on planar graphs for a family of problems of the following shape: given a graph, find a connected (induced) subgraph with bounded maximum degree and with maximum number of edges (or vertices). These problems are natural generalisations of the Longest Path problem. Our approach uses bidimensionality theory combined with novel dynamic programming techniques over branch decompositions of the input graph. These techniques can be applied to a more general family of problems that deal with finding connected subgraphs under certain degree constraints.     

The graph isomorphism disease

The graph isomorphism problem—to devise a good algorithm for determining if two graphs are isomorphic—is of considerable practical importance, and is also of theoretical interest due to its relationship to the concept of NP-completeness. No efficient (i.e., polynomial-bound) algorithm for graph isomorphism is known, and it has been conjectured that no such algorithm can exist. Many papers on the subject have appeared, but progress has been slight; in fact, the intractable nature of the problem and the way that many graph theorists have been led to devote much time to it, recall those aspects of the four-color conjecture which prompted Harary to rechristen it the “four-color disease.” This paper surveys the present state of the art of isomorphism testing, discusses its relationship to NP-completeness, and indicates some of the difficulties inherent in this particularly elusive and challenging problem. A comprehensive bibliography of papers relating to the graph isomorphism problem is given.     

Graph isomorphism and equality of simplices

We show that the graph isomorphism problem is equivalent to the problem of recognizing equal simplices in ? ⁿ . This result can lead to new methods in the graph isomorphism problem based on geometrical properties of simplices. In particular, relations between several well-known classes of invariants of graphs and geometrical invariants of simplices are established.     

NP-completeness results for edge modification problems

The aim of edge modification problems is to change the edge set of a given graph as little as possible in order to satisfy a certain property. Edge modification problems in graphs have a lot of applications in different areas, and many polynomial-time algorithms and NP-completeness proofs for this kind of problems are known. In this work we prove new NP-completeness results for these problems in some graph classes, such as interval, circular-arc, permutation, circle, bridged, weakly chordal and clique-Helly graphs.     

On Center Cycles in Grid Graphs

Finding good cycles in graphs is a problem of great interest in graph theory as well as in locational analysis. We show that the center and median problems are NP-hard in general graphs. This result holds both for the variable cardinality case (i.e., all cycles of the graph are considered) and the fixed cardinality case (i.e., only cycles with a given cardinality p are feasible). Hence it is of interest to investigate special cases where the problem is solvable in polynomial time. In grid graphs, the variable cardinality case is, for instance, trivially solvable if the shape of the cycle can be chosen freely. If the shape is fixed to be a rectangle one can analyze rectangles in grid graphs with, in sequence, fixed dimension, fixed cardinality, and variable cardinality. In all cases a complete characterization of the optimal cycles and closed form expressions of the optimal objective values are given, yielding polynomial time algorithms for all cases of center rectangle problems. Finally, it is shown that center cycles can be chosen as rectangles for bounded cardinalities such that the center cycle problem in grid graphs is in these cases completely solved.     

Set graphs. I. Hereditarily finite sets and extensional acyclic orientations

A graph $G$ is said to be a set graph if it admits an acyclic orientation which is also extensional, in the sense that the out-neighborhoods of its vertices are pairwise distinct. Equivalently, a set graph is the underlying graph of the digraph representation of a hereditarily finite set.In this paper, we initiate the study of set graphs. On the one hand, we identify several necessary conditions that every set graph must satisfy. On the other hand, we show that set graphs form a rich class of graphs containing all connected claw-free graphs and all graphs with a Hamiltonian path. In the case of claw-free graphs, we provide a polynomial-time algorithm for finding an extensional acyclic orientation. Inspired by manipulations of hereditarily finite sets, we give simple proofs of two well-known results about claw-free graphs. We give a complete characterization of unicyclic set graphs, and point out two NP-complete problems closely related to the problem of recognizing set graphs. Finally, we argue that these three problems are solvable in linear time on graphs of bounded treewidth.     

Threshold functions for small subgraphs in simple graphs and multigraphs

We revisit the problem of counting the number of copies of a fixed graph in a random graph or multigraph, for various models of random (multi)graphs. For our proofs we introduce the notion of patchworks to describe the possible overlappings of copies of subgraphs. Furthermore, the proofs are based on analytic combinatorics to carry out asymptotic computations. The flexibility of our approach allows us to tackle a wide range of problems. We obtain the asymptotic number and the limiting distribution of the number of subgraphs which are isomorphic to a graph from a given set of graphs. The results apply to multigraphs as well as to (multi)graphs with degree constraints. One application is to scale-free multigraphs, where the degree distribution follows a power law, for which we show how to obtain the asymptotic number of copies of a given subgraph and give as an illustration the expected number of small cycles.     

The isomorphism problem for classes of graphs closed under contraction

We consider the isomorphism problem for graphs in classes which, together with any graph, contain its connected induced subgraphs and graphs obtained by successive identifications of endpoints of edges. The main result is to establish sufficient conditions for the existence of a polynomial time algorithm testing graphs of such classes for isomorphism. It is shown that classes failing to satisfy these conditions are isomorphism-complete.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akad. Nauk SSSR, Vol. 174, pp. 147–177, 1988.     

Recognizing graphs without asteroidal triples

We consider the problem of recognizing AT-free graphs. Although there is a simple O(n³) algorithm, no faster method for solving this problem had been known. Here we give three different algorithms which have a better time complexity for graphs which are sparse or have a sparse complement; in particular we give algorithms which recognize AT-free graphs in , , and O(n^2.82+nm). In addition we give a new characterization of graphs with bounded asteroidal number by the help of the knotting graph, a combinatorial structure which was introduced by Gallai for considering comparability graphs.     

Subexponential Parameterized Algorithms for Bounded-Degree Connected Subgraph Problems on Planar Graphs

We present subexponential parameterized algorithms on planar graphs for a family of problems that consist in, given a graph G, finding a connected (induced) subgraph H with bounded maximum degree, while maximising the number of edges (or vertices) of H. These problems are natural generalisations of Longest Path. Our approach uses bidimensionality theory combined with novel dynamic programming techniques over branch decompositions of the input graph. These techniques can be applied to a more general family of problems that deal with finding connected subgraphs under certain degree constraints.     

On Switching to H‐Free Graphs

In this article, we study the problem of deciding if, for a fixed graph H, a given graph is switching equivalent to an H‐free graph. Polynomial‐time algorithms are known for H having at most three vertices or isomorphic to P₄. We show that for H isomorphic to a claw, the problem is polynomial, too. On the other hand, we give infinitely many graphs H such that the problem is NP‐complete, thus solving an open problem [Kratochvíl, Ne?et?il and Zýka, Ann Discrete Math 51 (1992)]. Further, we give a characterization of graphs switching equivalent to a K_{1, 2}‐free graph by ten forbidden‐induced subgraphs, each having five vertices. We also give the forbidden‐induced subgraphs for graphs switching equivalent to a forest of bounded vertex degrees.