Strategy improvement is a natural and well-studied family of algorithms for solving various classes of stochastic and deterministic graph games. We present an improved upper bound of O(n 2ⁿ) on the number of iterations performed by the most natural, and most greedy, variant of the algorithm when applied to n-vertex Energy Games. We also obtain a similar upper bound of O(poly(n)⋅ 2ⁿ) on the expected number of iterations performed by Random-Edge, one of the most natural randomized variants of the algorithm. To the best of our knowledge, these are the first bounds for natural strategy-improvement algorithms on non-binary energy games that beat the trivial nⁿ = 2^{n log n} bound obtained by enumerating all strategies. The proof is based on a new adaptation of the layering technique of [Dorfman, Kaplan, Zwick, ICALP 2019].

The MAX BISECTION problem seeks a maximum-size cut that evenly divides the vertices of a given undirected graph. An open problem raised by Austrin, Benabbas, and Georgiou [SODA'13, TALG'16] is whether MAX BISECTION can be approximated as well as MAX CUT, i.e., to within \(\alpha_{\mathrm{GW}} \approx 0.8785672\ldots\), which is the approximation ratio achieved by the celebrated Goemans-Williamson algorithm for MAX CUT, which is best possible assuming the Unique Games Conjecture (UGC). They conjectured that the answer is yes.

The input to the Multiway Cut problem is a weighted undirected graph, with nonnegative edge weights, and k designated terminals. The goal is to partition the vertices of the graph into k parts, each containing exactly one of the terminals, such that the sum of weights of the edges connecting vertices in different parts of the partition is minimized. The problem is APX-hard for k≥3. The currently best known approximation algorithm for the problem for arbitrary k, obtained by Sharma and Vondrák [STOC 2014] more than a decade ago, has an approximation ratio of 1.2965. We present an algorithm with an improved approximation ratio of 1.2787. Also, for small values of k ≥ 4 we obtain the first improvements in 25 years over the currently best approximation ratios obtained by Karger, Klein, Stein, Thorup, and Young [STOC 1999]. (For k=3 an optimal approximation algorithm is known.)

Abstract. Assuming the unique games conjecture (UGC), the best approximation ratio that can be obtained in polynomial time for the max cut problem is [Formula: see text], obtained by the celebrated SDP-based approximation algorithm of Goemans and Williamson. The current best approximation algorithm for max di-cut, i.e., the max cut problem in directed graphs, achieves a ratio of about 0.87401, leaving open the question of whether max di-cut can be approximated as well as max cut. We obtain a slightly improved algorithm for max di-cut and a new UGC-hardness for it, showing that [Formula: see text], where [Formula: see text] is the best approximation ratio that can be obtained in polynomial time for max di-cut under UGC. Our new upper bound shows that max di-cut cannot be approximated as well as max cut, which separates max di-cut from max cut and resolves a question raised by Feige and Goemans. A natural generalization of max di-cut is the max [Formula: see text]-and problem in which each constraint is of the form [Formula: see text], where [Formula: see text] and [Formula: see text] are literals, i.e., variables or their negations (in max di-cut each constraint is of the form [Formula: see text] where [Formula: see text] and [Formula: see text] are variables). Austrin separated max [Formula: see text]-and from max cut by showing that [Formula: see text] and conjectured that max [Formula: see text]-and and max di-cut have the same approximation ratio. Our new lower bound on max di-cut refutes this conjecture, completing the separation of the three problems max [Formula: see text]-and, max di-cut, and max cut. We also obtain a new lower bound for max [Formula: see text]-and, showing that [Formula: see text]. Our upper bound on max di-cut is achieved via a simple, analytical proof. The new lower bounds on max di-cut and max [Formula: see text]-and, i.e., the new approximation algorithms, use experimentally discovered distributions of rounding functions which are then verified via computer-assisted proofs. Code for the project is available at https://github.com/jbrakensiek/max-dicut .

We present a randomized Õ(n^{3.5})-time algorithm for computing optimal energetic paths for an electric car between all pairs of vertices in an n-vertex directed graph with positive and negative costs, or gains, which are defined to be the negatives of the costs. The optimal energetic paths are finite and well-defined even if the graph contains negative-cost, or equivalently, positive-gain, cycles. This makes the problem much more challenging than standard shortest paths problems. More specifically, for every two vertices s and t in the graph, the algorithm computes α_B(s,t), the maximum amount of charge the car can reach t with, if it starts at s with full battery, i.e., with charge B, where B is the capacity of the battery. The algorithm also outputs a concise description of the optimal energetic paths that achieve these values. In the presence of positive-gain cycles, optimal paths are not necessarily simple. For dense graphs, our new Õ(n^{3.5}) time algorithm improves on a previous Õ(mn²)-time algorithm of Dorfman et al. [ESA 2023] for the problem. The gain of an arc is the amount of charge added to the battery of the car when traversing the arc. The charge in the battery can never exceed the capacity B of the battery and can never be negative. An arc of positive gain may correspond, for example, to a downhill road segment, while an arc with a negative gain may correspond to an uphill segment. A positive-gain cycle, if one exists, can be used in certain cases to charge the battery to its capacity. This makes the problem more interesting and more challenging. As mentioned, optimal energetic paths are well-defined even in the presence of positive-gain cycles. Positive-gain cycles may arise when certain road segments have magnetic charging strips, or when the electric car has solar panels. Combined with a result of Dorfman et al. [SOSA 2024], this also provides a randomized Õ(n^{3.5})-time algorithm for computing minimum-cost paths between all pairs of vertices in an n-vertex graph when the battery can be externally recharged, at varying costs, at intermediate vertices.

Let G = (V, E, w ) be a weighted directed graph without negative cycles. For two vertices s,t ∈ V, we let d≤h(s, t ) be the minimum, according to the weight function w, of a path from s to t that uses at most h edges, or hops. We consider algorithms for computing d<h(s,t ) for every 1 ≤ h ≤ n, where n = |V|, in various settings. We consider the singlepair, single-source and all-pairs versions of the problem. We also consider a distance oracle version of the problem in which we are not required to explicitly compute all distances d

Austrin showed that the approximation ratio β ≈ 0.94016567 obtained by the MAX 2-SAT approximation algorithm of Lewin, Livnat and Zwick (LLZ) is optimal modulo the Unique Games Conjecture (UGC) and modulo a Simplicity Conjecture that states that the worst performance of the algorithm is obtained on so called simple configurations. We prove Austrin's conjecture, thereby showing the optimality of the LLZ approximation algorithm, relying only on the Unique Games Conjecture. Our proof uses a combination of analytic and computational tools.

Abstract. A resizable array is an array that can grow and shrink by the addition or removal of items from its end, or both its ends, while still supporting constant-time access to each item stored in the array given its index. Since the size of an array, i.e., the number of items in it, varies over time, space-efficient maintenance of a resizable array requires dynamic memory management. A standard doubling technique allows the maintenance of an array of size [Formula: see text] using only [Formula: see text] space, with [Formula: see text] amortized time, or even [Formula: see text] worst-case time, per operation. Sitarski, and (apparently independently) Brodnik, Carlsson, Demaine, Munro, and Sedgewick describe much better solutions that maintain a resizable array of size [Formula: see text] using only [Formula: see text] space, still with [Formula: see text] time per operation. Brodnik et al. give a simple proof that this is best possible. We distinguish between the space needed for storing a resizable array, and accessing its items, and the temporary space that may be needed while growing or shrinking the array. For every integer [Formula: see text], we show that [Formula: see text] space is sufficient for storing and accessing an array of size [Formula: see text], if [Formula: see text] space can be used briefly during grow and shrink operations. Accessing an item by index takes [Formula: see text] worst-case time, while grow and shrink operations take [Formula: see text] amortized time. Using an exact analysis of a growth game, we show that for any data structure from a wide class of data structures that uses only [Formula: see text] space to store the array, the amortized cost of grow is [Formula: see text], even if only grow and access operations are allowed. The time for grow and shrink operations cannot be made worst-case unless [Formula: see text].

Assuming the Unique Games Conjecture (UGC), the best approximation ratio that can be obtained in polynomial time for the MAX CUT problem is $\alpha_{\text {CUT}} \simeq 0.87856$, obtained by the celebrated SDP-based approximation algorithm of Goemans and Williamson. Currently, the best approximation algorithm for MAX DI-CUT, i.e., the MAX CUT problem in directed graphs, achieves a ratio of about 0.87401, leaving open the question whether MAX DI-CUT can be approximated as well as MAX CUT. We obtain a slightly improved algorithm for MAX DI-CUT and a new UG-Chardness result for it, showing that $0.87446 \leq \alpha_{\text {DI-CUT}} \leq 0.87461$, where $\alpha_{\text {DI-CUT}}$ is the best approximation ratio that can be obtained in polynomial time for MAX DI-CUT under UGC. The new upper bound separates MAX DI-CUT from MAX CUT, i.e., shows that MAX DI-CUT cannot be approximated as well as MAX CUT, resolving a question raised by Feige and Goemans. A natural generalization of MAX DI-CUT is the MAX 2-AND problem in which each constraint is of the form $z_{1} \wedge {z_{2}}$, where $z_{1}$ and ${z_{2}}$ are literals, i.e., variables or their negations. (In MAX DI-CUT each constraint is of the form $\bar{x}_{1} \wedge {x_{2}}$, where $x_{1}$ and ${x_{2}}$ are variables.) Austrin separated MAX 2-AND from MAX CUT by showing that $\alpha_{2 \mathrm{AND}} \leq 0.87435$ and conjectured that MAX 2-AND and MAX DI-CUT have the same approximation ratio. Our new lower bound on MAX DI-CUT refutes this conjecture, completing the separation of the three problems MAX 2-AND, MAX DI-CUT and MAX CUT. We also obtain a new lower bound for MAX 2-AND showing that $0.87414 \leq \alpha_{2 \text {AND}} \leq 0.87435$. Our upper bound on MAXDI-CUT is achieved via a simple analytical proof. The new lower bounds on MAX DI-CUT and MAX 2-AND, i.e., the new approximation algorithms, use experimentally-discovered distributions of rounding functions which are then verified via computer-assisted proofs.11Code for the project: https://github.com/jbrakensiek/max-dicut

