---
_id: '20159'
abstract:
- lang: eng
text: "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. \r\n1) Single source: Given any designated
source vertex s, there exists a data structure of size \U0001D4AA(|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
\U0001D4AA(|S|). \r\n2) All-pairs: There exists an \U0001D4AA(|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 \U0001D4AA(k), where k is the number of pairs of vertices
whose mincut increases. \r\nFor 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 \U0001D4AA(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 \U0001D4AA(n) size."
author:
- first_name: Surender
full_name: Baswana, Surender
last_name: Baswana
- first_name: Shiv
full_name: Gupta, Shiv
last_name: Gupta
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
citation:
ama: 'Baswana S, Gupta S, Knollmann T. Mincut Sensitivity Data Structures for the
Insertion of an Edge. In: Grandoni F, Herman G, Sanders P, eds. 28th Annual
European Symposium on Algorithms (ESA 2020). Vol 173. Leibniz International
Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum
für Informatik; 2020:12:1-12:14. doi:10.4230/LIPIcs.ESA.2020.12'
apa: 'Baswana, S., Gupta, S., & Knollmann, T. (2020). Mincut Sensitivity Data
Structures for the Insertion of an Edge. In F. Grandoni, G. Herman, & P. Sanders
(Eds.), 28th Annual European Symposium on Algorithms (ESA 2020) (Vol. 173,
pp. 12:1-12:14). Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ESA.2020.12'
bibtex: '@inproceedings{Baswana_Gupta_Knollmann_2020, place={Dagstuhl, Germany},
series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={Mincut
Sensitivity Data Structures for the Insertion of an Edge}, volume={173}, DOI={10.4230/LIPIcs.ESA.2020.12},
booktitle={28th Annual European Symposium on Algorithms (ESA 2020)}, publisher={Schloss
Dagstuhl -- Leibniz-Zentrum für Informatik}, author={Baswana, Surender and Gupta,
Shiv and Knollmann, Till}, editor={Grandoni, Fabrizio and Herman, Grzegorz and
Sanders, PeterEditors}, year={2020}, pages={12:1-12:14}, collection={Leibniz International
Proceedings in Informatics (LIPIcs)} }'
chicago: 'Baswana, Surender, Shiv Gupta, and Till Knollmann. “Mincut Sensitivity
Data Structures for the Insertion of an Edge.” In 28th Annual European Symposium
on Algorithms (ESA 2020), edited by Fabrizio Grandoni, Grzegorz Herman, and
Peter Sanders, 173:12:1-12:14. Leibniz International Proceedings in Informatics
(LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum für Informatik,
2020. https://doi.org/10.4230/LIPIcs.ESA.2020.12.'
ieee: S. Baswana, S. Gupta, and T. Knollmann, “Mincut Sensitivity Data Structures
for the Insertion of an Edge,” in 28th Annual European Symposium on Algorithms
(ESA 2020), 2020, vol. 173, pp. 12:1-12:14.
mla: Baswana, Surender, et al. “Mincut Sensitivity Data Structures for the Insertion
of an Edge.” 28th Annual European Symposium on Algorithms (ESA 2020), edited
by Fabrizio Grandoni et al., vol. 173, Schloss Dagstuhl -- Leibniz-Zentrum für
Informatik, 2020, pp. 12:1-12:14, doi:10.4230/LIPIcs.ESA.2020.12.
short: 'S. Baswana, S. Gupta, T. Knollmann, in: F. Grandoni, G. Herman, P. Sanders
(Eds.), 28th Annual European Symposium on Algorithms (ESA 2020), Schloss Dagstuhl
-- Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2020, pp. 12:1-12:14.'
date_created: 2020-10-21T12:00:20Z
date_updated: 2022-01-06T06:54:20Z
department:
- _id: '63'
doi: 10.4230/LIPIcs.ESA.2020.12
editor:
- first_name: Fabrizio
full_name: Grandoni, Fabrizio
last_name: Grandoni
- first_name: Grzegorz
full_name: Herman, Grzegorz
last_name: Herman
- first_name: Peter
full_name: Sanders, Peter
last_name: Sanders
intvolume: ' 173'
keyword:
- Mincut
- Sensitivity
- Data Structure
language:
- iso: eng
page: 12:1-12:14
place: Dagstuhl, Germany
publication: 28th Annual European Symposium on Algorithms (ESA 2020)
publication_identifier:
isbn:
- 978-3-95977-162-7
issn:
- 1868-8969
publisher: Schloss Dagstuhl -- Leibniz-Zentrum für Informatik
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: Mincut Sensitivity Data Structures for the Insertion of an Edge
type: conference
user_id: '39241'
volume: 173
year: '2020'
...