@inproceedings{31a2b0c3ec7a4ce58e067051d14f3698,
title = "Isolating cuts, (Bi-)submodularity, and faster algorithms for connectivity",
abstract = "Li and Panigrahi [37], in recent work, obtained the first deterministic algorithm for the global minimum cut of a weighted undirected graph that runs in time o(mn). They introduced an elegant and powerful technique to find isolating cuts for a terminal set in a graph via a small number of s-t minimum cut computations. In this paper we generalize their isolating cut approach to the abstract setting of symmetric bisubmodular functions (which also capture symmetric submodular functions). Our generalization to bisubmodularity is motivated by applications to element connectivity and vertex connectivity. Utilizing the general framework and other ideas we obtain significantly faster randomized algorithms for computing global (and subset) connectivity in a number of settings including hypergraphs, element connectivity and vertex connectivity in graphs, and for symmetric submodular functions.",
keywords = "Bisumodularity, Cuts, Element connectivity, Fast algorithms, Hypergraphs, Isolating cuts, Lattices, Submodularity, Vertex connectivity",
author = "Chandra Chekuri and Kent Quanrud",
note = "Publisher Copyright: {\textcopyright} 2021 Chandra Chekuri and Kent Quanrud.; 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021 ; Conference date: 12-07-2021 Through 16-07-2021",
year = "2021",
month = jul,
day = "1",
doi = "10.4230/LIPIcs.ICALP.2021.50",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Nikhil Bansal and Emanuela Merelli and James Worrell",
booktitle = "48th International Colloquium on Automata, Languages, and Programming, ICALP 2021",
}