We address long-standing open questions raised by Williamson, Goemans, Vazirani and Mihail pertaining to the design of approximation algorithms for problems in network design via the primal-dual method (Combinatorica 15(3):435-454, 1995). Williamson et al. prove an approximation ratio of two for connectivity augmentation problems where the connectivity requirements can be specified by uncrossable functions. They state: "Extending our algorithm to handle non-uncrossable functions remains a challenging open problem. The key feature of uncrossable functions is that there exists an optimal dual solution which is laminar... A larger open issue is to explore further the power of the primal-dual approach for obtaining approximation algorithms for other combinatorial optimization problems." Our main result proves a 16-approximation ratio via the primal-dual method for a class of functions that generalizes the notion of an uncrossable function. There exist instances that can be handled by our methods where none of the optimal dual solutions have a laminar support. We present applications of our main result to three network-design problems. 1) A 16-approximation algorithm for augmenting the family of small cuts of a graph G. The previous best approximation ratio was O(log |V(G)|). 2) A 16⋅⌈k/u_min⌉-approximation algorithm for the Cap-k-ECSS problem which is as follows: Given an undirected graph G = (V,E) with edge costs c ∈ ℚ_{≥0}^E and edge capacities u ∈ ℤ_{≥0}^E, find a minimum cost subset of the edges F ⊆ E such that the capacity across any cut in (V,F) is at least k; u_min (respectively, u_max) denote the minimum (respectively, maximum) capacity of an edge in E, and w.l.o.g. u_max ≤ k. The previous best approximation ratio was min(O(log|V|), k, 2u_max). 3) A 20-approximation algorithm for the model of (p,2)-Flexible Graph Connectivity. The previous best approximation ratio was O(log|V(G)|), where G denotes the input graph.

Abstract. We present a [Formula: see text]-approximation algorithm for the matching augmentation problem (MAP): given a multigraph with edges of cost either zero or one such that the edges of cost zero form a matching, find a 2-edge connected spanning subgraph (2-ECSS) of minimum cost. A [Formula: see text]-approximation algorithm for the same problem was presented recently; see Cheriyan et al. [ Math. Program., 182 (2020), pp. 315–354]. Our improvement is based on new algorithmic techniques, and some of these may lead to advances on related problems.

Given a connected undirected graph $\overline{G}$ on $n$ vertices and nonnegative edge costs $c$, the $\ensuremath{{2ECM}}$ problem is that of finding a 2-edge connected spanning multisubgraph of $\overline{G}$ of minimum cost. The natural linear program (LP) for $\ensuremath{{2ECM}}$, which coincides with the subtour LP for the traveling salesman problem on the metric closure of $\overline{G}$, gives a lower bound on the optimal cost. For instances where this LP is optimized by a half-integral solution $x$, Carr and Ravi (1998) showed that the integrality gap is at most $\frac43$: they show that the vector $\frac43 x$ dominates a convex combination of incidence vectors of 2-edge connected spanning multisubgraphs of $\overline{G}$. We present a simpler proof of the result due to Carr and Ravi by applying an extension of Lovász's splitting-off theorem. Our proof naturally leads to a $\frac43$-approximation algorithm for half-integral instances. Given a half-integral solution $x$ to the LP for $\ensuremath{{2ECM}}$, we give an $O(n^2)$-time algorithm to obtain a 2-edge connected spanning multisubgraph of $\overline{G}$ with cost at most $\frac43 c^T x$. We also consider a related problem of finding a cheap 2-edge connected spanning subgraph of a 3-regular, 3-edge connected graph $G = (V,E)$ with arbitrary edge costs $c$. We give a polynomial-time Las Vegas algorithm that finds a random 2-edge connected spanning subgraph $H$ of $G$ whose expected cost, $\mathbb{E}\left[{c(H)}\right]$, is at most $\frac45 c(E)$.

