Speeding up dynamic transitive closure for bounded degree graphs

In this paper we present an algorithm for solving two problems in dynamically maintaining the transitive closure of a digraph: In the first problem a sequence of edge insertions is performed on an initially empty graph, interspersed withp transitive closure queries of the form: is there a path froma tob in the graph. Our algorithm solves this problem in timeO (dm ^*+p), whered is the maximum outdegree of the resulting graphG andm ^* is the number of edges in the transitive closure ofG. In the second problem, a sequence of edge deletions is performed on anacyclic graph, interspersed withp transitive closure queries. Once again we solve this problem in timeO (dm ^*+p), whered is the maximum outdegree of the initial graphG andm ^* is the number of edges in the transitive closure ofG. For bounded degree graphs, this improves upon previous results. Our algorithms also work when insertions and deletions to the graph are intermixed. Finally, we show how to implement the operation findpath (x, y) which retrieves some path fromx toy in time proportional to the length of the path.     

Semi-dynamic breadth-first search in digraphs

In this paper we propose dynamic algorithms for maintaining a breadth-first search tree from a given source vertex of a directed graph G in either an incremental or a decremental setting. During a sequence of q edge insertions or a sequence of q edge deletions the total time required is O(m·min{q,n}), where n is the number of vertices of G, and m is the final number of edges of G in the case of insertions or the initial number of edges of G in the case of deletions. This gives O(n) amortized time for each operation if the sequence has length Ω(m). Our algorithms require O(n+m) space. These are the first results in the literature concerning the dynamic maintenance of a breadth-first search tree for directed graphs. As a straightforward application of such algorithms we can maintain a shortest path tree for a directed graph in the case of unit edge weights within the same time bounds. In this case distance queries can be answered in constant time, while shortest path queries can be answered in time linear in the length of the retrieved path.     

Applying Modular Decomposition to Parameterized Cluster Editing Problems

A graph G is said to be a bicluster graph if G is a disjoint union of bicliques (complete bipartite subgraphs), and a cluster graph if G is a disjoint union of cliques (complete subgraphs). In this work, we study the parameterized versions of the NP-hard Bicluster Graph Editing and Cluster Graph Editing problems. The former consists of obtaining a bicluster graph by making the minimum number of modifications in the edge set of an input bipartite graph. When at most k modifications are allowed (Bicluster(k) Graph Editing problem), this problem is FPT, and can be solved in O(4 ^k nm) time by a standard search tree algorithm. We develop an algorithm of time complexity O(4 ^k +n+m), which uses a strategy based on modular decomposition techniques; we slightly generalize the original problem as the input graph is not necessarily bipartite. The algorithm first builds a problem kernel with O(k ²) vertices in O(n+m) time, and then applies a bounded search tree. We also show how this strategy based on modular decomposition leads to a new way of obtaining a problem kernel with O(k ²) vertices for the Cluster(k) Graph Editing problem, in O(n+m) time. This problem consists of obtaining a cluster graph by modifying at most k edges in an input graph. A previous FPT algorithm of time O(1.92 ^k +n ³) for this problem was presented by Gramm et al. (Theory Comput. Syst. 38(4), 373–392, 2005, Algorithmica 39(4), 321–347, 2004). In their solution, a problem kernel with O(k ²) vertices is built in O(n ³) time.     

Bandwidth and pebbling

The main results of this paper establish relationships between the bandwidth of a graphG — which is the minimum over all layouts ofG in a line of the maximum distance between images of adjacent vertices ofG — and the ease of playing various pebble games onG. Three pebble games on graphs are considered: the well-known computational pebble game, the “progressive” (i.e., no recomputation allowed) version of the computational pebble game, both of which are played on directed acyclic graphs, and the quite different “breadth-first” pebble game, that is played on undirected graphs. We consider two costs of a play of a pebble game: the minimum number of pebbles needed to play the game on the graphG, and the maximumlifetime of any pebble in the game, i.e., the maximum number of moves that any pebble spends on the graph. The first set of results of the paper prove that the minimum lifetime cost of a play of either of the second two pebble games on a graphG is precisely the bandwidth ofG. The second set of results establish bounds on the pebble demand of all three pebble games in terms of the bandwidth of the graph being pebbled; for instance, the number of pebbles needed to pebble a graphG of bandwidthk is at most min (2k ²+k+1, 2k log₂|G|); and, in addition, there are bandwidth-k graphs that require 3k?1 pebbles. The third set of results relate the difficulty of deciding the cost of playing a pebble game on a given input graphG to the bandwidth ofG; for instance, the Pebble Demand problem forn-vertex graphs of bandwidthf(n) is in the class NSPACE (f(n) log² n); and the Optimal Lifetime Problem for either of the second two pebble games is NP-complete.     

