Polynomial Time Algorithms for 2-Edge-Connectivity Augmentation Problems

Abstract. Given a 2-edge-connected, real weighted graph G with n vertices and m edges, the 2-edge-connectivity augmentation problem is that of finding a minimum weight set of edges of G to be added to a spanning subgraph H of G to make it 2-edge-connected. While the general problem is NP-hard and 2 -approximable, in this paper we prove that it becomes polynomial time solvable if H is a depth-first search tree of G . More precisely, we provide an efficient algorithm for solving this special case which runs in O (M · α(M,n)) time, where α is the classic inverse of Ackermann's function and M=m · α(m,n) . This algorithm has two main consequences: first, it provides a faster 2 -approximation algorithm for the general 2 -edge-connectivity augmentation problem; second, it solves in O (m · α(m,n)) time the problem of restoring, by means of a minimum weight set of replacement edges, the 2 -edge-connectivity of a 2-edge-connected communication network undergoing a link failure.     

Maintaining the Classes of 4-Edge-Connectivity in a Graph On-Line

Two vertices of an undirected graph are called k -edge-connected if there exist k edge-disjoint paths between them (equivalently, they cannot be disconnected by the removal of less than k edges from the graph). Equivalence classes of this relation are called classes of k -edge-connectivity or k -edge-connected components. This paper describes graph structures relevant to classes of 4 -edge-connectivity and traces their transformations as new edges are inserted into the graph. Data structures and an algorithm to maintain these classes incrementally are given. Starting with the empty graph, any sequence of q Same-4-Class? queries and n Insert-Vertex and m Insert-Edge updates can be performed in O(q + m + n log n) total time. Each individual query requires O(1) time in the worst-case. In addition, an algorithm for maintaining the classes of k -edge-connectivity (k arbitrary) in a (k-1) -edge-connected graph is presented. Its complexity is O(q + m + n) , with O(M +k ² n log (n/k)) preprocessing, where M is the number of edges initially in the graph and n is the number of its vertices. Received July 5, 1995; revised October 21, 1996.     

Fully dynamic maintenance of k-connectivity in parallel

Given a graph G=(V, E) with n vertices and m edges, the k-connectivity of G denotes either the k-edge connectivity or the k-vertex connectivity of G. In this paper, we deal with the fully dynamic maintenance of k-connectivity of G in the parallel setting for k=2, 3. We study the problem of maintaining k-edge/vertex connected components of a graph undergoing repeatedly dynamic updates, such as edge insertions and deletions, and answering the query of whether two vertices are included in the same k-edge/vertex connected component. Our major results are the following: (1) An NC algorithm for the 2-edge connectivity problem is proposed, which runs in O(log n log(m/n)) time using O(n^3/4) processors per update and query. (2) It is shown that the biconnectivity problem can be solved in O(log^{2 n} ) time using O(nα(2n, n)/logn) processors per update and O(1) time with a single processor per query or in O(log n log_n/^m) time using O(nα(2n, n)/log n) processors per update and O(logn) time using O(nα(2n, n)/logn) processors per query, where α(.,.) is the inverse of Ackermann's function. (3) An NC algorithm for the triconnectivity problem is also derived, which takes O(log n log_n/^m+logn log log n/α(3n, n)) time using O(nα(3n, n)/log n) processors per update and O(1) time with a single processor per query. (4) An NC algorithm for the 3-edge connectivity problem is obtained, which has the same time and processor complexities as the algorithm for the triconnectivity problem. To the best of our knowledge, the proposed algorithms are the first NC algorithms for the problems using O(n) processors in contrast to Ω(m) processors for solving them from scratch. In particular, the proposed NC algorithm for the 2-edge connectivity problem uses only O(n^3/4) processors. All the proposed algorithms run on a CRCW PRAM     

Reconstructing a Minimum Spanning Tree after Deletion of Any Node

Abstract. Updating a minimum spanning tree (MST) is a basic problem for communication networks. In this paper we consider single node deletions in MSTs. Let G=(V,E) be an undirected graph with n nodes and m edges, and let T be the MST of G . For each node v in V , the node replacement for v is the minimum weight set of edges R(v) that connect the components of T-v . We present a sequential algorithm and a parallel algorithm that find R(v) for all V simultaneously. The sequential algorithm takes O(m log n) time, but only O(m α (m,n)) time when the edges of E are presorted by weight. The parallel algorithm takes O(log ² n) time using m processors on a CREW PRAM.     

Reconstructing a Minimum Spanning Tree after Deletion of Any Node

Abstract. Updating a minimum spanning tree (MST) is a basic problem for communication networks. In this paper we consider single node deletions in MSTs. Let G=(V,E) be an undirected graph with n nodes and m edges, and let T be the MST of G . For each node v in V , the node replacement for v is the minimum weight set of edges R(v) that connect the components of T-v . We present a sequential algorithm and a parallel algorithm that find R(v) for all V simultaneously. The sequential algorithm takes O(m log n) time, but only O(m α (m,n)) time when the edges of E are presorted by weight. The parallel algorithm takes O(log ² n) time using m processors on a CREW PRAM.     

Nearly Linear Time Minimum Spanning Tree Maintenance for Transient Node Failures

Given a 2-node connected, real weighted, and undirected graph $G=(V,E)$, with $n$ nodes and $m$ edges, and given a minimum spanning tree (MST) $T=(V,E_T)$ of $G$, we study the problem of finding, for every node $v \in V$, a set of replacement edges which can be used for constructing an MST of $G-v$ (i.e., the graph $G$ deprived of $v$ and all its incident edges). We show that this problem can be solved on a pointer machine in ${\cal O}(m \cdot \alpha(m,n))$ time and ${\cal O}(m)$ space, where $\alpha$ is the functional inverse of Ackermanns function. Our solution improves over the previously best known ${\cal O}(\min\{m \cdot \alpha(n,n), m + n \log n\})$ time bound, and allows us to close the gap existing with the fastest solution for the edge-removal version of the problem (i.e., that of finding, for every edge $e \in E_T$, a replacement edge which can be used for constructing an MST of $G-e=(V,E \backslash \{e\})$). Our algorithm finds immediate application in maintaining MST-based communication networks undergoing temporary node failures. Moreover, in a distributed environment in which nodes are managed by selfish agents, it can be used to design an efficient, truthful mechanism for building an MST.     

A new parallel and distributed shortest path algorithm forhierarchically clustered data networks

This paper presents new efficient shortest path algorithms to solve single origin shortest path problems (SOSP problems) and multiple origins shortest path problems (MOSP problems) for hierarchically clustered data networks. To solve an SOSP problem for a network with n nodes, the distributed version of our algorithm reaches the time complexity of O(log(n)), which is less than the time complexity of O(log ² (n)) achieved by the best existing algorithm. To solve an MOSP problem, our algorithm minimizes the needed computation resources, including computation processors and communication links for the computation of each shortest path so that we can achieve massive parallelization. The time complexity of our algorithm for an MOSP problem is O(m log(n)), which is much less than the time complexity of O(M log² (0)) of the best previous algorithm. Here, M is the number of the shortest paths to be computed and m is a positive number related to the network topology and the distribution of the nodes incurring communications, m is usually much smaller than M. Our experiment shows that m is almost a constant when the network size increases. Accordingly, our algorithm is significantly faster than the best previous algorithms to solve MOSP problems for large data networks     

Solving the 2-Disjoint Paths Problem in Nearly Linear Time

Given four distinct vertices s₁,s₂,t₁, and t₂ of a graph G, the 2-disjoint paths problem is to determine two disjoint paths, p₁ from s₁ to t₁ and p₂ from s₂ to t₂, if such paths exist. Disjoint can mean vertex- or edge-disjoint. Both, the edge- and the vertex-disjoint version of the problem, are NP-hard in the case of directed graphs. For undirected graphs, we show that the O(mn)-time algorithm of Shiloach can be modified to solve the 2-vertex-disjoint paths problem in only O(n + mα(m,n)) time, where m is the number of edges in G, n is the number of vertices in G, and where α denotes the inverse of the Ackermann function. Our result also improves the running time for the 2-edge-disjoint paths problem on undirected graphs as well as the running times for the 2-vertex- and the 2-edge-disjoint paths problem on dags.     

The Linear Arrangement Problem Parameterized Above Guaranteed Value

A linear arrangement (LA) is an assignment of distinct integers to the vertices of a graph. The cost of an LA is the sum of lengths of the edges of the graph, where the length of an edge is defined as the absolute value of the difference of the integers assigned to its ends. For many application one hopes to find an LA with small cost. However, it is a classical NP-complete problem to decide whether a given graph G admits an LA of cost bounded by a given integer. Since every edge of G contributes at least one to the cost of any LA, the problem becomes trivially fixed-parameter tractable (FPT) if parameterized by the upper bound of the cost. Fernau asked whether the problem remains FPT if parameterized by the upper bound of the cost minus the number of edges of the given graph; thus whether the problem is FPT "parameterized above guaranteed value." We answer this question positively by deriving an algorithm which decides in time O(m + n + 5.88^k) whether a given graph with m edges and n vertices admits an LA of cost at most m + k (the algorithm computes such an LA if it exists). Our algorithm is based on a procedure which generates a problem kernel of linear size in linear time for a connected graph G. We also prove that more general parameterized LA problems stated by Serna and Thilikos are not FPT, unless P = NP.     

A Fixed-Parameter Approach to 2-Layer Planarization

A bipartite graph is biplanar if the vertices can be placed on two parallel lines (layers) in the plane such that there are no edge crossings when edges are drawn as line segments between the layers. In this paper we study the 2-Layer Planarization problem: Can k edges be deleted from a given graph G so that the remaining graph is biplanar? This problem is NP-complete, and remains so if the permutation of the vertices in one layer is fixed (the 1-Layer Planarization problem). We prove that these problems are fixed-parameter tractable by giving linear-time algorithms for their solution (for fixed k). In particular, we solve the 2-Layer Planarization problem in O(k · 6^k + |G|) time and the 1-Layer Planarization problem in O(3^k · |G|) time. We also show that there are polynomial-time constant-approximation algorithms for both problems.     

An Algorithm for Minimum Cost Arc-Connectivity Orientations

Given a 2k-edge-connected undirected graph, we consider to find a minimum cost orientation that yields a k-arc-connected directed graph. This minimum cost k-arc-connected orientation problem is a special case of the submodular flow problem. Frank (1982) devised a combinatorial algorithm that solves the problem in O(k ² n ³ m) time, where n and m are the numbers of vertices and edges, respectively. Gabow (1995) improved Frank’s algorithm to run in O(kn ² m) time by introducing a new sophisticated data structure. We describe an algorithm that runs in O(k ³ n ³+kn ² m) time without using sophisticated data structures. In addition, we present an application of the algorithm to find a shortest dijoin in O(n ² m) time, which matches the current best bound.     

A Flexible Algorithm for Generating All the Spanning Trees in Undirected Graphs

In this paper we propose an algorithm for generating all the spanning trees in undirected graphs. The algorithm requires O (n+m+ τ n) time where the given graph has n vertices, m edges, and τ spanning trees. For outputting all the spanning trees explicitly, this time complexity is optimal. Our algorithm follows a special rooted tree structure on the skeleton graph of the spanning tree polytope. The rule by which the rooted tree structure is traversed is irrelevant to the time complexity. In this sense, our algorithm is flexible. If we employ the depth-first search rule, we can save the memory requirement to O (n+m). A breadth-first implementation requires as much as O (m+ τ n) space, but when a parallel computer is available, this might have an advantage. When a given graph is weighted, the best-first search rule provides a ranking algorithm for the minimum spanning tree problem. The ranking algorithm requires O (n+ m + τ n) time and O (m+ τ n) space when we have a minimum spanning tree. Received January 21, 1995; revised February 19, 1996.     

Detecting Holes and Antiholes in Graphs

In this paper we study the problems of detecting holes and antiholes in general undirected graphs, and we present algorithms for these problems. For an input graph G on n vertices and m edges, our algorithms run in O(n + m²) time and require O(n m) space; we thus provide a solution to the open problem posed by Hayward et al. asking for an O(n⁴)-time algorithm for finding holes in arbitrary graphs. The key element of the algorithms is the use of the depth-first-search traversal on appropriate auxiliary graphs in which moving between any two adjacent vertices is equivalent to walking along a P₄ (i.e., a chordless path on four vertices) of the input graph or on its complement, respectively. The approach can be generalized so that for a fixed constant k ≥ 5 we obtain an O(n^k-1)-time algorithm for the detection of a hole (antihole resp.) on at least k vertices. Additionally, we describe a different approach which allows us to detect antiholes in graphs that do not contain chordless cycles on five vertices in O(n + m²) time requiring O(n + m) space. Again, for a fixed constant k ≥ 6, the approach can be extended to yield O(n^k-2)-time and O(n²)-space algorithms for detecting holes (antiholes resp.) on at least k vertices in graphs which do not contain holes (antiholes resp.) on k - 1 vertices. Our algorithms are simple and can be easily used in practice. Finally, we also show how our detection algorithms can be augmented so that they return a hole or an antihole whenever such a structure is detected in the input graph; the augmentation takes O(n + m) time and space.     

An Optimal Parallel Co-Connectivity Algorithm

In this paper we consider the problem of computing the connected components of the complement of a given graph. We describe a simple sequential algorithm for this problem, which works on the input graph and not on its complement, and which for a graph on n vertices and m edges runs in optimal O(n+m) time. Moreover, unlike previous linear co-connectivity algorithms, this algorithm admits efficient parallelization, leading to an optimal O(log n)-time and O((n+m)log n)-processor algorithm on the EREW PRAM model of computation. It is worth noting that, for the related problem of computing the connected components of a graph, no optimal deterministic parallel algorithm is currently available. The co-connectivity algorithms find applications in a number of problems. In fact, we also include a parallel recognition algorithm for weakly triangulated graphs, which takes advantage of the parallel co-connectivity algorithm and achieves an O(log² n) time complexity using O((n+m²) log n) processors on the EREW PRAM model of computation.     

