Arrow Research search

Author name cluster

Liam Roditty

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

33 papers
2 author rows

Possible papers

33

ECAI Conference 2024 Conference Paper

The Complexity of Manipulation of k-Coalitional Games on Graphs

  • Hodaya Barr
  • Yohai Trabelsi
  • Sarit Kraus
  • Liam Roditty
  • Noam Hazon

In many settings, there is an organizer who would like to divide a set of agents into k coalitions, and cares about the friendships within each coalition. Specifically, the organizer might want to maximize utilitarian social welfare, maximize egalitarian social welfare, or simply guarantee that every agent will have at least one friend within his coalition. However, in many situations, the organizer is not familiar with the friendship connections, and he needs to obtain them from the agents. In this setting, a manipulative agent may falsely report friendship connections in order to increase his utility. In this paper, we analyze the complexity of finding manipulation in such k-coalitional games on graphs. We also introduce a new type of manipulation, socially-aware manipulation, in which the manipulator would like to increase his utility without decreasing the social welfare. We then study the complexity of finding socially-aware manipulation in our setting. Finally, we examine the frequency of socially-aware manipulation and the running time of our algorithms via simulation results.

Details

SODA Conference 2023 Conference Paper

Improved girth approximation in weighted undirected graphs

  • Avi Kadria
  • Liam Roditty
  • Aaron Sidford
  • Virginia Vassilevska Williams
  • Uri Zwick

Let G = ( V, E, ℓ) be a n -nodes m -edges weighted undirected graph, where ℓ: E → (0, ∞) is a real length function defined on its edges. Let g be the length of the shortest cycle in G. We present an algorithm that in O ( kn 1+1/ k log n + m(k + log n )) expected running time finds a cycle of length at most, for every integer k ≥ 1. This improves upon the previous best algorithm that in O((n 1+1/k log n + m ) log( nM )) time, where ℓ: E → [1, M ] is an integral length function, finds a cycle of length at most 2 kg [KRS + 22]. For k = 1 our algorithm also improves the result of Roditty and Tov [RT13].

Details

SODA Conference 2020 Conference Paper

An almost 2-approximation for all-pairs of shortest paths in subquadratic time

  • Maor Akav
  • Liam Roditty

Let G = ( V, E ) be an unweighted undirected graph with n vertices and m edges. Dor, Halperin, and Zwick [FOCS 1996, SICOMP 2000] presented an Õ ( n 2 )-time algorithm that computes estimated distances with a multiplicative approximation of 3. Berman and Kasiviswanathan [WADS 2007] improved the approximation of Dor et al. and presented an Õ ( n 2 )-time algorithm that produces for every u, v ϵ V an estimate ( u, v ) such that: d G ( u, v ) ≤ ( u, v ) ≤ 2 d G ( u, v ) + 1. We refer to such an approximation as an ( α, β )-approximation, where a is the multiplicative approximation and β is the additive approximation. A prerequisite for an O ( n 2− ε )-time algorithm, where ε ϵ (0, 1), is a data structure that uses O ( n 2− δ ) space, for some δ ≥ ε, and answers queries in constant time. An O ( n 2− ε )-time (3, 0)-approximation algorithm became plausible after Thorup and Zwick [STOC 2001, JACM 2005] presented their approximate distance oracles, and in particular an O ( n 1. 5 )-space data structure that reports a (3, 0)-approximate distance in O (1) time. Indeed, using Thorup and Zwick distance oracles together with more ideas, Baswana, Gaur, Sen, and Upadhyay [ICALP 2008] improved the running time of Dor et al. , and obtained an O ( n 2− ε ) time algorithm, at the cost of introducing also an additive approximation. They presented an algorithm that in Õ ( m + n 23/12 ) expected running time constructs an O ( n 1. 5 )-space data structure, that in O (1) time reports a (3, 14)-approximate distance. An O ( n 2− ε )-time (2, 1)-approximation algorithm became plausible only after Pǎtraşcu and Roditty [FOCS 2010, SICOMP 2014] presented an O ( n 5/3 )-space data structure that reports (2, 1)-approximate distances in O (1) time. However, only few years ago, Sommer [ICALP 2016] obtained an Õ ( n 2 ) time algorithm that computes a (2, 1)-distance oracle with Õ ( n 5/3 ) space. This leads to the following natural question of whether Ω( n 2 ) time is a lower bound for any (3− α, β )-approximation, where α ϵ (0, 1), and β is constant. In this paper we show that this is not the case by presenting an algorithm that for every ε ϵ (0, 1/2) computes in Õ ( m ) + n 2−Ω( ε ) time an -space data structure that in O (1/ ε ) time reports, for every u, v ϵ V, an estimate ( u, v ) such that: Our result improves, simultaneously, the running time and the multiplicative approximation of the Õ ( n 2 )-time (3, 0)-approximation algorithm of Dor et al. at the cost of introducing also an additive approximation.