A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs

In this paper we give a fully dynamic approximation scheme for maintaining all-pairs shortest paths in planar networks. Given an error parameter such that , our algorithm maintains approximate all-pairs shortest paths in an undirected planar graph G with nonnegative edge lengths. The approximate paths are guaranteed to be accurate to within a 1+ factor. The time bounds for both query and update for our algorithm is O( ^-1 n ^2/3 log ² n log D) , where n is the number of nodes in G and D is the sum of its edge lengths. The time bound for the queries is worst case, while that for the additions is amortized. Our approximation algorithm is based upon a novel technique for approximately representing all-pairs shortest paths among a selected subset of the nodes by a sparse substitute graph. Received January 1995; revised February 1997.     

All Structured Programs Have Small Tree Width and Good Register Allocation

The register allocation problem for an imperative program is often modeled as the coloring problem of the interference graph of the control-flow graph of the program. The interference graph of a flow graphGis the intersection graph of some connected subgraphs ofG. These connected subgraphs represent the lives, or life times, of variables, so the coloring problem models that two variables with overlapping life times should be in different registers. For general programs with unrestricted gotos, the interference graph can be any graph, and hence we cannot in general color within a factorO(n) from optimality unless NP=P. It is shown that if a graph has tree widthk, we can efficiently color any intersection graph of connected subgraphs within a factor (k/2+1) from optimality. Moreover, it is shown that structured (≡goto-free) programs, including, for example, short circuit evaluations and multiple exits from loops, have tree width at most 6. Thus, for every structured program, we can do register allocation efficiently within a factor 4 from optimality, regardless of how many registers are needed. The bounded tree decomposition may be derived directly from the parsing of a structured program, and it implies that the many techniques for bounded tree width may now be applied in compiler optimization, solving problems in linear time that are NP-hard, or even P-space hard, for general graphs.     

Coloring inductive graphs on-line

In this paper we consider the problem of on-line graph coloring. In an instance of on-line graph coloring, the nodes are presented one at a time. As each node is presented, its edges to previously presented nodes are also given. Each node must be assigned a color, different from the colors of its neighbors, before the next node is given. LetA(G) be the number of colors used by algorithmA on a graphG and letx(G) be the chromatic number ofG. The performance ratio of an on-line graph coloring algorithm for a class of graphsC is max_{G C(A(G)/(G))}. We consider the class ofd-inductive graphs. A graphG isd-inductive if the nodes ofG can be numbered so that each node has at mostd edges to higher-numbered nodes. In particular, planar graphs are 5-inductive, and chordal graphs arex(G)-inductive. First Fit is the algorithm that assigns each node the lowest-numbered color possible. We show that ifG isd-inductive, then First Fit usesO(d logn) colors onG. This yields an upper bound ofo(logn) on the performance ratio of First Fit on chordal and planar graphs. First Fit does as well as any on-line algorithm ford-inductive graphs: we show that, for anyd and any on-line graph coloring algorithmA, there is ad-inductive graph that forcesA to use (d logn) colors to colorG. We also examine on-line graph coloring with lookahead. An algorithm is on-line with lookaheadl, if it must color nodei after examining only the firstl+i nodes. We show that, forl/logn, the lower bound ofd logn colors still holds.This research was supported by an IBM Graduate Fellowship.     

Cyclic bundle Hamiltonicity

Cyclic bundle Hamiltonicity cbH(G) of a graph G is the minimal n for which there is an automorphism α of G such that the graph bundle C _n □^α G is Hamiltonian. We define an invariant I that is related to the maximal vertex degree of spanning trees suitably involving the symmetries of G and prove cbH(G)≤I≤cbH(G)+1 for any non-trivial connected graph G.     

Floorplanning by graph dualization: L-shaped modules

We propose a novel technique for constructing a floorplan from an adjacency requirement — represented by a graphG. The algorithm finds a geometric dual ofG involving both rectangular and L-shaped modules. This is the first dualization technique which permits L-shaped modules. We can test inO(n ^3/2) time ifG admits an L-shaped dual and construct one, if it exists, inO(n ²) time, wheren is the number of modules.This work was supported in part by the National Science Foundation under Grants MIP-8709074 and MIP-8921540. The research by Yachyang Sun was done while he was with Northwestern University.     