We present approximation algorithms for several network design problems in the model of Flexible Graph Connectivity (Adjiashvili, Hommelsheim and Mühlenthaler, "Flexible Graph Connectivity", Math. Program. pp. 1-33 (2021), IPCO 2020: pp. 13-26). In an instance of the Flexible Graph Connectivity (FGC) problem, we have an undirected connected graph G = (V,E), a partition of E into a set of safe edges S and a set of unsafe edges U, and nonnegative costs {c_e}_{e ∈ E} on the edges. A subset F ⊆ E of edges is feasible for FGC if for any unsafe edge e ∈ F ∩ U, the subgraph (V,F⧵{e}) is connected. The algorithmic goal is to find a (feasible) solution F that minimizes c(F) = ∑_{e ∈ F} c_e. We present a simple 2-approximation algorithm for FGC via a reduction to the minimum-cost r-out 2-arborescence problem. This improves upon the 2.527-approximation algorithm of Adjiashvili et al. For integers p ≥ 1 and q ≥ 0, the (p,q)-FGC problem is a generalization of FGC where we seek a minimum-cost subgraph H = (V,F) that remains p-edge connected against the failure of any set of at most q unsafe edges; that is, for any set F' ⊆ U with |F'| ≤ q, H-F' = (V, F ⧵ F') should be p-edge connected. Note that FGC corresponds to the (1,1)-FGC problem. We give approximation algorithms for two important special cases of (p,q)-FGC: (a) Our 2-approximation algorithm for FGC extends to a (k+1)-approximation algorithm for the (1,k)-FGC problem. (b) We present a 4-approximation algorithm for the (k,1)-FGC problem. For the unweighted FGC problem, where each edge has unit cost, we give a 16/11-approximation algorithm. This improves on the result of Adjiashvili et al. for this problem. The (p,q)-FGC model with p = 1 or q ≤ 1 can be cast as the Capacitated k-Connected Subgraph problem which is a special case of the well-known Capacitated Network Design problem. We denote the former problem by Cap-k-ECSS. An instance of this problem consists of an undirected graph G = (V,E), nonnegative integer edge-capacities {u_e}_{e ∈ E}, nonnegative edge-costs {c_e}_{e ∈ E}, and a positive integer k. The goal is to find a minimum-cost edge-set F ⊆ E such that every (non-trivial) cut of the capacitated subgraph H(V,F,u) has capacity at least k. We give a min(k, 2max_{e ∈ E} u_e)-approximation algorithm for this problem.

We present a $\frac53$-approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost zero form a matching, find a 2-edge connected spanning subgraph (2-ECSS) of minimum cost. A $\frac74$-approximation algorithm for the same problem was presented recently, see Cheriyan, et al., "The matching augmentation problem: a $\frac{7}{4}$-approximation algorithm," {\em Math. Program.}, 182(1):315--354, 2020; arXiv:1810.07816. Our improvement is based on new algorithmic techniques, and some of these may lead to advances on related problems.

Given a connected undirected graph $\bar{G}$ on $n$ vertices, and non-negative edge costs $c$, the 2ECM problem is that of finding a $2$-edge~connected spanning multisubgraph of $\bar{G}$ of minimum cost. The natural linear program (LP) for 2ECM, which coincides with the subtour LP for the Traveling Salesman Problem on the metric closure of $\bar{G}$, gives a lower bound on the optimal cost. For instances where this LP is optimized by a half-integral solution $x$, Carr and Ravi (1998) showed that the integrality gap is at most $\frac43$: they show that the vector $\frac43 x$ dominates a convex combination of incidence vectors of $2$-edge connected spanning multisubgraphs of $\bar{G}$. We present a simpler proof of the result due to Carr and Ravi by applying an extension of Lov\'{a}sz's splitting-off theorem. Our proof naturally leads to a $\frac43$-approximation algorithm for half-integral instances. Given a half-integral solution $x$ to the LP for 2ECM, we give an $O(n^2)$-time algorithm to obtain a $2$-edge connected spanning multisubgraph of $\bar{G}$ whose cost is at most $\frac43 c^T x$.

We present a 6-approximation algorithm for the minimum-cost $k$-node connected spanning subgraph problem, assuming that the number of nodes is at least $k^3(k-1)+k$. We apply a combinatorial preprocessing, based on the Frank--Tardos algorithm for $k$-outconnectivity, to transform any input into an instance such that the iterative rounding method gives a 2-approximation guarantee. This is the first constant factor approximation algorithm even in the asymptotic setting of the problem, that is, the restriction to instances where the number of nodes is lower bounded by a function of $k$.

The Directed Steiner Tree (DST) problem is a cornerstone problem in network design. We focus on the generalization of the problem with higher connectivity requirements. The problem with one root and two sinks is APX-hard. The problem with one root and many sinks is as hard to approximate as the directed Steiner forest problem, and the latter is well known to be as hard to approximate as the label cover problem. Utilizing previous techniques, we strengthen these results and extend them to undirected graphs. Specifically, we give an Ω( k ϵ ) hardness bound for the rooted k -connectivity problem in undirected graphs. As a consequence, we obtain an Ω( k ϵ ) hardness bound for the undirected subset k -connectivity problem. Additionally, we give a result on the integrality ratio of the natural linear programming relaxation of the directed rooted k -connectivity problem.

We present a 6-approximation algorithm for the minimum-cost k-node connected spanning sub graph problem, assuming that the number of nodes is at least k3(k-1)+k. We apply a combinatorial preprocessing, based on the Frank-Tardos algorithm for k-out connectivity, to transform any input into an instance such that the iterative rounding method gives a 2-approximation guarantee. This is the first constant-factor approximation algorithm even in the asymptotic setting of the problem, that is, the restriction to instances where the number of nodes is lower bounded by a function of k.

In the minimum-cost $k\hbox{-}(S,T)$ connected digraph (abbreviated as $k\hbox{-}(S,T)$ connectivity) problem we are given a positive integer $k$, a directed graph $G=(V,E)$ with nonnegative costs on the edges, and two subsets $S,T$ of $V$; the goal is to find a subset of edges $\widehat{E}$ of minimum cost such that the subgraph $(V,\widehat{E})$ has $k$ edge-disjoint directed paths from each vertex in $S$ to each vertex in $T$. Most of our results focus on a specialized version of the problem that we call the standard version, where every edge of positive cost has its tail in $S$ and its head in $T$. This version of the problem captures NP-hard problems such as the minimum-cost $k$-vertex connected spanning subgraph problem. We give an approximation algorithm with a guarantee of $O((\log{k})(\log{n}))$ for the standard version of the $k\hbox{-}(S,T)$ connectivity problem, where $n$ denotes the number of vertices. For $k=1$, we give a simple 2-approximation algorithm that generalizes a well-known 2-approximation algorithm for the minimum-cost strongly connected spanning subgraph problem. For $k=2$, we give a 3-approximation algorithm; this matches the best approximation guarantee known for the special case of the minimum-cost $2$-vertex connected spanning subgraph problem. Besides the standard version, we study another version that is intermediate between the standard version and the problem in its full generality. In the relaxed version of the $(S,T)$ connectivity problem, each edge of positive cost has its head in $T$ but there is no restriction on the tail. We study the relaxed version with the connectivity parameter $k$ fixed at one and observe that this version is at least as hard to approximate as the directed Steiner tree problem. We match this by giving an algorithm that achieves an approximation guarantee of $\alpha(n)+1$ for the relaxed $(S,T)$ connectivity problem, where $\alpha(n)$ denotes the best approximation guarantee available for the directed Steiner tree problem. The key to the analysis is a structural result that decomposes any feasible solution into a set of so-called junction trees that are disjoint on the vertices of $T$. Our algorithm and analysis specialize to the case when the input digraph is acyclic on $T$, meaning that there exists no dicycle that contains two distinct vertices of $T$. In this setting, we show that the relaxed $(S,T)$ connectivity problem is at least as hard to approximate as the set covering problem, and we prove that our algorithm achieves a matching approximation guarantee of $O(\log{|S|})$.

The Directed Steiner Tree (DST) problem is a cornerstone problem in network design. We focus on the generalization of the problem with higher connectivity requirements. The problem with one root and two sinks is APX-hard. The problem with one root and many sinks is as hard to approximate as the directed Steiner forest problem, and the latter is well known to be as hard to approximate as the label cover problem. Utilizing previous techniques (due to others), we strengthen these results and extend them to undirected graphs. Specifically, we give an Ω(k∊) hardness bound for the rooted k-connectivity problem in undirected graphs; this addresses a recent open question of Khanna. As a consequence, we also obtain the Ω(k∊) hardness of the undirected subset k-connectivity problem. Additionally, we give a result on the integrality ratio of the natural linear programming relaxation of the directed rooted k-connectivity problem.

