Let G be an undirected graph on a set V of n vertices. For any non-empty subset A⊊ V, cut defined by A is the ordered pair (A,V\A). Suppose each cut is assigned a value, which is any arbitrary real number. Let u,v ∈ V be any pair of vertices. A cut is said to be a (u,v)-cut if it separates u and v. A (u,v)-cut of the minimum value is called a (u,v)-mincut. A 2nd (u,v)-mincut is a (u,v)-cut of second minimum value. We can define k-th mincut accordingly. We present the following results for the all-pairs k-th mincuts. (1) Distinct Values of all-pairs k-th Mincuts: There exist k spanning trees on V such that for any pair (u,v), the value of k-th (u,v)-mincut is equal to the capacity of an edge on the (u,v)-path in one of the k trees. We also show a matching lower bound of Ω(min{kn,n²}). Our result generalizes the well-known result by Gomory and Hu [JSIAM 1961] stating that there are at most n-1 distinct values of all-pairs mincuts. (2) Ancestor Trees for all-pairs k-th Mincuts: In 1991, Cheng and Hu [AOR 1991] invented a rooted binary tree, called ancestor tree, whose leaves are the vertices of the graph and each internal node stores a cut with the following property. For any pair (u,v), the cut stored at their lowest common ancestor (LCA) is a (u,v)-mincut. We introduce a tree called gen-ancestor tree, that generalizes the ancestor tree for k-th mincuts, and achieve the following result. There exists a set of 𝒪(klog n) gen-ancestor trees such that, for any pair (u,v), a k-th (u,v)-mincut is stored at the LCA of u and v in at least one of these trees. (3) Data Structures: We present the following data structures for all-pairs k-th mincuts. (i) There exists an 𝒪(nlog n) space data structure that can report the value of 2nd (u,v)-mincut in 𝒪(log n) time for any given pair (u,v). We generalize this data structure for k-th mincuts with a factor of k² in the space and query time. (ii) There exists an 𝒪(kn² log n) space data structure that can report a k-th (u,v)-mincut (A,V\A) in 𝒪(|A|) time for any given pair (u,v). For any constant k, the bounds stated above match, up to a logarithmic factor, the best-known bounds guaranteed by the data structure for all-pairs mincuts (Cheng and Hu [AOR 1991]).

Let G be a directed graph on n vertices and m edges. In this article, we study (s,t)-cuts of second minimum capacity and present the following algorithmic and graph-theoretic results. 1) Second (s,t)-mincut: Vazirani and Yannakakis [ICALP 1992] designed the first algorithm for computing an (s,t)-cut of second minimum capacity using {O}(n²) maximum (s,t)-flow computations. We present the following algorithm that improves the running time significantly. For directed integer-weighted graphs, there is an algorithm that can compute an (s,t)-cut of second minimum capacity using Õ(√n) maximum (s,t)-flow computations with high probability. To achieve this result, a close relationship of independent interest is established between (s,t)-cuts of second minimum capacity and global mincuts in directed weighted graphs. 2) Minimum+1 (s,t)-cuts: Minimum+1 (s,t)-cuts have been studied quite well recently [Baswana, Bhanja, and Pandey, ICALP 2022 & TALG 2023], which is a special case of second (s,t)-mincut. We present the following structural result and the first nontrivial algorithm for minimum+1 (s,t)-cuts. 3) Algorithm: For directed multi-graphs, we design an algorithm that, given any maximum (s,t)-flow, computes a minimum+1 (s,t)-cut, if it exists, in O(m) time. 4) Structure: The existing structures for storing and characterizing all minimum+1 (s,t)-cuts occupy {O}(mn) space [Baswana, Bhanja, and Pandey, TALG 2023]. For undirected multi-graphs, we design a directed acyclic graph (DAG) occupying only {O}(m) space that stores and characterizes all minimum+1 (s,t)-cuts. This matches the space bound of the widely-known DAG structure for all (s,t)-mincuts [Picard and Queyranne, Math. Prog. Studies 1980]. 5) Dual Edge Sensitivity Oracle: The study of minimum+1 (s,t)-cuts often turns out to be useful in designing dual edge sensitivity oracles - a compact data structure for efficiently reporting an (s,t)-mincut after insertion/failure of any given pair of query edges. It has been shown recently [Bhanja, ICALP 2025] that any dual edge sensitivity oracle for (s,t)-mincut in undirected multi-graphs must occupy Ω(n²) space in the worst-case irrespective of the query time. Interestingly, for undirected unweighted simple graphs, we break this quadratic barrier while achieving a non-trivial query time as follows. There is an O(n√n) space data structure that can report an (s,t)-mincut in O(min{m,n√n}) time after the insertion/failure of any given pair of query edges. To arrive at our results, as one of our key techniques, we establish interesting relationships between (s,t)-cuts of capacity (minimum+Δ), Δ ≥ 0, and maximum (s,t)-flow. We believe that these techniques and the graph-theoretic result in 2.(b) are of independent interest.

Let G be a directed weighted graph (DiGraph) on n vertices and m edges with source s and sink t. An edge in G is vital if its removal reduces the capacity of (s,t)-mincut. Since the seminal work of Ford and Fulkerson, a long line of work has been done on computing the most vital edge and all vital edges of G. Unfortunately, after 60 years, the existing results are for undirected or unweighted graphs. We present the following result for DiGraph, which solves an open problem stated by Ausiello et al. 1. There is an algorithm that computes all vital edges as well as the most vital edge of G using O(n) maxflow computations. Vital edges play a crucial role in the design of Sensitivity Oracle (SO) for (s,t)-mincut. For directed graphs, the only existing SO is for unweighted graphs by Picard and Queyranne. We present the first and optimal SO for DiGraph. 2. (a) There is an O(n) space SO that can report in O(1) time the capacity of (s,t)-mincut and (b) an O($n^2$) space SO that can report an (s,t)-mincut in O(n) time after failure/insertion of an edge. For unweighted graphs, Picard and Queyranne designed an O(m) space DAG that stores and characterizes all mincuts for all vital edges. Conversely, there is a set containing at most n-1 (s,t)-cuts such that at least one mincut for every vital edge belongs to the set. We generalize these results for DiGraph. 3. (a) There is a set containing at most n-1 (s,t)-cuts such that at least one mincut for every vital edge is present in the set. (b) We design two compact structures for storing and characterizing all mincuts for all vital edges, (i) O(m) space DAG for partial characterization and (ii) O(mn) space structure for complete characterization. To arrive at our results, we develop new techniques, especially a generalization of maxflow-mincut theorem by Ford and Fulkerson, which might be of independent interest.

Let G be a directed multi-graph on n vertices and m edges with a designated source vertex s and a designated sink vertex t . We study the ( s,t )-cuts of capacity minimum+1 and as an important application of them, we give a solution to the dual-edge sensitivity for ( s,t )-mincuts—reporting an ( s,t )-mincut upon failure or insertion of any pair of edges. Picard and Queyranne [Mathematical Programming Studies, 13(1): 8–16 (1980)] showed that there exists a directed acyclic graph (DAG) that compactly stores all minimum ( s,t )-cuts of G . This structure also acts as an oracle for the single-edge sensitivity of minimum ( s,t )-cut. For undirected multi-graphs, Dinitz and Nutov [STOC, 509–518 (1995)] showed that there exists an 𝒪( n ) size 2-level Cactus model that stores all global cuts of capacity minimum+1. However, for minimum+1 ( s,t )-cuts, no such compact structure exists till date. We present the following structural and algorithmic results on minimum+1 ( s,t )-cuts. (1) Structure: There is an 𝒪( m ) size 2-level DAG structure that stores all minimum+1 (s,t) -cuts of G such that each minimum+1 ( s,t )-cut appears as 3-transversal cut—it intersects any path in this structure at most thrice. We also show that there is an 𝒪( mn ) size structure for storing and characterizing all minimum+1 (s,t) -cuts in terms of 1-transversal cuts. (2) Data structure: There exists an 𝒪( n 2 ) size data structure that, given a pair of vertices {u,v} that are not separated by an ( s,t )-mincut, can determine in 𝒪(1) time if there exists a minimum+1 ( s,t )-cut, say ( A,B ), such that s,u ∊ A and v,t∊ B ; the corresponding cut can be reported in 𝒪(| B |) time. (3) Sensitivity oracle: There exists an 𝒪( n 2 ) size data structure that solves the dual-edge sensitivity problem for (s,t) -mincuts. It takes 𝒪(1) time to report the capacity of a resulting (s,t) -mincut (A,B) and 𝒪(| B |) time to report the cut. (4) Lower bounds: For the data structure problems addressed in results (2) and (3) above, we also provide a matching conditional lower bound. We establish a close relationship among three seemingly unrelated problems—all-pairs directed reachability problem, the dual-edge sensitivity problem for ( s,t )-mincuts, and the problem of reporting the capacity of ({ x,y }, { u,v })-mincut for any four vertices x,y,u,v in G . Assuming the Directed Reachability Hypothesis by Patrascu [SIAM J. Computing, 827–847 (2011)] and Goldstein et al. [WADS, 421–436 (2017)], this leads to \(\tilde{\Omega }(n^2)\) lower bounds on the space for the latter two problems.

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 cs,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.

Let G = (V,E) be an undirected graph on n vertices with non-negative capacities on its edges. The mincut sensitivity problem for the insertion of an edge is defined as follows. Build a compact data structure for G and a given set S ⊆ V of vertices that, on receiving any edge (x,y) ∈ S×S of positive capacity as query input, can efficiently report the set of all pairs from S× S whose mincut value increases upon insertion of the edge (x,y) to G. The only result that exists for this problem is for a single pair of vertices (Picard and Queyranne, Mathematical Programming Study, 13 (1980), 8-16). We present the following results for the single source and the all-pairs versions of this problem. 1) Single source: Given any designated source vertex s, there exists a data structure of size 𝒪(|S|) that can output all those vertices from S whose mincut value to s increases upon insertion of any given edge. The time taken by the data structure to answer any query is 𝒪(|S|). 2) All-pairs: There exists an 𝒪(|S|²) size data structure that can output all those pairs of vertices from S× S whose mincut value gets increased upon insertion of any given edge. The time taken by the data structure to answer any query is 𝒪(k), where k is the number of pairs of vertices whose mincut increases. For both these versions, we also address the problem of reporting the values of the mincuts upon insertion of any given edge. To derive our results, we use interesting insights into the nearest and the farthest mincuts for a pair of vertices. In addition, a crucial result, that we establish and use in our data structures, is that there exists a directed acyclic graph of 𝒪(n) size that compactly stores the farthest mincuts from all vertices of V to a designated vertex s in the graph. We believe that this result is of independent interest, especially, because it also complements a previously existing result by Hariharan et al. (STOC 2007) that the nearest mincuts from all vertices of V to s is a laminar family, and hence, can be stored compactly in a tree of 𝒪(n) size.

Let G=(V,E) be an n -vertices m -edges directed graph with edge weights in the range [1, W ] for some parameter W , and sϵ V be a designated source. In this article, we address several variants of the problem of maintaining the (1+ε)-approximate shortest path from s to each v ϵ V { s } in the presence of a failure of an edge or a vertex. From the graph theory perspective, we show that G has a subgraph H with Õ(ε -1 } n log W ) edges such that for any x,vϵ V , the graph H \ x contains a path whose length is a (1+ε)-approximation of the length of the shortest path from s to v in G \ x . We show that the size of the subgraph H is optimal (up to logarithmic factors) by proving a lower bound of Ω (ε -1 n log W ) edges. Demetrescu, Thorup, Chowdhury, and Ramachandran (SICOMP 2008) showed that the size of a fault tolerant exact shortest path subgraph in weighted directed/undirected graphs is Ω ( m ). Parter and Peleg (ESA 2013) showed that even in the restricted case of unweighted undirected graphs, the size of any subgraph for the exact shortest path is at least Ω ( n 1.5 ). Therefore, a (1+ε)-approximation is the best one can hope for. We consider also the data structure problem and show that there exists an ϕ(ε -1 n log W ) size oracle that for any vϵ V reports a (1+ε)-approximate distance of v from s on a failure of any xϵ V in O(log log 1+ε ( nW )) time. We show that the size of the oracle is optimal (up to logarithmic factors) by proving a lower bound of Ω (ε -1 n log W log -1 n ). Finally, we present two distributed algorithms . We present a single-source routing scheme that can route on a (1+ε)-approximation of the shortest path from a fixed source s to any destination t in the presence of a fault. Each vertex has a label and a routing table of ϕ(ε -1 log W ) bits. We present also a labeling scheme that assigns each vertex a label of ϕ(ε -1 log W ) bits. For any two vertices x,vϵ V , the labeling scheme outputs a (1+ε)-approximation of the distance from s to v in G \ x using only the labels of x and v .

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.