Details

SODA Conference 2018 Conference Paper

Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners

  • Jakub Pachocki
  • Liam Roditty
  • Aaron Sidford
  • Roei Tov
  • Virginia Vassilevska Williams

The girth of a graph, i. e. the length of its shortest cycle, is a fundamental graph parameter. Unfortunately all known algorithms for computing, even approximately, the girth and girth-related structures in directed weighted m -edge and n -node graphs require Ω(min{ n ω, mn }) time (for 2 ≤ ω < 2. 373). In this paper, we drastically improve these runtimes as follows: • Multiplicative Approximations in Nearly Linear Time: We give an algorithm that in Õ ( m ) time computes an Õ (1)-multiplicative approximation of the girth as well as an Õ (1)-multiplicative roundtrip spanner with Õ ( n ) edges with high probability (w. h. p). • Nearly Tight Additive Approximations: For unweighted graphs and any a ∊ (0, 1) we give an algorithm that in Õ ( mn 1– a ) time computes an O ( n a )-additive approximation of the girth, w. h. p. We show that the runtime of our algorithm cannot be significantly improved without a breakthrough in combinatorial boolean matrix multiplication. We also show that if the girth is O ( n a ), then the same guarantee can be achieved via a deterministic algorithm. Our main technical contribution to achieve these results is the first nearly linear time algorithm for computing roundtrip covers, a directed graph decomposition concept key to previous roundtrip spanner constructions. Previously it was not known how to compute these significantly faster than Ω( mn ) time. Given the traditional difficulty in efficiently processing directed graphs, we hope our techniques may find further applications.

Details

STOC Conference 2018 Conference Paper

Towards tight approximation bounds for graph diameter and eccentricities

  • Arturs Backurs
  • Liam Roditty
  • Gilad Segal
  • Virginia Vassilevska Williams
  • Nicole Wein

Among the most important graph parameters is the Diameter, the largest distance between any two vertices. There are no known very efficient algorithms for computing the Diameter exactly. Thus, much research has been devoted to how fast this parameter can be approximated . Chechik et al. [SODA 2014] showed that the diameter can be approximated within a multiplicative factor of 3/2 in Õ( m 3/2 ) time. Furthermore, Roditty and Vassilevska W. [STOC 13] showed that unless the Strong Exponential Time Hypothesis (SETH) fails, no O ( n 2−ε ) time algorithm can achieve an approximation factor better than 3/2 in sparse graphs. Thus the above algorithm is essentially optimal for sparse graphs for approximation factors less than 3/2. It was, however, completely plausible that a 3/2-approximation is possible in linear time. In this work we conditionally rule out such a possibility by showing that unless SETH fails no O ( m 3/2−ε ) time algorithm can achieve an approximation factor better than 5/3. Another fundamental set of graph parameters are the Eccentricities. The Eccentricity of a vertex v is the distance between v and the farthest vertex from v . Chechik et al. [SODA 2014] showed that the Eccentricities of all vertices can be approximated within a factor of 5/3 in Õ( m 3/2 ) time and Abboud et al. [SODA 2016] showed that no O ( n 2−ε ) algorithm can achieve better than 5/3 approximation in sparse graphs. We show that the runtime of the 5/3 approximation algorithm is also optimal by proving that under SETH, there is no O ( m 3/2−ε ) algorithm that achieves a better than 9/5 approximation. We also show that no near-linear time algorithm can achieve a better than 2 approximation for the Eccentricities. This is the first lower bound in fine-grained complexity that addresses near-linear time computation. We show that our lower bound for near-linear time algorithms is essentially tight by giving an algorithm that approximates Eccentricities within a 2+δ factor in Õ( m /δ) time for any 0<δ<1. This beats all Eccentricity algorithms in Cairo et al. [SODA 2016] and is the first constant factor approximation for Eccentricities in directed graphs. To establish the above lower bounds we study the S - T Diameter problem: Given a graph and two subsets S and T of vertices, output the largest distance between a vertex in S and a vertex in T . We give new algorithms and show tight lower bounds that serve as a starting point for all other hardness results. Our lower bounds apply only to sparse graphs. We show that for dense graphs, there are near-linear time algorithms for S - T Diameter, Diameter and Eccentricities, with almost the same approximation guarantees as their Õ( m 3/2 ) counterparts, improving upon the best known algorithms for dense graphs.