An efficient parallel algorithm for computing a large independent set in a planar graph

Let α(G) denote the independence number of a graphG, that is the maximum number of pairwise independent vertices inG. We present a parallel algorithm that computes in a planar graphG = (V, E), an independent set \(I \subseteq V\) such that ¦I¦≥ α (G)/2. The algorithm runs in timeOlog² n) and requires a linear number of processors. This is achieved by denning a new set of reductions that can be executed “locally” and simultaneously; furthermore, it is shown that a constant fraction of the vertices in the graph are reducible. This is the best known approximation scheme when the number of processors available is linear; parallel implementation of known sequential algorithms requires many more processors.     

Parallel Algorithms for Maximal Acyclic Sets

Given a graph G=(V,E), the well-known spanning forest problem of G can be viewed as the problem of finding a maximal subset F of edges in G such that the subgraph induced by F is acyclic. Although this problem has well-known efficient NC algorithms, its vertex counterpart, the problem of finding a maximal subset U of vertices in G such that the subgraph induced by U is acyclic, has not been shown to be in NC (or even in RNC) and is not believed to be parallelizable in general. In this paper we present NC algorithms for solving the latter problem for two special cases. First, we show that, for a planar graph with n vertices, the problem can be solved in time with O(n) processors on an EREW PRAM. Second, we show that the problem is solvable in NC if the input graph G has only vertex-induced paths of length polylogarithmic in the number of vertices of G. As a consequence of this result, we show that certain natural extensions of the well-studied maximal independent set problem remain solvable in NC. Moreover, we show that, for a constant-degree graph with n vertices, the problem can be solved in time with O(n ² ) processors on an EREW PRAM. Received July 3, 1995; revised April 1, 1996.     

An Approximation Algorithm for the Minimum Co-Path Set Problem

We present an approximation algorithm for the problem of finding a minimum set of edges in a given graph G whose removal from G leaves a graph in which each connected component is a path. It achieves a ratio of \frac 107\frac {10}{7} and runs in O(n ^1.5) time, where n is the number of vertices in the input graph. The previously best approximation algorithm for this problem achieves a ratio of 2 and runs in O(n ²) time.     

Augmenting the Rigidity of a Graph in <Emphasis Type="Italic">R</Emphasis><Superscript>2</Superscript>

Given a Laman graph G, i.e. a minimally rigid graph in R ², we provide a Θ(n ²) algorithm to augment G to a redundantly rigid graph, by adding a minimum number of edges. Moreover, we prove that this problem of augmenting is NP-hard for an arbitrary rigid graph G in R ².     

Orthogonally Drawing Cubic Graphs in Parallel

In this paper we describe a parallel algorithm that, given annvertex cubic graphGas input, outputs an orthogonal drawing ofGwithO(n) bends,O(n) maximum edge length, andO(n²) area inO(log n) time using a CRCW PRAM withnprocessors. We give two slight variants of the algorithm. The first generates a drawing in which each edge has at most 2 bends; the total number of bends and the area are bounded byn+3 and [formula], respectively. The second optimizes the number of bends per edge (at most one) even if the values of the other functions are slightly worst. Despite its nonoptimality, this parallel algorithm is the first dealing with nonplanar, nonbiconnected graphs. Moreover, no embedding of the graph is requested as input nor is anst-numbering (orlmc-numbering) computed.     

Constrained-Path Labellings on Graphs of Bounded Clique-Width

Given a graph G we consider the problem of preprocessing it so that given two vertices x,y and a set X of vertices, we can efficiently report the shortest path (or just its length) between x,y that avoids X. We attach labels to vertices in such a way that this length can be determined from the labels of x,y and the vertices X. For a graph with n vertices of tree-width or clique-width k, we construct labels of size O(k ²log ² n). The constructions extend to directed graphs. The problem is motivated by routing in networks in case of failures or of routing policies which forbid certain paths.     

Parallel Algorithms for the Edge-Coloring and Edge-Coloring Update Problems

