This corrigendum corrects errors found by Jérémie Dusart in the proof of correctness of the algorithms in [D. G. Corneil, B. Dalton, and M. Habib, SIAM J. Comput., 42 (2013), pp. 792--807]; there are no changes in the algorithms themselves.

In this paper we study how graph searching on a cocomparability graph $G$ can be used to produce cocomp orderings (i.e., orderings that are linear extensions of some transitive orientation of $\overline{G}$) that yield simple algorithms for various intractable problems in general. Such techniques have been used to find a simple certifying algorithm for the minimum path cover problem. In particular we present a characterization of the searches that preserve cocomp orderings when used as a “$^+$” sweep. This allows us to present a toolbox of different graph searches and a framework to solve various problems on cocomparability graphs. We illustrate these techniques by describing a very simple certifying algorithm for the maximum independent set problem as well as a simple permutation graph recognition algorithm.

For graph $G(V,E)$, a minimum path cover (MPC) is a minimum cardinality set of vertex disjoint paths that cover $V$ (i.e., every vertex of $G$ is in exactly one path in the cover). This problem is a natural generalization of the Hamiltonian path problem. Cocomparability graphs (the complements of graphs that have an acyclic transitive orientation of their edge sets) are a well studied subfamily of perfect graphs that includes many popular families of graphs such as interval, permutation, and cographs. Furthermore, for every cocomparability graph $G$ and acyclic transitive orientation of the edges of $\overline{G}$ there is a corresponding poset $P_G$; it is easy to see that an MPC of $G$ is a linear extension of $P_G$ that minimizes the bump number of $P_G$. Although there are directly graph-theoretical MPC algorithms (i.e., algorithms that do not rely on poset formulations) for various subfamilies of cocomparability graphs, notably interval graphs, until now all MPC algorithms for cocomparability graphs themselves have been based on the bump number algorithms for posets. In this paper we present the first directly graph-theoretical MPC algorithm for cocomparability graphs; this algorithm is based on two consecutive graph searches followed by a certifying algorithm. Surprisingly, except for a lexicographic depth first search (LDFS) preprocessing step, this algorithm is identical to the corresponding algorithm for interval graphs. The running time of the algorithm is $O({\rm min}(n^2, n + {\rm mloglogn}))$, with the nonlinearity coming from LDFS.

Given a graph $G$, the longest path problem asks to compute a simple path of $G$ with the largest number of vertices. This problem is the most natural optimization version of the well-known and well-studied Hamiltonian path problem, and thus it is NP-hard on general graphs. However, in contrast to the Hamiltonian path problem, there are only a few restricted graph families, such as trees, and some small graph classes where polynomial algorithms for the longest path problem have been found. Recently it has been shown that this problem can be solved in polynomial time on interval graphs by applying dynamic programming to a characterizing ordering of the vertices of the given graph [K. Ioannidou, G. B. Mertzios, and S. D. Nikolopoulos, Algorithmica, 61 (2011), pp. 320--341], thus answering an open question. In the present paper, we provide the first polynomial algorithm for the longest path problem on a much greater class, namely on cocomparability graphs. Our algorithm uses a similar, but essentially simpler, dynamic programming approach, which is applied to a lexicographic depth first search (LDFS) characterizing ordering of the vertices of a cocomparability graph. Therefore, our results provide evidence that this general dynamic programming approach can be used in a more general setting, leading to efficient algorithms for the longest path problem on greater classes of graphs. LDFS has recently been introduced in [D. G. Corneil and R. M. Krueger, SIAM J. Discrete Math., 22 (2008), pp. 1259--1276]. Since then, a similar phenomenon of extending an existing interval graph algorithm to cocomparability graphs by using an LDFS preprocessing step has also been observed for the minimum path cover problem [D. G. Corneil, B. Dalton, and M. Habib, submitted]. Therefore, more interestingly, our results also provide evidence that cocomparability graphs present an interval graph structure when they are considered using an LDFS ordering of their vertices, which may lead to other new and more efficient combinatorial algorithms.

A graph is an interval graph if it is the intersection graph of intervals on a line. Interval graphs are known to be the intersection of chordal graphs and asteroidal triple–free graphs, two families where the well-known lexicographic breadth first search (LBFS) plays an important algorithmic and structural role. In this paper we show that interval graphs have a very rich LBFS structure and that by exploiting this structure one can design a linear time, easily implementable, interval graph recognition algorithm.

Recently lexicographic breadth first search (LexBFS) has been shown to be a very powerful tool for the development of linear time, easily implementable recognition algorithms for various families of graphs. In this paper, we add to this work by producing a simple two LexBFS sweep algorithm to recognize the family of cographs. This algorithm extends to other related graph families such as $P_4$-reducible, $P_4$-sparse, and distance hereditary. It is an open question whether our cograph recognition algorithm can be extended to a similarly easy algorithm for modular decomposition.

Graph searching is perhaps one of the simplest and most widely used tools in graph algorithms. Despite this, few theoretical results are known about the vertex orderings that can be produced by a specific search algorithm. A simple characterizing property, such as is known for LexBFS, can aid greatly in devising algorithms, writing proofs of correctness, and showing impossibility results. This paper unifies our view of graph search algorithms by showing simple, closely related characterizations of various well-known search paradigms, including BFS and DFS. Furthermore, these characterizations naturally lead to other search paradigms, namely, maximal neighborhood search and LexDFS.

MOTIVATION: Algorithmic and modeling advances in the area of protein-protein interaction (PPI) network analysis could contribute to the understanding of biological processes. Local structure of networks can be measured by the frequency distribution of graphlets, small connected non-isomorphic induced subgraphs. This measure of local structure has been used to show that high-confidence PPI networks have local structure of geometric random graphs. Finding graphlets exhaustively in a large network is computationally intensive. More complete PPI networks, as well as PPI networks of higher organisms, will thus require efficient heuristic approaches. RESULTS: We propose two efficient and scalable heuristics for finding graphlets in high-confidence PPI networks. We show that both PPI and their model geometric random networks, have defined boundaries that are sparser than the 'inner parts' of the networks. In addition, these networks exhibit 'uniformity' of local structure inside the networks. Our first heuristic exploits these two structural properties of PPI and geometric random networks to find good estimates of graphlet frequency distributions in these networks up to 690 times faster than the exhaustive searches. Our second heuristic is a variant of a more standard sampling technique and it produces accurate approximate results up to 377 times faster than the exhaustive searches. We indicate how the combination of these approaches may result in an even better heuristic. AVAILABILITY: Supplementary information is available at http://www.cs.toronto.edu/~natasha/BIOINF-2005-0946/Supplementary.pdf. Software implementing the algorithms is available at http://www.cs.toronto.edu/~natasha/BIOINF-2005-0946/estimate_grap-hlets.html. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Asteroidal triple free (AT‐free) graphs have been introduced as a generalization of interval graphs, since interval graphs are exactly the chordal AT‐free graphs. While for interval graphs it is obvious that there is always a linear ordering of the vertices, such that for each triple of independent vertices the middle one intercepts any path between the remaining vertices of the triple, it is not clear that such an ordering exists for AT‐free graphs in general. In this paper we study graphs that are defined by enforcing such an ordering. In particular, we introduce two subfamilies of AT‐free graphs, namely, path orderable graphs and strong asteroid free graphs. Path orderable graphs are defined by a linear ordering of the vertices that is a natural generalization of the ordering that characterizes cocomparability graphs. On the other hand, motivation for the definition of strong asteroid free graphs comes from the fundamental work of Gallai on comparability graphs. We show that cocomparability graphs $\subset$ path orderable graphs $\subset$ strong asteroid free graphs $\subset$ AT‐free graphs. In addition, we settle the recognition question for the two new classes by proving that recognizing path orderable graphs is NP‐complete, whereas the recognition problem for strong asteroid free graphs can be solved in polynomial time.

Treewidth is generally regarded as one of the most useful parameterizations of a graph's construction. Clique-width is a similar parameterization that shares one of the powerful properties of treewidth, namely: if a graph is of bounded treewidth (or clique-width), then there is a polynomial time algorithm for any graph problem expressible in monadic second order logic, using quantifiers on vertices (in the case of clique-width you must assume a clique-width parse expression is given). In studying the relationship between treewidth and clique-width, Courcelle and Olariu [Discrete Appl. Math., 101 (2000), pp. 77--114] showed that any graph of bounded treewidth is also of bounded clique-width; in particular, for any graph G with treewidth k, the clique-width of G is at most 4 * 2 k - 1 + 1. In this paper, we improve this result by showing that the clique-width of G is at most 3 * 2 k - 1 and, more importantly, that there is an exponential lower bound on this relationship. In particular, for any k, there is a graph G with treewidth equal to k, where the clique-width of G is at least $2^{\lfloor k/2\rfloor - 1}$.