Abstract. Let [Formula: see text] be an [Formula: see text]-node [Formula: see text]-edge weighted undirected graph, where [Formula: see text] is a real length function defined on its edges, and let [Formula: see text] denote the girth of [Formula: see text], i.e., the length of a shortest cycle. We present an algorithm that, for any input, integer [Formula: see text], in [Formula: see text] expected time finds a cycle of length at most [Formula: see text]. This algorithm nearly matches an [Formula: see text]-time algorithm of Kadria et al. [ Algorithmic trade-offs for girth approximation in undirected graphs, in Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2022, pp. 1471–1492] which applied to unweighted graphs of girth 3. For weighted graphs, this result also improves upon the previous state-of-the-art algorithm that in [Formula: see text] time, where [Formula: see text] is an integral length function, finds a cycle of length at most [Formula: see text] of Kadria et al. [ Algorithmic trade-offs for girth approximation in undirected graphs, in Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2022, pp. 1471–1492]. For [Formula: see text], this result improves upon the result of Roditty and Tov [ ACM Trans. Algorithms, 9 (2013), pp. 15:1–15:13].

We present several new efficient algorithms for approximating the girth, g, of weighted and unweighted n-vertex, m-edge undirected graphs. For undirected graphs with polynomially bounded, integer, non-negative edge weights, we provide an algorithm that for every integer k ≥ 1, runs in Õ(m + n1 + 1/k log g) time and returns a cycle of length at most 2kg. For unweighted, undirected graphs we present an algorithm that for every k ≥ 1, runs in Õ(n1 + 1/k) time and returns a cycle of length at most 2k[g/2], an almost k-approximation. Both algorithms provide trade-offs between the running time and the quality of the approximation. We also obtain faster algorithms for approximation factors better than 2, and improved approximations when the girth is odd or small (e.g., 3 and 4).

It is well known that a queue can be simulated by two stacks using a constant number of stack operations per queue operation. In this paper we consider the forgotten converse problem of simulating a stack using several queues. We consider several variants of this problem. For the offline variant, we obtain a tight upper and lower bounds for the worst-case number of queue operations needed to simulate a sequence of n stack operations using k queues. For the online variant, when the number of queues k is constant, and n is the maximum number of items in the stack at any given time, we obtain tight Θ(n1/k) upper and lower bounds on the worst-case and amortized number of queue operations needed to simulate one stack operation. When k is allowed to grow with n, we prove an upper bound of O(n1/k + logk n) and a lower bound of on the amortized number of queue operations per stack operation. We also prove an upper bound of O(kn1/k) and a lower bound of Ω(n1/k + logk n) on the worst-case number of queue operations per stack operation. We also show that the specific but interesting sequence of n pushes followed by n pops can be implemented much faster using a total number of only Θ(n logk n) queue operations, for every k ≥ 2, an amortized number of Θ(logk n) queue operations per stack operation, and this bound is tight. On the other hand, we show that the same sequence requires at least Ω(n1/k) queue operations per stack operation in the worst case.

Abstract. MAX NAE-SAT is a natural optimization problem, closely related to its better-known relative MAX SAT. The approximability status of MAX NAE-SAT is almost completely understood if all clauses have the same size [Formula: see text] for some [Formula: see text]. We refer to this problem as MAX NAE-[Formula: see text]-SAT. For [Formula: see text], it is a slight extension of the celebrated MAX CUT problem. For [Formula: see text], it is related to the MAX CUT problem in graphs that can be fractionally covered by triangles. For [Formula: see text], it is known that an approximation ratio of [Formula: see text], obtained by choosing a random assignment, is optimal, assuming [Formula: see text]. For every [Formula: see text], an approximation ratio of at least [Formula: see text] can be obtained for MAX NAE-[Formula: see text]-SAT. There was some hope, therefore, that there is also a [Formula: see text]-approximation algorithm for MAX NAE-SAT, where clauses of all sizes are allowed simultaneously. Our main result is that there is no [Formula: see text]-approximation algorithm for MAX NAE-SAT, assuming the Unique Games Conjecture (UGC). In fact, even for almost satisfiable instances of MAX NAE-[Formula: see text]-SAT (i.e., MAX NAE-SAT where all clauses have size 3 or 5), the best approximation ratio that can be achieved, assuming UGC, is at most [Formula: see text]. Using calculus of variations, we extend the analysis of O’Donnell and Wu for MAX CUT to MAX NAE-[Formula: see text]-SAT. We obtain an optimal algorithm, assuming UGC, for MAX NAE-[Formula: see text]-SAT, slightly improving on previous algorithms. The approximation ratio of the new algorithm is about 0.9089. This gives a full understanding of MAX NAE-[Formula: see text]-SAT for every [Formula: see text]. Interestingly, the rounding function used by this optimal algorithm is the solution of an integral equation. We complement our theoretical results with some experimental results. We describe an approximation algorithm for almost satisfiable instances of MAX NAE-[Formula: see text]-SAT with a conjectured approximation ratio of 0.8728, and an approximation algorithm for almost satisfiable instances of MAX NAE-SAT with a conjectured approximation ratio of 0.8698. We further conjecture that these are essentially the best approximation ratios that can be achieved for these problems, assuming the UGC. Somewhat surprisingly, the rounding functions used by these approximation algorithms are nonmonotone step functions that assume only the values [Formula: see text].

Each vertex of an arbitrary simple graph on n vertices chooses k random incident edges. What is the expected number of edges in the original graph that connect different connected components of the sampled subgraph? We prove that the answer is O(n/k), when k ≥ c log n, for some large enough c. We conjecture that the same holds for smaller values of k, possibly for any k ≥ 2. Such a result is best possible for any k ≥ 2. As an application, we use this sampling result to obtain a one-way communication protocol with private randomness for finding a spanning forest of a graph in which each vertex sends only O (√n log n) bits to a referee.

We study the computational complexity of solving mean payoff games. This class of games can be seen as an extension of parity games, and they have similar complexity status: in both cases solving them is in NP ∩ coNP and not known to be in P. In a breakthrough result Calude, Jain, Khoussainov, Li, and Stephan constructed in 2017 a quasipolynomial time algorithm for solving parity games, which was quickly followed by a few other algorithms with the same complexity. Our objective is to investigate how these techniques can be extended to mean payoff games. The starting point is the combinatorial notion of universal trees: all quasipolynomial time algorithms for parity games have been shown to exploit universal trees. Universal graphs extend universal trees to arbitrary (positionally determined) objectives. We show that they yield a family of value iteration algorithms for solving mean payoff games which includes the value iteration algorithm due to Brim, Chaloupka, Doyen, Gentilini, and Raskin. The contribution of this paper is to prove tight bounds on the complexity of algorithms for mean payoff games using universal graphs. We consider two parameters: the largest weight N in absolute value and the number k of weights. The dependence in N in the existing value iteration algorithm is linear, we show that this can be improved to N^{1 - 1/n} and obtain a matching lower bound. However, we show that we cannot break the linear dependence in the exponent in the number k of weights implying that universal graphs do not yield a quasipolynomial time algorithm for solving mean payoff games.

We consider word RAM data structures for maintaining ordered sets of integers whose select and rank operations are allowed to return approximate results, i.e., ranks, or items whose rank, differ by less than Delta from the exact answer, where Delta=Delta(n) is an error parameter. Related to approximate select and rank is approximate (one-dimensional) nearest-neighbor. A special case of approximate select queries are approximate min queries. Data structures that support approximate min operations are known as approximate heaps (priority queues). Related to approximate heaps are soft heaps, which are approximate heaps with a different notion of approximation. We prove the optimality of all the data structures presented, either through matching cell-probe lower bounds, or through equivalences to well studied static problems. For approximate select, rank, and nearest-neighbor operations we get matching cell-probe lower bounds. We prove an equivalence between approximate min operations, i.e., approximate heaps, and the static partitioning problem. Finally, we prove an equivalence between soft heaps and the classical sorting problem, on a smaller number of items. Our results have many interesting and unexpected consequences. It turns out that approximation greatly speeds up some of these operations, while others are almost unaffected. In particular, while select and rank have identical operation times, both in comparison-based and word RAM implementations, an interesting separation emerges between the approximate versions of these operations in the word RAM model. Approximate select is much faster than approximate rank. It also turns out that approximate min is exponentially faster than the more general approximate select. Next, we show that implementing soft heaps is harder than implementing approximate heaps. The relation between them corresponds to the relation between sorting and partitioning. Finally, as an interesting byproduct, we observe that a combination of known techniques yields a deterministic word RAM algorithm for (exactly) sorting n items in O(n log log_w n) time, where w is the word length. Even for the easier problem of finding duplicates, the best previous deterministic bound was O(min{n log log n,n log_w n}). Our new unifying bound is an improvement when w is sufficiently large compared with n.

We describe an efficient deterministic adversary that forces any comparison-based sorting algorithm to perform at least n log n comparisons. This improves on previous efficient adversaries of Atallah and Kosaraju (1981), Richards and Vaidya (1988), and of Brodal et al. (1996) that force any sorting algorithm to perform at least ψn log n comparisons.

The PPSZ algorithm, due to Paturi, Pudlak, Saks and Zane, is currently the fastest known algorithm for the k-SAT problem, for every k>3. For 3-SAT, a tiny improvement over PPSZ was obtained by Hertli. We introduce a biased version of the PPSZ algorithm using which we obtain an improvement over PPSZ for every k≥ 3. For k=3 we also improve on Herli’s result and get a much more noticeable improvement over PPSZ, though still relatively small. In particular, for Unique 3-SAT, we improve the current bound from 1.308n to 1.307n.

We describe a way of assigning labels to the vertices of any undirected graph on up to $n$ vertices, each composed of $n/2+O(1)$ bits, such that given the labels of two vertices, and no other information regarding the graph, it is possible to decide whether or not the vertices are adjacent in the graph. This is optimal, up to an additive constant, and constitutes the first improvement in almost 50 years of an $n/2+O(\log n)$ bound of Moon. As a consequence, we obtain an induced-universal graph for $n$-vertex graphs containing only $O(2^{n/2})$ vertices, which is optimal up to a multiplicative constant, solving an open problem of Vizing from 1968. We obtain similar tight results for directed graphs, tournaments, and bipartite graphs.

We revisit multipass pairing heaps and path-balanced binary search trees (BSTs), two classical algorithms for data structure maintenance. The pairing heap is a simple and efficient "self-adjusting" heap, introduced in 1986 by Fredman, Sedgewick, Sleator, and Tarjan. In the multipass variant (one of the original pairing heap variants described by Fredman et al.) the minimum item is extracted via repeated pairing rounds in which neighboring siblings are linked. Path-balanced BSTs, proposed by Sleator (Subramanian, 1996), are a natural alternative to Splay trees (Sleator and Tarjan, 1983). In a path-balanced BST, whenever an item is accessed, the search path leading to that item is re-arranged into a balanced tree. Despite their simplicity, both algorithms turned out to be difficult to analyse. Fredman et al. showed that operations in multipass pairing heaps take amortized $O(\log{n} \cdot \log\log{n} / \log\log\log{n})$ time. For searching in path-balanced BSTs, Balasubramanian and Raman showed in 1995 the same amortized time bound of $O(\log{n} \cdot \log\log{n} / \log\log\log{n})$, using a different argument. In this paper we show an explicit connection between the two algorithms and improve the two bounds to $O\left(\log{n} \cdot 2^{\log^{\ast}{n}} \cdot \log^{\ast}{n}\right)$, respectively $O\left(\log{n} \cdot 2^{\log^{\ast}{n}} \cdot (\log^{\ast}{n})^2 \right)$, where $\log^{\ast}(\cdot)$ denotes the very slowly growing iterated logarithm function. These are the first improvements in more than three, resp. two decades, approaching in both cases the information-theoretic lower bound of $Ω(\log{n})$.

The pairing heap is a classical heap data structure introduced in 1986 by Fredman, Sedgewick, Sleator, and Tarjan. It is remarkable both for its simplicity and for its excellent performance in practice. The "magic" of pairing heaps lies in the restructuring that happens after the deletion of the smallest item. The resulting collection of trees is consolidated in two rounds: a left-to-right pairing round, followed by a right-to-left accumulation round. Fredman et al. showed, via an elegant correspondence to splay trees, that in a pairing heap of size n all heap operations take O(log n) amortized time. They also proposed an arguably more natural variant, where both pairing and accumulation are performed in a combined left-to-right round (called the forward variant of pairing heaps). The analogy to splaying breaks down in this case, and the analysis of the forward variant was left open. In this paper we show that inserting an item and deleting the minimum in a forward-variant pairing heap both take amortized time O(log(n) * 4^(sqrt(log n))). This is the first improvement over the O(sqrt(n)) bound showed by Fredman et al. three decades ago. Our analysis relies on a new potential function that tracks parent-child rank-differences in the heap.

We introduce the hollow heap , a very simple data structure with the same amortized efficiency as the classical Fibonacci heap. All heap operations except delete and delete - min take O (1) time, worst case as well as amortized; delete and delete - min take O (log n ) amortized time on a heap of n items. Hollow heaps are the simplest structure to achieve these bounds. Hollow heaps combine two novel ideas: the use of lazy deletion and re-insertion to do decrease - key operations and the use of a dag (directed acyclic graph) instead of a tree or set of trees to represent a heap. Lazy deletion produces hollow nodes (nodes without items), giving the data structure its name.