Details

SODA Conference 2017 Conference Paper

Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications

  • Haim Kaplan
  • Wolfgang Mulzer
  • Liam Roditty
  • Paul Seiferth
  • Micha Sharir

We describe a new data structure for dynamic nearest neighbor queries in the plane with respect to a general family of distance functions that includes L p -norms and additively weighted Euclidean distances, and for general (convex, pair- wise disjoint) sites that have constant description complexity (line segments, disks, etc.). Our data structure has a polylogarithmic update and query time, improving an earlier data structure of Agarwal, Efrat and Sharir that required O ( n ∊ ) time for an update and O (log n ) time for a query [1]. Our data structure has numerous applications, and in all of them it gives faster algorithms, typically reducing an O ( n ∊ ) factor in the bounds to polylogarithmic. To further demonstrate its effectiveness, we give here two new applications: an efficient construction of a spanner in a disk intersection graph, and a data structure for efficient connectivity queries in a dynamic disk graph. To obtain this data structure, we combine and extend various techniques and obtain several side results that are of independent interest. Our data structure depends on the existence and an efficient construction of “vertical” shallow cuttings in arrangements of bivariate algebraic functions. We prove that an appropriate level in an arrangement of a random sample of a suitable size provides such a cutting. To compute it efficiently, we develop a randomized incremental construction algorithm for finding the lowest k levels in an arrangement of bivariate algebraic functions (we mostly consider here collections of functions whose lower envelope has linear complexity, as is the case in the dynamic nearest- neighbor context). To analyze this algorithm, we improve a longstanding bound on the combinatorial complexity of the vertical decomposition of these levels. Finally, to obtain our structure, we plug our vertical shallow cutting construction into Chan's algorithm for efficiently maintaining the lower envelope of a dynamic set of planes in ℝ 3. While doing this, we also revisit Chan's technique and present a variant that uses a single binary counter, with a simpler analysis and an improved amortized deletion time.

Details

SODA Conference 2014 Conference Paper

Better Approximation Algorithms for the Graph Diameter

  • Shiri Chechik
  • Daniel H. Larkin
  • Liam Roditty
  • Grant Schoenebeck
  • Robert Endre Tarjan
  • Virginia Vassilevska Williams

