Search Results

Documents authored by Baswana, Surender

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.17
Vital Edges for (s,t)-Mincut: Efficient Algorithms, Compact Structures, & Optimal Sensitivity Oracles

Authors: Surender Baswana and Koustav Bhanja

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Let G be a directed weighted graph on n vertices and m edges with designated source and sink vertices s and 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 [CJM 1956], a long line of work has been done on computing the most vital edge and all vital edges of G. However, even after 60 years, the existing results are for either undirected or unweighted graphs. We present the following result for directed weighted graphs that also solves an open problem by Ausiello, Franciosa, Lari, and Ribichini [NETWORKS 2019]. 1. Algorithmic Results: There is an algorithm that computes all vital edges as well as the most vital edge of G using {O}(n) maximum (s,t)-flow computations. Vital edges play a crucial role in the design of sensitivity oracle for (s,t)-mincut - a compact data structure for reporting (s,t)-mincut after insertion/failure of any edge. For directed graphs, the only existing sensitivity oracle is for unweighted graphs by Picard and Queyranne [MPS 1982]. We present the first and optimal sensitivity oracle for directed weighted graphs as follows. 2. Sensitivity Oracles: a) There is an optimal O(n²) space data structure that can report an (s,t)-mincut C in O(|C|) time after the failure/insertion of any edge. b) There is an O(n) space data structure that can report the capacity of (s,t)-mincut after failure or insertion of any edge e in O(1) time if the capacity of edge e is known. A mincut for a vital edge e is an (s,t)-cut of the least capacity in which edge e is outgoing. For unweighted graphs, in a classical work, Picard and Queyranne [MPS 1982] designed an O(m) space directed acyclic graph (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 directed weighted graphs as follows. 3. Structural & Combinatorial Results: a) There is a set M containing at most n-1 (s,t)-cuts such that at least one mincut for every vital edge belongs to the set. This bound is tight as well. We also show that set M can be computed using O(n) maximum (s,t)-flow computations. b) We design two compact structures for storing and characterizing all mincuts for all vital edges - (i) an O(m) space DAG for partial and (ii) an 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 [CJM 1956], which might be of independent interest.
Cite as