LetG(V,E) be a simple undirected graph with a maximum vertex degree Δ(G) (or Δ for short), |V| =nand |E| =m. An edge-coloring ofGis an assignment to each edge inGa color such that all edges sharing a common vertex have different colors. The minimum number of colors needed is denoted by χ′(G) (called thechromatic index). For a simple graphG, it is known that Δ ≤ χ′(G) ≤ Δ + 1. This paper studies two edge-coloring problems. The first problem is to perform edge-coloring for an existing edge-colored graphGwith Δ + 1 colors stemming from the addition of a new vertex intoG. The proposed parallel algorithm for this problem runs inO(Δ^3/2log³Δ + Δ logn) time usingO(max{nΔ, Δ³}) processors. The second problem is to color the edges of a given uncolored graphGwith Δ + 1 colors. For this problem, our first parallel algorithm requiresO(Δ^5.5log³Δ logn+ Δ⁵log⁴n) time andO(max{n²Δ,nΔ³}) processors, which is a slight improvement on the algorithm by H. J. Karloff and D. B. Shmoys [J. Algorithms8 (1987), 39–52]. Their algorithm costsO(Δ⁶log⁴n) time andO(n²Δ) processors if we use the fastest known algorithm for finding maximal independent sets by M. Goldberg and T. Spencer [SIAM J. Discrete Math.2 (1989), 322–328]. Our second algorithm requiresO(Δ^4.5log³Δ logn+ Δ⁴log⁴n) time andO(max{n²,nΔ³}) processors. Finally, we present our third algorithm by incorporating the second algorithm as a subroutine. This algorithm requiresO(Δ^3.5log³Δ logn+ Δ³log⁴n) time andO(max{n²log Δ,nΔ³}) processors, which improves, by anO(Δ^2.5) factor in time, on Karloff and Shmoys' algorithm. All of these algorithms run in the COMMON CRCW PRAM model.     

Communication Complexity of Sum-Type Functions Invariant under Translation

The communication complexity of a function f denotes the number of bits that two processors have to exchange in order to compute f(x, y), when each processor knows one of the variables x and y, respectively. In this paper the deterministic communication complexity of sum-type functions, such as the Hamming distance and the Lee distance, is examined. Here f: X × X → G, where X is a finite set and G is an Abelian group, and the sum-type function f_n:Xⁿ × Xⁿ → G is defined by f_n((x₁, ..., x_n), (y₁, ..., y_n)) = Σⁿ_i=1f(x_i, y_i) Since the functions examined are also translation-invariant, their function matrices are simultaneously diagonalizable and the corresponding eigenvalues can be calculated. This allows to apply a rank lower bound for the communication complexity. The best results are obtained for G = /2 . For prime numbers |X| in this case the communication complexity of all non-trivial sum-type functions is determined exactly. Exact results are also obtained for the parity of the Hamming distance and the parity of the Lee distance. For the Hamming distance and the Lee distance exact results are only obtained for special parameters n and |X|.     

Parallel breadth-first search algorithms for trees and graphs

Parallel Breadth-First Search (BFS) algorithms for ordered trees and graphs on a shared memory model of a Single Instruction-stream Multiple Data-stream computer are proposed. The parallel BFS algorithm for trees computes the BFS rank of eachnode of an ordered tree consisting of n nodes in time of 0(β log n) when 0(n ^1+1/β) processors are used, β being an integer greater than or equal to 2. The parallel BFS algorithm for graphs produces Breadth-First Spanning Trees (BFSTs) of a directedgraph G having n nodes in time 0(log d.log n) using 0(n ³) processors, where d is the diameter of G If G is a strongly connected graph or a connected undirected graph the BFS algorithm produces n BFSTs, each BFST having a different start node.     

Embedding Complete Binary Trees into Star and Pancake Graphs

Let G and H be two simple undirected graphs. An embedding of the graph G into the graph H is an injective mapping f from the vertices of G to the vertices of H . The dilation of the embedding is the maximum distance between f(u),f(v) taken over all edges (u,v) of G . We give a construction of embeddings of dilation 1 of complete binary trees into star graphs. The height of the trees embedded with dilation 1 into the n -dimensional star graph is Ω (n log n) , which is asymptotically optimal. Constructions of embeddings of complete binary trees of dilation 2δ and 2δ +1 , δ≥ 1, into star graphs are given. The use of larger dilation allows embeddings of trees of greater height into star graphs. It is shown that all these constructions can be modified to yield embeddings of dilation 1 and 2δ , δ≥ 1 , of complete binary trees into pancake graphs. Received February 1996, and in final form October 1997.