Data Structures for Node 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 Θ(kn2) 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 [18]. 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 [7] for checking k-connectivity, we give an O(k2n) space data structure that returns an st-cut of size ≤ k in O(log k) time, while O(k3n) space enables to return a minimum st-cut.