2026-07-24T11:00:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17020 2024-03-06T10:58:59Z ddc:004 open_access

Data Structures for Node Connectivity Queries Nutov, Zeev node connectivity minimum cuts data structure connectivity queries Let κ(s,t) denote the maximum number of internally disjoint st-paths in an undirected graph G. We consider designing a data structure that includes a list of cuts, and answers the following query: given s,t ∈ V, determine whether κ(s,t) ≤ k, and if so, return a pointer to an st-cut of size ≤ k (or to a minimum st-cut) in the list. A trivial data structure that includes a list of n(n-1)/2 cuts and requires Θ(kn²) space can answer each query in O(1) time. We obtain the following results. - In the case when G is k-connected, we show that 2n cuts suffice, and that these cuts can be partitioned into 2k+1 laminar families. Thus using space O(kn) we can answers each min-cut query in O(1) time, slightly improving and substantially simplifying the proof of a recent result of Pettie and Yin [S. Pettie and L. Yin, 2021]. We then extend this data structure to subset k-connectivity. - In the general case we show that (2k+1)n cuts suffice to return an st-cut of size ≤ k, and a list of size k(k+2)n contains a minimum st-cut for every s,t ∈ V. Combining our subset k-connectivity data structure with the data structure of Hsu and Lu [T-H. Hsu and H-I. Lu, 2009] for checking k-connectivity, we give an O(k² n) space data structure that returns an st-cut of size ≤ k in O(log k) time, while O(k³ n) space enables to return a minimum st-cut. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zeev Nutov 2022 Is Part Of LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2022.82 urn:nbn:de:0030-drops-170205 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.82 eng https://creativecommons.org/licenses/by/4.0/legalcode