MOTIVATION: Networks have been used to model many real-world phenomena to better understand the phenomena and to guide experiments in order to predict their behavior. Since incorrect models lead to incorrect predictions, it is vital to have as accurate a model as possible. As a result, new techniques and models for analyzing and modeling real-world networks have recently been introduced. RESULTS: One example of large and complex networks involves protein-protein interaction (PPI) networks. We analyze PPI networks of yeast Saccharomyces cerevisiae and fruitfly Drosophila melanogaster using a newly introduced measure of local network structure as well as the standardly used measures of global network structure. We examine the fit of four different network models, including Erdos-Renyi, scale-free and geometric random network models, to these PPI networks with respect to the measures of local and global network structure. We demonstrate that the currently accepted scale-free model of PPI networks fails to fit the data in several respects and show that a random geometric model provides a much more accurate model of the PPI data. We hypothesize that only the noise in these networks is scale-free. CONCLUSIONS: We systematically evaluate how well-different network models fit the PPI networks. We show that the structure of PPI networks is better modeled by a geometric random graph than by a scale-free model. SUPPLEMENTARY INFORMATION: Supplementary information is available at http://www.cs.utoronto.ca/~juris/data/data/ppiGRG04/

In this paper, we study the complexity of recognizing powers of chordal graphs and its subclasses. We present the first polynomial time algorithm to recognize squares of proper interval graphs and give an outline of an algorithm to recognize kth powers of proper interval graphs for every natural number k. These are the first results of this type for a family of graphs that contains arbitrarily large cliques. On the other hand, we show the NP-completeness of recognizing squares of chordal graphs, recognizing squares of split graphs, and recognizing chordal graphs that are squares of some graph.

Abstract Recently, considerable effort has been spent on showing that Lexicographic Breadth First Search (LBFS) can be used to determine a tight bound on the diameter of graphs from various restricted classes. In this paper, we show that, in some cases, the full power of LBFS is not required and that other variations of Breadth First Search (BFS) suffice. The restricted graph classes that are amenable to this approach all have a small constant upper bound on the maximum‐sized cycle that may appear as an induced subgraph. We show that, on graphs that have no induced cycle of size greater thank, BFS finds an estimate of the diameter that is no worse than diam(G) − ⌊k/2⌋. © 2003 Wiley Periodicals, Inc.

The design of programmable logic architectures and supporting computer-aided design tools fundamentally requires both a good understanding of the combinatorial nature of netlist graphs and sufficient quantities of realistic examples to evaluate or benchmark the results. In this paper, the authors investigate these two issues. They introduce an abstract model for describing sequential circuits and a collection of statistical parameters for better understanding the nature of circuits. Based upon this model they introduce and formally define the signature of a circuit netlist and the signature equivalence of netlists. They give an algorithm (GEN) for generating sequential benchmark netlists, significantly expanding previous work (Hutton et al, 1998) which generated purely combinational circuits. By comparing synthetic circuits to existing benchmarks and random graphs they show that GEN circuits are significantly more realistic than random graphs. The authors further illustrate the viabilty of the methodology by applying GEN to a case study comparing two partitioning algorithms.

An independent set of three vertices is called an asteroidal triple if between each pair in the triple there exists a path that avoids the neighborhood of the third. A graph is asteroidal triple-free (AT-free) if it contains no asteroidal triple. The motivation for this investigation is provided, in part, by the fact that AT-free graphs offer a common generalization of interval, permutation, trapezoid, and cocomparability graphs. Previously, the authors have given an existential proof of the fact that every connected AT-free graph contains a dominating pair, that is, a pair of vertices such that every path joining them is a dominating set in the graph. The main contribution of this paper is a constructive proof of the existence of dominating pairs in connected AT-free graphs. The resulting simple algorithm, based on the well-known lexicographic breadth-first search, can be implemented to run in time linear in the size of the input, whereas the best algorithm previously known for this problem has complexity O(|V| 3 ) for input graph G=(V,E). In addition, we indicate how our algorithm can be extended to find, in time linear in the size of the input, all dominating pairs in a connected AT-free graph with diameter greater than 3. A remarkable feature of the extended algorithm is that, even though there may be O(|V| 2 ) dominating pairs, the algorithm can compute and represent them in linear time.

The development of new field-programmed, mask-programmed, and laser-programmed gate-array architectures is hampered by the lack of realistic test circuits that exercise both the architectures and their automatic placement and routing algorithms. In this paper, we present a method and a tool for generating parameterized and realistic synthetic circuits. To obtain the realism, we propose a set of graph-theoretic characteristics that describe a physical netlist, and have built a tool that can measure these characteristics on existing circuits. The generation tool uses the characteristics as constraints in the synthetic circuit generation. To validate the quality of the generated netlists, parameters that are not specified in the generation are compared with those of real circuits and with those of more "random" graphs.

