Data structure for node connectivity queries.

Let $\kappa(s,t)$ denote the maximum number of internally disjoint paths in an undirected graph $G$. We consider designing a data structure that includes a list of cuts, and answers in $O(1)$ time the following query: given $s,t \in V$, determine whether $\kappa(s,t) \leq k$, and if so, return a pointer to an $st$-cut of size $\leq k$ in the list. A trivial data structure includes a list of $n(n-1)/2$ cuts and requires $\Theta(kn^2)$ space. We show that $O(kn)$ cuts suffice, thus reducing the space to $O(k^2 n+n^2)$. In the case when $G$ is $k$-connected, we show that $O(n)$ cuts suffice, and that these cuts can be partitioned into $O(k)$ laminar families; this reduces the space to $O(kn)$. The latter result slightly improves and substantially simplifies a recent result of Pettie and Yin [ICALP 2021].