We study undirected networks with edge costs that satisfy the triangle inequality. Let n denote the number of nodes. We present an $O(1)$-approximation algorithm for a generalization of the metric-cost subset k-node-connectivity problem. Our approximation guarantee is proved via lower bounds that apply to the simple edge-connectivity version of the problem, where the requirements are for edge-disjoint paths rather than for openly node-disjoint paths. A corollary is that, for metric costs and for each $k=1,2,\dots,n-1$, there exists a k-node connected graph whose cost is within a factor of ${ 22\/}$ of the cost of any simple k-edge connected graph. Based on our $O(1)$-approximation algorithm, we present an $O(\log r_{\max})$-approximation algorithm for the metric-cost node-connectivity survivable network design problem, where $r_{\max}$ denotes the maximum requirement over all pairs of nodes. Our results contrast with the case of edge costs of 0 or 1, where Kortsarz, Krauthgamer, and Lee. [SIAM J. Comput., 33 (2004), pp. 704–720] recently proved, assuming NP$\nsubseteq\;$DTIME($n^{polylog(n)}$), a hardness-of-approximation lower bound of $2^{\log^{1-\epsilon}n}$ for the subset k-node-connectivity problem, where $\epsilon$ denotes a small positive number.

Given an undirected graph G ( V , E ) with terminal set T ⊆ V , the problem of packing element-disjoint Steiner trees is to find the maximum number of Steiner trees that are disjoint on the nonterminal nodes and on the edges. The problem is known to be NP-hard to approximate within a factor of Ω(log n ), where n denotes | V |. We present a randomized O (log n )-approximation algorithm for this problem, thus matching the hardness lower bound. Moreover, we show a tight upper bound of O (log n ) on the integrality ratio of a natural linear programming relaxation.

We study undirected networks with edge costs that satisfy the triangle inequality. Let n denote the number of nodes. We present an O(1)-approximation algorithm for a generalization of the metric-cost subset k-node-connectivity problem. Our approximation guarantee is proved via lower bounds that apply to the simple edge-connectivity version of the problem, where the requirements are for edge-disjoint paths rather than for openly node-disjoint paths. A corollary is that, for metric costs and for each k=1,2,…,n-1, there exists a k-node connected graph whose cost is within a factor of 24 of the cost of any simple k-edge connected graph. This resolves an open question in the area. Based on our O(1)-approximation algorithm, we present an O(log rmax)-approximation algorithm for the node-connectivity survivable network design problem where rmax denotes the maximum requirement over all pairs of nodes. Our results contrast with the case of edge costs of zero or one, where Kortsarz et al. [20]recently proved, assuming NP⊈, quasi-P, a hardness-of-approximation lower bound of 2log 1-εn for the subset k-node-connectivity problem, where ε denotes a small positive number.

Our main result is an O(nm) -time (deterministic) algorithm for constructing an ear decomposition of a matching-covered graph, where n and m denote the number of nodes and edges. The improvement in the running time comes from new structural results that give a sharpened version of Lovász and Plummer's Two-Ear Theorem. Our algorithm is based on O(nm) -time algorithms for two other fundamental problems in matching theory, namely, finding all the allowed edges of a graph, and finding the canonical partition of an elementary graph. To the best of our knowledge, no faster deterministic algorithms are known for these two fundamental problems.

We present an approximation algorithm for the problem of finding a minimum-cost k-vertex connected spanning subgraph, assuming that the number of vertices is at least 6k 2 . The approximation guarantee is six times the kth harmonic number (which is O(log k)), and this is also an upper bound on the integrality ratio for a standard linear programming relaxation.

We present two new algorithms for the problem of nding a minimum-cost k-vertex connected spanning subgraph. The rst algorithm works on undirected graphs with at least 6k vertices and achieves an approximation of 6 times the kth harmonic number (which is O(log k)), The second algorithm works on any graph (directed or undirected) and gives an O( n=)-approximation algorithm for any > 0 and k (1 )n. These algorithms improve on the previous best approximation factor (more than k=2). The latter algorithm also extends to other problems in network design with vertex connectivity requirements. Our main tools are setpair relaxations, a theorem of Mader's (in the undirected case) and iterative rounding (general case).

The seminal paper of F.T. Leighton and S. Rao (1988) and subsequent papers presented approximate min-max theorems relating multicommodity flow values and cut capacities in undirected networks, developed the divide-and-conquer method for designing approximation algorithms, and generated novel tools for utilizing linear programming relaxations. Yet, despite persistent research efforts, these achievements could not be extended to directed networks, excluding a few cases that are "symmetric" and therefore similar to undirected networks. The paper is an attempt to remedy the situation. We consider the problem of finding a minimum multicut in a directed multicommodity flow network, and give the first nontrivial upper bounds on the maxflow-to-min multicut ratio. Our results are algorithmic, demonstrating nontrivial approximation guarantees.