Random-Edge and Random-Facet are two very natural randomized pivoting rules for the simplex algorithm. The behavior of Random-Facet is fairly well understood. It performs an expected sub-exponential number of pivoting steps on any linear program, or more generally, on any Acyclic Unique Sink Orientation (AUSO) of an arbitrary polytope, making it the fastest known pivoting rule for the simplex algorithm. The behavior of Random-Edge is much less understood. We show that in the AUSO setting, Random-Edge is slower than Random-Facet. To do that, we construct AUSOs of the n-dimensional hypercube on which Random-Edge performs an expected number of 2^{Omega(sqrt(n*log(n)))} steps. This improves on a 2^{Omega(sqrt^3(n))} lower bound of Matoušek and Szabó. As Random-Facet performs an expected number of 2^{O(sqrt(n)} steps on any n-dimensional AUSO, this established our result. Improving our 2^{Omega(sqrt(n*log(n)))} lower bound seems to require radically new techniques.

Gabow and Tarjan showed that the Bottleneck Path (BP) problem, i.e., finding a path between a given source and a given target in a weighted directed graph whose largest edge weight is minimized, as well as the Bottleneck spanning tree (BST) problem, i.e., finding a directed spanning tree rooted at a given vertex whose largest edge weight is minimized, can both be solved deterministically in O(m * log^*(n)) time, where m is the number of edges and n is the number of vertices in the graph. We present a slightly improved randomized algorithm for these problems with an expected running time of O(m * beta(m,n)), where beta(m,n) = min{k >= 1 | log^{(k)}n <= m/n } <= log^*(n) - log^*(m/n)+1. This is the first improvement for these problems in over 25 years. In particular, if m >= n * log^{(k)} * n, for some constant k, the expected running time of the new algorithm is O(m). Our algorithm, as that of Gabow and Tarjan, work in the comparison model. We also observe that in the word-RAM model, both problems can be solved deterministically in O(m) time. Finally, we solve an open problem of Andersson et al., giving a deterministic O(m)-time comparison-based algorithm for solving deterministic 2-player turn-based zero-sum terminal payoff games, also known as Deterministic Graphical Games (DGG).

We obtain a new fully dynamic algorithm for the reachability problem in directed graphs. Our algorithm has an amortized update time of $O(m+n\log n)$ and a worst-case query time of $O(n)$, where $m$ is the current number of edges in the graph, and $n$ is the number of vertices in the graph. Each update operation either inserts a set of edges that touch the same vertex, or deletes an arbitrary set of edges. The algorithm is deterministic and uses fairly simple data structures. One of the ingredients used by this new algorithm may be interesting in its own right. It is a new dynamic algorithm for strong connectivity in directed graphs with an interesting ``retrospectiveness'' property. Each insert operation creates a new version of the graph. A delete operation deletes edges from all versions. Strong connectivity queries can be made on each version of the graph. The algorithm handles each update in $O(m\alpha(n))$ amortized time, and each query in $O(1)$ worst-case time, where $\alpha(n)$ is a functional inverse of Ackermann's function appearing in the analysis of the Union-Find data structure. Note that the update time of $O(m\alpha(n))$, in the case of a delete operation, is the time needed for updating all versions of the graph.

We obtain an essentially optimal tradeoff between the amortized cost of the three basic priority queue operations insert, delete and find-min in the comparison model. More specifically, we show that for any fixed ε > 0, where n is the number of items in the priority queue and A(insert), A(delete) and A(find-min) are the amortized costs of the insert, delete and find-min operations, respectively. In particular, if A(insert) + A(delete) = O(1), then A(find-min) = Ω(n), and A(find-min) = O(nα), for some α < 1, only if A(insert) + A(delete) = Ω(log n). (We can, of course, have A(insert) = O(1), A(delete) = O(log n), or vice versa, and A(find-min) = O(1).) Our lower bound holds even if randomization is allowed. Surprisingly, such fundamental bounds on the amortized cost of the operations were not known before. Brodal, Chaudhuri and Rad-hakrishnan, obtained similar bounds for the worst-case complexity of find-min.

We describe a way of assigning labels to the vertices of any undirected graph on up to n vertices, each composed of n/2+O(1) bits, such that given the labels of two vertices, and no other information regarding the graph, it is possible to decide whether or not the vertices are adjacent in the graph. This is optimal, up to an additive constant, and constitutes the first improvement in almost 50 years of an n/2+O(log n) bound of Moon. As a consequence, we obtain an induced-universal graph for n-vertex graphs containing only O(2n/2) vertices, which is optimal up to a multiplicative constant, solving an open problem of Vizing from 1968. We obtain similar tight results for directed graphs, tournaments and bipartite graphs.

The Random-Facet pivoting rule of Kalai and of Matousek, Sharir and Welzl is an elegant randomized pivoting rule for the simplex algorithm, the classical combinatorial algorithm for solving linear programs (LPs). The expected number of pivoting steps performed by the simplex algorithm when using this rule, on any linear program involving n inequalities in d variables, is 2O(√{(n-d),log({d}/{√{n-d}}},), where log n=max{1,log n}. A dual version of the algorithm performs an expected number of at most 2O(√{d,log({(n-d)}/√d},) dual pivoting steps. This dual version is currently the fastest known combinatorial algorithm for solving general linear programs. Kalai also obtained a primal pivoting rule which performs an expected number of at most 2O(√d,log n) pivoting steps. We present an improved version of Kalai's pivoting rule for which the expected number of primal pivoting steps is at most min{2O(√(n-d),log(d/(n-d),)},2O(√{d,log((n-d)/d}},)}. This seemingly modest improvement is interesting for at least two reasons. First, the improved bound for the number of primal pivoting steps is better than the previous bounds for both the primal and dual pivoting steps. There is no longer any need to consider a dual version of the algorithm. Second, in the important case in which n=O(d), i.e., the number of linear inequalities is linear in the number of variables, the expected running time becomes 2O(√d) rather than 2O(√d log d). Our results, which extend previous results of Gartner, apply not only to LP problems, but also to LP-type problems, supplying in particular slightly improved algorithms for solving 2-player turn-based stochastic games and related problems.

We describe a new forward-backward variant of Dijkstra's and Spira's single-source shortest paths (SSSP) algorithms. While essentially all SSSP algorithms scan edges only forward, the new algorithm scans some edges backward. The new algorithm assumes that edges in the outgoing and incoming adjacency lists of the vertices appear in nondecreasing order of weight. (Spira's algorithm makes the same assumption about the outgoing adjacency lists but does not use incoming adjacency lists.) The running time of the algorithm on a complete directed graph on $n$ vertices with independent exponential edge weights is $O(n)$ with very high probability. This improves on the previous best result of $O(n\log n)$, which is best possible if only forward scans are allowed, exhibiting an interesting separation between forward-only and forward-backward SSSP algorithms. As a consequence, we also get a new all-pairs shortest paths algorithm. The expected running time of the algorithm on complete graphs with independent exponential edge weights is $O(n^2)$, matching a recent algorithm of Demetrescu and Italiano as analyzed by Peres et al. [J. ACM, 60 (2013), 26]. Furthermore, the probability that the new algorithm requires more than $O(n^2)$ time is exponentially small, improving on the $O(n^{-1/26})$ probability bound obtained by Peres et al.

Dantzig's pivoting rule is one of the most studied pivoting rules for the simplex algorithm. While the simplex algorithm with Dantzig's rule may require an exponential number of pivoting steps on general linear programs, and even on min cost flow problems, Orlin showed that O(mn2 logn) Dantzig's pivoting steps suffice to solve shortest paths problems, where n and m are the number of vertices and edges, respectively, in the graph. Post and Ye recently showed that the simplex algorithm with Dantzig's rule requires only O(m2n3 log2 n) pivoting steps to solve deterministic MDPs with the same discount factor for each edge, and only O(m3n5 log2 n) pivoting steps to solve deterministic MDPs with possibly a distinct discount factor for each edge. We improve Orlin's bound for shortest paths and Post and Ye's bound for deterministic MDPs with the same discount factor by a factor of n to O(mnlogn), and O(m2n2 log2n), respectively. We also improve by a factor of n the bound for deterministic MDPs with varying discounts when all discount factors are sufficiently close to 1. These bounds follow from a new proof technique showing that after a certain number of steps, either many edges are excluded from participating in further policies, or there is a large decrease in the value. We also obtain an Ω(n2) lower bound on the number of Dantzig's pivoting steps required to solve shortest paths problems, even when m = Θ(n). Finally, we describe a reduction from the problem of finding a minimum cost to time ratio cycle to the problem of finding an optimal policy for a discounted deterministic MDP with varying discount factors that tend to 1. This gives a strongly polynomial time algorithm for the problem that does not use Megiddo's parametric search technique.

Upper bounds are given for the complexity of two very natural randomized algorithms for finding the sink of an Acyclic Unique Sink Orientation (AUSO) of the n-cube. For Random-Edge, we obtain an upper bound of about 1.80n, improving upon the the previous upper bound of about 2n/nlog n obtained by Gärtner and Kaibel. For Random-Jump, we obtain an upper bound of about (3/2)n, improving upon the previous upper bound of about 1.72n obtained by Mansour and Singh. AUSOs provide an appealing combinatorial abstraction of linear programming and other computational problems such as finding optimal strategies for turn-based Stochastic Games.

A union-find data structure maintains a collection of disjoint sets under the operations makeset, union, and find. Kaplan, Shafrir, and Tarjan [SODA 2002] designed data structures for an extension of the union-find problem in which items of the sets maintained may be deleted. The cost of a delete operation in their implementations is essentially the same as the cost of a find operation; namely, O (log n ) worst-case and O (α ⌈ M / N ⌉ ( n )) amortized, where n is the number of items in the set returned by the find operation, N is the total number of makeset operations performed, M is the total number of find operations performed, and α ⌈ M / N ⌉ ( n ) is a functional inverse of Ackermann’s function. They left open the question whether delete operations can be implemented more efficiently than find operations, for example, in o (log n ) worst-case time. We resolve this open problem by presenting a relatively simple modification of the classical union-find data structure that supports delete, as well as makeset and union operations, in constant worst-case time, while still supporting find operations in O (log n ) worst-case time and O (α ⌈ M/N⌉ ( n )) amortized time. Our analysis supplies, in particular, a very concise potential-based amortized analysis of the standard union-find data structure that yields an O (α ⌈ M / N ⌉ ( n )) amortized bound on the cost of find operations. All previous potential-based analyses yielded the weaker amortized bound of O (α ⌈ M / N ⌉ ( N )). Furthermore, our tighter analysis extends to one-path variants of the path compression technique such as path splitting .

We obtain several improved solutions for the deterministic rendezvous problem in general undirected graphs. Our solutions answer several problems left open by Dessmark et al. We also introduce an interesting variant of the rendezvous problem, which we call the deterministic treasure hunt problem. Both the rendezvous and the treasure hunt problems motivate the study of universal traversal sequences and universal exploration sequences with some strengthened properties. We call such sequences strongly universal traversal (exploration) sequences . We give an explicit construction of strongly universal exploration sequences. The existence of strongly universal traversal sequences, as well as the solution of the most difficult variant of the deterministic treasure hunt problem, are left as intriguing open problems.

We describe a new forward-backward variant of Dijkstra's and Spira's Single-Source Shortest Paths (SSSP) algorithms. While essentially all SSSP algorithm only scan edges forward, the new algorithm scans some edges backward. The new algorithm assumes that edges in the out-going and incoming adjacency lists of the vertices appear in nondecreasing order of weight. (Spira's algorithm makes the same assumption about the out-going adjacency lists, but does not use incoming adjacency lists.) The running time of the algorithm on a complete directed graph on n vertices with independent exponential edge weights is O(n), with very high probability. This improves on the previously best result of O(n log n), which is best possible if only forward scans are allowed, exhibiting an interesting separation between forward-only and forward-backward SSSP algorithms. As a consequence, we also get a new all-pairs shortest paths algorithm. The expected running time of the algorithm on complete graphs with independent exponential edge weights is O(n2), matching a recent result of Peres et al. Furthermore, the probability that the new algorithm requires more than O(n2) time is exponentially small, improving on the polynomially small probability of Peres et al.

Ye [2011] showed recently that the simplex method with Dantzig’s pivoting rule, as well as Howard’s policy iteration algorithm, solve discounted Markov decision processes (MDPs), with a constant discount factor, in strongly polynomial time. More precisely, Ye showed that both algorithms terminate after at most O ( mn 1− γ log n 1− γ ) iterations, where n is the number of states, m is the total number of actions in the MDP, and 0 < γ < 1 is the discount factor. We improve Ye’s analysis in two respects. First, we improve the bound given by Ye and show that Howard’s policy iteration algorithm actually terminates after at most O ( m 1− γ log n 1− γ ) iterations. Second, and more importantly, we show that the same bound applies to the number of iterations performed by the strategy iteration (or strategy improvement ) algorithm, a generalization of Howard’s policy iteration algorithm used for solving 2-player turn-based stochastic games with discounted zero-sum rewards. This provides the first strongly polynomial algorithm for solving these games, solving a long standing open problem. Combined with other recent results, this provides a complete characterization of the complexity the standard strategy iteration algorithm for 2-player turn-based stochastic games; it is strongly polynomial for a fixed discount factor, and exponential otherwise.

We present an all-pairs shortest path algorithm whose running time on a complete directed graph on n vertices whose edge weights are chosen independently and uniformly at random from [0,1] is O ( n 2 ), in expectation and with high probability. This resolves a long-standing open problem. The algorithm is a variant of the dynamic all-pairs shortest paths algorithm of Demetrescu and Italiano [2006]. The analysis relies on a proof that the number of locally shortest paths in such randomly weighted graphs is O ( n 2 ), in expectation and with high probability. We also present a dynamic version of the algorithm that recomputes all shortest paths after a random edge update in O (log 2 n ) expected time.

In 1998, Chazelle [J. ACM, 47 (2000), pp. 1012--1027] introduced a new kind of meldable heap (priority queue) called the soft heap. Soft heaps trade accuracy for speed: the heap operations are allowed to increase the keys of certain items, thereby making these items bad, as long as the number of bad items in the data structure is at most $\varepsilon m$, where $m$ is the total number of insertions performed so far, and $\varepsilon$ is an error parameter. The amortized time per heap operation is $O(\lg \frac{1}{\varepsilon})$, reduced from $O(\lg n)$, where $n$ is the number of items in the heap. Chazelle used soft heaps in several applications, including a faster deterministic minimum-spanning-tree algorithm and a new deterministic linear-time selection algorithm. We give a simplified implementation of soft heaps that uses less space and avoids Chazelle's dismantling operations. We also give a simpler, improved analysis that yields an amortized time bound of $O(\lg \frac{1}{\varepsilon})$ for each deletion, $O(1)$ for each other operation.

We obtain three new dynamic algorithms for the approximate all-pairs shortest paths problem in unweighted undirected graphs: (i) For any fixed $\varepsilon>0$, a decremental algorithm with an expected total running time of $\tilde{O}(mn)$, where $m$ is the number of edges and $n$ is the number of vertices in the initial graph. Each distance query is answered in $O(1)$ worst-case time, and the stretch of the returned distances is at most $1+\varepsilon$. The algorithm uses $\tilde{O}(n^2)$ space. (ii) For any fixed integer $k\geq1$, a decremental algorithm with an expected total running time of $\tilde{O}(mn)$. Each query is answered in $O(1)$ worst-case time, and the stretch of the returned distances is at most $2k-1$. This algorithm, however, uses only $O(m+n^{1+1/k})$ space. It is obtained by dynamizing techniques of Thorup and Zwick. In addition to being more space efficient, this algorithm is also one of the building blocks used to obtain the first algorithm. (iii) For any fixed $\varepsilon,\delta>0$ and every $t\leq m^{1/2-\delta}$, a fully dynamic algorithm with an expected amortized update time of $\tilde{O}(mn/t)$ and worst-case query time of $O(t)$. The stretch of the returned distances is at most $1+\varepsilon$. All algorithms can also be made to work on undirected graphs with small integer edge weights. If the largest edge weight is $b$, then all bounds on the running times are multiplied by $b$.

Let G = ( V,E ) be a directed graph and let P be a shortest path from s to t in G . In the replacement paths problem, we are required to find, for every edge e on P , a shortest path from s to t in G that avoids e . The only known algorithm for solving the problem, even for unweighted directed graphs, is the trivial algorithm in which each edge on the path, in its turn, is excluded from the graph and a shortest paths tree is computed from s . The running time is O ( mn + n 2 log n ). The replacement paths problem is strongly motivated by two different applications: (1) The fastest algorithm to compute the k simple shortest paths between s and t in directed graphs [Yen 1971; Lawler 1972] computes the replacement paths between s and t . Its running time is Õ ( mnk ). (2) The replacement paths problem is used to compute the Vickrey pricing of edges in a distributed network. It was raised as an open problem by Nisan and Ronen [2001] whether it is possible to compute the Vickrey pricing faster than n computations of a shortest paths tree. In this article we present the first nontrivial algorithm for computing replacement paths in unweighted directed graphs (and in graphs with small integer weights). Our algorithm is Monte-Carlo and its running time is Õ ( m √ n ). This result immediately improves the running time of the two applications mentioned above in a factor of √ n . We also show how to reduce the problem of computing k simple shortest paths between s and t to O ( k ) computations of a second simple shortest path from s to t each time in a different subgraph of G . The importance of this result is that computing a second simple shortest path may turn out to be an easier problem than computing the replacement paths, thus, we can focus our efforts to improve the k simple shortest paths algorithm in obtaining a faster algorithm for the second shortest path problem.

Parity Games form an intriguing family of infinite duration games whose solution is equivalent to the solution of important problems in automatic verification and automata theory. They also form a very natural subclass of Deterministic Mean Payoff Games, which in turn is a very natural subclass of turn-based Stochastic Mean Payoff Games. It is a major open problem whether these game families can be solved in polynomial time. The currently theoretically fastest algorithms for the solution of all these games are adaptations of the randomized algorithms of Kalai and of Matousek, Sharir and Welzl for LP-type problems, an abstract generalization of linear programming. The expected running time of both algorithms is subexponential in the size of the game, i.e., , where n is the number of vertices in the game. We focus in this paper on the algorithm of Matousek, Sharir and Welzl and refer to it as the Random Facet algorithm. Matoušek constructed a family of abstract optimization problems such that the expected running time of the Random Facet algorithm, when run on a random instance from this family, is close to the subexponential upper bound given above. This shows that in the abstract setting, the upper bound on the complexity of the Random Facet algorithm is essentially tight. It is not known, however, whether the abstract optimization problems constructed by Matoušek correspond to games of any of the families mentioned above. There was some hope, therefore, that the Random Facet algorithm, when applied to, say, parity games, may run in polynomial time. We show, that this, unfortunately, is not the case by constructing explicit parity games on which the expected running time of the Random Facet algorithm is close to the subexponential upper bound. The games we use mimic the behavior of a randomized counter. They are also the first explicit LP-type problems on which the Random Facet algorithm is not polynomial.

The problem of checking whether a given tower of bricks is stable can be easily answered by checking whether a system of linear inequalities has a feasible solution. A more challenging problem is to determine how an unstable tower of bricks collapses. We use Gauß’ principle of least restraint to show that this, and more general rigid-body simulation problems in which many parts touch each other, can be reduced to solving a sequence of convex quadratic programs, with linear constraints, corresponding to a discretization of time. The first of these quadratic programs gives an exact description of initial infinitesimal collapse. The results of the subsequent programs need to be integrated over time to yield an approximation of the global motion of the system.

The simplex algorithm is among the most widely used algorithms for solving linear programs in practice. With essentially all deterministic pivoting rules it is known, however, to require an exponential number of steps to solve some linear programs. No non-polynomial lower bounds were known, prior to this work, for randomized pivoting rules. We provide the first subexponential (i.e., of the form 2Ω(nα), for some α>0) lower bounds for the two most natural, and most studied, randomized pivoting rules suggested to date.

We present an all-pairs shortest path algorithm whose running time on a complete directed graph on n vertices whose edge weights are chosen independently and uniformly at random from [0,1] is O(n2), in expectation and with high probability. This resolves a long standing open problem. The algorithm is a variant of the dynamic all-pairs shortest paths algorithm of Demetrescu and Italiano. The analysis relies on a proof that the number of locally shortest paths in such randomly weighted graphs is O(n2), in expectation and with high probability. We also present a dynamic version of the algorithm that recomputes all shortest paths after a random edge update in O(log2n) expected time.

We present algorithms for finding optimal strategies for discounted, infinite-horizon, Determinsitc Markov Decision Processes (DMDPs). Our fastest algorithm has a worst-case running time of O ( mn ), improving the recent bound of O ( mn 2 ) obtained by Andersson and Vorbyov [2006]. We also present a randomized O ( m 1/2 n 2 )-time algorithm for finding Discounted All-Pairs Shortest Paths (DAPSP), improving an O ( mn 2 )-time algorithm that can be obtained using ideas of Papadimitriou and Tsitsiklis [1987].

Pebbles are placed on some vertices of a directed graph. Is it possible to move each pebble along at most one edge of the graph so that in the final configuration no pebble is left on its own? We give an O ( mn )-time algorithm for solving this problem, which we call the 2-gathering problem, where n is the number of vertices and m is the number of edges of the graph. If such a 2-gathering is not possible, the algorithm finds a solution that minimizes the number of solitary pebbles. The 2-gathering problem forms a nontrivial generalization of the nonbipartite matching problem and it is solved by extending the augmenting paths technique used to solve matching problems.

Chazelle (JACM 47(6), 2000) devised an approximate meldable priority queue data structure, called Soft Heaps, and used it to obtain the fastest known deterministic comparison-based algorithm for computing minimum spanning trees, as well as some new algorithms for selection and approximate sorting problems. If n elements are inserted into a collection of soft heaps, then up to ∊n of the elements still contained in these heaps, for a given error parameter ∊, may be corrupted, i.e., have their keys artificially increased. In exchange for allowing these corruptions, each soft heap operation is performed in O(log-) amortized time. Chazelle's soft heaps are derived from the binomial heaps data structure in which each priority queue is composed of a collection of binomial trees. We describe a simpler and more direct implementation of soft heaps in which each priority queue is composed of a collection of standard binary trees. Our implementation has the advantage that no clean-up operations similar to the ones used in Chazelle's implementation are required. We also present a concise and unified potential-based amortized analysis of the new implementation.

We present two new algorithms for finding optimal strategies for discounted, infinite-horizon, Deterministic Markov Decision Processes (DMDP). The first one is an adaptation of an algorithm of Young, Tarjan and Orlin for finding minimum mean weight cycles. It runs in O(mn + n2 log n) time, where n is the number of vertices (or states) and m is the number of edges (or actions). The second one is an adaptation of a classical algorithm of Karp for finding minimum mean weight cycles. It runs in O(mn) time. The first algorithm has a slightly slower worst-case complexity, but is faster than the first algorithm in many situations. Both algorithms improve on a recent O(mn2)-time algorithm of Andersson and Vorobyov. We also present a randomized -time algorithm for finding Discounted All-Pairs Shortest Paths (DAPSP), improving several previous algorithms.

Pebbles are placed on some vertices of a directed graph. Is it possible to move each pebble along at most one edge of the graph so that in the final configuration no pebble is left on its own? We give an O(mn)-time algorithm for solving this problem, which we call the 2-gathering problem, where n is the number of vertices and m is the number of edges of the graph. If such a 2-gathering is not possible, the algorithm finds a solution that minimizes the number of solitary pebbles. The 2-gathering problem forms a non-trivial generalization of the non-bipartite matching problem and it is solved by extending the augmenting paths technique used to solve matching problems.

The existence of polynomial-time algorithms for the solution of parity games is a major open problem. The fastest known algorithms for the problem are randomized algorithms that run in subexponential time. These algorithms are all ultimately based on the randomized subexponential simplex algorithms of Kalai and of Matoušek, Sharir, and Welzl. Randomness seems to play an essential role in these algorithms. We use a completely different, and elementary, approach to obtain a deterministic subexponential algorithm for the solution of parity games. The new algorithm, like the existing randomized subexponential algorithms, uses only polynomial space, and it is almost as fast as the randomized subexponential algorithms mentioned above.

We obtain several new dynamic algorithms for maintaining the transitive closure of a directed graph and several other algorithms for answering reachability queries without explicitly maintaining a transitive closure matrix. Among our algorithms are: (i) A decremental algorithm for maintaining the transitive closure of a directed graph, through an arbitrary sequence of edge deletions, in $O(mn)$ total expected time, essentially the time needed for computing the transitive closure of the initial graph. Such a result was previously known only for acyclic graphs. (ii) Two fully dynamic algorithms for answering reachability queries. The first is deterministic and has an amortized insert/delete time of $O(m\sqrt{n})$, and worst-case query time of $O(\sqrt{n})$. The second is randomized and has an amortized insert/delete time of $O(m^{0.58}n)$ and worst-case query time of $O(m^{0.43})$. This significantly improves the query times of algorithms with similar update times. (iii) A fully dynamic algorithm for maintaining the transitive closure of an acyclic graph. The algorithm is deterministic and has a worst-case insert time of $O(m)$, constant amortized delete time of $O(1)$, and a worst-case query time of $O(n/\log n)$. Our algorithms are obtained by combining several new ideas, one of which is a simple sampling idea used for detecting decompositions of strongly connected components, with techniques of Even and Shiloach [J. ACM, 28 (1981), pp. 1–4], Italiano [Inform. Process. Lett., 28 (1988), pp. 5–11], Henzinger and King [Proceedings of the $36$th Annual Symposium on Foundations of Computer Science, Milwaukee, WI, 1995, pp. 664–672], and Frigioni et al. [ACM J. Exp. Algorithmics, 6 (2001), (electronic)].

We introduce the notion of roundtrip-spanners of weighted directed graphs and describe efficient algorithms for their construction. We show that for every integer k ≥ 1 and any ϵ > 0, any directed graph on n vertices with edge weights in the range [1, W ] has a (2 k + ϵ)-roundtrip-spanner with O (min{( k 2 /ϵ) n 1 + 1/ k (log( nW ), ( k /ϵ) 2 n 1 + 1/ k ,(log n ) 2−1/ k }) edges. We then extend these constructions and obtain compact roundtrip routing schemes. For every integer k ≥ 1 and every ϵ > 0, we describe a roundtrip routing scheme that has stretch 4 k + ϵ, and uses at each vertex a routing table of size Õ (( k 2 /ϵ) n 1/ k log( nW )). We also show that any weighted directed graph with arbitrary/ positive edge weights has a 3-roundtrip-spanner with O ( n 3/2 ) edges. This result is optimal. Finally, we present a stretch 3 roundtrip routing scheme that uses local routing tables of size Õ ( n 1/2 ). This routing scheme is essentially optimal. The roundtrip-spanner constructions and the roundtrip routing schemes for directed graphs that we describe are only slightly worse than the best available spanners and routing schemes for undirected graphs. Our roundtrip routing schemes substantially improve previous results of Cowen and Wagner. Our results are obtained by combining ideas of Cohen, Cowen and Wagner, Thorup and Zwick, with some new ideas.

We show that any priority queue data structure that supports insert , delete , and find-min operations in pq ( n ) amortized time, where n is an upper bound on the number of elements in the priority queue, can be converted into a priority queue data structure that also supports fast meld operations with essentially no increase in the amortized cost of the other operations. More specifically, the new data structure supports insert , meld and find-min operations in O (1) amortized time, and delete operations in O ( pq ( n ) + α( n )) amortized time, where α( n ) is a functional inverse of the Ackermann function, and where n this time is the total number of operations performed on all the priority queues. The construction is very simple. The meldable priority queues are obtained by placing a nonmeldable priority queues at each node of a union-find data structure. We also show that when all keys are integers in the range [1, N ], we can replace n in the bound stated previously by min{ n , N }.Applying this result to the nonmeldable priority queue data structures obtained recently by Thorup [2002b] and by Han and Thorup [2002] we obtain meldable RAM priority queues with O (log log n ) amortized time per operation, or O (√log log n ) expected amortized time per operation, respectively. As a by-product, we obtain improved algorithms for the minimum directed spanning tree problem on graphs with integer edge weights, namely, a deterministic O ( m log log n )-time algorithm and a randomized O ( m √log log n )-time algorithm. For sparse enough graphs, these bounds improve on the O ( m + n log n ) running time of an algorithm by Gabow et al. [1986] that works for arbitrary edge weights.

Let G = (V, E, w) be a weighted directed graph, where w : E /spl rarr/ {-M, ..., 0, ..., M}. We show that G can be preprocessed in O/spl tilde/(Mn/sup /spl omega//) time, where /spl omega/n/sup /spl omega/- 1/2 / /spl sime/ n/sup 1.876/.

Let G = (V,E) be an undirected weighted graph with | V | = n and | E | = m . Let k ≥ 1 be an integer. We show that G = (V,E) can be preprocessed in O ( kmn 1/ k ) expected time, constructing a data structure of size O ( kn 1+1/ k ), such that any subsequent distance query can be answered, approximately, in O(k) time. The approximate distance returned is of stretch at most 2k −1, that is, the quotient obtained by dividing the estimated distance by the actual distance lies between 1 and 2k −1. A 1963 girth conjecture of Erdós, implies that Ω( n 1+1/ k ) space is needed in the worst case for any real stretch strictly smaller than 2 k +1. The space requirement of our algorithm is, therefore, essentially optimal. The most impressive feature of our data structure is its constant query time, hence the name "oracle". Previously, data structures that used only O ( n 1+1/ k ) space had a query time of Ω( n 1/ k ).Our algorithms are extremely simple and easy to implement efficiently. They also provide faster constructions of sparse spanners of weighted graphs, and improved tree covers and distance labelings of weighted or unweighted graphs.

Let A and B two n × n matrices over a ring R (e.g., the reals or the integers) each containing at most m nonzero elements. We present a new algorithm that multiplies A and B using O ( m 0.7 n 1.2 + n 2+ o (1) ) algebraic operations (i.e., multiplications, additions and subtractions) over R . The naïve matrix multiplication algorithm, on the other hand, may need to perform Ω( mn ) operations to accomplish the same task. For m ≤ n 1.14 , the new algorithm performs an almost optimal number of only n 2+ o (1) operations. For m ≤ n 1.68 , the new algorithm is also faster than the best known matrix multiplication algorithm for dense matrices which uses O ( n 2.38 ) algebraic operations. The new algorithm is obtained using a surprisingly straightforward combination of a simple combinatorial idea and existing fast rectangular matrix multiplication algorithms. We also obtain improved algorithms for the multiplication of more than two sparse matrices. As the known fast rectangular matrix multiplication algorithms are far from being practical, our result, at least for now, is only of theoretical value.

We obtain three dynamic algorithms for the approximate all-pairs shortest paths problem in unweighted undirected graphs: 1) For any fixed /spl epsiv/ > 0, a decremental algorithm with an expected total running time of O(mn), where m is the number of edges and n is the number of vertices in the initial graph. Each distance query is answered in O(1) worst-case time, and the stretch of the returned distances is at most 1 + /spl epsiv/. The algorithm uses O(n/sup 2/) space; 2) For any fixed integer k /spl ges/ 1, a decremental algorithm with an expected total running time of O(mn). Each query is answered in O(1) worst-case time, and the stretch of the returned distances is at most 2k - 1. This algorithm uses, however, only O(m + n/sup 1+1/k/) space. It is obtained by dynamizing techniques of Thorup and Zwick. In addition to being more space efficient, this algorithm is also one of the building blocks used to obtain the first algorithm; 3) For any fixed /spl epsiv/, /spl delta/ > 0 and every t /spl les/ m/sup 1/2-/spl delta//, a fully dynamic algorithm with an expected amortized update time of O(mn/t) and worst-case query time of O(t). The stretch of the returned distances is at most 1+/spl epsiv/. All algorithms can also be made to work on undirected graphs with small integer edge weights. If the largest edge weight is b, then all bounds on the running times are multiplied by b.

We obtain a new fully dynamic algorithm for the reachability problem in directed graphs. Our algorithm has an amortized update time of O(m+n log n) and a worst-case query time of O(n), where m is the current number of edges in the graph, and n is the number of vertices in the graph. Each update operation either inserts a set of edges that touch the same vertex, or deletes an arbitrary set of edges. The algorithm is deterministic and uses fairly simple data structures. This is the first algorithm that breaks the O(n2) update barrier for all graphs with o(n2) edges.One of the ingredients used by this new algorithm may be interesting in its own right. It is a new dynamic algorithm for strong connectivity in directed graphs with an interesting persistency property. Each insert operation creates a new version of the graph. A delete operation deletes edges from emphall versions. Strong connectivity queries can be made on each version of the graph. The algorithm handles each update in O(mα(m,n)) amortized time, and each query in O(1) time, where α(m,n) is a functional inverse of Ackermann's function appearing in the analysis of the union-find data structure. Note that the update time of O(mα(m,n)), in case of a delete operation, is the time needed for updating all versions of the graph.

Reachability and distance queries in graphs are fundamental to numerous applications, ranging from geographic navigation systems to Internet routing. Some of these applications involve huge graphs and yet require fast query answering. We propose a new data structure for representing all distances in a graph. The data structure is distributed in the sense that it may be viewed as assigning labels to the vertices, such that a query involving vertices u and v may be answered using only the labels of u and v. Our labels are based on 2-hop covers of the shortest paths, or of all paths, in a graph. For shortest paths, such a cover is a collection S of shortest paths such that, for every two vertices u and v, there is a shortest path from u to v that is a concatenation of two paths from S. We describe an efficient algorithm for finding an almost optimal 2-hop cover of a given collection of paths. Our approach is general and can be applied to directed or undirected graphs, exact or approximate shortest paths, or to reachability queries. We study the proposed data structure using a combination of theoretical and experimental means. We implemented our algorithm and checked the size of the resulting data structure on several real-life networks from different application areas. Our experiments show that the total size of the labels is typically not much larger than the network itself, and is usually considerably smaller than an explicit representation of the transitive closure of the network.

We obtain several new dynamic algorithms for maintaining the transitive closure of a directed graph, and several other algorithms for answering reachability queries without explicitly maintaining a transitive closure matrix. Among our algorithms are: (i) a decremental algorithm for maintaining the transitive closure of a directed graph, through an arbitrary sequence of edge deletions, in O(mn) total expected time, essentially the time needed for computing the transitive closure of the initial graph. Such a result was previously known only for acyclic graphs; (ii) two fully dynamic algorithms for answering reachability queries. The first is deterministic and has an amortized insert/delete time of O(m/spl radic/n), and worst-case query time of O(/spl radic/n). The second is randomized and has an amortized insert/delete time of O(m/sup 0.58/n) and worst-case query time of O(m/sup 0.43/). This significantly improves the query times of algorithms with similar update times; and (iii) a fully dynamic algorithm for maintaining the transitive closure of an acyclic graph. The algorithm is deterministic and has a worst-case insert time of O(m), constant amortized delete time of O(1), and a worst-case query time of O(n/ log n). Our algorithms are obtained by combining several new ideas, one of which is a simple sampling idea used for detecting decompositions of strongly connected components, with techniques of Even and Shiloach (1981), Italiano (1988), Henzinger and King (1995), and Frigioni et al. (2001). We also adapt results of Cohen (1997) on estimating the size of the transitive closure to the dynamic setting.

We present two new algorithms for solving the All Pairs Shortest Paths (APSP) problem for weighted directed graphs. Both algorithms use fast matrix multiplication algorithms.The first algorithm solves the APSP problem for weighted directed graphs in which the edge weights are integers of small absolute value in Õ ( n 2+μ ) time, where μ satisfies the equation ω(1, μ, 1) = 1 + 2μ and ω(1, μ, 1) is the exponent of the multiplication of an n × n μ matrix by an n μ × n matrix. Currently, the best available bounds on ω(1, μ, 1), obtained by Coppersmith, imply that μ < 0.575. The running time of our algorithm is therefore O ( n 2.575 ). Our algorithm improves on the Õ ( n (3c+ω)/2 ) time algorithm, where ω = ω(1, 1, 1) < 2.376 is the usual exponent of matrix multiplication, obtained by Alon et al., whose running time is only known to be O ( n 2.688 ).The second algorithm solves the APSP problem almost exactly for directed graphs with arbitrary nonnegative real weights. The algorithm runs in Õ(( n ω /ϵ) log( W /ϵ)) time, where ϵ > 0 is an error parameter and W is the largest edge weight in the graph, after the edge weights are scaled so that the smallest non-zero edge weight in the graph is 1. It returns estimates of all the distances in the graph with a stretch of at most 1 + ϵ. Corresponding paths can also be found efficiently.

We describe several compact routing schemes for general weighted undirected networks. Our schemes are simple and easy to implement. The routing tables stored at the nodes of the network are all very small. The headers attached to the routed messages, including the name of the destination, are extremely short. The routing decision at each node takes constant time. Yet, the stretch of these routing schemes, i.e., the worst ratio between the cost of the path on which a packet is routed and the cost of the cheapest path from source to destination, is a small constant. Our schemes achieve a near-optimal tradeoff between the size of the routing tables used and the resulting stretch. More specifically, we obtain:

Let G=(V,E) be an undirected weighted graph with |V|=n and |E|=m. Let k\ge 1 be an integer. We show that G=(V,E) can be preprocessed in O(kmn^{1/k}) expected time, constructing a data structure of size O(kn^{1+1/k}), such that any subsequent distance query can be answered, approximately, in O(k) time. The approximate distance returned is of stretch at most 2k-1, i.e., the quotient obtained by dividing the estimated distance by the actual distance lies between 1 and 2k-1. We show that a 1963 girth conjecture of Erd{\H{o}}s, implies that ω(n^{1+1/k}) space is needed in the worst case for any real stretch strictly smaller than 2k+1. The space requirement of our algorithm is, therefore, essentially optimal. The most impressive feature of our data structure is its constant query time, hence the name oracle. Previously, data structures that used only O(n^{1+1/k}) space had a query time of ω(n^{1/k}) and a slightly larger, non-optimal, stretch. Our algorithms are extremely simple and easy to implement efficiently. They also provide faster constructions of sparse spanners of weighted graphs, and improved tree covers and distance labelings of weighted or unweighted graphs.}

Semidefinite programming based approximation algorithms, such as the Goemans and Williamson approximation algorithm for the MAX CUT problem, are usually shown to have certain performance guarantees using local ratio techniques. Are the bounds obtained in this way tight? This problem was considered before by Karloff [SIAM J. Comput., 29 (1999), pp. 336--350] and by Alon and Sudakov [ Combin. Probab. Comput., 9 (2000), pp. 1--12]. Here we further extend their results and show, for the first time, that the local analyses of the Goemans and Williamson MAX CUT algorithm, as well as its extension by Zwick, are tight for every possible relative size of the maximum cut in the sense that the expected value of the solutions obtained by the algorithms may be as small as the analyses ensure. We also obtain similar results for a related problem. Our approach is quite general and could possibly be applied to some additional problems and algorithms.

We present a reformulation of the 2n+o(n) lower bound of Bent and John [Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985, pp. 213--216] for the number of comparisons needed for selecting the median of n elements. Our reformulation uses a weight function. Apart from giving a more intuitive proof for the lower bound, the new formulation opens up possibilities for improving it. We use the new formulation to show that any pair-forming median finding algorithm, i.e., a median finding algorithm that starts by comparing $\lfloor n/2\rfloor$ disjoint pairs of elements must perform, in the worst case, at least 2.01 n + o(n) comparisons. This provides strong evidence that selecting the median requires at least cn+o(n) comparisons for some c> 2.

Improving a long standing result of Bent and John [Proceedings of the 17th Annual ACM Symposium on Theory of Computing, Providence, RI, 1985, pp. 213--216], and extending a recent result of Dor, Håstad, Ulfberg, and Zwick [ SIAM J. Discrete Math., 14 (2001), pp. 299--311], we obtain a $(2{+}\epsilon)n$ lower bound (for some fixed $\epsilon>0$) on the number of comparisons required, in the worst case, for selecting the median of n elements.

Motivated by Web applications, we recently introduced the following theoretical model for connection-caching: Each host on a network can maintain (cache) a limited number of connections to other hosts. A message can be transmitted from one host to another only if the connection between these two hosts is open, i.e., it is cached by both endpoints. If a message request arrives and the respective connection is not open (a miss), the connection needs to be established and certain activation cost is incurred. The establishment of the new connection may force the termination (eviction) of other connections at each endpoint.

We show that the all pairs shortest paths (APSP) problem for undirected graphs with integer edge weights taken from the range {1, 2, ..., M} can be solved using only a logarithmic number of distance products of matrices with elements in the range (1, 2, ..., M). As a result, we get an algorithm for the APSP problem in such graphs that runs in O~(Mn/sup /spl omega//) time, where n is the number of vertices in the input graph, M is the largest edge weight in the graph, and /spl omega/<2.376 is the exponent of matrix multiplication. This improves, and also simplifies, an O~(M/sup (/spl omega/+1)/2/n/sup /spl omega//) time algorithm of Galil and Margalit (1997).

Article Connection caching Share on Authors: Edith Cohen AT&T Labs-Research, 180 Park Avenue, Florham Park, NJ AT&T Labs-Research, 180 Park Avenue, Florham Park, NJView Profile , Haim Kaplan AT&T Labs-Research, 180 Park Avenue, Florham Park, NJ AT&T Labs-Research, 180 Park Avenue, Florham Park, NJView Profile , Uri Zwick Tel-Aviv University, Tel-Aviv 69978, Israel Tel-Aviv University, Tel-Aviv 69978, IsraelView Profile Authors Info & Claims STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of ComputingMay 1999 Pages 612–621https://doi.org/10.1145/301250.301416Online:01 May 1999Publication History 9citation221DownloadsMetricsTotal Citations9Total Downloads221Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Two vertices in a weighted directed graph may be connected by many shortest paths. Although all these paths are shortest in terms of weight, the number of edges on them may vary substantially. This leads us to consider the All Pairs Lightest Shortest Paths (APLSP) problem. A solution to this problem is a representation of shortest paths between all of pairs of vertices in the graph such that each of these shortest paths uses a minimal, or a close to minimal, number of edges. We present the following algorithms for obtaining exact or approximate solutions to the APLSP problem: ffl An ~ O(n 2+ ) time algorithm for exactly solving the APLSP problem for directed graphs with integer weights of small absolute value, where n is the number of vertices in the graph and ! 0:747 is the solution of the equation !(1; ; 1) = 3, where !(1; ; 1) is the exponent of the multiplication of an n \\Theta n matrix by an n \\Theta n matrix. ffl An ~ O(n 2+ ) time algorithm, where ! 0:575 is the solutio...

Article Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems Share on Author: Uri Zwick Department of Computer Science, Tel-Aviv University, Tel-Aviv 69978, Israel Department of Computer Science, Tel-Aviv University, Tel-Aviv 69978, IsraelView Profile Authors Info & Claims STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of ComputingMay 1999 Pages 679–687https://doi.org/10.1145/301250.301431Published:01 May 1999 82citation613DownloadsMetricsTotal Citations82Total Downloads613Last 12 Months23Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Improving a long-standing result of Schönhage, Paterson, and Pippenger [ J. Comput. System Sci., 13 (1976), pp. 184--199] we show that the median of a set containing n elements can always be found using at most $c \cdot n$ comparisons, where c

We present two new algorithms for solving the All Pairs Shortest Paths (APSP) problem for weighted directed graphs. Both algorithms use fast matrix multiplication algorithms. The first algorithm solves the APSP problem for weighted directed graphs in which the edge weights are integers of small absolute value in O/spl tilde/(n/sup 2+/spl mu//) time, where /spl mu/ satisfies the equation /spl omega/(1,/spl mu/,1)=1+2/spl mu/ and /spl omega/(1,/spl mu/,1) is the exponent of the multiplication of an n/spl times/n/sup /spl mu// matrix by an n/sup /spl mu///spl times/n matrix. The currently best available bounds on /spl omega/(1,/spl mu/,1), obtained by Coppersmith and Winograd, and by Huang and Pan, imply that /spl mu/0 is an error parameter and W is the largest edge weight in the graph, after the edge weights are scaled so that the smallest non-zero edge weight in the graph is 1. It returns estimates of all the distances in the graph with a stretch of at most 1+/spl epsiv/. Corresponding paths can also be found efficiently.

Schaefer showed, long ago, that there are, essentially, only three non-trivial classes of conjunctive Boolean formulae (or constraint satisfaction problems) for which oatisflability can be decided in polynomial time (assuming P $ NP), These three classes are LIN, 2-SAT and HORN-SAT.LIN is the constraint satisfaction problem in which all the constraints are linear equations modulo 2, 2-SAT is the constraint satisfaction problem in which all the constraints are disjunctions of at most two variables or their negations.HORN-SAT is the constraint satisfaction problem in which all the constraints are Horn clauses, i.e., disjunctions containing at most one negated variable.Given aatisfiable instances of LIN, P-SAT and HORN-SAT, we can very efficiently find satisfying assignments.Suppose, however, that the instances that we are given are only almost-satisfiable, i.e., there are assignments that satisfy 1 -e of their constraints, for some small con&ant e > 0, but no assignments that satisfy all their constraints.Can we efficiently find almost-satisfying assignments, i.e., assignments that satisfy 1 -f(e) of the constraints, where f(c) is a function that tends to 0 an E tends to 01 For LIN, the answer turns out to be 'no'.H&ad showed that, for any e > 0 and 6 > 0, finding an assignment that satisfies l/2 -t 6 of the constraints of a (1 -e)-satisfiable instance of LIN is NP-hard.In sharp contrast, we show here that the answer for 2-SAT and HORN-SAT is 'yes'.Given almost-satisfiable instances of P-SAT and of HORN-SAT we cun efhcicntly find almost-satisfying assignments.More specifically, given a (1 -e)-satisfiable 2-SAT formula we can eflicicntly find a (1 -O(e1/3))-satisfying assignment.Given a (1-c)-satisfiable HORN-SAT formula we can

Consider the following communication problem. Alice gets a word x/spl isin/{0,1}/sup n/ and Bob gets a word y/spl isin/{0,1}/sup n/. Alice and Bob are told that x/spl ne/y. Their goal is to find an index 1/spl les/i/spl les/n such that x/sub i//spl ne/y/sub i/ (the index i should be known to both of them). This problem is one of the most basic communication problems. It arises naturally from the correspondence between circuit depth and communication complexity discovered by M. Karchmer and A. Wigderson (1990). We present three protocols using which Alice and Bob can solve the problem by exchanging at most it n+2 bits. One of this protocols is due to S. Rudich and G. Tardos. These protocols improve the previous upper bound of n+log* n, obtained by M. Karchmer. We also show that any protocol for solving the problem must exchange, in the worst case, at least n+1 bits. This improves a simple lower bound of n-1 obtained by Karchmer. Our protocols, therefore, are at most one bit away from optimality.

We describe a randomized approximation algorithm which takes an instance of MAX 3SAT as input. If the instance-a collection of clauses each of length at most three-is satisfiable, then the expected weight of the assignment found is at least 7/8 of optimal. We provide strong evidence (but not a proof) that the algorithm performs equally well on arbitrary MAX 3SAT instances. Our algorithm uses semidefinite programming and may be seen as a sequel to the MAX CUT algorithm of Goemans and Williamson (1995) and the MAX 2SAT algorithm of Feige and Goemans (1995). Though the algorithm itself is fairly simple, its analysis is quite complicated as it involves the computation of volumes of spherical tetrahedra. Hastad has recently shown that, assuming P/spl ne/NP, no polynomial-time algorithm for MAX 3SAT can achieve a performance ratio exceeding 7/8, even when restricted to satisfiable instances of the problem. Our algorithm is therefore optimal in this sense. We also describe a method of obtaining direct semidefinite relaxations of any constraint satisfaction problem of the form MAX CSP(F), where F is a finite family of Boolean functions. Our relaxations are the strongest possible within a natural class of semidefinite relaxations.

Moore and Shannon have shown that relays with arbitrarily high reliability can be built from relays with arbitrarily poor reliability. Valiant used similar methods to construct monotone read-once formulas of size $O(n^{\alpha+2})$ (where $\alpha=\log_{\sqrt{5}-1}2\simeq 3.27$) that amplify $(\psi-\frac{1}{n},\psi+\frac{1}{n})$ (where $\psi=(\sqrt{5}-1)/2\simeq0.62$) to $(2^{-n},1-2^{-n})$ and deduced as a consequence the existence of monotone formulas of the same size that compute the majority of n bits. Boppana has shown that any monotone read-once formula that amplifies $(p-\frac{1}{n},p+\frac{1}{n})$ to $(\frac{1}{4},\frac{3}{4})$ (where $0 < p < 1$ is constant) has size $\Omega(n^\alpha)$ and that any monotone, not necessarily read-once, contact network (and in particular any monotone formula) that amplifies $(\frac{1}{4},\frac{3}{4})$ to $(2^{-n},1-2^{-n})$ has size $\Omega(n^2)$. We extend Boppana's results in two ways. We first show that his two lower bounds hold for general read-once formulas, not necessarily monotone, that may even include exclusive-or gates. We are then able to join his two lower bounds together and show that any read-once, not necessarily monotone, formula that amplifies $(p-\frac{1}{n},p+\frac{1}{n})$ to $(2^{-n},1-2^{-n})$ has size $\Omega(n^{\alpha+2})$. This result does not follow from Boppana's arguments, and it shows that the amount of amplification achieved by Valiant is the maximal achievable using read-once formulas. In a companion paper we construct monotone read-once contact networks of size $O(n^{2.99})$ that amplify $(\frac{1}{2}-\frac{1}{n},\frac{1}{2}+\frac{1}{n})$ to $(\frac{1}{4},\frac{3}{4})$. This shows that Boppana's lower bound for the first amplification stage does not apply to contact networks, even if they are required to be both monotone and read-once.

We describe efficient algorithms for finding even cycles in undirected graphs. Our main results are the following: (i) For every $k \geq 2$, there is an $O(V^2)$ time algorithm that decides whether an undirected graph $G=(V,E)$ contains a simple cycle of length $2k$, and finds one if it does. (ii) There is an $O(V^2)$ time algorithm that finds a shortest even cycle in an undirected graph $G=(V,E)$.

Let G=(V,E) be an unweighted undirected graph on n vertices. A simple argument shows that computing all distances in G with an additive one-sided error of at most 1 is as hard as Boolean matrix multiplication. Building on recent work of Aingworth et al. [SIAM J. Comput., 28 (1999), pp. 1167--1181], we describe an $\Ot(\min\{n^{3/2}m^{1/2},n^{7/3}\})$-time algorithm APASP 2 for computing all distances in G with an additive one-sided error of at most 2. Algorithm APASP 2 is simple, easy to implement, and faster than the fastest known matrix-multiplication algorithm. Furthermore, for every even k>2, we describe an ${\tilde{O}}(\min\{n^{2-{2}/{(k+2)}}m^{{2}/{(k+2)}}, n^{2+{2}/{(3k-2)}}\})$-time algorithm APASP k for computing all distances in G with an additive one-sided error of at most k. We also give an ${\tilde{O}}(n^2)$-time algorithm ${\bf APASP}_\infty$ for producing stretch 3 estimated distances in an unweighted and undirected graph on n vertices. No constant stretch factor was previously achieved in ${\tilde{O}}(n^2)$ time. We say that a weighted graph F=(V,E') k-emulates an unweighted graph G=(V,E) if for every $u,v\in V$ we have $\delta_G(u,v)\le \delta_F(u,v)\le \delta_G(u,v)+k$. We show that every unweighted graph on n vertices has a 2-emulator with ${\tilde{O}}(n^{3/2})$ edges and a 4-emulator with ${\tilde{O}}(n^{4/3})$ edges. These results are asymptotically tight. Finally, we show that any weighted undirected graph on n vertices has a 3-spanner with ${\tilde{O}}(n^{3/2})$ edges and that such a 3-spanner can be built in ${\tilde{O}}(mn^{1/2})$ time. We also describe an ${\tilde{O}}(n(m^{2/3}+n))$-time algorithm for estimating all distances in a weighted undirected graph on n vertices with a stretch factor of at most 3.

Improving a long standing result of Bent and John (1985), we obtain a (2+/spl epsiv/)n lower bound (for some fixed /spl epsiv/>0) on the number of comparisons required, in the worst case, for selecting the median of n elements. The new lower bound is obtained using a weight function that allows us to combine leaf counting and adversary arguments.

We describe a novel randomized method.the method of cobm-coding for finding simple paths and cycles of a specified length k, and other small subgraphs, within a gwen graph G = ( 1', E).The randomized algorithms obtained using this method can be derandomlzcd using kmihes of petfect hash f~wtctmns.Using the color-coding method we obtain.m particular, the following new results:-For every fixed k, if a graph G = (V.E) contains a simple cycle of size exactly k, then such a cycle can be found m either 0( V'") expected time or 0( L'"' log P') worst-case t]mc, where w < ?,376 ]s the exponent of matrrx multiplication.(Here and in what follows we use V and E instead of Ib' and IEI whenever no confusion may arise.)-For every fwed k, if a planar graph G = (P-, E) contains a simple cycle of size e.wrctly k, then such a cycle cmr be found m either 0(V) expected time or 0( V log V ) worst-case time.The same algorithm applies, in fact, not only to planar gmphs, but to any mino~closed family of graphs which is not the f~mily of all graphs, -If a grdph G = (V, E) contains a subgraph isomorphic to a boanded tree-width graph H = ( V~, E~) where IV, I = O(log V), then such a copy of H can be found in polyzonzml tune.This was not prewously known even if H were Just a path of length O(log V).These results improve upon previous results of many authors.The third result resolves in the affirmative a conjecture of Papadimltnou and Yannakakis that the LOG PATH problem is m P. We can show that it is even in NC.

This paper considers the exact number of character comparisons needed to find all occurrences of a pattern of length m in a text of length n using on-line and general algorithms. For on-line algorithms, a lower bound of about $(1 + \frac{9}{4(m + 1)}) \cdot n$ character comparisons is obtained. For general algorithms, a lower bound of about $(1 + \frac{2}{m + 3}) \cdot n$ character comparisons is obtained. These lower bounds complement an on-line upper bound of about $(1 + \frac{8}{3(m + 1)}) \cdot n$ comparisons obtained recently by Cole and Hariharan. The lower bounds are obtained by finding patterns with interesting combinatorial properties. It is also shown that for some patterns off-line algorithms can be more efficient than on-line algorithms.

Improving a long chain of works we obtain a randomized EREW PRAM algorithm for finding the connected components of a graph G=(V,E) with n vertices and m edges in O(log n) time using an optimal number of O((m+n)/log n) processors. The result returned by the algorithm is always correct. The probability that the algorithm will not complete in O(log n) time is at most n-c for any desired c > 0.

We describe a novel randomized method, the method of color-coding for finding simple paths and cycles of a specified length k, and other small subgraphs, within a given graph G = (V,E). The randomized algorithms obtained using this method can be derandomized using families of perfect hash functions. Using the color-coding method we obtain, among others, the following new results: • For every fixed k, if a graph G = (V,E) contains a simple cycle of size exactly k, then such a cycle can be found in either O(V ω) expected time or O(V ω log V ) worst-case time, where ω < 2.376 is the exponent of matrix multiplication. (Here and in what follows we use V and E instead of |V | and |E| whenever no confusion may arise.) • For every fixed k, if a planar graph G = (V,E) contains a simple cycle of size exactly k, then ∗Work supported in part by The basic research foundation administrated by The Israel academy of sciences and humanities and by grant No. 93-6-6 of the Sloan foundation. †Institute for Advanced study, school of Mathematics, Princeton, NJ 08540, USA. ‡School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, ISRAEL. E-mail addresses of authors: {noga,raphy,zwick}@math.tau.ac.il. such a cycle can be found in either O(V ) expected time or O(V log V ) worst-case time. The same algorithm applies, in fact, not only to planar graphs, but to any minor closed family of graphs which is not the family of all graphs. • If a graph G = (V,E) contains a subgraph isomorphic to a bounded tree-width graph H = (VH , EH) where |VH | = O(log V ), then such a copy of H can be found in polynomial time. This was not previously known even if H were just a path of length O(log V ). These results improve upon previous results of many authors. The third result resolves in the affirmative a conjecture of Papadimitriou and Yannakakis that the LOG PATH problem is in P. We can even show that the LOG PATH problem is in NC.

The authors extend R.B. Boppana's results (1989) in two ways. They first show that his two lower bounds hold for general read-once formulae, not necessarily monotone, that may even include exclusive-or gates. They are then able to join his two lower bounds together and show that any read-once, not necessarily monotone, formula that amplifies (p-/sup 1///sub n/,p+/sup 1///sub n/) to (2/sup -n/,1-2/sup -n/) has size of at least Omega (n/sup alpha +2/). This result does not follow from Boppana's arguments and it shows that the amount of amplification achieved by L.G. Valiant (1984) is the maximal achievable using read-once formulae.>

Paterson, Pippenger and Zwick have recently obtained a general theory that describes the optimal way in which given carry-save adders can be combined into carry-save networks. Their work produces, in particular, multiplication circuits of depth 3.71 log2 n (these circuits put out two numbers whose sum is the result of the multiplication).

Y. Ofman (1963), C.S. Wallace (1964), and others used carry save adders to design multiplication circuits whose total delay is proportional to the logarithm of the length of two numbers multiplied. An extension of their work is presented. A general theory is presented describing the optimal way in which given carry save adders can be combined into carry save networks. Two new designs of basic carry save adders are described. Using these building blocks and the general theory, the shallowest known theoretical circuits for multiplication are obtained.>

It is shown that a random restriction leaving only a fraction in of the input variables unassigned reduces the expected de Morgan formula size of the induced function by a factor of O( in /sup 1.63/). This is an improvement over previous results. The new exponent yields an increased lower bound of approximately n/sup 2.63/ for the de Morgan formula size of a function in P defined by A.E. Andreev (1987). This is the largest lower bound known, even for functions in NP.>

A simple, and easy-to-check, property of a symmetric boolean function is shown to imply a $4n - O(1)$ lower bound on the circuit complexity of the function over $U_2 = B_2 - \{ \oplus , \equiv \}$, the basis of unate dyadic boolean functions. Among the functions to which this lower bound applies are the modular functions ${\operatorname{MOD}}_k (n)$ for any fixed $k \geqq 3$ (${\operatorname{MOD}}_k (n)$ is the function which returns 1 if and only if $(\sum x_i )\bmod k = 0$). Finally, a $5n$ upper bound is obtained on the circuit complexity over $U_2 $ of the function ${\operatorname{MOD}}_4 (n)$.

A general theory is developed for constructing the shallowest possible circuits and the shortest possible formulas for the carry-save addition of n numbers using any given basic addition unit. More precisely, it is shown that if BA is a basic addition unit with occurrence matrix N, then the shortest multiple carry-save addition formulas that could be obtained by composing BA units are of size n/sup 1/p+o(1)/, where p is the unique real number for which the L/sub p/ norm of the matrix N equals 1. An analogous result connects the delay matrix M of the basic addition unit BA and the minimal q such that multiple carry-save addition circuits of depth (q+o(1)) log n could be constructed by combining BA units. On the basis of these optimal constructions of multiple carry-save adders, the shallowest known multiplication circuits are constructed.>