Search Results

Documents authored by Bhanja, Koustav

Document
DOI: 10.4230/LIPIcs.ISAAC.2024.10
Optimal Sensitivity Oracle for Steiner Mincut

Authors: Koustav Bhanja

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
Let G = (V,E) be an undirected weighted graph on n = |V| vertices and S ⊆ V be a Steiner set. Steiner mincut is a well-studied concept, which also provides a generalization to both (s,t)-mincut (when |S| = 2) and global mincut (when |S| = n). Here, we address the problem of designing a compact data structure that can efficiently report a Steiner mincut and its capacity after the failure of any edge in G; such a data structure is known as a Sensitivity Oracle for Steiner mincut. In the area of minimum cuts, although many Sensitivity Oracles have been designed in unweighted graphs, however, in weighted graphs, Sensitivity Oracles exist only for (s,t)-mincut [Annals of Operations Research 1991, NETWORKS 2019, ICALP 2024], which is just a special case of Steiner mincut. Here, we generalize this result from |S| = 2 to any arbitrary set S ⊆ V, that is, 2 ≤ |S| ≤ n. We first design an {O}(n²) space Sensitivity Oracle for Steiner mincut by suitably generalizing the approach used for (s,t)-mincuts [Annals of Operations Research 1991, NETWORKS 2019]. However, the main question that arises quite naturally is the following. Can we design a Sensitivity Oracle for Steiner mincut that breaks the {O}(n²) bound on space? In this article, we present the following two results that provide an answer to this question. 1. Sensitivity Oracle: Assuming the capacity of every edge is known, a) there is an O(n) space data structure that can report the capacity of Steiner mincut in O(1) time and b) there is an O(n(n-|S|+1)) space data structure that can report a Steiner mincut in O(n) time after the failure of any edge in G. 2. Lower Bound: We show that any data structure that, after the failure of any edge in G, can report a Steiner mincut or its capacity must occupy Ω(n²) bits of space in the worst case, irrespective of the size of the Steiner set. The lower bound in (2) shows that the assumption in (1) is essential to break the Ω(n²) lower bound on space. Sensitivity Oracle in (1.b) occupies only subquadratic, that is O(n^{1+ε}), space if |S| = n-n^ε+1, for every ε ∈ [0,1). For |S| = n-k for any constant k ≥ 0, it occupies only O(n) space. So, we also present the first Sensitivity Oracle occupying O(n) space for global mincut. In addition, we are able to match the existing best-known bounds on both space and query time for (s,t)-mincut [Annals of Operations Research 1991, NETWORKS 2019] in undirected graphs.
Cite as

Koustav Bhanja. Optimal Sensitivity Oracle for Steiner Mincut. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bhanja:LIPIcs.ISAAC.2024.10,
  author =	{Bhanja, Koustav},
  title =	{{Optimal Sensitivity Oracle for Steiner Mincut}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{10:1--10:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.10},
  URN =		{urn:nbn:de:0030-drops-221371},
  doi =		{10.4230/LIPIcs.ISAAC.2024.10},
  annote =	{Keywords: mincut, (s, t)-mincut, Steiner mincut, fault tolerant structures, data structure, vital edges, vitality, sensitivity oracle}
}
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}
}
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact