Data Structures for Node Connectivity Queries

Abstract

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.