We give a $\frac{17}{12}$-approximation algorithm for the following NP-hard problem: Given a simple undirected graph, find a 2-edge connected spanning subgraph that has the minimum number of edges. The best previous approximation guarantee was $\frac{3}{2}$. If the well-known $\frac{4}{3}$ conjecture for the metric traveling salesman problem holds, then the optimal value (minimum number of edges) is at most $\frac{4}{3}$ times the optimal value of a linear programming relaxation. Thus our main result gets halfway to this target.

An efficient heuristic is presented for the problem of finding a minimum-size k-connected spanning subgraph of an (undirected or directed) simple graph G=(V,E). There are four versions of the problem, and the approximation guarantees are as follows:minimum-size k-node connected spanning subgraph of an undirected graph 1 + [1/k], minimum-size k-node connected spanning subgraph of a directed graph 1 + [1/k], minimum-size k-edge connected spanning subgraph of an undirected graph 1+[2/(k+1)], minimum-size k-edge connected spanning subgraph of a directed graph 1 + [4/\sqrt{k}]. The heuristic is based on a subroutine for the degree-constrained subgraph (b-matching) problem. It is simple and deterministic and runs in time O(k|E| 2 ). The following result on simple undirected graphs is used in the analysis: The number of edges required for augmenting a graph of minimum degree k to be k-edge connected is at most k,|V|/(k+1). For undirected graphs and k=2, a (deterministic) parallel NC version of the heuristic finds a 2-node connected (or 2-edge connected) spanning subgraph whose size is within a factor of ($1.5+\epsilon$) of minimum, where $\epsilon > 0$ is a constant.

Given an undirected graph G = (V ∪ A, E), where A is a set of terminal nodes and V is a set of nonterminal nodes, a node multiterminal cut is a set of nonterminal nodes whose deletion disconnects every pair of terminal nodes. We study the node multiterminal cut polyhedron, denoted P(G, A). We give some general results concerning facets of P(G, A) and introduce several classes of facet-inducing inequalities. We focus on the so-called A-tree inequalities (a generalization of the well-known path inequalities) and show that if G is a tree then these inequalities give a complete description of P(G, A). Assuming that the number of terminal nodes in an A-tree is O(1) or G is a tree, we give efficient separation algorithms for the A-tree inequalities. © 1997 John Wiley & Sons, Inc. Networks 30: 133–148, 1997

A randomized (Las Vegas) algorithm is given for finding the Gallai--Edmonds decomposition of a graph. Let n denote the number of vertices, and let M(n) denote the number of arithmetic operations for multiplying two n $\times$ n matrices. The sequential running time (i.e., number of bit operations) is within a poly-logarithmic factor of M(n). The parallel complexity is O((log n) 2 ) parallel time using a number of processors within a poly-logarithmic factor of M(n). The same complexity bounds suffice for solving several other problems: finding a minimum vertex cover in a bipartite graphfinding a minimum X ---> Y vertex separator in a directed graph, where X and Y are specified sets of vertices,finding the allowed edges (i.e., edges that occur in some maximum matching) of a graph,finding the canonical partition of the vertex set of an elementary graph. The sequential algorithms for problems (i), (ii), and (iv) are Las Vegas, and the algorithm for problem (iii) is Monte Carlo. The new complexity bounds are significantly better than the best previous ones, e.g., using the best value of M(n) currently known, the new sequential running time is O(n 2.38 ) versus the previous best O(n 2.5 /(log n)) or more.

The average degree of a subgraph H of the r-dimensional hypercube $Q_r$ equals at most the maximum Hamming distance of any two nodes in H. A corollary is that the minimum number of edges to delete from $Q_r$ such that any two nodes at Hamming distance $\ell$ are separated is $(r+1-\ell) 2^{r-1}$. This corollary has applications to multicommodity flows.

