Surender Baswana

SODA Conference 2022 Conference Paper

Sensitivity Oracles for All-Pairs Mincuts

• Surender Baswana
• Abhyuday Pandey

Let G = (V, E ) be an undirected unweighted graph on n vertices and m edges. We address the problem of sensitivity oracle for all-pairs mincuts in G defined as follows. Build a compact data structure that, on receiving any pair of vertices s, t ∊ V and failure (or insertion) of any edge as query, can efficiently report the mincut between s and t after the failure (or the insertion). To the best of our knowledge, there exists no data structure for this problem which takes o(mn ) space and a non-trivial query time. We present the following results. Our first data structure occupies space and guarantees query time to report the value of resulting ( s, t )-mincut upon failure (or insertion) of any edge. Moreover, the set of vertices defining a resulting ( s, t )-mincut after the update can be reported in time which is worst-case optimal. Our second data structure optimizes space at the expense of increased query time. It takes space–which is also the space taken by G. The query time is where c s, t is the value of the mincut between s and t in G. This query time is faster by a factor of compared to the best known deterministic algorithm [21, 26, 28] to compute a ( s, t )-mincut from scratch. If we are only interested in knowing if failure (or insertion) of an edge changes the value of ( s, t )-mincut for any s, t ∊ V, we can distribute our space data structure evenly among n vertices. For any failed (or inserted) edge we only require the data structures stored at its endpoints to determine if the value of ( s, t )-mincut has changed for any s, t ∊ V. Moreover, using these data structures we can also output efficiently a compact encoding of all pairs of vertices whose mincut value is changed after the failure (or the insertion) of an edge.

MFCS Conference 2019 Conference Paper

Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient

• Surender Baswana
• Shiv Kumar Gupta 0001
• Ayush Tulsyan

We present an algorithm for a fault tolerant Depth First Search (DFS) Tree in an undirected graph. This algorithm is drastically simpler than the current state-of-the-art algorithms for this problem, uses optimal space and optimal preprocessing time, and still achieves better time complexity. This algorithm also leads to a better time complexity for maintaining a DFS tree in a fully dynamic environment.

SODA Conference 2018 Conference Paper

Approximate Single Source Fault Tolerant Shortest Path

• Surender Baswana
• Keerti Choudhary
• Moazzam Hussain
• Liam Roditty

SODA Conference 2018 Conference Paper

Incremental DFS algorithms: a theoretical and experimental study

• Surender Baswana
• Ayush Goel
• Shahbaz Khan 0004

The depth first search (DFS) tree is a fundamental data structure used for solving various graph problems. For a given graph G = ( V, E ) on n vertices and m edges, a DFS tree can be built in O ( m + n ) time. In the last 20 years, a few algorithms have been designed for maintaining a DFS tree efficiently under insertion of edges. For undirected graphs, there are two prominent algorithms, namely, ADFS1 and ADFS2 [ICALP14] that achieve total update time of and O ( n 2 ) respectively. For directed acyclic graphs, the only non-trivial algorithm, namely, FDFS [IPL97] requires total O ( mn ) update time. However, even after 20 years of this result, there does not exist any non-trivial incremental algorithm for maintaining a DFS tree in directed graphs with o ( m 2 ) worst case bound. In this paper, we carry out extensive experimental and theoretical evaluation of the existing incremental DFS algorithms in random graphs and real world graphs and derive the following results. 1. For insertion of a uniformly random sequence of edges, each of ADFS1, ADFS2 and FDFS perform equally well and are found to take Θ( n 2 ) time experimentally. This is quite surprising because the worst case bounds of ADFS1 and FDFS are greater than Θ( n 2 ) by a factor of and m/n respectively, which are also proven to be tight. We complement this experimental result with a probabilistic analysis of these algorithms establishing Õ ( n 2 ) bound on their time complexity. For this purpose, we derive results about the structure of a DFS tree in a random graph. These results are of independent interest in the domain of random graphs. 2. The insight that we developed about DFS tree in random graphs leads us to design an extremely simple algorithm for incremental DFS that works for both undirected and directed graphs. Moreover, this algorithm theoretically matches and experimentally outperforms the state-of-the-art algorithm in dense random graphs. Furthermore, it can also be used as a single-pass semi-streaming algorithm for computing incremental DFS and strong connectivity for random graphs using O ( n log n ) space. 3. Even for real world graphs, which are usually sparse, both ADFS1 and FDFS turn out to be much better than their theoretical bounds. Here again, we present two simple algorithms for incremental DFS for directed and undirected graphs respectively, which perform very well on real graphs. In fact our proposed algorithm for directed graphs almost always matches the performance of FDFS.