Depth first search (DFS) tree is a fundamental data structure for solving various problems in graphs. It is well known that it takes $O(m+n)$ time to build a DFS tree for a given 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 $\tilde{O}(m)$ (where $\tilde{O}()$ hides the polylogarithmic factors) which can be preprocessed in $\tilde{O}(m)$ time such that given any set ${\cal F}$ of failed vertices or edges, a DFS tree of the graph $G\setminus {\cal F}$ can be reported in $\tilde{O}(n|{\cal F}|)$ time. (2) Fully dynamic DFS tree: There exists a fully dynamic algorithm for maintaining a DFS tree that takes $\tilde{O}(m)$ time for preprocessing and worst case $\tilde{O}(\sqrt{mn})$ time per update for any arbitrary online sequence of updates. (3) Incremental DFS tree: There exists an incremental algorithm for maintaining a DFS tree that takes $\tilde{O}(m)$ time for preprocessing and worst case $\tilde{O}(n)$ time per update for any arbitrary online sequence of edge insertion. These are the first $o(m)$ worst case time results for maintaining a DFS tree of a dense graph in a dynamic environment. Moreover, our fully dynamic algorithm provides, in a seamless manner, the first deterministic algorithm for dense graphs with $O(1)$ query time and $o(m)$ worst case update time for connectivity, biconnectivity, and 2-edge connectivity in the dynamic subgraph model.

Let G = (V, E) be an n-vertices m-edges directed graph with edge weights in the range [1, W] and L = log(W). Let s ∊ V be a designated source. In this paper we address several variants of the problem of maintaining the (1 + ∊)-approximate shortest path from s to each υ ∊ V \ {s} in the presence of a failure of an edge or a vertex. From the graph theory perspective we show that G has a subgraph H with Õ(nL/∊) edges such that for any x,υ ∊ V, the graph H \ x contains a path whose length is a (1 + ∊)-approximation of the length of the shortest path from s to υ in G \ x. We show that the size of the subgraph H is optimal (up to logarithmic factors) by proving a lower bound of Ω(nL/∊) edges. Demetrescu, Thorup, Chowdhury and Ramachandran [12] showed that the size of a fault tolerant exact shortest path subgraph in weighted directed/undirected graphs is Ω(m). Parter and Peleg [18] showed that even in the restricted case of unweighted undirected graphs the size of any subgraph for the exact shortest path is at least Ω(n1.5). Therefore, a (1 + ∊)-approximation is the best one can hope for. We consider also the data structure problem and show that there exists an Õ(nL/∊) size oracle that for any υ ∊ V reports a (1 + ∊)-approximate distance of v from s on a failure of any x ∊ V in O(loglog1+∊(nW)) time. We show that the size of the oracle is optimal (up to logarithmic factors) by proving a lower bound of Ω(nL/∊ log n). Finally, we present two distributed algorithms. We present a single source routing scheme that can route on a (1 + ∊)-approximation of the shortest path from a fixed source s to any destination t in the presence of a fault. Each vertex has a label and a routing table of Õ(L/∊) bits. We present also a labeling scheme that assigns each vertex a label of Õ(L/∊) bits. For any two vertices x, υ ∊ V the labeling scheme outputs a (1 + ∊)-approximation of the distance from s to υ in G\x using only the labels of x and v.

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(n2) 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(m2) 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 Θ(n2) time experimentally. This is quite surprising because the worst case bounds of ADFS1 and FDFS are greater than Θ(n2) 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 Õ(n2) 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.