Abstract—The design of programmable logic architectures and supporting computer-aided design tools fundamentally requires both a good understanding of the combinatorial nature of netlist graphs and sufficient quantities of realistic examples to evaluate or benchmark the results. In this paper, the authors investigate these two issues. They introduce an abstract model for describing sequential circuits and a collection of statistical parameters for better understanding the nature of circuits. Based upon this model they introduce and formally define the signature of a circuit netlist and the signature equivalence of netlists. They give an algorithm (GEN) for generating sequential benchmark netlists, significantly expanding previous work (Hutton et al., 1998) which generated purely combinational circuits. By comparing synthetic circuits to existing benchmarks and random graphs they show that GEN circuits are significantly more realistic than random graphs. The authors further illustrate the viabilty of the methodology by applying GEN to a case study comparing two partitioning algorithms. Index Terms—Benchmark, digital circuits, placement. I.

An independent set of three vertices such that each pair is joined by a path that avoids the neighborhood of the third is called an asteroidal triple. A graph is asteroidal triple-free (AT-free) if it contains no asteroidal triples. The motivation for this investigation was provided, in part, by the fact that the AT-free graphs provide a common generalization of interval, permutation, trapezoid, and cocomparability graphs. The main contribution of this work is to investigate and reveal fundamental structural properties of AT-free graphs. Specifically, we show that every connected AT-free graph contains a dominating pair, that is, a pair of vertices such that every path joining them is a dominating set in the graph. We then provide characterizations of AT-free graphs in terms of dominating pairs and minimal triangulations. Subsequently, we state and prove a decomposition theorem for AT-free graphs. An assortment of other properties of AT-free graphs is also provided. These properties generalize known structural properties of interval, permutation, trapezoid, and cocomparability graphs.

The development of new Field-Programmed, Mask-Programmed and Laser-Programmed Gate Array architectures is hampered by the lack of realistic test circuits that exercise both the architectures and their automatic placement and routing algorithms.In this paper, we present a method and a tool for generating parameterized and realistic random circuits.To obtain the realism, we propose a set of graph-theoretic characteristics that describe a physical netlist, and have built a tool that can measure these characteristics on existing circuits.The generation tool uses the characteristics as constraints in the random circuit generation.To validate the quality of the generated netlists, parameters that are not speci ed in the generation are c ompared with those of real circuits, and with those of \random" graphs.rameter which i s a c haracteristic of the circuit in question. Circuit Characterization Circuit Generation ValidationCharacteristics and Measured Parameters (n, nPI, nPO, delay, shape, edge-length, fanout dist'n) 2 Circuit Characterization This section describes some of the statistical and structural characteristics of circuits which w e h a v e identi ed.For the purposes of this paper we focus on combinational circuits only, and have used the MCNC benchmark circuits to form the

A tree t-spanner T of a graph G is a spanning tree in which the distance between every pair of vertices is at most t times their distance in G. This notion is motivated by applications in communication networks, distributed systems, and network design. This paper studies graph-theoretic, algorithmic, and complexity issues about tree spanners. It is shown that a tree 1-spanner, if it exists, in a weighted graph with m edges and n vertices is a minimum spanning tree and can be found in $O( m\log \beta ( m,n ) )$ time, where $\beta ( m,n ) = \min \{ i|\log^{( i )} n \leq m/n \}$. On the other hand, for any fixed $t > 1$, the problem of determining the existence of a tree t-spanner in a weighted graph is proven to be NP-complete. For unweighted graphs, it is shown that constructing a tree 2-spanner takes linear time, whereas determining the existence of a tree t-spanner is NP-complete for any fixed $t \geq 4$. A theorem that captures the structure of tree 2-spanners is presented for unweighted graphs. For digraphs, an $O( ( m + n )\alpha ( m,n ) )$ algorithm is provided for finding a tree t-spanner with t as small as possible, where $\alpha ( m,n )$ is a functional inverse of Ackerman’s function. The results for tree spanners on undirected graphs are extended to “quasi-tree spanners” on digraphs. Furthermore, linear-time algorithms are derived for verifying tree spanners and quasi-tree spanners.

An important family of graphs is the n-dimensional hypercube, the graph with $2^{n}$ nodes labelled $0,1,\cdots, 2^{n}-1$, and an edge joining two nodes whenever their binary representation differs in a single coordinate. The problem of deciding if a given source graph is a partial subgraph of an n-dimensional cube has recently been shown to be NP-complete. In this paper the same problem on a very restricted family of source graphs, trees, is considered. It is shown that the problem of determining for a given tree T and integer k if T is a partial subgraph of a k-dimensional cube is NP-complete.

Cographs are the graphs formed from a single vertex under the closure of the operations of union and complement. Another characterization of cographs is that they are the undirected graphs with no induced paths on four vertices. Cographs arise naturally in such application areas as examination scheduling and automatic clustering of index terms. Furthermore, it is known that cographs have a unique tree representation called a cotree. Using the cotree it is possible to design very fast polynomial time algorithms for problems which are intractable for graphs in general. Such problems include chromatic number, clique determination, clustering, minimum weight domination, isomorphism, minimum fill-in and Hamiltonicity. In this paper we present a linear time algorithm for recognizing cographs and constructing their cotree representation.

The graph isomorphism problem has received considerable attention due to the many practical applications of the problem and its unresolved complexity status. To deal with practical instances of the problem, a great deal of effort has gone into the development of seemingly quite effective heuristic algorithms Typically, these algorithms exploit various vertex properties which are invariant under isomorphism.Empirically, these heuristics have been analyzed extensively; however, very little theoretical analysis has been done on their intrinsic value. In this paper we show that most commonly used vertex invariants are theoretically ineffective in the sense that any pair of graphs may be uniquely represented by a pair of graphs where the vertex invariant fails to give any information whatsoever about isomorphism or nonisomorphism. As a byproduct of these results, new restricted families of graphs are shown to be isomorphism complete (i.e., the isomorphism problem on these graphs is polynomial-time equivalent to the general isomorphism problem).

In parallel computation two approaches are common, namely unbounded parallelism and bounded parallelism. In this paper both approaches will be considered with respect to graph theoretical algorithms. The problem of unbounded parallelism is studied in § 2 where some lower and upper bounds on different graph properties for directed and undirected graphs are presented. In § 3 we mention bounded parallelism and three different K-parallel graph search techniques, namely K-depth search, breadth-depth search, and breadth-first search. Each parallel algorithm is analyzed with respect to the optimal serial algorithm. It is shown that for sufficiently dense graphs the parallel breadth-first search technique is very close to the optimal bound.

In parallel computation two approaches are common; namely unbounded parallelism and bounded parallelism. In this paper both approaches will be considered. The problem of unbounded parallelism is studied in section II and some lower and upper bounds on different connectivity problems for directed and undirected graphs are presented. In section III we mention bounded parallelism and three different k-parallel graph search techniques, namely k-depth search, breadth depth search, and breadth-first search. Each algorithm is analyzed with respect to the optimal serial algorithm. It is shown that for sufficiently dense graphs the parallel breadth first search technique is very close to the optimal bound. Techniques for searching sparse graphs are also discussed.

A heuristic algorithm for the determination of the chromatic number of a finite graph is presented. This algorithm is based on Zykov’s theorem for chromatic polynomials, and extensive empirical tests show that it is the best algorithm available. Christofides’ algorithm for the determination of chromatic number is described and is used in the comparison tests.

Recently Augustson and Minker presented a version of the Bierstone algorithm for finding the set of cliques of a finite undirected linear graph.Their version contains two errors.In this paper the counterexamples to their version and the modified version of the Bierstone algorithm are presented.

A procedure for determining whether two graphs are isomorphic is described.During the procedure, from any given graph two graphs, the representative graph and the reordered graph, are derived.The representative graph is a homomorphic image of the original graph; the reordered graph is constructed from the representative graph to be isomorphic to the given graph.Unique labels are assigned to the vertices of both derived graphs.It follows that two representative graphs or two reordered graphs are isomorphic if and only if they are identical.A conjecture states that the representative graphs exhibit the automorphism partitioning of the given graph.The representative graphs form a necessity condition for isomorphism; namely, if the representative graphs are not identical, then the given graphs are not isomorphic.The converse is true for trees and follows from the conjecture for other types of graphs.It is also shown that the reordered graphs form a sufficiency condition for isomorphism; namely, if the reordered graphs are identical, then the given graphs are isomorphic.The converse follows from the conjecture.The time required to determine both derived graphs depends on a power of n, the order of the given graph.This power is a function of an adjacency property known as the strong regularity of the given graph.For graphs that do not contain a strongly regular transitive subgraph, the power is, at worst, five.