The diameter is a fundamental graph parameter and its computation is necessary in many applications. The fastest known way to compute the diameter exactly is to solve the All-Pairs Shortest Paths (APSP) problem. In the absence of fast algorithms, attempts were made to seek fast algorithms that approximate the diameter. In a seminal result Aingworth, Chekuri, Indyk and Motwani [SODA'96 and SICOMP'99] designed an algorithm that computes in time an estimate for the diameter D in directed graphs with nonnegative edge weights, such that ⌊⅔ · D ⌋ – ( M – 1) ≤ ≤ D, where M is the maximum edge weight in the graph. In recent work, Roditty and Vassilevska W. [STOC 13] gave a Las Vegas algorithm that has the same approximation guarantee but improves the (expected) runtime to. Roditty and Vassilevska W. also showed that unless the Strong Exponential Time Hypothesis fails, no ( n 2− ∊ ) time algorithm for sparse unweighted undirected graphs can achieve an approximation ratio better than. Thus their algorithm is essentially tight for sparse unweighted graphs. For weighted graphs however, the approximation guarantee can be meaningless, as M can be arbitrarily large. In this paper we exhibit two algorithms that achieve a genuine -approximation for the diameter, one running in time, and one running in time. Furthermore, our algorithms are deterministic, and thus we present the first deterministic (2 – ∊ )-approximation algorithm for the diameter that takes subquadratic time in sparse graphs. In addition, we address the question of obtaining an additive c -approximation for the diameter, i. e. an estimate such that D – c ≤ ≤ D. An extremely simple time algorithm achieves an additive n ∊ -approximation; no better results are known. We show that for any ∊ > 0, getting an additive n ∊ -approximation algorithm for the diameter running in ( n 2− δ ) time for any δ > 2 ∊ would falsify the Strong Exponential Time Hypothesis. Thus the simple algorithm is probably essentially tight for sparse graphs, and moreover, obtaining a subquadratic time additive c -approximation for any constant c is unlikely. Finally, we consider the problem of computing the eccentricities of all vertices in an undirected graph, i. e. the largest distance from each vertex. Roditty and Vassilevska W. [STOC 13] show that in time, one can compute for each v ∊ V in an undirected graph, an estimate ∊( v ) for the eccentricity ∊( v ) such that max { R, · ∊( v )} ≤ ∊( v ) ≤ min { D, · ∊( v )} where R = min v ∊(v) is the radius of the graph. Here we improve the approximation guarantee by showing that a variant of the same algorithm can achieve estimates ∊ ′ ( v ) with · ∊( v ) ≤ ∊′ ( v ) ≤ ∊( v ).

Details

SODA Conference 2013 Conference Paper

Decremental maintenance of strongly connected components

  • Liam Roditty

We consider the problem of maintaining the strongly connected components (SCCs) of an n -nodes and m -edges directed graph that undergoes a sequence of edge deletions. Recently, in SODA 2011, Łącki presented a deterministic algorithm that preprocess the graph in O ( mn ) time and creates a data structure that maintains the SCCs of a graph under edge deletions with a total update time of O ( mn ). The data structure answers strong connectivity queries in O (1) time. The worst case update time after a single edge deletion might be as large as O ( mn ). In this paper we reduce the preprocessing time and the worst case update time of Łącki's data structure from O ( mn ) to O ( m log n ). The query time and the total update time remain unchanged.

Details

STOC Conference 2013 Conference Paper

Fast approximation algorithms for the diameter and radius of sparse graphs

  • Liam Roditty
  • Virginia Vassilevska Williams

