Polynomial Time Algorithms for 2-Edge-Connectivity Augmentation Problems

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.     

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.     

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.     

Algorithmic Aspects of Acyclic Edge Colorings

Abstract. A proper coloring of the edges of a graph G is called acyclic if there is no two-colored cycle in G . The acyclic edge chromatic number of G , denoted by a'(G) , is the least number of colors in an acyclic edge coloring of G . For certain graphs G , a'(G)\geq Δ(G)+2 where Δ(G) is the maximum degree in G . It is known that a'(G)≤ Δ + 2 for almost all Δ -regular graphs, including all Δ -regular graphs whose girth is at least cΔ log Δ . We prove that determining the acyclic edge chromatic number of an arbitrary graph is an NP-complete problem. For graphs G with sufficiently large girth in terms of Δ(G) , we present deterministic polynomial-time algorithms that color the edges of G acyclically using at most Δ(G)+2 colors.     

Erratum: An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems

Abstract. There is an error in our paper ``An Approximation Algorithm for Minimum-Cost Vertex- Connectivity Problems' (Algorithmica (1997), 18:21—43). In that paper we considered the following problem: given an undirected graph and values r _ij for each pair of vertices i and j , find a minimum-cost set of edges such that there are r _ij vertex-disjoint paths between vertices i and j . We gave approximation algorithms for two special cases of this problem. Our algorithms rely on a primal—dual approach which has led to approximation algorithms for many edge-connectivity problems. The algorithms work in a series of stages; in each stage an augmentation subroutine augments the connectivity of the current solution. The error is in a lemma for the proof of the performance guarantee of the augmentation subroutine. In the case r _ij = k for all i,j , we described a polynomial-time algorithm that claimed to output a solution of cost no more than 2 H (k) times optimal, where H = 1 + 1/2 + · · · + 1/n . This result is erroneous. We describe an example where our primal—dual augmentation subroutine, when augmenting a k -vertex connected graph to a (k+1) -vertex connected graph, gives solutions that are a factor Ω(k) away from the minimum. In the case r _ij ∈ {0,1,2} for all i,j , we gave a polynomial-time algorithm which outputs a solution of cost no more than three times the optimal. In this case we prove that the statement in the lemma that was erroneous for the k -vertex connected case does hold, and that the algorithm performs as claimed.     

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.     

Smallest Bipartite Bridge-Connectivity Augmentation

This paper addresses two augmentation problems related to bipartite graphs. The first, a fundamental graph-theoretical problem, is how to add a set of edges with the smallest possible cardinality so that the resulting graph is 2-edge-connected, i.e., bridge-connected, and still bipartite. The second problem, which arises naturally from research on the security of statistical data, is how to add edges so that the resulting graph is simple and does not contain any bridges. In both cases, after adding edges, the graph can be either a simple graph or, if necessary, a multi-graph. Our approach then determines whether or not such an augmentation is possible. We propose a number of simple linear-time algorithms to solve both problems. Given the well-known bridge-block data structure for an input graph, the algorithms run in O(log n) parallel time on an EREW PRAM using a linear number of processors, where n is the number of vertices in the input graph. We note that there is already a polynomial time algorithm that solves the first augmentation problem related to graphs with a given general partition constraint in O(n(m+nlog n)log n) time, where m is the number of distinct edges in the input graph. We are unaware of any results for the second problem. H.-W. Wei, W.-C. Lu and T.-s. Hsu research supported in part by NSC of Taiwan Grants 94-2213-E-001-014, 95-2221-E-001-004 and 96-2221-E-001-004.     

Competitive Call Control in Mobile Networks

Abstract. In this paper we deal with competitive local on-line algorithms for non-preemptive channel allocation in mobile networks. The signal interferences in a network are modeled using an interference graph G . We prove that the greedy on-line algorithm is Δ -competitive, where Δ is the maximum degree of G . We employ the ``classify and randomly select" paradigm [5], [17], and give a 5 -competitive randomized algorithm for the case of planar interference graphs, a 2 -competitive randomized algorithm for trees, and a (2c) -competitive randomized algorithm for graphs of arboricity c . We also show that the problem of call control in mobile networks with multiple available frequencies reduces to the problem of call control in mobile networks with a single frequency. Using this reduction, we present on-line algorithms for general networks with a single frequency. We give a local on-line algorithm which is (α (δ +1 + α )/(1/2+α ) ² )-competitive, where α is the independence number of G , and δ is the average degree of G . The above results hold in the case when the duration of each request is infinite, and the benefit the algorithm gains by accepting each request is equal to one. They are extended to handle requests of arbitrary durations, and arbitrary benefits.     

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.     

Approximating Minimum-Power Degree and Connectivity Problems

Power optimization is a central issue in wireless network design. Given a graph with costs on the edges, the power of a node is the maximum cost of an edge incident to it, and the power of a graph is the sum of the powers of its nodes. Motivated by applications in wireless networks, we consider several fundamental undirected network design problems under the power minimization criteria. Given a graph G=(V,E)\mathcal{G}=(V,\mathcal{E}) with edge costs {c(e):e∈ℰ} and degree requirements {r(v):v∈V}, the Minimum-Power Edge-Multi-Cover\textsf{Minimum-Power Edge-Multi-Cover} (MPEMC\textsf{MPEMC} ) problem is to find a minimum-power subgraph G of G\mathcal{G} so that the degree of every node v in G is at least r(v). We give an O(log n)-approximation algorithms for MPEMC\textsf{MPEMC} , improving the previous ratio O(log ⁴ n). This is used to derive an O(log n+α)-approximation algorithm for the undirected $\textsf{Minimum-Power $\textsf{Minimum-Power ($\textsf{MP$\textsf{MP ) problem, where α is the best known ratio for the min-cost variant of the problem. Currently, _boxclosen-k)\alpha=O(\log k\cdot \log\frac{n}{n-k}) which is O(log k) unless k=n−o(n), and is O(log ² k)=O(log ² n) for k=n−o(n). Our result shows that the min-power and the min-cost versions of the $\textsf{$\textsf{ problem are equivalent with respect to approximation, unless the min-cost variant admits an o(log n)-approximation, which seems to be out of reach at the moment.     

Approximating Minimum Feedback Sets and Multicuts in Directed Graphs

This paper deals with approximating feedback sets in directed graphs. We consider two related problems: the weighted feedback vertex set (FVS) problem, and the weighted feedback edge set (FES) problem. In the {FVS} (resp. FES) problem, one is given a directed graph with weights (each of which is at least one) on the vertices (resp. edges), and is asked to find a subset of vertices (resp. edges) with minimum total weight that intersects every directed cycle in the graph. These problems are among the classical NP-hard problems and have many applications. We also consider a generalization of these problems: subset-fvs and subset-fes, in which the feedback set has to intersect only a subset of the directed cycles in the graph. This subset consists of all the cycles that go through a distinguished input subset of vertices and edges, denoted by X . This generalization is also NP-hard even when |X|=2 . We present approximation algorithms for the subset-fvs and subset-fes problems. The first algorithm we present achieves an approximation factor of O(log ² |X|) . The second algorithm achieves an approximation factor of O(min{log τ ^* log log τ ^* , log n log log n)} , where τ ^* is the value of the optimum fractional solution of the problem at hand, and n is the number of vertices in the graph. We also define a multicut problem in a special type of directed networks which we call circular networks, and show that the subset-fes and subset-fvs problems are equivalent to this multicut problem. Another contribution of our paper is a combinatorial algorithm that computes a (1+ɛ) approximation to the fractional optimal feedback vertex set. Computing the approximate solution is much simpler and more efficient than general linear programming methods. All of our algorithms use this approximate solution. Received May 31, 1995; revised June 11, 1996, and October 9, 1996.     

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.     

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.     

Reporting Red—Blue Intersections between Two Sets of Connected Line Segments

Abstract. We present a new line sweep algorithm, HEAPSWEEP, for reporting bichromatic (``purple') intersections between a red and a blue family of line segments. If the union of the segments in each family is connected as a point set, HEAPSWEEP reports all k purple intersections in time O((n+k) α(n) log ³ n) , where n is the total number of input segments and α(n) is the nearly constant inverse Ackermann function. To achieve these bounds, the algorithm maintains only partial information about the vertical ordering between curves of the same color, using a new data structure called a kinetic queue . In order to analyze the running time of HEAPSWEEP, we also show that a simple polygon containing a set of n line segments can be partitioned into monotone regions by a set of vertical threads cutting these segments O(n log n) times.     

Property Testing in Bounded Degree Graphs

Abstract. We further develop the study of testing graph properties as initiated by Goldreich, Goldwasser and Ron. Loosely speaking, given an oracle access to a graph, we wish to distinguish the case when the graph has a pre-determined property from the case when it is ``far' from having this property. Whereas they view graphs as represented by their adjacency matrix and measure the distance between graphs as a fraction of all possible vertex pairs, we view graphs as represented by bounded-length incidence lists and measure the distance between graphs as a fraction of the maximum possible number of edges. Thus, while the previous model is most appropriate for the study of dense graphs, our model is most appropriate for the study of bounded-degree graphs. In particular, we present randomized algorithms for testing whether an unknown bounded-degree graph is connected, k -connected (for k>1 ), cycle-free and Eulerian. Our algorithms work in time polynomial in 1/ɛ , always accept the graph when it has the tested property, and reject with high probability if the graph is ɛ -far from having the property. For example, the 2-connectivity algorithm rejects (with high probability) any N -vertex d -degree graph for which more than ɛ dN edges need to be added in order to make the graph 2-edge-connected. In addition we prove lower bounds of Ω(\sqrt N ) on the query complexity of testing algorithms for the bipartite and expander properties.     

The Impact of Social Ignorance on Weighted Congestion Games

We consider weighted linear congestion games, and investigate how social ignorance, namely lack of information about the presence of some players, affects the inefficiency of pure Nash equilibria (PNE) and the convergence rate of the ε-Nash dynamics. To this end, we adopt the model of graphical linear congestion games with weighted players, where the individual cost and the strategy selection of each player only depends on his neighboring players in the social graph. We show that such games admit a potential function, and thus a PNE. Next, we investigate the Price of Anarchy (PoA) and the Price of Stability (PoS) of graphical linear congestion games with respect to the players’ total actual cost. Our main result is that the impact of social ignorance on the PoA and on the PoS is naturally quantified by the independence number α(G) of the social graph G. In particular, we show that the PoA grows roughly as α(G)(α(G)+2), which is essentially tight as long as α(G) does not exceed half the number of players, and that the PoS lies between α(G) and 2α(G). Moreover, we show that the ε-Nash dynamics reaches an α(G)(α(G)+2)-approximate configuration in polynomial time that does not directly depend on the social graph. For unweighted graphical linear games with symmetric strategies, we show that the ε-Nash dynamics reaches an ε-approximate PNE in polynomial time that exceeds the corresponding time for symmetric linear games by a factor at most as large as the number of players.     

Some Aperture-Angle Optimization Problems

Abstract. Let P and Q be two disjoint convex polygons in the plane with m and n vertices, respectively. Given a point x in P , the aperture angle of x with respect to Q is defined as the angle of the cone that: (1) contains Q , (2) has apex at x and (3) has its two rays emanating from x tangent to Q . We present algorithms with complexities O(n log m) , O(n + n log (m/n)) and O(n + m) for computing the maximum aperture angle with respect to Q when x is allowed to vary in P . To compute the minimum aperture angle we modify the latter algorithm obtaining an O(n + m) algorithm. Finally, we establish an Ω(n + n log (m/n)) time lower bound for the maximization problem and an Ω(m + n) bound for the minimization problem thereby proving the optimality of our algorithms.     

Efficient algorithms for constructing (1+∊,β)-spanners in the distributed and streaming models

For an unweighted undirected graph G = (V,E), and a pair of positive integers α ≥ 1, β ≥ 0, a subgraph G′ = (V,H), H ⊂eqE, is called an (α,β)-spanner of G if for every pair of vertices u,v ∊ V, dist_G′(u,v) ≤ α ⋅ dist_G(u,v) + β. It was shown in [21] that for any ∊ > 0, κ = 1,2,…, there exists an integer β = β(∊,κ) such that for every n-vertex graph G there exists a (1+∊,β)-spanner G′ with O(n^1+1/κ) edges. An efficient distributed protocol for constructing (1+∊,β)-spanners was devised in [19]. The running time and the communication complexity of that protocol are O(n^1+ρ) and O(|E|n^ρ), respectively, where ρ is an additional control parameter of the protocol that affects only the additive term β. In this paper we devise a protocol with a drastically improved running time (O(n^ρ) as opposed to O(n^1+ρ)) for constructing (1+∊,β)-spanners. Our protocol has the same communication complexity as the protocol of [19], and it constructs spanners with essentially the same properties as the spanners that are constructed by the protocol of [19]. The protocol can be easily extended to a parallel implementation which runs in O(log n + (|E|⋅ n^ρlog n)/p) time using p processors in the EREW PRAM model. In particular, when the number of processors, p, is at least |E|⋅ n^ρ, the running time of the algorithm is O(log n). We also show that our protocol for constructing (1+∊,β)-spanners can be adapted to the streaming model, and devise a streaming algorithm that uses a constant number of passes and O(n^1+1/κ⋅ {log} n) bits of space for computing all-pairs-almost-shortest-paths of length at most by a multiplicative factor (1+∊) and an additive term of β greater than the shortest paths. Our algorithm processes each edge in time O(n^ρ), for an arbitrarily small ρ > 0. The only previously known algorithm for the problem [23] constructs paths of length κ times greater than the shortest paths, has the same space requirements as our algorithm, but requires O(n^1+1/κ) time for processing each edge of the input graph. However, the algorithm of [23] uses just one pass over the input, as opposed to the constant number of passes in our algorithm. We also show that any streaming algorithm for o(n)-approximate distance computation requires Ω(n) bits of space. This work was Supported by the DoD University Research Initiative (URI) administered by the Office of Naval Research under Grant N00014-01-1-0795. Michael Elkin was supported by ONR grant N00014-01-1-0795. Jian Zhang was supported by ONR grant N00014-01-1-0795 and NSF grants CCR-0105337 and ITR-0331548. Preliminary version of this paper was published in PODC’04, see [22]. After the preliminary version of our paper [22] appeared on PODC’04, Feigenbaum et al. [24] came up with a new streaming algorithm for the problem that is far more efficient than [23] in terms of time-per-edge processing. However, our algorithm is still the only existing streaming algorithm that provides an almost additive approximation of distances.     

An $\tilde{O}(m^{2}n)$ Algorithm for Minimum Cycle Basis of Graphs

We consider the problem of computing a minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Minimum cycle basis are useful in a number of contexts, e.g. the analysis of electrical networks and structural engineering. The previous best algorithm for computing a minimum cycle basis has running time O(m ^ω n), where ω is the best exponent of matrix multiplication. It is presently known that ω<2.376. We exhibit an O(m ² n+mn ²log n) algorithm. When the edge weights are integers, we have an O(m ² n) algorithm. For unweighted graphs which are reasonably dense, our algorithm runs in O(m ^ω ) time. For any ε>0, we also design an 1+ε approximation algorithm. The running time of this algorithm is O((m ^ω /ε)log (W/ε)) for reasonably dense graphs, where W is the largest edge weight. A preliminary version of this paper appeared in Kavitha et al. (31st International Colloquium on Automata, Languages and Programming (ICALP), pp. 846–857, 2004). T. Kavitha and K.E. Paluch were in Max-Planck-Institut für Informatik, Saarbrücken, Germany, while this work was done.