Surender Baswana

Minimum Cuts

I started working in this area during my sabbatical [2019] at the University of Paderborn, Germany. The area of mincuts (and maximum flows) is so deep, vast, and full of amazing results. I am so fascinated by these aspects that I might like to work in this area for the rest of my professional life. My collaborators and I have been working primarily on the sensitivity aspect of mincuts till now (refer to the following section). However, the following recent work might interest a broader audience.

1. 1. A Compact Structure for Steiner Mincuts [SOSA 2025]
2. 2. Vital Edges for (s,t)-mincuts in directed weighted graphs [ICALP 2024]

Fault Tolerant Structures

Consider an algorithmic problem that involves computing a structure. This structure could be a subgraph with some desired properties, for example, a depth first search (DFS) tree, a spanner. This structure could be a data structure that efficiently answers some query, for example, shortest path query. In the real world, the faults (failure of edges or vertices) are inevitable. It is also usually true that faults are transient due to some repair mechanism undertaken in the application. So, the number of faults at any time is small though the set of faults may keep changing with time. In such scenarios, how do we maintain the subgraph or the data structure ?

Two trivial ways to handle the faults are the following:

1. 1. Re-compute the subgraph (or the data structure) from scratch after each fault.
2. 2. Store the set of all subgraphs (or the data structure) for each possible fault.

The first way is very inefficient from the perspective of time, and the second way is very inefficient from the perspective of space.

Therefore, the aim is to design an algorithm that can update the data structure (or the subgraph) upon failure of any given edge efficiently – in time much faster than computing the data structure (or the corresponding subgraph) from scratch. Moreover, it should also answer the corresponding queries very efficiently.

My collaborators and I have designed efficient fault tolerant algorithms for the following problems.

1. 1. All-pairs mincuts [SODA 2022], and (s,t)-mincuts [ICALP 2022and TALG 2023, ICALP 2024]
2. 2. DFS tree [SODA 2016 and SICOMP 2019]. Subsequently, we simplified this structure drastically [Algorithmica 2022].
3. 3. Sparse subgraph that preserves single source reachabilities. [STOC 2016 and SICOMP 2018]. The size of the subgraph is worst-case optimal. This subgraph can be viewed as a generalization of the well-known concept of dominators.
4. 4. Approximate shortest paths [STACS 2010 and Algorithmica 2013]

Dynamic graph algorithms

The model underlying the dynamic graph algorithms is quite different from the fault tolerant model described above. In this model, there is an online sequence of updates – insertion or deletion of edges. The aim is to keep a data structure for a given problem so that we can update the data structure efficiently after each update. If there is a query associated with the problem, the aim is to answer each query efficiently as well. We have worked on dynamic graph algorithms for the following graph problems.

1. 1. Depth first search tree [ICALP 2014 and Algorithmica 2017, SODA 2016 and SICOMP 2019]
2. 2. Maximal matching [FOCS 2011 and SICOMP 2018].
3. 3. Graph spanners [SODA 2008 and ACM TALG 2012]
4. 4. Approximate shortest paths [SODA 2003]
5. 5. All-pairs directed reachability [STOC 2002 and J. of Algorithms 2007]

Approximate Shortest Paths

Computing all-pairs shortest paths is arguably one of the most fundamental graph problems. However, there does not exist any sub-cubic algorithm for computing all-pairs shortest paths till date. So the aim is to have an algorithm that takes sub-cubic time but computes approximate distances. However, the algorithm must provide a worst-case guarantee on the factor by which the distance is stretched for any pair of vertices. One of the milestone results in this area is the approximate distance oracles designed by Thorup and Zwick. They designed a data structure that provides almost an optimal trade-off between the size of the data structure and the stretch factor. However, they posed it as an open question: Can we build this oracle in quadratic time ? The following 2 articles answered this question in the affirmative.

1. 1. Approximate shortest paths in undirected weighted graphs [FOCS 2006 and SICOMP 2010 ]
2. 2. Approximate shortest paths in undirected unweighted graphs [SODA 2004 and TALG 2006]. It was one of the 11 selected best papers (judged by the PC) among 117 papers that were accepted in SIAM SODA 2004.

We also worked on computing nearly 2-approximate shortest paths in undirected unweighted graphs [ICALP 2008, STACS 2005 and Theoretical Computer Science 2009]

Graph Spanner

A spanner is a subgraph that is sparse and still preserves approximately the distance between each pair of vertices in the graph. There is a trade-off between the sparseness of the subgraph and the factor by which the distance between any pair of vertices is stretched – the larger the stretch we can tolerate, the greater the sparseness we can achieve. For undirected unweighted graphs, Halperin and Zwick [1996] designed a simple linear time algorithm for graph spanners while achieving optimal trade-off between the size and the stretch. However, for undirected weighted graphs, there exist many algorithms before 2003 that achieve an almost optimal trade-off between the size and the stretch, but none of them took linear time. Each of these algorithms involves some distance computation, and hence achieve time far from linear.

1. 1. An almost optimal algorithm for constructing spanners for weighted graphs in centralized, distributed, external-memory, and parallel environment [ICALP 2003 and Random Structures and Algorithms 2007]. This article was among the selected best papers of ICALP 2003 and was invited for a special issue of Theoretical Computer Science. This algorithm is based on a novel local approach that avoids any distance computation altogether. This algorithm is so elegant and simple that it can be taught in an undergraduate level algorithms course.
2. 2. An algorithm for spanners for unweighted graphs in a streaming environment [IPL 2008].