Search

The subclass of directed series-parallel graphs plays an important role in computer science. Whether a given graph is series-parallel is a well studied problem in algorithmic graph theory, for which fast sequential and parallel algorithms have been developed in a sequence of papers. Also methods are known to solve the reachability and the decomposition problem for series-parallel graphs time efficiently. However, no dedicated results have been obtained for the space complexity of these problems when restricted to series-parallel graphs - the topic of this paper.Deterministic algorithms are presented for the recognition, reachability, decomposition and the path counting problem for series-parallel graphs that use only logarithmic space. Since for arbitrary directed graphs reachability and path counting are believed not to be solvable in Logspace, the main contribution of this work are novel deterministic path finding routines that work correctly in series-parallel graphs, and a characterization of series-parallel graphs by forbidden subgraphs that can be tested space-efficiently. The space bounds are best possible, i.e. the decision problem is shown to be L-complete with respect to AC0-reductions. They have also implications for the parallel time complexity of these problems when restricted to series-parallel graphs.Finally we sketch how these results can be generalized to extension of the series-parallel graph family: to graph with multiple sources or multiple sinks and to the minimal vertex series-parallel graphs.

In this paper we show that a very simple and efficient approach can be used to solve the all pairs almost shortest path problem on the class of weakly chordal graphs and its different subclasses. Moreover, this approach works well also on graphs with small size of largest induced cycle and gives a unified way to solve the all pairs almost shortest path and all pairs shortest path problems on different graph classes including chordal, strongly chordal, chordal bipartite, and distance-hereditary graphs.

The cutwidth of a graph G is defined to be the smallest integer k such that the vertices of G can be arranged in a vertex ordering [v"1,...,v"n] in a way that, for every i=1,...,n-1, there are at most k edges with one endpoint in {v"1,...,v"i} and the other in {v"i"+"1,...,v"n}. We examine the problem of computing in polynomial time the cutwidth of a partial w-tree with bounded degree. In particular, we show how to construct an algorithm that, in n^O^(^w^^^2^d^) steps, computes the cutwidth of any partial w-tree with vertices of degree bounded by a fixed constant d. Our algorithm is constructive in the sense that it can be adapted to output a corresponding optimal vertex ordering. Also, it is the main subroutine of an algorithm computing the pathwidth of a bounded degree partial w-tree with the same time complexity.

We describe an algorithm for the dominating set problem with time complexity O((4g+40)kn2) for graphs of bounded genus g ≥ 1, where k is the size of the set. It has previously been shown that this problem is fixed parameter tractable for planar graphs. We give a simpler proof for the previous O(8kn2) result for planar graphs. Our method is a refinement of the earlier techniques.

We discuss general techniques, centered around the "Layerwise Separation Property" (LSP) of a planar graph problem, that allow to develop algorithms with running time c√k|G|, given an instance G of a problem on planar graphs with parameter k. Problems having LSP include PLANAR VERTEX COVER. PLANAR INDEPENDENT SET, and PLANAR DOMINATING SET. Extensions of our speed-up technique to basically all fixed-parameter tractable planar graph problems are also exhibited. Moreover, we relate, e.g., the domination number or the vertex cover number, with the treewidth of a plane graph.

We consider two problems pertaining to P4-comparability graphs, namely, the problem of recognizing whether a simple undirected graph is a P4-comparability graph and the problem of producing an acyclic P4-transitive orientation of such a graph. Sequential algorithms for these problems have been presented by Hoang and Reed and very recently by Raschle and Simon, and by Nikolopoulos and Palios. In this paper, we establish properties of P4-comparability graphs which allow us to describe parallel algorithms for the recognition and orientation problems on this class of graphs; for a graph on n vertices and m edges, our algorithms run in O(log2n) time and require O(nm/log n) processors on the CREW PRAM model. Since the currently fastest sequential algorithms for these problems run in O(nm) time, our algorithms are cost-efficient; moreover, to the best of our knowledge, this is the first attempt to introduce parallelization in problems involving P4-comparability graphs. Our approach relies on the parallel computation and proper orientation, the P4-components of the input graph.

There exists a polynomial time algorithm to compute the pathwidth of outerplanar graphs, but the large exponent makes this algorithm impractical. In this paper, we give an algorithm that, given a biconnected outerplanar graph G, finds a path decomposition of G of pathwidth at most twice the pathwidth of G plus one. To obtain the result, several relations between the pathwidth of a biconnected outerplanar graph and its dual are established.