Let $G$ be a directed graph with $n$ vertices, $m$ edges, and a designated source vertex $s$. We address the problem of single-source reachability (SSR) from $s$ in the presence of failures of vertices/edges. We show that for every $k\geq1$, there is a subgraph $H$ of $G$ with at most $2^kn$ edges that preserves the reachability from $s$ even after the failure of any $k$ edges. Formally, given a set $F$ of $k$ edges, a vertex $v\in V(G)$ is reachable from $s$ in $G\setminus F$ if and only if $v$ is reachable from $s$ in $H\setminus F$. We call $H$ a $k$-fault tolerant reachability subgraph ($\textsc{$k$-FTRS}$). We also prove a matching lower bound of $\Omega(2^kn)$ edges for such subgraphs that holds for all $n,k$ with $2^k\leq n$. Our results extend to vertex failures without any extra overhead. The construction of ${$k$-FTRS}$ is interesting from several different perspectives. From the Graph theory perspective it reveals a separation between SSR and single-source shortest paths (SSSP) in directed graphs. More specifically, in the case of SSSP in weighted directed and undirected graphs, Demetrescu et al. showed that there is a lower bound of $\Omega(m)$ edges even for a single edge failure [ SIAM J. Comput., 37 (2008), pp. 1299--1318]. In the case of unweighted graphs Parter and Peleg gave a lower bound of $\Omega(n^{3/2})$ edges, again, even for a single edge failure [ Proc. Algorithms---21st Annual European Symposium, 2013, pp. 779--790]. From the Algorithms perspective it implies fault-tolerant algorithms for other interesting problems, namely, (i) verifying if the strong connectivity of a graph is preserved after $k$ edge or vertex failures, and (ii) computing a dominator tree of a graph after $k$-failures. From the perspective of techniques it makes an interesting usage of the concept of farthest min-cut which was already introduced by Ford and Fulkerson in their pioneering work on flows and cuts [ Flows in Networks, Princeton University Press, 1962; reprinted 2011]. We show that there is a close relationship between the farthest min-cut and the ${$k$-FTRS}$. We believe that our new technique is of independent interest.