SODA Conference 2016 Conference Paper

Dynamic DFS in Undirected Graphs: breaking the O( m ) barrier

• Surender Baswana
• Shreejit Ray Chaudhury
• Keerti Choudhary
• Shahbaz Khan 0004

Given an undirected graph G = ( V, E ) on n vertices and m edges, we address the problem of maintaining a DFS tree when the graph is undergoing updates (insertion and deletion of vertices or edges). We present the following results for this problem. 1. Fault tolerant DFS tree: There exists a data structure of size Õ ( m ) 1 such that given any set ℱ of failed vertices or edges, a DFS tree of the graph G\ℱ can be reported in Õ ( n | ℱ |) time. 2. Fully dynamic DFS tree: There exists a fully dynamic algorithm for maintaining a DFS tree that takes worst case time per update for any arbitrary online sequence of updates. 3. Incremental DFS tree: Given any arbitrary online sequence of edge insertions, we can maintain a DFS tree in Õ ( n ) worst case time per edge insertion. These are the first o ( m ) worst case time results for maintaining a DFS tree in a dynamic environment. Moreover, our fully dynamic algorithm provides, in a seamless manner, the first deterministic algorithm with O (1) query time and o ( m ) worst case update time for the dynamic subgraph connectivity, biconnectivity, and 2-edge connectivity.

STOC Conference 2016 Conference Paper

Fault tolerant subgraph for single source reachability: generic and optimal

• Surender Baswana
• Keerti Choudhary
• Liam Roditty

SODA Conference 2012 Conference Paper

Single source distance oracle for planar digraphs avoiding a failed node or link

• Surender Baswana
• Utkarsh Lath
• Anuradha S. Mehta

Let G = ( V, E ) be a directed planar graph on n = | V | vertices, and let s ∊ V be any fixed source vertex. We show that G can be preprocessed in O ( n polylog n ) time to build a data structure of O ( n polylog n ) size which can answer the following query in O (log n ) time for any u, v ∊ V: report distance from s to v in the graph G\{u} We also address the all-pairs version of this problem and present a data structure with O ( n √ n polylog n ) preprocessing time and space which guarantees O (√ n polylog n ) query time.

FOCS Conference 2011 Conference Paper

Fully Dynamic Maximal Matching in O (log n) Update Time

• Surender Baswana
• Manoj Gupta 0002
• Sandeep Sen

We present an algorithm for maintaining maximal matching in a graph under addition and deletion of edges. Our data structure is randomized that takes $O( \log n)$ expected amortized time for each edge update where $n$ is the number of vertices in the graph. While there is a trivial $O(n)$ algorithm for edge update, the previous best known result for this problem was due to Ivkovi\'c and Llyod\cite{llyod}. For a graph with $n$ vertices and $m$ edges, they give an $O( {(n+ m)}^{0. 7072})$ update time algorithm which is sub linear only for a sparse graph. %To the best of our knowledge this %is the first polylog update time for maximal matching that implies an % exponential improvement from the previous results. For the related problem of maximum matching, Onak and Rubinfeld \cite{onak} designed a randomized data structure that achieves $O(\log^2 n)$ expected amortized time for each update for maintaining a $c$-approximate maximum matching for some large constant $c$. In contrast, we can maintain a factor two approximate maximum matching in $O(\log n )$ expected amortized time per update as a direct corollary of the maximal matching scheme. This in turn also implies a two approximate vertex cover maintenance scheme that takes $O(\log n )$expected amortized time per update.

TCS Journal 2009 Journal Article

All-pairs nearly 2-approximate shortest paths in O ( n 2 polylog n ) time

• Surender Baswana
• Vishrut Goyal
• Sandeep Sen

Let G = ( V, E ) be an unweighted undirected graph on | V | = n vertices and | E | = m edges. Let δ ( u, v ) denote the distance between vertices u, v ∈ V. An algorithm is said to compute all-pairs t -approximate shortest-paths/distances, for some t ≥ 1, if for each pair of vertices u, v ∈ V, the path/distance reported by the algorithm is not longer/greater than t ⋅ δ ( u, v ). This paper presents two extremely simple randomized algorithms for computing all-pairs nearly 2-approximate distances. The first algorithm requires an expected O ( m 2 / 3 n log n + n 2 ) time, and for any u, v ∈ V reports a distance no greater than 2 δ ( u, v ) + 1. Our second algorithm requires an expected O ( n 2 log 3 / 2 n ) time, and for any u, v ∈ V reports a distance bounded by 2 δ ( u, v ) + 3.