The diameter and the radius of a graph are fundamental topological parameters that have many important practical applications in real world networks. The fastest combinatorial algorithm for both parameters works by solving the all-pairs shortest paths problem (APSP) and has a running time of ~O(mn) in m-edge, n-node graphs. In a seminal paper, Aingworth, Chekuri, Indyk and Motwani [SODA'96 and SICOMP'99] presented an algorithm that computes in ~O(m√ n + n 2 ) time an estimate D for the diameter D, such that ⌊ 2/3 D ⌋ ≤ ^D ≤ D. Their paper spawned a long line of research on approximate APSP. For the specific problem of diameter approximation, however, no improvement has been achieved in over 15 years. Our paper presents the first improvement over the diameter approximation algorithm of Aingworth et. al, producing an algorithm with the same estimate but with an expected running time of ~O(m√ n). We thus show that for all sparse enough graphs, the diameter can be 3/2-approximated in o(n 2 ) time. Our algorithm is obtained using a surprisingly simple method of neighborhood depth estimation that is strong enough to also approximate, in the same running time, the radius and more generally, all of the eccentricities, i.e. for every node the distance to its furthest node. We also provide strong evidence that our diameter approximation result may be hard to improve. We show that if for some constant ε>0 there is an O(m 2-ε ) time (3/2-ε)-approximation algorithm for the diameter of undirected unweighted graphs, then there is an O*( (2-δ) n ) time algorithm for CNF-SAT on n variables for constant δ>0, and the strong exponential time hypothesis of [Impagliazzo, Paturi, Zane JCSS'01] is false. Motivated by this negative result, we give several improved diameter approximation algorithms for special cases. We show for instance that for unweighted graphs of constant diameter D not divisible by 3, there is an O(m 2-ε ) time algorithm that gives a (3/2-ε) approximation for constant ε>0. This is interesting since the diameter approximation problem is hardest to solve for small D.

Details

FOCS Conference 2012 Conference Paper

A New Infinity of Distance Oracles for Sparse Graphs

  • Mihai Patrascu
  • Liam Roditty
  • Mikkel Thorup

Given a weighted undirected graph, our basic goal is to represent all pairwise distances using much less than quadratic space, such that we can estimate the distance between query vertices in constant time. We will study the inherent trade-off between space of the representation and the stretch (multiplicative approximation disallowing underestimates) of the estimates when the input graph is sparse with m = Õ(n) edges. In this paper, for any fixed positive integers k and ℓ, we obtain stretches = 2k + 1 ± 2/ℓ = 2k + 1 - 2/ℓ, 2k + 1 + 2/ℓ, using space S(α, m) = Õ(m 1+2/(α+1) ). The query time is O(k + ℓ) = O(1). For integer stretches, this coincides with the previous bounds (odd stretches with ℓ = 1 and even stretches with ℓ = 2). The infinity of fractional stretches between consecutive integers are all new (even though ℓ is fixed as a constant independent of the input, the number of integers ℓ is still countably infinite). We will argue that the new fractional points are not just arbitrary, but that they, at least for fixed stretches below 3, provide a complete picture of the inherent trade-off between stretch and space in m. Consider any fixed stretch α 3/2 ) to Ω̃(m 5/3 ), thus matching their upper bound for stretch 2. For space in terms of m, this is the first hardness matching the space of a non-trivial/sub-quadratic distance oracle.

Details

SODA Conference 2011 Conference Paper

Fast, precise and dynamic distance queries

  • Yair Bartal
  • Lee-Ad Gottlieb
  • Tsvi Kopelowitz
  • Moshe Lewenstein
  • Liam Roditty

We present an approximate distance oracle for a point set S with n points and doubling dimension Λ. For every ε > 0, the oracle supports (1 + ε)-approximate distance queries in (universal) constant time, occupies space [ε − O (Λ) + 2 O (Λ log Λ) ] n, and can be constructed in [2 O (Λ) log 3 n + ε − O (Λ) + 2 O (Λ log Λ) ] n expected time. This improves upon the best previously known constructions, presented by Har-Peled and Mendel [13]. Furthermore, the oracle can be made fully dynamic with expected O (1) query time and only 2 O (Λ) log n + ε − O (Λ) + 2 O (Λ log Λ) update time. This is the first fully dynamic (1 + ε)-distance oracle.

Details

FOCS Conference 2011 Conference Paper

Minimum Weight Cycles and Triangles: Equivalences and Algorithms

  • Liam Roditty
  • Virginia Vassilevska Williams