An efficient heuristic is presented for the problem of finding a minimum-size k-connected spanning subgraph of a given (undirected or directed) graph G=(V,E). There are four versions of the problem, depending on whether G is undirected or directed, and whether the spanning subgraph is required to be k-node connected (k-NCSS) or k-edge connected (k-ECSS). The approximation guarantees are as follows: min-size k-NCSS of an undirected graph 1+[1/k], min-size k-NCSS of a directed graph 1+[1/k], min-size k-ECSS of an undirected graph 1+[7/k], & min-size k-ECSS of a directed graph 1+[4//spl radic/k]. The heuristic is based on a subroutine for the degree-constrained subgraph (b-matching) problem. It is simple, deterministic, and runs in time O(k|E|/sup 2/). For undirected graphs and k=2, a (deterministic) parallel NC version of the heuristic finds a 2-node connected (or a-edge connected) spanning subgraph whose size is within a factor of (1.5+/spl epsiv/) of minimum, where /spl epsiv/>0 is a constant.

A k-separator (k-shredder) of a graph is a set of k nodes whose removal results in two or more (three or more) cunnect ed components.Let the given (undirected) graph be k-node connected, and let n denote the number of nodes.Solving au open question, we show that the problem of counting the number of k-separators is #P-complete.However, we present an O(k2n2 + k3ra15 )-time (deterministic) algorithm for finding all the k-shredders.This solves an open question: efficiently find a k-separator whose removal maximizes the number of connected components.For k z 4, our running time equals that of the fastest algorithm known for testing k-node connectivity.One application of shredders is in increasing the node connectivity from k to (k + 1) by efficiently adding an (approximately) minimum number of new edges.Jord6n [JCT(B) 1995] gave an ~l(ns).timeaugmentation ~gofithmSu& thatthenumber of new edgesiswithin an additive term of (k -z) from a lower bound.We improve the running time to O(min(k, @)k2n2 + (log n)kn2), while acltieving the same performance guarantee.For k ~4, the running time compares favorably with the rtrnuing time for testing k-node connectivity.

We show that a maximum flow in a network with n vertices can be computed deterministically in $O({{n^3 } / {\log n}})$ time on a uniform-cost RAM. For dense graphs, this improves the previous best bound of $O(n^3 )$. The bottleneck in our algorithm is a combinatorial problem on (unweighted) graphs. The number of operations executed on flow variables is $O(n^{{8 / 3}} (\log n)^{{4 / 3}} )$, in contrast with $\Omega (nm)$ flow operations for all previous algorithms, where m denotes the number of edges in the network. A randomized version of our algorithm executes $O(n^{{3 / 2}} m^{{1 / 2}} \log n + {{n^2 (\log n)^2 } / {\log }}(2 + {{n(\log n)^2 } / m})$ flow operations with high probability. For the special case in which all capacities are integers bounded by U, we show that a maximum flow can be computed deterministically using $O(n^{{3 / 2}} m^{{1 / 2}} + n^2 (\log U)^{{1 / 2}} + \log U$ flow operations and $O(\min \{ {{nm,n^3 } / {\log n\} + n^2 }}(\log U)^{{1 / 2}} + \log U)$ time. We finally argue that several of our results yield parallel algorithms with optimal speedup.

A randomized algorithm for computing a maximum flow is presented. For an n-vertex m-edge network, the running time is $O(nm + n^{2}(\log n)^{2})$ with probability at least $1-2^{-\sqrt {nm}}$. The algorithm is always correct, and in the worst case runs in $O(nm \log n)$ time. The only use of randomization is to randomly permute the adjacency lists of the network vertices at the start of the execution. The analysis introduces the notion of premature target relabeling (PTR) events and shows that each PTR event contributes $O(\log n)$ amortized time to the overall running time. The number of PTR events is always $O(nm)$; however, it is shown that when the adjacency lists are randomly permuted, then this quantity is $O(n^{3/2}m^{1/2} + n^{2} \log n)$ with high probability.

The notion of output uensitive parallel algorithms for linear algebra problems is formalised in this paper, and such algorithms are presented for finding the rank R of an n x n matrix in randomised parallel time O(log n + logs@ using d(nz + iU(R)) processors, and for finding a maximum linearly independent subset of an n-set of n-dimensional vectors in randomised parallel time O((log n) logz R) using d(n2 + RIW(R)) processors (R is the sise of the subset).Also, output sensitive R.AfC algorithms for some combinatorial problems are developed.The best WC algorithm known for finding a maximum linearly independent subset of an n-set of n-dimensional vectors is giv+ the randomised parallel time ie O(logs TZ) using d(~(n)) processors.Note thatthis problem k-likely harder than the problem of finding a baais for the space spanned by the input vectors.An output sensitive 7WC-algorithm for computing greatest common divisors of polynomials is developed.This result is due to the second author.A miuimum vertex cover in a bipartite graph and a minimum X-Y vertex separator in a digraph can be found in rartdornised parallel time 0(log2 n) using d(lf(n)) processors (n is the number of vertices).This result is due to the first author.Not e that this is the best complexity bound known for 'RhfC algorithms, and matches the best R.Afc complexity bounds for the associated deciuion problems.1

Given a graph $G = (V,E)$, a certificate of k-vertex connectivity is an edge subset $E' \subset E$ such that the subgraph $(V,E')$ is k-vertex connected if and only if G is k-vertex connected. Let n and m denote the number of vertices and edges. A certificate is called sparse if it contains $O(kn)$ edges. For undirected graphs, this paper introduces a graph search called the scan-first search, and shows that a certificate with at most $k(n - 1)$ edges can be computed by executing scan-first search k times in sequence on subgraphs of G. For each of the parallel, distributed, and sequential models of computation, the complexity of scan-first search matches the best complexity of any graph search on that model. In particular, the parallel scan-first search runs in $O(\log n)$ time using $C(n,m)$ processors on a CRCW PRAM, where $C(n,m)$ is the number of processors needed to find a spanning tree in each connected component in $O(\log n)$ time, and the parallel certificate algorithm runs in $O(k\log n)$ time using $C(n,m)$ processors. The parallel certificate algorithm can be employed to test the k-vertex connectivity of an undirected graph in $O(k^2 \log n)$ time using $knC(n,kn)$ processors on a CRCW PRAM. For all combinations of n, m, and $k > 3$, both the running time and the number of processors either improve on or match those of all known deterministic parallel algorithms. This paper also obtains an online algorithm for computing an undirected graph certificate with at most $2kn$ edges, and a sequential algorithm for computing a directed graph certificate with at most $2k^2 n$ edges.

A certificatefor the k-vertex connectivity of a graph G = (V, E) is a subset E' of E such thatLet n = IV[ and m = IEI.A certificate is called sparse if it has size lE'I = O(kn).We show that sparse certificates for undirected graphs can be computed by executing k breadth first searches in sequence.This directly gives an efficient algorithm on the distributed model of computation.Using certificates of size O(k2 n), we show that the k-vertex connectivity of an undirected graph can be tested on the CRCW PRAM model in a parallel running time of O(k2 log n) using k3n2cr(k2n, n)/(log n) processors.For k >3 and m > k2n, this improves on previous deterministic parallel algorithms (for dense graphs and for constant k >4 the number of processors improves by a factor of roughly n).We also give sequential algorithms for finding (undirected) sparse certificates '(on-line", and for finding -.certificate es of size <2 k2 n for directed graphs,

The authors present a randomized maximum-flow algorithm, called the PLED (prudent linking excess diminishing) algorithm, whose expected running time is O(nm+n/sup 2/(log n)/sup 3/); this is O(nm) for all except relatively sparse networks. The algorithm is always correct, and in the worst case, which occurs with negligible probability, it take O(nm log n) time. The approach taken is to maintain a parameter Delta , which is a measure of the maximum flow excess of a vertex and of the maximum amount of flow sent by a single operation. Initially, Delta is less than or equal to the maximum edge capacity, and Delta =0 at termination. The execution of the PLED algorithm is partitioned into phases so that Delta stays fixed during each phase and decreases between consecutive phases. In order to achieve a bound on the number of phases that is independent of the maximum edge capacity, the algorithm decreases Delta by as large a factor (>or=2) as possible, rather than by a constant factor. The algorithm uses the dynamic trees data structure.>

The class of preflow push algorithms recently introduced by Goldberg and Tarjan for solving the maximum flow problem on a weighted digraph with n vertices and m edges is studied. Goldberg and Tarjan’s $O(n^3 )$ time bound for the highest distance preflow push algorithm is improved to $O(n^2 \sqrt m )$, and it is shown that this bound is tight by constructing a parametrized worst-case network. It is also shown that the $O(n^3 )$ time bound is tight for the FIFO preflow push algorithm, and the $O(n^2 m)$ time bound is tight for the LIFO preflow push algorithm. The maximal excess preflow push algorithm is then developed, and it is shown that it performs $O(n^2 \sqrt m )$ pushes and that this bound is tight. Based on this, the authors develop a maximum flow algorithm for the synchronous distributed model of computation that uses $O(n^2 \sqrt m )$ messages and $O(n^2 )$ time, thereby improving upon the best previously known algorithms for this model.