In this paper, we present a one-to-one embedding of a graph with bounded treewidth into its optimal hypercube. This is the first time that embeddings of graphs with a highly irregular structure into hypercubes are investigated. The presented embedding achieves dilation of at most 3?log((d+1)(t+1))?+8 and node-congestion of at most O(d(dt)3), where t denotes the treewidth of the graph and d denotes the maximal degree of a vertex in the graph. Provided that the graph is given by its tree-decomposition the embedding can be computed efficiently on the hypercube itself. In particular, the embedding of a graph with constant treewidth and constant degree can be computed in time O(log2(n)logloglog(n)log*(n)). For graphs with constant treewidth, a minimal tree-decomposition can be computed efficiently in parallel due to a result of Bodlaender and Hagerup. In this case, the embedding can be computed on the hypercube in time O(log2(n)(d2+log(n)loglog2(n))).

We present efficient (parallel) algorithms for two hierarchical clustering heuristics. We point out that these heuristics can also be applied to solving some algorithmic problems in graphs, including split decomposition. We show that efficient parallel split decomposition induces an efficient parallel parity graph recognition algorithm. This is a consequence of the result of S. Cicerone and D. Di Stefano 7] that parity graphs are exactly those graphs that can be split decomposed into cliques and bipartite graphs.

We show that there is an O(nm) algorithm to approximate the bandwidth of an AT-free graph with worst case performance ratio 2. Alternatively, at the cost of the approximation factor, we can also obtain an O(m+nlogn) algorithm to approximate the bandwidth of an AT-free graph within a factor 4. For the special cases of permutation graphs and trapezoid graphs we obtain O(nlog2n) algorithms with worst-case performance ratio 2. For cocomparability graphs we obtain an O(n+m) algorithm with worst-case performance ratio 3.

We present NC-approximation schemes for a number of graph problems when restricted to geometric graphs including unit disk graphs and graphs drawn in a civilized manner. Our approximation schemes exhibit the same time versus performance trade-off as the best known approximation schemes for planar graphs. We also define the concept of ?-precision unit disk graphs and show that for such graphs the approximation schemes have a better time versus performance trade-off than the approximation schemes for arbitrary unit disk graphs. Moreover, compared to unit disk graphs, we show that for ?-precision unit disk graphs many more graph problems have efficient approximation schemes.Our NC-approximation schemes can also be extended to obtain efficient NC-approximation schemes for several PSPACE-hard problems on unit disk graphs specified using a restricted version of the hierarchical specification language of Bentley, Ottmann, and Widmayer. The approximation schemes for hierarchically specified unit disk graphs presented in this paper are among the first approximation schemes in the literature for natural PSPACE-hard optimization problems.

A graph has an optimall-interval routing scheme if it is possible to direct messages along shortest paths by labeling each edge with at mostlpairwise-disjoint subintervals of the cyclic interval 1?n (where each node of the graph is labeled by an integer in the range). Although much progress has been made forl=1, there is as yet no general tight characterization of the classes of graphs associated with largerl. Bodlaenderet al. have shown that under the assumption of dynamic cost links, each graph with an optimall-interval routing scheme has treewidth of at most 4l. For the setting without dynamic cost links, this paper addresses the complementary question of the number of intervals required to label classes of graphs of treewidthk. Although it has been shown that there exist graphs of treewidth 2 that require a nonconstant number of intervals, our work demonstrates a class of graphs of treewidth 2, namely 2-trees, that are guaranteed to allow 3-interval routing schemes. In contrast, this paper presents a 2-tree that cannot have a 2-interval routing scheme. For generalk, anyk-tree is shown to have an optimal interval routing scheme using 2k+1intervals per edge.

For any fixed integerk?2, define the class ofk-polygon graphs as the intersection graphs of chords inside a convexk-polygon, where the endpoints of each chord lie on two different sides. The case wherek=2 is degenerate; for our purpose, we view any pair of parallel lines as a 2-polygon. Hence, polygon graphs are all circle graphs. Interest in such graphs arises since a number of intractable problems on circle graphs can be solved in polynomial time onk-polygon graphs, for any fixedk, given a polygon representation of the input graph. In this paper we show that determining whether a given circle graph is ak-polygon graph, for any fixedk, can be solved inO(4kn2) time. The algorithm exploits the structure of a decomposition tree of the input graph and produces ak-polygon representation, if one exists. In contrast, we show that determining the minimum value ofkis NP-complete.