We present an algorithm for maintaining a maximal matching in a graph under addition and deletion of edges. Our algorithm is randomized and it takes expected amortized $O(\log n)$ time for each edge update, where $n$ is the number of vertices in the graph. Moreover, for any sequence of $t$ edge updates, the total time taken by the algorithm is $O(t\log n + n \log^2 n)$ with high probability. (Original article at https://doi.org/10.1137/130914140.)

In this paper we study the problem of maintaining the strongly connected components of a graph in the presence of failures. In particular, we show that given a directed graph G=(V,E) with n=|V| and m=|E|, and an integer value k\geq 1, there is an algorithm that computes in O(2^{k}n log^2 n) time for any set F of size at most k the strongly connected components of the graph G\F. The running time of our algorithm is almost optimal since the time for outputting the SCCs of G\F is at least \Omega(n). The algorithm uses a data structure that is computed in a preprocessing phase in polynomial time and is of size O(2^{k} n^2). Our result is obtained using a new observation on the relation between strongly connected components (SCCs) and reachability. More specifically, one of the main building blocks in our result is a restricted variant of the problem in which we only compute strongly connected components that intersect a certain path. Restricting our attention to a path allows us to implicitly compute reachability between the path vertices and the rest of the graph in time that depends logarithmically rather than linearly in the size of the path. This new observation alone, however, is not enough, since we need to find an efficient way to represent the strongly connected components using paths. For this purpose we use a mixture of old and classical techniques such as the heavy path decomposition of Sleator and Tarjan and the classical Depth-First-Search algorithm. Although, these are by now standard techniques, we are not aware of any usage of them in the context of dynamic maintenance of SCCs. Therefore, we expect that our new insights and mixture of new and old techniques will be of independent interest.

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.

Let G=(V,E) be an n-vertices m-edges directed graph. Let s∈ V be any designated source vertex. We address the problem of single source reachability (SSR) from s in presence of failures of vertices/edges. We show that for every k≥ 1, there is a subgraph H of G with at most 2k n edges that preserves the reachability from s even after the failure of any k edges. Formally, given a set F of k edges, a vertex u∈ V is reachable from s in G∖ F if and only if u is reachable from s in H∖ F. We call H a k-Fault Tolerant Reachability Subgraph (k-FTRS). We prove also a matching lower bound of Ω(2kn) for such subgraphs. Our results extend to vertex failures without any extra overhead. The general construction of k-FTRS is interesting from several different perspectives. From the Graph theory perspective it reveals a separation between SSR and single source shortest paths (SSSP) in directed graphs. More specifically, in the case of SSSP in weighted directed graphs, there is a lower bound of Ω(m) even for a single edge failure. In the case of unweighted graphs there is a lower bound of Ω(n3/2) edges, again, even for a single edge failure. There is also a matching upper bound but nothing is known for two or more failures in the directed graphs. From the Algorithms perspective it implies fault tolerant solutions to other interesting problems, namely, (i) verifying if the strong connectivity of a graph is preserved after k edge or vertex failures, (ii) computing a dominator tree of a graph after k-failures. From the perspective of Techniques it makes an interesting usage of the concept of farthest min-cut which was already introduced by Ford and Fulkerson in their pioneering work on flows and cuts. We show that there is a close relationship between the farthest min-cut and the k-FTRS. We believe that our new technique is of independent interest.

We present an algorithm for maintaining maximal matching in a graph under addition and deletion of edges. Our algorithm is randomized and it takes expected amortized $O(\log n)$ time for each edge update, where $n$ is the number of vertices in the graph. While there exists a trivial $O(n)$ time algorithm for each edge update, the previous best known result for this problem is due to Ivković and Lloyd [ Lecture Notes in Comput. Sci. 790, Springer-Verlag, London, 1994, pp. 99--111]. For a graph with $n$ vertices and $m$ edges, they gave an $O( {(n+ m)}^{0.7072})$ update time algorithm which is sublinear only for a sparse graph. For the related problem of maximum matching, Onak and Rubinfeld [ Proceedings of STOC'10, Cambridge, MA, 2010, pp. 457--464] designed a randomized algorithm that achieves expected amortized $O(\log^2 n)$ time for each update for maintaining a $c$-approximate maximum matching for some unspecified large constant $c$. In contrast, we can maintain a factor 2 approximate maximum matching in expected amortized $O(\log n )$ time per update as a direct corollary of the maximal matching scheme. This in turn also implies a 2-approximate vertex cover maintenance scheme that takes expected amortized $O(\log n )$ time per update. (A corrected version is at https://epubs.siam.org/doi/abs/10.1137/16M1106158.)

Acyclic path profiles are an indispensable tool geared towards multiple ends, with applications spanning from compiler optimizations to software engineering. Though such profiles provide an usable approximation to the program trace, many a times programmers are more interested in uncovering high-level interactions among a set of pertinent statements - not so much in the overall control-flow profile of the program. We propose a new profiling technique, Pertinent Path Profiling, which attempts to unveil such high-level interactions efficiently: given a control-flow graph and a set of pertinent basic-blocks (containing the relevant statements, Pertinent Path Profiling uniquely and efficiently identifies these high-level interactions, revealing execution demeanors that are otherwise difficult to discover via current control-flow profiling schemes. Additionally, if the number of pertinent basic-blocks is small, most of the time our algorithm yields much smaller path-frequency tables than those obtained by acyclic path profilers: if we are interested in a pertinent path profile with about 30% of the basic-blocks marked pertinent, most functions shrink their path-tables to about 15% of that of the acyclic path profiler. We illustrate a couple of possible applications of this new technology and provide experimental results on a set of benchmark programs to testify the utility of this new profiling technique.

We present a fully dynamic algorithm for maintaining approximate maximum weight matching in general weighted graphs. The algorithm maintains a matching M whose weight is at least 1/8 M^{*} where M^{*} is the weight of the maximum weight matching. The algorithm achieves an expected amortized O(log n log C) time per edge insertion or deletion, where C is the ratio of the weights of the highest weight edge to the smallest weight edge in the given graph.

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.

Spanner of an undirected graph G = ( V,E ) is a subgraph that is sparse and yet preserves all-pairs distances approximately. More formally, a spanner with stretch t ∈ ℕ is a subgraph ( V,E S ), E S ⊆ E such that the distance between any two vertices in the subgraph is at most t times their distance in G . Though G is trivially a t -spanner of itself, the research as well as applications of spanners invariably deal with a t -spanner that has as small number of edges as possible. We present fully dynamic algorithms for maintaining spanners in centralized as well as synchronized distributed environments. These algorithms are designed for undirected unweighted graphs and use randomization in a crucial manner. Our algorithms significantly improve the existing fully dynamic algorithms for graph spanners. The expected size (number of edges) of a t -spanner maintained at each stage by our algorithms matches, up to a polylogarithmic factor, the worst case optimal size of a t -spanner. The expected amortized time (or messages communicated in distributed environment) to process a single insertion/deletion of an edge by our algorithms is close to optimal.

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.

Let $G=(V,E)$ be any undirected graph on $V$ vertices and $E$ edges. A path $\textbf{P}$ between any two vertices $u,v\in V$ is said to be $t$-approximate shortest path if its length is at most $t$ times the length of the shortest path between $u$ and $v$. We consider the problem of building a compact data structure for a given graph $G$ which is capable of answering the following query for any $u,v,z\in V$ and $t>1$. \centerline{\em report $t$-approximate shortest path between $u$ and $v$ when vertex $z$ fails} We present data structures for the single source as well all-pairs versions of this problem. Our data structures guarantee optimal query time. Most impressive feature of our data structures is that their size {\em nearly} match the size of their best static counterparts.

Let $G=(V,E)$ be a weighted undirected graph having nonnegative edge weights. An estimate $\hat{\delta}(u,v)$ of the actual distance $\delta(u,v)$ between $u,v\in V$ is said to be of stretch t if and only if $\delta(u,v)\leq\hat{\delta}(u,v)\leq t\cdot\delta(u,v)$. Computing all-pairs small stretch distances efficiently (both in terms of time and space) is a well-studied problem in graph algorithms. We present a simple, novel, and generic scheme for all-pairs approximate shortest paths. Using this scheme and some new ideas and tools, we design faster algorithms for all-pairs t-stretch distances for a whole range of stretch t, and we also answer an open question posed by Thorup and Zwick in their seminal paper [J. ACM, 52 (2005), pp. 1–24].

An (α, β)-spanner of an unweighted graph G is a subgraph H that distorts distances in G up to a multiplicative factor of α and an additive term β. It is well known that any graph contains a (multiplicative) (2 k −1, 0)-spanner of size O ( n 1+1/ k ) and an (additive) (1,2)-spanner of size O ( n 3/2 ). However no other additive spanners are known to exist. In this article we develop a couple of new techniques for constructing (α, β)-spanners. Our first result is an additive (1,6)-spanner of size O ( n 4/3 ). The construction algorithm can be understood as an economical agent that assigns costs and values to paths in the graph, purchasing affordable paths and ignoring expensive ones, which are intuitively well approximated by paths already purchased. We show that this path buying algorithm can be parameterized in different ways to yield other sparseness-distortion tradeoffs. Our second result addresses the problem of which (α, β)-spanners can be computed efficiently, ideally in linear time. We show that, for any k , a ( k , k −1)-spanner with size O ( kn 1+1/ k ) can be found in linear time, and, further, that in a distributed network the algorithm terminates in a constant number of rounds. Previous spanner constructions with similar performance had roughly twice the multiplicative distortion.

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(kmn1k/) algorithm to construct a data structure of size O(kn1 + 1k/) 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(n2log n) algorithm to construct such a data structure of size O(kn1+1k/) 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(n2log n) time

Let G = ( V , E ) be an undirected graph on n vertices, and let δ( u , v ) denote the distance in G between two vertices u and v . Thorup and Zwick showed that for any positive integer t , the graph G can be preprocessed to build a data structure that can efficiently report t -approximate distance between any pair of vertices. That is, for any u , v ∈ V , the distance reported is at least δ( u , v ) and at most t δ( u , v ). The remarkable feature of this data structure is that, for t ≥3, it occupies subquadratic space, that is, it does not store all-pairs distances explicitly, and still it can answer any t -approximate distance query in constant time. They named the data structure “approximate distance oracle” because of this feature. Furthermore, the trade-off between the stretch t and the size of the data structure is essentially optimal.In this article, we show that we can actually construct approximate distance oracles in expected O ( n 2 ) time if the graph is unweighted. One of the new ideas used in the improved algorithm also leads to the first expected linear-time algorithm for computing an optimal size (2, 1)-spanner of an unweighted graph. A (2, 1) spanner of an undirected unweighted graph G = ( V , E ) is a subgraph ( V , Ê), Ê ⊆ E , such that for any two vertices u and v in the graph, their distance in the subgraph is at most 2δ( u , v ) + 1.

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 log2n + \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/nc) for any constant c).