Augmenting the Edge Connectivity of Planar Straight Line Graphs to Three

We characterize the planar straight line graphs (Pslgs) that can be augmented to 3-connected and 3-edge-connected Pslgs, respectively. We show that if a Pslg with n vertices can be augmented to a 3-edge-connected Pslg, then at most 2n−2 new edges are always sufficient and sometimes necessary for the augmentation. If the input Pslg is, in addition, already 2-edge-connected, then n−2 new edges are always sufficient and sometimes necessary for the augmentation to a 3-edge-connected Pslg.     

Augmenting the Connectivity of Outerplanar Graphs

We provide an optimal algorithm for the problem of augmenting an outerplanar graph G by adding a minimum number of edges in such a way that the augmented graph G′ is outerplanar and 2-connected. We also solve optimally the same problem when instead we require G′ to be 2-edge-connected.     

Approximating Unweighted Connectivity Problems in Parallel

Given an integer k and a k-edge-connected graph G=(V, E), we wish to find an E′E of minimum size such that the graph (V, E′) is k-edge-connected. This problem is NP-hard and the best performance ratio achieved by known NC approximation algorithms is 2. For the special case where the input integer k is fixed to be 2, it is known that a performance ratio of 1.5+ε for any ε>0 can be achieved by an NC approximation algorithm. This paper considers the more general case where k is polylogarithmic in the size of the input graph, and presents the first NC approximation algorithm with a performance ratio of 1.924 for this case. We also consider the vertex analogue of this problem in which we require k-vertex-connectivity instead of k-edge-connectivity. We present the first NC approximation algorithm with a performance ratio of 1.931 for the special case where the input integer k is fixed to be 3.     

Matching Polyhedral Terrains Using Overlays of Envelopes

For a collection $\F$ of $d$-variate piecewise linear functions of overall combinatorial complexity $n$, the lower envelope $\E(\F)$ of $\F$ is the pointwise minimum of these functions. The minimization diagram $\M(\F)$ is the subdivision of $\reals^d$ obtained by vertically (i.e., in direction $x_{d+1}$) projecting $\E(\F)$. The overlay $\O(\F,\G)$ of two such subdivisions $\M(\F)$ and $\M(\G)$ is their superposition. We extend and improve the analysis of de Berg et al. \cite{bgh-vdt3s-96} by showing that the combinatorial complexity of $\O(\F,\G)$ is $\Omega(n^d \alpha^{2}(n))$ and $O(n^{d+\eps})$ for any $\eps>0$ when $d \ge 2$, and $O(n^2 \alpha(n) \log n)$ when $d=2$. We also describe an algorithm that constructs $\O(\F,\G)$ in this time. We apply these results to obtain efficient general solutions to the problem of matching two polyhedral terrains in higher dimensions under translation. That is, given two piecewise linear terrains of combinatorial complexity $n$ in $\reals^{d+1}$, we wish to find a translation of the first terrain that minimizes its distance to the second, according to some distance measure. For the perpendicular distance measure, which we adopt from functional analysis since it is natural for measuring the similarity of terrains, we present a matching algorithm that runs in time $O(n^{2d+\eps})$ for any $\eps>0$. Sharper running time bounds are shown for $d \le 2$. For the directed and undirected \Hd\ distance measures, we present a matching algorithm that runs in time $O(n^{d^2+d+\eps})$ for any $\eps>0$.     

A Simple and Fast Min-Cut Algorithm

We present an algorithm which calculates a minimum cut and its weight in an undirected graph with nonnegative real edge weights, n vertices and m edges, in time O(max(log n, min(m/n,δ_G/ε)) n²), where ε is the minimal edge weight, and δ_G is the minimal weighted degree. For integer edge weights this time is further improved to O(δ_G n²) and O(λ_G n²). In both cases these bounds are improvements of the previously known best bounds of deterministic algorithms. These were O(nm + n² log n) for real edge weights and O(nM + n²) and O(M + λ_G n²) for integer weights, where M is the sum of all edge weights.     

确定两个任意简单多边形空间关系的算法

阐述了把简单多边形的边分为奇偶边的新思想,根据一多边形的边与另一多边形的拓朴关系,划分边为5种拓朴类型:内边、外边、重叠边、相交边、复杂边,进而给出了确定两个多边形空间关系的算法,算法的时间复杂度为O((n+m)log(n+m)),其中n、m分别是两输入多边形的顶点数。该算法建立在数学理论基础之上,没有奇异情况需要处理,易于编程实现。算法的主要思想对确定两个简单多面体空间关系亦有参考价值。