We present two algorithms solving the minimum fill-in problem on circle graphs and on circular-arc graphs in timeO(n3).

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.

In this paper we give, for all constantsk,l, explicit algorithms that, given a graphG=(V,E) with a tree-decomposition ofGwith treewidth at mostl, decide whether the treewidth (or pathwidth) ofGis at mostk, and, if so, find a tree-decomposition (or path-decomposition) ofGof width at mostk, and that useO(|V|) time. In contrast with previous solutions, our algorithms do not rely on non-constructive reasoning and are single exponential inkandl. This result can be combined with a result of B. Reed in“Proceedings of the 24th Annual Symposium on Theory of Computing,” pp. 221?228, 1992, yielding explicitO(nlogn) algorithms for the problem, given a graphG, to determine whether the treewidth (or pathwidth) ofGis at mostk, and, if so, to find a tree- (or path-) decomposition of width at mostk(kconstant). Also, H. L. Bodlaender in“Proceedings of the 25th Annual Symposium on Theory of Computing,” pp. 226?234, 1993 has used the result of this paper to obtain linear time algorithms for these problems. We also show that for all constantsk, there exists a polynomial time algorithm that, when given a graphG=(V,E) with treewidth ?k, computes the pathwidth ofGand a path-decomposition ofGof minimum width.

The graph sandwich problem for property Π is defined as follows: Given two graphs G 1 = ( V , E 1 ) and G 2 = ( V , E 2 ) such that E 1 ⊆ E 2 , is there a graph G = ( V , E ) such that E 1 ⊆ E ⊆ E 2 which satisfies property Π? Such problems generalize recognition problems and arise in various applications. Concentrating mainly on properties characterizing subfamilies of perfect graphs, we give polynomial algorithms for several properties and prove the NP-completeness of others. We describe polynomial time algorithms for threshold graphs, split graphs, and cographs. For the sandwich problem for threshold graphs, the only case in which a previous algorithm existed, we obtain a faster algorithm. NP-completeness proofs are given for comparability graphs, permutation graphs, and several other families. For Eulerian graphs; one Version of the problem is polynomial and another is NP-complete.

Chordal bipartite graphs are exactly those bipartite graphs in which every cycle of length at least six has a chord. The treewidth of a graph G is the smallest maximum cliquesize among all chordal supergraphs of G decreased by one. We present a polynomial time algorithm for the exact computation of the treewidth of all chordal bipartite graphs.

The problems of determining whether an undirected graph G is sequentially edge-connected, whether G has a dominating path, and whether there is a Hamiltonian path in the line graph of G are shown to be equivalent. These problems are NP-hard even if G is bipartite. They can be used to model certain page retrieval problems in relational database systems in which a graph called page connectivity graph is used to represent a join operation. Many page connectivity graphs encountered in practice are forward-convex . In this paper we develop an algorithm that solves the above-mentioned problems in O(| E ( G )|) time for forward-convex graphs G .

We present an algorithm for optimally edge coloring series parallel graphs. We give a linear time implementation, as well as a parallel implementation, of the algorithm that runs in O (log 3 n ) time using O ( n ) processors. The sequential implementation, which is optimal, improves the best-known algorithm. The parallel implementation of the algorithm is the first known NC algorithm for this problem. The algorithm is based on the ear decomposition of a graph (Y. Maon, B. Schieber, and U. Vishkin, Parallel ear decomposition search (EDS) and ST-Numbering in graphs, Theoret. Comput. Sci. 47 (1986), 277-298). Eppstein (Parallel recognition of series-parallel graphs, Inform. Comput. 98 (1992), 41-55) found that any ear decomposition of a series parallel graph is nested . We show constructively that for every biconnected series parallel graph there exists an open ear decomposition, such that its corresponding tree of ears has an O (log n ) depth, and this ear decomposition contains no ear whose endpoints are connected by a single edge in its parent. This result is used to reduce a match in series parallel graphs into a match in outerplanar graphs, and to establish the edge coloring problem of series parallel graphs in NC.

Various parameters of graphs connected to sparse matrix factorization and other applications can be approximated using an algorithm of Leighton et al . that finds vertex separators of graphs. The approximate values of the parameters, which include minimum front size, treewidth, pathwidth, and minimum elimination tree height, are no more than O (log n ) (minimum front size and treewidth) and O (log 2 n ) (pathwidth and minimum elimination tree height) times the optimal values. In addition, we show that unless P = NP there are no absolute approximation algorithms for any of the parameters.

This paper presents a new algorithm for recognizing circle graphs, combining ideas from an earlier circle graph recognition algorithm due to Gabor, Hsu, and Supowit and an algorithm to determine whether a graph can be decomposed by the split decomposition. The result is an O(n2) algorithm for placing chords on the circle when the split decomposition is known. When combined with the result of the companion paper, this gives an O(n2) algorithm for circle graph recognition.

This paper presents a simple divide-and-conquer algorithm for computing the prime tree decomposition of a two-structure. The algorithm runs in O ( n 2 ) time, when n is the number of nodes of the two-structure. A directed or undirected graph is a special case of a two-structure, and the restriction of the decomposition to graphs is known as the modular decomposition or substitution decomposition . The decomposition has applications in solving certain scheduling problems and a number of problems on graphs and partial orders. Two algorithms with a comparable time bound have previously been published for undirected graphs, but they make use of elaborate data structures that limit their practical use, and they have no easy generalization to directed graphs or two-structures.

We consider the problem of finding a small set of edges (an edge separator) whose removal divides a given graph into roughly equal parts. We show that every planar graph with n vertices and a maximum degree k has an O ([formula])-edge separator, which bound is asymptotically optimal. This improves the previously best known upper bound of O ( k [formula]). We prove that the bisection width of the class of planar graphs and trees of n vertices and maximum degree k is O ([formula] and O ( k log n /log k ), respectively, both optimal within a constant factor. All proofs are constructive and yield optimal O ( n ) algorithms. The separator theorems are applied to embed efficiently planar and outerplanar graphs into binary trees, hypercubes, butterfly graphs, CCC graphs, shuffle-exchange graphs, de Brujn graphs, and d -dimensional meshes. The embeddings are shown to be optimal or almost optimal with respect to the average dilation and the expansion of the embedding.

We show how to generate k-regular graphs on n vertices uniformly at random in expected time O(nk3), provided k = O(n 1 3 ) . The algorithm employs a modification of a switching argument previously used to count such graphs asymptotically for k = o(n 1 3 ) . The asymptotic formula is re-derived, using the new switching argument. The method is applied also to graphs with given degree sequences, provided certain conditions are met. In particular, it applies if the maximum degree is O(∥E(G)∥ 1 4 ) . The method is also applied to bipartite 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.

An algorithm is described which generates a random labeled cubic graph on n vertices. Also described is a procedure which, if successful, generates a random (0,1)-matrix with prescribed row and column sums. The latter yields procedures which, if successful, generate random labeled graphs with specified degree sequence and random labeled bipartite graphs with specified degree sequences. These procedures can be implemented so that each trial requires time which is linear in the number of vertices plus edges, but in generating a random r-regular graph, the probability of success of a given trial is about exp ( (1 − r 2 ) 4 ) , which is prohibitively small for large r. Comparisons are made between the complexities of the two methods of generating random cubic graphs. The two general schemes presented derive from methods which have been used to enumerate regular graphs, both asymptotically and exactly.

We consider the problem of finding a minimum size cutset in a directed graph G = (V, E), i.e., a vertex set that cuts all cycles in G. Since the general problem is NP-complete we concentrate on finding small cutsets. The algorithm we suggest uses contraction operations to reduce the graph size and to identify candidates for the cutset; the complexity of the algorithm is O(|E|log|V|). This contraction algorithm is compared to Shamir-Rosen algorithm. It is shown that the class of graphs for which the contraction algorithm finds a minimum cutset (completely contractible graphs) properly contains the class of graphs for which Shamir-Rosen algorithm finds a minimum cutset (quasi-reducible graphs) and thus that the contraction algorithm is more powerful. As a by-product of this analysis we construct a hierarchy of the classes of graphs for which minimum cutsets can be found efficiently. The class of quasi-reducible graphs lies, in this hierarchy, between two classes which are closely related. This result illuminates the nature of the quasi-reducible graphs. The hierarchy constructed allows us also to compare the Wang-Lloyd-Soffa algorithm to the Shamir-Rosen algorithm and to the contraction algorithm.

We present a polynomial-time algorithm for producing a feasible real-valued circulation in undirected graphs with upper and lower bounds, based on Seymour's characterization. For directed graphs, an efficient algorithm follows from a classical result by Hoffman. We show that, for mixed graphs, i.e., graphs having both directed and undirected edges, the problem is NP-complete.