SODA Conference 2008 Conference Paper

Fully dynamic algorithm for graph spanners with poly-logarithmic update time

• Surender Baswana
• Soumojit Sarkar

FOCS Conference 2006 Conference Paper

Faster Algorithms for Approximate Distance Oracles and All-Pairs Small Stretch Paths

• Surender Baswana
• Telikepalli Kavitha

Let G = (V, E) be a weighted undirected graph with |V| = n and |E| = m. An estimate deltacirc(u, v) of the distance delta(u, v) in G between u, v isin V is said to be of stretch t iff delta(u, v) les deltacirc(u, v) les t middot delta(u, v). The most efficient algorithms known for computing small stretch distances in G are the approximate distance oracles of (M. Thorup and U. Zwick, 2005) and the three algorithms in (E. Cohen and U. Zwick, 2001) to compute all-pairs stretch t distances for t = 2, 7/3, and 3. We present faster algorithms for these problems. For any integer k ges 1, Thorup and Zwick (2005) gave an O(kmn 1 k/) algorithm to construct a data structure of size O(kn 1 + 1 k/) which, given a query (u, v) isin V times V, returns in O(k) time, a 2k - 1 stretch estimate of delta(u, v). But for small values of k, the time to construct the oracle is rather high. Here we present an O(n 2 log n) algorithm to construct such a data structure of size O(kn 1+1 k/) for all integers k ges 2. Our query answering time is O(k) for k > 2 and Theta (log n) for k = 2. We use a new generic scheme for all-pairs approximate shortest paths for these results. This scheme also enables us to design faster algorithms for all-pairs t-stretch distances for t = 2 and 7/3, and compute all-pairs almost stretch 2 distances in O(n 2 log n) time

SODA Conference 2005 Conference Paper

New constructions of (alpha, beta)-spanners and purely additive spanners

• Surender Baswana
• Telikepalli Kavitha
• Kurt Mehlhorn
• Seth Pettie

SODA Conference 2004 Conference Paper

Approximate distance oracles for unweighted graphs in Õ(n 2 ) time

• Surender Baswana
• Sandeep Sen

SODA Conference 2003 Conference Paper

Maintaining all-pairs approximate shortest paths under deletion of edges

• Surender Baswana
• Ramesh Hariharan
• Sandeep Sen

STOC Conference 2002 Conference Paper

Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths

• Surender Baswana
• Ramesh Hariharan
• Sandeep Sen

We present improved algorithms for maintaining transitive closure and all-pairs shortest paths/distances in a digraph under deletion of edges.(MATH) For the problem of transitive closure, the previous best known algorithms, for achieving O (1) query time, require O (\min(m, \frac{n^3}{m}))$ amortized update time, implying an upper bound of O (n^{\frac{3}{2}})$ on update time per edge-deletion. We present an algorithm that achieves $O(1)$ query time and O (n \log^2n + \frac{n^2}{\sqrt{m}}{\sqrt{\log n}})$ update time per edge-deletion, thus improving the upper bound to O (n^{\frac{4}{3}}\sqrt[3]{\log n})$.(MATH) For the problem of maintaining all-pairs shortest distances in unweighted digraph under deletion of edges, we present an algorithm that requires O (\frac{n^3}{m} \log^2 n)$ amortized update time and answers a distance query in O (1) time. This improves the previous best known update bound by a factor of log n . For maintaining all-pairs shortest paths, we present an algorithm that achieves O (\min(n^{\frac{3}{2}} \sqrt{\log n}, \frac{n^3}{m} \log ^2n))$ amortized update time and reports a shortest path in optimal time (proportional to the length of the path). For the latter problem we improve the worst amortized update time bound by a factor of O (\sqrt{\frac{n}{\log n}})$.(MATH) We also present the first decremental algorithm for maintaining all-pairs (1+ε) approximate shortest paths/distances, for any ε > 0 , that achieves a sub-quadratic update time of O ( n log 2 n + \frac{n^2}{\sqrt{\epsilon m}}\sqrt{\log n})$ and optimal query time.Our algorithms are randomized and have one-sided error for query (with probability O (1/ n c ) for any constant c ).