We consider the fundamental algorithmic problem of finding a cycle of minimum weight in a weighted graph. In particular, we show that the minimum weight cycle problem in an undirected n-node graph with edge weights in {1, .. ., M} or in a directed n-node graph with edge weights in {-M, .. ., M} and no negative cycles can be efficiently reduced to finding a minimum weight triangle in an Θ(n)- node undirected graph with weights in {1, .. ., O(M)}. Roughly speaking, our reductions imply the following surprising phenomenon: a minimum cycle with an arbitrary number of weighted edges can be "encoded" using only three edges within roughly the same weight interval! This resolves a longstanding open problem posed in a seminal work by Itai and Rodeh [SIAM J. Computing 1978] on minimum cycle in unweighted graphs. A direct consequence of our efficient reductions are Õ(Mn ω ) ≤ 6(Mn 2. 376 )-time algorithms using fast matrix multiplication (FMM) for finding a minimum weight cycle in both undirected graphs with integral weights from the interval [1, M] and directed graphs with integral weights from the interval [-M, M]. The latter seems to reveal a strong separation between the all pairs shortest paths (APSP) problem and the minimum weight cycle problem in directed graphs as the fastest known APSP algorithm has a running time of O(M 0. 681 n 2. 575 ) by Zwick [J. ACM 2002]. In contrast, when only combinatorial algorithms are allowed (that is, without FMM) the only known solution to minimum weight cycle is by computing APSP. Interestingly, any separation between the two problems in this case would be an amazing breakthrough as by a recent paper by Vassilevska W. and Williams [FOCS'10], any O(n3 -ε )-time algorithm (ε >; 0) for minimum weight cycle immediately implies a O(n 3-δ )-time algorithm (δ >; 0) for APSP.

Details

FOCS Conference 2010 Conference Paper

Distance Oracles beyond the Thorup-Zwick Bound

  • Mihai Patrascu
  • Liam Roditty

We give the first improvement to the space/approximation trade-off of distance oracles since the seminal result of Thorup and Zwick [STOC'01]. For unweighted graphs, our distance oracle has size O(n 5/3 ) = O(n 1. 66⋯ ) and, when queried about vertices at distance d, returns a path of length 2d + 1. For weighted graphs with m = n 2 /α edges, our distance oracle has size O(n 2 /3√α) and returns a factor 2 approximation. Based on a plausible conjecture about the hardness of set intersection queries, we show that a 2-approximate distance oracle requires space Ω̃(n 2 /√α). For unweighted graphs, this implies a Ω̃(n 1. 5 ) space lower bound to achieve approximation 2d + 1.

Details

FOCS Conference 2008 Conference Paper

Dynamic Connectivity: Connecting to Networks and Geometry

  • Timothy M. Chan
  • Mihai Patrascu
  • Liam Roditty

Dynamic connectivity is a well-studied problem, but so far the most compelling progress has been confined to the edge-update model: maintain an understanding of connectivity in an undirected graph, subject to edge insertions and deletions. In this paper, we study two more challenging, yet equally fundamental problems: Subgraph connectivity asks to maintain an understanding of connectivity under vertex updates: updates can turn vertices on and off, and queries refer to the subgraph induced by "on" vertices. (For instance, this is closer to applications in networks of routers, where node faults may occur.)We describe a data structure supporting vertex updates in O~(m^{2/3}) amortized time, where m denotes the number of edges in the graph. This greatly improves over the previous result [Chan, STOC'02], which required fast matrix multiplication and had an update time of O(m^{0. 94}). The new data structure is also simpler. Geometric connectivity asks to maintain a dynamic set of ngeometric objects, and query connectivity in their intersection graph. (For instance, the intersection graph of balls describes connectivity in a network of sensors with bounded transmission radius.)Previously, nontrivial fully dynamic results were known onlyfor special cases like axis-parallel line segments and rectangles. We provide similarly improved update times, O~(n^{2/3}), for these special cases. Moreover, we show how to obtain sublinear update bounds for virtually all families of geometric objects which allow sublinear-time range queries. In particular, we obtain the first sublinear update time for arbitrary 2D line segments: O*(n^{9/10}); for d-dimensional simplices: O*(n^{1-1/d(2d+1)}); and for d-dimensional balls: O*(n^{1-1/(d+1)(2d+3)}).

Details

STOC Conference 2004 Conference Paper

A fully dynamic reachability algorithm for directed graphs with an almost linear update time

  • Liam Roditty
  • Uri Zwick

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 ( n 2 ) update barrier for all graphs with o ( n 2 ) 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.

Details

FOCS Conference 2004 Conference Paper

Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs

  • Liam Roditty
  • Uri Zwick

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.

Details

FOCS Conference 2002 Conference Paper

Improved Dynamic Reachability Algorithms for Directed Graphs

  • Liam Roditty
  • Uri Zwick

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.

Details