Surender Baswana and Koustav Bhanja. Vital Edges for (s,t)-Mincut: Efficient Algorithms, Compact Structures, & Optimal Sensitivity Oracles. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{baswana_et_al:LIPIcs.ICALP.2024.17,
  author =	{Baswana, Surender and Bhanja, Koustav},
  title =	{{Vital Edges for (s,t)-Mincut: Efficient Algorithms, Compact Structures, \& Optimal Sensitivity Oracles}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{17:1--17:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.17},
  URN =		{urn:nbn:de:0030-drops-201601},
  doi =		{10.4230/LIPIcs.ICALP.2024.17},
  annote =	{Keywords: maxflow, vital edges, graph algorithms, structures, st-cuts, sensitivity oracle}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.15
Minimum+1 (s,t)-cuts and Dual Edge Sensitivity Oracle

Authors: Surender Baswana, Koustav Bhanja, and Abhyuday Pandey

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
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 the (s,t)-mincut upon failure or addition 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. Dinitz and Nutov [STOC, pages 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 structures exist till date. We present the following structural and algorithmic results on minimum+1 (s,t)-cuts. 1) There exists a pair of DAGs of size O(m) that compactly store all minimum+1 (s,t)-cuts of G. Each minimum+1 (s,t)-cut appears as a (s,t)-cut in one of the 2 DAGs and is 3-transversal - it intersects any path in the DAG at most thrice. 2) There exists an O(n²) size data structure that, given a pair of vertices {u,v} which 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) There exists an O(n²) size data structure that solves the dual edge sensitivity problem for (s,t)-mincuts. It takes 𝒪(1) time to report the value of a resulting (s,t)-mincut (A,B) and 𝒪(|B|) time to report the cut. 4) For the data structure problems addressed in (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 2× 2 maximum flow. Assuming the directed reachability hypothesis, this leads to Ω(n²) lower bounds on the space for the latter two problems.
Cite as

Surender Baswana, Koustav Bhanja, and Abhyuday Pandey. Minimum+1 (s,t)-cuts and Dual Edge Sensitivity Oracle. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 15:1-15:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{baswana_et_al:LIPIcs.ICALP.2022.15,
  author =	{Baswana, Surender and Bhanja, Koustav and Pandey, Abhyuday},
  title =	{{Minimum+1 (s,t)-cuts and Dual Edge Sensitivity Oracle}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{15:1--15:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.15},
  URN =		{urn:nbn:de:0030-drops-163566},
  doi =		{10.4230/LIPIcs.ICALP.2022.15},
  annote =	{Keywords: mincut, maxflow, fault tolerant}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.12
Mincut Sensitivity Data Structures for the Insertion of an Edge

Authors: Surender Baswana, Shiv Gupta, and Till Knollmann

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
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.
Cite as

Surender Baswana, Shiv Gupta, and Till Knollmann. Mincut Sensitivity Data Structures for the Insertion of an Edge. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{baswana_et_al:LIPIcs.ESA.2020.12,
  author =	{Baswana, Surender and Gupta, Shiv and Knollmann, Till},
  title =	{{Mincut Sensitivity Data Structures for the Insertion of an Edge}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.12},
  URN =		{urn:nbn:de:0030-drops-128781},
  doi =		{10.4230/LIPIcs.ESA.2020.12},
  annote =	{Keywords: Mincut, Sensitivity, Data Structure}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.65
Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient

Authors: Surender Baswana, Shiv Gupta, and Ayush Tulsyan

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
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.
Cite as

Surender Baswana, Shiv Gupta, and Ayush Tulsyan. Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 65:1-65:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{baswana_et_al:LIPIcs.MFCS.2019.65,
  author =	{Baswana, Surender and Gupta, Shiv and Tulsyan, Ayush},
  title =	{{Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{65:1--65:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.65},
  URN =		{urn:nbn:de:0030-drops-110096},
  doi =		{10.4230/LIPIcs.MFCS.2019.65},
  annote =	{Keywords: Depth first search, DFS, Dynamic graph algorithms, Fault tolerant}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.72
An Efficient Strongly Connected Components Algorithm in the Fault Tolerant Model

Authors: Surender Baswana, Keerti Choudhary, and Liam Roditty

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
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.
Cite as

Surender Baswana, Keerti Choudhary, and Liam Roditty. An Efficient Strongly Connected Components Algorithm in the Fault Tolerant Model. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 72:1-72:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{baswana_et_al:LIPIcs.ICALP.2017.72,
  author =	{Baswana, Surender and Choudhary, Keerti and Roditty, Liam},
  title =	{{An Efficient  Strongly Connected Components Algorithm in the Fault Tolerant Model}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{72:1--72:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.72},
  URN =		{urn:nbn:de:0030-drops-74168},
  doi =		{10.4230/LIPIcs.ICALP.2017.72},
  annote =	{Keywords: Fault tolerant, Directed graph, Strongly connected components}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2012.257
Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs

Authors: Abhash Anand, Surender Baswana, Manoj Gupta, and Sandeep Sen

Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Abstract
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.
Cite as

Abhash Anand, Surender Baswana, Manoj Gupta, and Sandeep Sen. Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 257-266, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{anand_et_al:LIPIcs.FSTTCS.2012.257,
  author =	{Anand, Abhash and Baswana, Surender and Gupta, Manoj and Sen, Sandeep},
  title =	{{Maintaining Approximate Maximum Weighted Matching in Fully  Dynamic Graphs}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  pages =	{257--266},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.257},
  URN =		{urn:nbn:de:0030-drops-38648},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.257},
  annote =	{Keywords: Matching, Dynamic Algorithm, Graph Algorithm}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2481
Approximate Shortest Paths Avoiding a Failed Vertex: Optimal Size Data Structures for Unweighted Graphs

Authors: Neelesh Khanna and Surender Baswana

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
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.
Cite as

Neelesh Khanna and Surender Baswana. Approximate Shortest Paths Avoiding a Failed Vertex: Optimal Size Data Structures for Unweighted Graphs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 513-524, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{khanna_et_al:LIPIcs.STACS.2010.2481,
  author =	{Khanna, Neelesh and Baswana, Surender},
  title =	{{Approximate Shortest Paths Avoiding a Failed Vertex: Optimal Size Data Structures for Unweighted Graphs}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{513--524},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2481},
  URN =		{urn:nbn:de:0030-drops-24812},
  doi =		{10.4230/LIPIcs.STACS.2010.2481},
  annote =	{Keywords: Shortest path, distance, distance queries, oracle}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact