# Optimal Vertex Connectivity Oracles††thanks: This work was supported by NSF
grant CCF-1815316.

Seth Pettie
University of Michigan  Thatchaphol Saranurak
University of Michigan  Longhui Yin
Tsinghua University

###### Abstract

A $k$-vertex connectivity oracle for undirected $G$ is a data structure that,
given $u,v\in V(G)$, reports $\min\\{k,\kappa(u,v)\\}$, where $\kappa(u,v)$ is
the pairwise vertex connectivity between $u,v$. There are three main measures
of efficiency: construction time, query time, and space. Prior work of Izsak
and Nutov [IN12] shows that a data structure of total size $\tilde{O}(kn)$ can
even be encoded as a $\tilde{O}(k)$-bit labeling scheme so that vertex-
connectivity queries can be answered in $\tilde{O}(k)$ time. The construction
time is polynomial, but unspecified.

In this paper we address the top three complexity measures.

Space.

We prove that any $k$-vertex connectivity oracle requires $\Omega(kn)$ bits of
space. This answers a long-standing question on the structural complexity of
vertex connectivity, and gives a strong separation between the complexity of
vertex- and edge-connectivity. Both Izsak and Nutov [IN12] and our data
structure match this lower bound up to polylogarithmic factors.

Query Time.

We answer queries in $O(\log n)$ time, independent of $k$, improving on
$\tilde{\Omega}(k)$ time of [IN12]. The main idea is to build instances of
SetIntersection data structures, with additional structure based on affine
planes. This structure allows for optimum query time that is linear in the
output size (This evades the general $k^{1/2-o(1)}$ and $k^{1-o(1)}$ lower
bounds on SetIntersection from the 3SUM or OMv hypotheses, resp. [KPP16,
HKNS15].)

Construction Time.

We build the data structure in time roughly that of a max-flow computation on
a unit-capacity graph, which is $m^{4/3+o(1)}$ using state-of-the-art
algorithms [KLS20]. Max-flow is a natural barrier for many problems that have
an all-pairs-min-cut flavor. The main technical contribution here is a fast
algorithm for computing a $k$-bounded version of a Gomory-Hu tree for _element
connectivity_ , a notion that generalizes edge and vertex connectivity.

##  1 Introduction

Most measures of _graph connectivity_ can be computed in polynomial time, and
much of the recent work in graph _algorithms_ aims at reducing these
complexities to some natural barrier, either near-linear [Kar00, KP09, FNY+20,
GMW20, GMW21, MN20, vdBLL+21, Sar21], max-flow-time [LP20, LNP+21], or matrix-
multiplication-time [CLL13, AGI+19]. Graph connectivity has also been
extensively studied from a _structural_ perspective, where the aims are to
understand the structure of some/all minimum cuts. This genre includes Gomory-
Hu trees [GH61], the cactus representation [DKL76], block-trees, SPQR-trees,
and extensions to higher vertex connectivity [BT96, KTBC91, CDBKT93, PY21],
and many others [Ben95b, BG08, GN93, DV94, DV95, DV00, DN95, DN99a, DN99b,
PQ80, GILP16, GILP18, FGI+16].

In this paper we study the _data structural_ approach to understanding graph
connectivity, which incorporates elements of the _algorithmic_ and
_structural_ camps, but goes further in that we want to be able to efficiently
_query_ the connectivity, e.g., either ask for the size of a min-cut or the
min-cut itself.

Suppose we are given an undirected graph $G$ and wish to be able to answer
pairwise edge- and vertex-connectivities up to some threshold $k$. Let
$\lambda(u,v)$ and $\kappa(u,v)$ be the maximum number of edge-disjoint and
internally vertex-disjoint paths, resp., between $u$ to $v$. By Menger’s
theorem, these are equal to the minimum number of edges and vertices, resp.,
necessary to disconnect $u$ and $v$.111If $\\{u,v\\}\in E$, then $\kappa(u,v)$
represents the size of a _mixed cut_ separating $u,v$ consisting of
$\\{u,v\\}$ and $\kappa(u,v)-1$ other vertices.

$\mathsf{e}\text{-}\mathsf{conn}(u,v)$ :

Return $\min\\{\lambda(u,v),k\\}$.

$\mathsf{e}\text{-}\mathsf{cut}(u,v)$ :

If $\lambda(u,v)<k$, return an edge-cut separating $u,v$ with size
$\lambda(u,v)$.

$\mathsf{v}\text{-}\mathsf{conn}(u,v)$ :

Return $\min\\{\kappa(u,v),k\\}$.

$\mathsf{v}\text{-}\mathsf{cut}(u,v)$ :

If $\kappa(u,v)<k$, return a vertex-cut separating $u,v$ with size
$\kappa(u,v)$.

The edge-connectivity problems are close to being solved. A _Gomory-Hu tree_
$T$ [GH61] (aka _cut equivalent tree_) is an edge-weighted tree such that the
bottleneck edge $e$ between any $u,v$ has weight $\lambda(u,v)$, and the
partition defined by $T-\\{e\\}$ corresponds to a $\lambda(u,v)$-edge cut,
which can be explicitly associated with $e$ if we wish to also answer
$\mathsf{e}\text{-}\mathsf{cut}$ queries. Bottleneck queries can be answered
in $O(1)$ time with $O(n\log n)$ preprocessing, or $O(\alpha(n))$ time with
$O(n)$ preprocessing; see [Pet06, DLW09, Cha87].222These upper and lower
bounds are in the comparison model. When $G$ is unweighted, all min-cut values
are integers in $[1,n)$, which can be sorted in linear time. In this case
$O(n)$ preprocesssing for $O(1)$-time queries is possible. The time to compute
the full Gomory-Hu tree is $\tilde{O}(m^{3/2}n^{1/6})$ [AKT20] and there are
faster $\tilde{O}(n^{2})$-time algorithms on simple graphs [AKT21, LPS21] or
$\tilde{O}(m+nk^{3})$-time algorithms [HKP07] for representing connectivity up
to $k$.

Thus, $\mathsf{e}\text{-}\mathsf{conn}$-queries can be answered in $O(1)$ time
by a data structure occupying space $O(n)$. It is a long-standing open problem
whether a similar result is possible for
$\mathsf{v}\text{-}\mathsf{conn}$-queries. In 1979 Schnorr [Sch79] proposed a
cut-equivalent tree for _roundtrip_ flow333$\min\\{f(u,v),f(v,u)\\}$ in
directed graphs, and in 1990 Gusfield and Naor [GN90] used Schnorr’s result to
build a Gomory-Hu-type tree for vertex connectivity. Benczur [Ben95a] found
errors in Schnorr [Sch79] and Gusfield and Naor [GN90], and proved more
generally that there is no cut-equivalent tree for vertex connectivity.
Benczur [Ben95a, pp. 505-506] suggested a way to get a _flow_ -equivalent tree
for roundtrip flow using a result of Cheng and Hu [CH91], which would yield a
Gomory-Hu-type tree suitable for answering $\mathsf{v}\text{-}\mathsf{conn}$
(but not $\mathsf{v}\text{-}\mathsf{cut}$) queries. This too, turned out to be
incorrect. Hassin and Levin [HL07] gave an example of a vertex-capacitated
graph (integer capacities in $[1,n^{O(1)}]$) that has $\Omega(n^{2})$ distinct
pairwise vertex connectivities, which cannot be captured by a Gomory-Hu-type
tree representation.444Hassin and Levin [HL07] pointed out that Benczur’s
proposal yields a Gomory-Hu-type tree representation for vertex “
_separations_ ” in a capacitated graph $G=(V,E,c:V\rightarrow\mathbb{R}^{+})$.
The minimum separation of $u,v$ is the minimum of $c(u),c(v),$ and the minimum
$c(K)$ over all vertex cuts $K$ disconnecting $u,v$.

When the underlying graph has _unit capacity_ , the counterexamples of
[Ben95a, HL07] do not rule out a representation of vertex-connectivity using,
say, $\tilde{O}(1)$ trees, nor do they rule out some completely different
$\tilde{O}(n)$-space structure for answering
$\mathsf{v}\text{-}\mathsf{conn}$-queries, independent of $k$.

Citation |  Space (Words) Labeling (Bits) | Query Time | Construction Time
---|---|---|---
Block-tree $k=2$ | $O(n)$ | $O(1)$ | $O(m)$
Block-tree + SPQR-tree [BT96] $k=3$ | $O(n)$ | $O(1)$ | $O(m)$
Block-tree + SPQR-tree + [KTBC91] $k=4$ | $O(n)$ | $O(1)$ | $O(m+n\alpha(n))$
[KKKP04] |  $O(n2^{k})$ $O(2^{k}\log n)$ | $O(2^{k})$ | $\mathrm{poly}(n)$
| $\Omega(k\log(n/k^{3}))$ | _any_ | _any_
[Kor10] |  $O(nk^{3})$ $O(k^{3}\log n)$ | $O(k\log k)$ | $\mathrm{poly}(n)$
[HL09] |  $O(nk^{2})$ $O(k^{2}\log n)$ | $O(\log k)$ | $\mathrm{poly}(n)$
[IN12] |  $O(nk\log n)$ $O(k\log^{3}n)$ | $O(k\log n)$ | $\mathrm{poly}(n)$
[AGI+19] |  $O(n^{2})$ $O(n\log n)$ | $O(1)$ | $O(nk)^{\omega}$
[PY21] $k=\kappa(G)+1$ |  $O(n\kappa(G))$ $O(\kappa(G)\log n)$ | $O(1)$ | $\tilde{O}(m+n\cdot\mathrm{poly}(\kappa(G)))$
[Nut21] ($\star$) | $O(nk^{2}+n^{2})$ | $O(1)$ | $\mathrm{poly}(n)$
New |  $O(nk\log n)$ $O(k\log^{3}n)$ | $O(\log n)$ | $T_{\operatorname{flow}}(m)\cdot\mathrm{poly}(k,\log n)$
|  $\Omega(nk/\log n)$ $\Omega(k)$ avg. | _any_ | _any_
Table 1: A history of vertex-connectivity oracles. By convention, space for
centralized data structures is measured in $O(\log n)$-bit words and space for
labeling schemes is measured in bits. With a couple exceptions, all data
structures and lower bounds are for
$\mathsf{v}\text{-}\mathsf{conn}(u,v)=\min\\{\kappa(u,v),k\\}$ queries, where
$k$ is an arbitrary parameter. The constructions based on block trees, SPQR
trees [BT96], and [KTBC91] only work for $k\in\\{2,3,4\\}$, and Pettie and Yin
[PY21] only works when $k=\kappa(G)+1$ where $\kappa(G)$ is the global minimum
vertex connectivity of $G$. Nutov’s [Nut21] data structure ($\star$)
determines whether $\kappa(u,v)\leq k$ and if so, returns a pointer to a cut
of size at most $k$ in $O(1)$ time. The $\Omega(k\log(n/k^{3}))$ lower bound
of Katz et al. [KKKP04] is for the worst-case (longest) label length; it
implies nothing on average length. The new $\Omega(nk)$-bit lower bound is for
the total size of the data structure, and implies an $\Omega(k)$-bit lower
bound on the average length of any labeling scheme.

Most prior data structures supporting $\mathsf{v}\text{-}\mathsf{conn}$
queries were actually _labeling schemes_. I.e., a vertex _labeling_
$\ell:V\rightarrow\\{0,1\\}^{*}$ is created such that a
$\mathsf{v}\text{-}\mathsf{conn}(u,v)$ query is answered by inspecting
$\ell(u),\ell(v)$. Katz, Katz, Korman, and Peleg [KKKP04] initiated this line
of research into labeling for connectivity. They proved that the maximum label
length to answer $\mathsf{v}\text{-}\mathsf{conn}$ queries is
$\Omega(k\log(n/k^{3}))$ and $O(2^{k}\log n)$. To be specific, they give a
class of graphs for which a $\Theta(1/k^{2})$-fraction of the vertices require
$\Omega(k\log(n/k^{3}))$-bit labels. However, this does not imply any non-
trivial bound on the average/total label length. Their upper bound was
subsequently improved to $O(k^{3}\log n)$ [Kor10] and then to $O(k^{2}\log n)$
[HL09].555The labeling schemes of Katz et al. [KKKP04], Korman [Kor10], and
Hsu and Lu [HL09] differentiate between $\kappa(u,v)\geq k_{0}$ and
$\kappa(u,v)<k_{0}$ using labels of size $O(2^{k_{0}}\log n)$,
$O(k_{0}^{2}\log n)$, and $O(k_{0}\log n)$, respectively. They can be used to
answer $\mathsf{v}\text{-}\mathsf{conn}$ queries by concatenating labels for
all $k_{0}=1,2,\ldots,k$, thereby introducing an $O(k)$-factor overhead in
[Kor10, HL09]. Using a different approach, Izsak and Nutov [IN12] gave an
$O(k\log^{3}n)$-bit labeling scheme for $\mathsf{v}\text{-}\mathsf{conn}$
queries. A centralized version of the data structure takes $O(kn\log n)$ total
space666Following convention, the space of centralized data structures is
measured in $O(\log n)$-bit words and labeling schemes are measured in bits.
and can be augmented to support $\mathsf{v}\text{-}\mathsf{cut}$ queries with
$O(k^{2}n\log n)$ total space.

The labeling schemes [KKKP04, Kor10, HL09, IN12] focus on label-length, and do
not discuss the construction time in detail, which is a large polynomial.

###  1.1 New Results

We resolve the long-standing question concerning the space complexity of
representing vertex connectivity; cf. [Ben95a, HL07]. In particular, we prove
that any data structure answering $\mathsf{v}\text{-}\mathsf{conn}$ queries
requires space $\Omega(kn/\log n)$ (i.e., $\Omega(kn)$ _bits_), and that the
lower bound extends to threshold queries (decide whether $\kappa(u,v)\leq k$),
equality queries (decide whether $\kappa(u,v)=k$), and approximate queries
(distinguish $\kappa(u,v)<k-\sqrt{k}$ from $\kappa(u,v)>k+\sqrt{k}$). This
implies that Izsak and Nutov’s [IN12] centralized data structures are
_optimal_ to within a $\log^{2}n$-factor, and that even the _average_ length
of their labeling scheme cannot be improved by more than a $\log^{3}n$-factor;
cf. [KKKP04]. It also implies a strong separation between the space complexity
of storing all edge-connectivities ($O(n)$ space) and all vertex-
connectivities ($\Omega(n^{2}/\log n)$ space when $k=n$).

Although the Izsak-Nutov structure is space-optimal, its $O(k\log n)$ query
time and polynomial construction time can be substantially improved. We design
a version of this structure that allows for $O(\log n)$ query time independent
of $k$. The key problem is to create random instances of SetIntersection that
are still structured enough to answer intersection queries $S_{i}\cap S_{j}$
optimally, in time $O(|S_{i}\cap S_{j}|)$. Conditional lower bounds from 3SUM
and OMv [KPP16, HKNS15] imply that this should be impossible for worst-case
instances of SetIntersection.

Turning to construction time, we prove that the vertex connectivity oracle (or
labeling scheme) can be constructed in time
$T_{\operatorname{uflow}}(m)\cdot\mathrm{poly}(k,\log n)$, where
$T_{\operatorname{uflow}}(m)$ is the time for one max-flow computation on
unit-capacity graphs with $m$ edges. The main subproblem solved in the
construction algorithm is computing a Gomory-Hu tree for _element
connectivities_ up to $k$.

###  1.2 Organization

Section 2 covers some preliminary concepts such as vertex connectivity,
element connectivity, Gomory-Hu trees, and the (vertex-cut version of) the
isolating cuts lemma of [LP20, LNP+21].

Section 3 presents the lower bound on representations of vertex connectivity.
Section 4 presents a space- and query-efficient vertex connectivity oracle
based on Izsak and Nutov’s [IN12] labeling scheme. In order to build this
oracle efficiently, we need to compute Gomory-Hu trees that capture all
element connectivities up to $k$. In Section 5 we show how to do this in
$T_{\operatorname{uflow}}(m)\mathrm{poly}(k,\log n)$ time.

Section 6 concludes with some outstanding open problems.

##  2 Preliminaries

###  2.1 Vertex Connectivity, Element Connectivity, and Gomory-Hu Trees

Define $\kappa_{G}(u,v)$ to be the vertex connectivity of $u,v$ in $G=(V,E)$,
i.e., the maximum number of internally vertex-disjoint paths between $u$ and
$v$. By Menger’s theorem [Men27], this is the size of the smallest mixed cut
$C\subset(E\cup(V-\\{u,v\\}))$ whose removal disconnects $u,v$.777Sometimes
only “pure” vertex cuts $C\subset V-\\{u,v\\}$ are considered and
$\kappa_{G}(u,v)$ is left undefined or artificially defined to be $|V|-1$
whenever $u,v$ are adjacent in $G$. This definition fails to distinguish
highly connected and poorly connected pairs of vertices that happen to be
adjacent. _Element connectivity_ is a useful generalization of vertex- and
edge-connectivity [Che15, CRX15, JMVW02, CK12]. Let $U\subseteq V$ be a set of
terminals. Then for $u,v\in U$, $\kappa^{\prime}_{G,U}(u,v)$ is the maximum
number of paths between $u$ and $v$ that are $E$-disjoint and
$(V-U)$-disjoint. By duality, this is equivalently the size of the smallest
mixed cut $C\subset(E\cup(V-U))$ whose removal disconnects $u,v$. Observe that
when $U=V$, $\kappa^{\prime}_{G,U}(u,v)=\lambda_{G}(u,v)$ is the same as edge-
connectivity, and when $U=\\{u,v\\}$,
$\kappa^{\prime}_{G,U}(u,v)=\kappa_{G}(u,v)$ captures vertex connectivity.
More generally we have Lemma 2.1, which follows directly from the definitions.

######  Lemma 2.1.

Fix an undirected graph $G=(V,E)$ and a terminal set $U\subseteq V$. For any
$u,v\in U$, $\kappa^{\prime}_{G,U}(u,v)\geq\kappa_{G}(u,v)$ with equality if
and only if there exists a mixed $\kappa_{G}(u,v)$-cut $C$ disconnecting $u,v$
with $C\cap U=\emptyset$.

If $C$ is a mixed cut, the connected components of $G-C$ are called _sides_ of
$C$. Note that minimum edge-cuts have two sides but minimum vertex-cuts may
have an unbounded number of sides. For any $A\subset V$, $\partial A$ is the
set of vertices adjacent to $A$ in $G$, but not in $A$. Thus, $\partial A$ is
a vertex cut disconnecting $A$ from $V-(A\cup\partial A)$.

It is well known that Gomory-Hu trees exist for element connectivity; see
[Sch03, CRX15]. We use the following general definition:

######  Definition 2.2.

A $k$-Gomory-Hu tree for element connectivity w.r.t. graph $G$ and terminal
set $U$ is a triple $(T,f,C)$ satisfying

  * •

(Flow equivalency) $T=(V_{T},E_{T},w:E_{T}\rightarrow[1,k))$ is a weighted
tree and $f:U\rightarrow V_{T}$. If $f(u)=f(v)$ then
$\kappa^{\prime}_{G,U}(u,v)\geq k$ and otherwise,
$\kappa^{\prime}_{G,U}(u,v)=\min_{e\in T(f(u),f(v))}w(e)$, where $T(x,y)$ is
the unique $T$-path between $x$ and $y$.

  * •

(Cut equivalency) $C:E_{T}\rightarrow 2^{E\cup(V-U)}$. For any $e\in
T(f(u),f(v))$, $C(e)$ is a $w(e)$-cut disconnecting $u,v$. (Each of the two
connected components in $T-e$ represents the union of some subset of the sides
of $C(e)$.)

Note that $f$ is unnecessary ($V_{T}=U$) if $k=\infty$ is unbounded, and that
$C$ is unnecessary if we are only interested in
$\min\\{\kappa^{\prime}_{G,U}(u,v),k\\}$-queries. This definition can be
extended to $(1+\epsilon)$-approximations by relaxing the first criterion to
$\kappa^{\prime}_{G,U}(u,v)\leq\min_{e\in
T(f(u),f(v))}w(e)\leq(1+\epsilon)\kappa^{\prime}_{G,U}(u,v)$, with trivial
$f$($V_{T}=U$ and $f$ maps trivially), and the second criterion similarly.

###  2.2 Isolating Cut Lemma and Max-Flows

Li and Panigrahi’s [LP20] _isolating cuts_ lemma finds, for a terminal set
$I$, the minimum edge-cut separating $u\in I$ from $I-\\{u\\}$ in time
proportional to $O(\log|I|)$ max-flows. It was generalized to vertex
connectivity in [LNP+21] and here we generalize this lemma slightly further to
be able to handle _element_ connectivity.

######  Lemma 2.3 (Isolating cuts, vertex version with forbidden terminals).

Let $I\cup F$ be an independent set in graph $G=(V,E)$, and $I\cap
F=\emptyset$. We want to find, for each $v\in I$, a set $S_{v}\subset V$ such
that (i) $S_{v}\cap I=\\{v\\}$ and $(\partial S_{v})\cap F=\emptyset$, (ii) it
minimizes $\left|\partial S_{v}\right|$, (iii) subject to (ii), it minimizes
$|S_{v}|$. Then $\\{S_{v}\\}_{v\in I}$ can be computed with $\log|I|$ calls to
max-flow on graphs with $O(m)$ edges, $O(m)$ vertices, and capacities in
$\\{1,\infty\\}$. If we do not care to minimize $|\partial S_{v}|$ if it is
larger than $k$, then the max-flow instances can be unit-capacity multigraphs
with $O(m+k|F|)$ edges and vertices.

###### Proof.

(sketch) The proof follows [LNP+21, Lemma 4.2]. The authors called max-flow
instances to compute the isolating cuts. Our lemma adds a new requirement,
that $\partial S_{v}\cap F=\emptyset$. This can be effected by replacing $v\in
F$ in the flow networks with two vertices and an edge
$v_{\operatorname{in}}\to v_{\operatorname{out}}$ with capacity $\infty$. (Or
in the unit-capacity case, with $k+1$ parallel edges from
$v_{\operatorname{in}}$ to $v_{\operatorname{out}}$.) This ensures vertices in
$F$ never appear in the cuts $\partial S_{v}$ we are interested in. ∎

##  3 Space Lower Bound on Vertex Connectivity Oracles

##### Informal strategy and intuitions.

We use an error-correcting-code-type argument to derive an $\Omega(n^{2})$-bit
lower bound in the case that $k=n$. By taking the product of $n/k$ copies of
this construction on $\Theta(k)$-vertex graphs, we derive the $\Omega(kn)$-bit
lower bound for general $k\in[1,n]$. The idea is to show the existence of a
_codebook_ $\mathcal{T}$ of $n\times n$ Boolean matrices with the following
property. Each $T\in\mathcal{T}$ can be represented by a certain graph $G[T]$
on $O(n)$ vertices. We compute a $b$-bit vertex connectivity oracle for this
graph and query $\kappa_{G[T]}(u,v)$ for all pairs $u,v$. From these values we
reconstruct a different Boolean matrix $\tilde{T}\neq T$, which is within the
decoding radius of $\mathcal{T}$, and therefore lets us deduce the identity of
the original matrix $T$. In other words, it must be that
$b\geq\log_{2}|\mathcal{T}|$. A key technical idea is to show that each
$T\in\mathcal{T}$ in the codebook can, in a certain sense, be _approximately_
factored as the product of two rectangular Boolean matrices, with addition and
multiplication over $\mathbb{Z}$.

The specifics of the construction are detailed in Theorem 3.1.

######  Theorem 3.1.

There exists a constant $c\geq 5$ and a subset
$\mathcal{T}\subseteq\\{0,1\\}^{n\times n}$ of boolean matrices having the
following properties.

  1. 1.

(Code Properties) $|\mathcal{T}|=2^{n^{2}/3}$, each row of each
$T\in\mathcal{T}$ has Hamming weight exactly $n/2$, and every two
$T,T^{\prime}\in\mathcal{T}$ has Hamming distance at least $n^{2}/3$.

  2. 2.

(Matrix Decomposition) For every $T\in\mathcal{T}$, there exists
$A\in\\{0,1\\}^{n\times cn},B\in\\{0,1\\}^{cn\times n}$ such that $C=AB$
encodes $T$ in the following way. Let $\tilde{T}\in\\{0,1\\}^{n\times n}$ be
such that

$\tilde{T}(i,j)=\left\\{\begin{array}[]{ll}0&\mbox{if $C(i,j)<2n$}\\\
1&\mbox{if $C(i,j)\geq 2n$}\end{array}\right.$

Then $T,\tilde{T}$ have Hamming distance less than $n^{2}/6$. Moreover,
$C(i,j)\leq 2.1n$ for all $i,j$.

  3. 3.

(Vertex Connectivity) Let $A,B$ be the matrices corresponding to $T$ from Part
2. Let $G[T]=(X\cup Y\cup Z,E)$ be an undirected tripartite graph with
$|X|=|Z|=n$ and $|Y|=cn$, where $E\cap(X\times Y)$ encodes $A$ and
$E\cap(Y\times Z)$ encodes $B$. Let $\tilde{T}$ be such that

$\tilde{T}(i,j)=\left\\{\begin{array}[]{ll}0&\mbox{if
$\kappa(x_{i},z_{j})<4n-2$}\\\ 1&\mbox{if $\kappa(x_{i},z_{j})\geq
4n-2$}\end{array}\right.$

Then $T,\tilde{T}$ have Hamming distance less than $n^{2}/6$.

###### Proof.

For Part 1, a simple probabilistic construction shows the existence of
$\mathcal{T}$. Pick a random codebook $\mathcal{T}_{0}$ containing
$(1+o(1))2^{n^{2}/3}$ matrices and discard a negligible fraction of codewords
that are within distance $(2/5)n^{2}$ of another codeword. Obtain
$\mathcal{T}$ from $\mathcal{T}_{0}$ as follows. Take each
$T_{0}\in\mathcal{T}_{0}$ and see if it is within Hamming distance
$O(n^{3/2})$ of a matrix $T$, all of whose rows have Hamming weight $n/2$. If
so, include $T\in\mathcal{T}$ as a representative of $T_{0}$. Only a
negligible fraction of $\mathcal{T}_{0}$ matrices fail to satisfy this
property. Thus, $\mathcal{T}$ has the requisite size and each pair of matrices
in $\mathcal{T}$ has Hamming distance at least
$(2/5)n^{2}-O(n^{3/2})>n^{2}/3$.

Turning to Part 2, the construction of $A,B$ is probabilistic. We pick $B$
uniformly at random such that each row has Hamming weight $n/2$, then choose
$A$ depending on $B$. We call $(i,k)$ _eligible_ if the vector $B(k,\cdot)$
has an unusually high agreement with $T(i,\cdot)$, in particular, if

$|\\{j:B(k,j)=T(i,j)\\}|\geq n/2+\sqrt{n}.$

For each row $i$, we set $A(i,k)=1$ for the first $4n$ values of $k$ for which
$(i,k)$ is eligible. Since the probability of $(i,k)$ being eligible is some
constant $p$, it is possible to build $A$ with high probability if $c$ is
sufficiently large, say $4p^{-1}+1$.

Suppose $T(i,j)=1$ and consider the random variable $C(i,j)$. By the
definition of eligibility and the fact that rows of $B$ and $T$ have Hamming
weight $n/2$,

$\Pr(B(k,j)=1\mid(i,k)\mbox{
eligible})\geq\frac{1/2(n/2+\sqrt{n})}{n/2}=\frac{1}{2}+\frac{1}{\sqrt{n}}$

Thus $C(i,j)$ is a random variable that dominates
$\text{Binom}(4n,1/2+1/\sqrt{n})$, hence ${\mathbb{E}\/}(C(i,j))\geq
2n+4\sqrt{n}$. The case when $T(i,j)=0$ is symmetric, in which case
$\text{Binom}(4n,1/2-1/\sqrt{n})$ dominates $C(i,j)$. By a Chernoff bound, the
probability that $\tilde{T}(i,j)\neq T(i,j)$ is the probability that $C(i,j)$
deviates from its expectation by at least $4\sqrt{n}$, which is at most
$\exp(-2(4\sqrt{n})^{2}/4n)=\exp(-8)$. The Hamming distance between
$\tilde{T}$ and $T$ is therefore at most $n^{2}\exp(-8)<n^{2}/6$ in
expectation.

Lastly, by a Chernoff bound, the probability that $C(i,j)$ deviates from $2n$
by a constant factor is exponentially small. In particular, we have
$C(i,j)\leq 2.1n$ for all $i,j$ with high probability. This proves the
existence of matrices $A,B$ for any $T\in\mathcal{T}$.

Part 3. Observe that $C(i,j)$ reflects the maximum flow from $x_{i}$ to
$z_{j}$ if $G[T]$ were a unit-capacity network with all edges directed from
$X\rightarrow Y\rightarrow Z$. However, $G[T]$ is undirected, and by Menger’s
theorem $\kappa(x_{i},z_{j})$ is the maximum number of internally vertex
disjoint paths from $x_{i},z_{j}$. We consider paths of length 2
(corresponding to $C(i,j)$) and two types of paths of length 4.

For technical reasons we will modify the construction of $A$ as follows. For
each row $i$, set $A(i,k)=1$ for $r=O(c\log n)$ values of $k$ chosen uniformly
at random, then set $A(i,k)=1$ for $4n-r$ additional values of $k$ for which
$(i,k)$ is eligible. This changes the expectation of $C(i,j)$ by $O(c\log
n)/\sqrt{n}<1$ but does not otherwise affect the analysis in Part 2.

We claim that with high probability, the vertex connectivity of $x_{i},z_{j}$
is exactly

$\kappa(x_{i},z_{j})=\min\\{C(i,j)+2(n-1),4n\\}.$

In particular there are $\kappa(x_{i},z_{j})$ paths $P=P_{0}\cup P_{1}\cup
P_{2}$, where $|P_{0}|=C(i,j)$ are length-2 paths, $P_{1}$ are $n-1$ paths
internally disjoint from $P_{0}$ of the form $x_{i}\rightarrow Y\rightarrow
X\rightarrow Y\rightarrow z_{j}$ and $P_{2}$ are up to $n-1$ paths disjoint
from $P_{0}\cup P_{1}$ of the form $x_{i}\rightarrow Y\rightarrow Z\rightarrow
Y\rightarrow z_{j}$.

We construct $P_{1}$ as follows. Choose $Y_{1,x}$ to be any $n-1$ neighbors of
$x_{i}$ that are not part of $P_{0}$ paths, and $Y_{1,z}$ to be any $n-1$
neighbors of $z_{j}$ that are not part of $P_{0}$ paths. Clearly $Y_{1,x}\cap
Y_{1,z}=\emptyset$. Let $G_{1,x},G_{1,z}$ be the subgraphs of $G[T]$ induced
by $X-\\{x_{i}\\}\cup Y_{1,x}$ and $X-\\{x_{i}\\}\cup Y_{1,z}$, respectively.
These graphs contain many edges of derived from $A$, but we only consider the
$r$ edges per vertex generated randomly.888The edges included by the
eligibility criterion have subtle dependencies, which makes reasoning about
them somewhat tricky. Including truly random edges in $A$ is a technical hack
and surely not necessary. Since $r=\Theta(c\log n)$ and $|Y|=cn$, vertices in
both $G_{1,x}$ and $G_{1,z}$ have degree $\Theta(\log n)$ with high
probability. It is well known that such graphs have perfect matchings w.h.p.
(see [Bol11] or [FK16]); call them $M_{1,x},M_{1,z}$. Together with
$x_{i},z_{j}$, these form $n-1$ paths $P_{1}$ internally disjoint from
$P_{0}$. The construction of paths $P_{2}$ is symmetric. Let $Y_{2,x}$ be
$\min\\{n-1,4n-|P_{0}|-|P_{1}|\\}$ neighbors of $x_{i}$ not already included
in $P_{0},P_{1}$, and $Y_{2,z}$ be $|Y_{2,x}|$ neighbors of $z_{j}$ not
included in $P_{0},P_{1}$. Note that both $Y_{2,x}$ and $Y_{2,z}$ have size at
least $0.9n$ because $|P_{0}|\leq 2.1n$ and $|P_{1}|\leq n$. The graphs
$G_{2,x},G_{2,z}$ induced by $Z-\\{z_{j}\\}\cup Y_{2,x}$ and
$Z-\\{z_{j}\\}\cup Y_{2,z}$ again contain perfect matchings $M_{2,x},M_{2,z}$
with high probability.999Note that $G_{2,x},G_{2,z}$ correspond to submatrices
of $B$, which was chosen randomly with density 1/2. Due to the Hamming weight
restriction, the entries of $B$ are slightly negatively correlated, which only
_improves_ the chance of finding perfect matchings. Together with $x_{i}$ and
$z_{j}$ these generate $|Y_{2,x}|$ paths internally disjoint from
$P_{0},P_{1}$.

We conclude that with high probability, $C(i,j)<2n$ if and only if
$\kappa(x_{i},z_{j})<2n+2(n-1)$ and, from Part 2, that there exist $A,B$ such
that $\tilde{T},T$ have Hamming distance less than $n^{2}/6$. ∎

######  Corollary 3.2.

Suppose $\mathscr{D}(G,k)$ is a data structure for an undirected $n$-vertex
graph $G$ that can determine whether $\kappa(u,v)<k$ or $\kappa(u,v)\geq k$.
Then $\mathscr{D}$ requires $\Omega(kn)$ bits of space in the worst case.

###### Proof.

Pick any $T\in\mathcal{T}$, and let $G=G[T]$ be the $(c+2)n$-vertex graph
encoding of $T$ from Theorem 3.1. Using $\mathscr{D}(G,k)$ we can generate the
matrix $\tilde{T}$, where $k=4n-2$, and then deduce $T$ since $\tilde{T}$ is
within its decoding radius. Thus, $\mathscr{D}$ requires at least
$\log|\mathcal{T}|=\Theta(n^{2})$ bits of space. For general values of $k$, we
can take $\Theta(n/k)$ disjoint copies of this construction, each having
$\Theta(k)$ vertices and requiring $\Theta(k^{2})$ space. ∎

######  Remark 3.3.

The lower bound of Corollary 3.2 also applies to data structures
$\mathscr{D}(G,k)$ that distinguish between $\kappa(u,v)=k$ and
$\kappa(u,v)\neq k$. For this case we would use the construction of Theorem
3.1 with $k=4n$ and let $\tilde{T}(i,j)=1$ iff $\kappa(x_{i},z_{j})=4n$.

######  Corollary 3.4.

Suppose $\mathscr{D}(G,k,\epsilon)$ is a data structure for an undirected
$n$-vertex graph $G$ that can distinguish between $\kappa(u,v)<(1-\epsilon)k$
or $\kappa(u,v)>(1+\epsilon)k$. Then $\mathscr{D}$ requires
$\Omega(n\epsilon^{-2})$ bits of space for some $\epsilon$.

###### Proof.

The construction of Theorem 3.1 and Corollary 3.2 still works when
$k=\Theta(n)$ and $\epsilon=\Theta(1/\sqrt{n})$. ∎

##  4 Vertex Connectivity Oracles

Lemma 2.1 says that for any terminal set $U$, $\kappa^{\prime}_{G,U}(u,v)$
_never_ underestimates the true value $\kappa_{G}(u,v)$ and achieves the
equality $\kappa^{\prime}_{G,U}(u,v)=\kappa_{G}(u,v)$ in the event that some
minimum mixed $u$-$v$ cut $C_{u,v}$ is disjoint from $U$. Furthermore,
$\kappa^{\prime}_{G,U}$ is superior than $\kappa_{G}$ inasmuch as it can be
succinctly represented as a Gomory-Hu tree (Definition 2.2) and queried via
bottleneck edge queries [Pet06, DLW09, Cha87].

Izsak and Nutov’s [IN12] ingenious algorithm proceeds by sampling several
terminal sets with probability $1/k$. Each terminal set includes both $u$ and
$v$ with probability $1/k^{2}$ and _avoids_ $C_{u,v}$ with constant
probability if $|C_{u,v}|\leq k$, hence $O(k^{2}\log n)$ terminal sets suffice
to accurately capture all vertex connectivities up to $k$ with high
probability. The space for the centralized data structure is just that of
storing $O(k^{2}\log n)$ Gomory-Hu trees and data structures for answering
bottleneck-edge queries. Each tree is on $O(n/k)$ terminals, for a total of
$O(kn\log n)$ space. A query $\mathsf{v}\text{-}\mathsf{conn}(u,v)$ needs to
examine all terminal sets containing _both_ $u$ and $v$. This is a classic
SetIntersection query. Each of $u,v$ is in $\Theta(k\log n)$ sets, and are
jointly in $\Theta(\log n)$ sets. In this section we show how to build
appropriate SetIntersection instances such that queries are answered in
(optimal) $O(\log n)$ time. (If minimum cuts are associated with edges in the
Gomory-Hu tree, a $\mathsf{v}\text{-}\mathsf{cut}(u,v)$ query can be answered
in $O(1)$ additional time be returning a pointer to the appropriate cut. This
increases the space to $O(k^{2}n\log n)$.)

A terminal set $U\subseteq V$ _captures_ $u,v$ if there exists a
$\kappa(u,v)$-cut $C\subseteq V\cup E$ such that

$U\cap(\\{u,v\\}\cup C)=\\{u,v\\}.$

We show how to find $O(k^{2}\log n)$ terminal sets that capture all pairs in
$V^{2}$ using a construction based on affine planes and 3-wise independent
hash functions.

######  Lemma 4.1.

There is an algorithm using $O(\log^{2}n)$ random bits that generates terminal
sets $\mathcal{U}$ with the following properties.

  * •

$|\mathcal{U}|=O(k^{2}\log n)$ and each $U\in\mathcal{U}$ has $|U|=O(n/k)$.

  * •

Given vertices $u,v$ with $\kappa(u,v)\leq k$ we can find $O(\log n)$ sets
$U_{1},\ldots,U_{O(\log n)}$ such that each, independently, captures $u,v$
with constant probability. As a consequence, w.h.p., $\mathcal{U}$ captures
all of $V^{2}$.

###### Proof.

Let $p_{0}$ be the first prime larger than $n=|V|$ and $p$ be the first prime
larger than $2k$. Let $H=(P,L)$ be a subset of an affine plane, defined as
follows. $P=\\{u_{i,j}\mid i\in[p],j\in[\left\lceil{p_{0}/p}\right\rceil]\\}$
is a set of points arranged in a rectangular grid and $L=\\{\ell_{s,j}\mid
s,j\in[p]\\}$ is a set of lines, where $\ell_{s,j}=\\{u_{t,j+st\ \mathrm{mod}\
p}\mid t\in[\left\lceil{p_{0}/p}\right\rceil]\\}$ is the line with slope $s$
passing through $u_{0,j}$. We pick a hash function $h:V\rightarrow P$ of the
form

$h(x)=(ax^{2}+bx+c)\ \mathrm{mod}\ p_{0}$

where $a,b,c$ are chosen uniformly at random from $[p_{0}]$, then form the
$p^{2}=\Theta(k^{2})$ terminal sets $\mathcal{U}[h]=\\{U_{s,j}\\}$ as follows.

$U_{s,j}=\\{v\mid h(v)\in\ell_{s,j}\\}.$

Now fix any two vertices $u,v$ and a $\kappa(u,v)$ cut $C$ with
$\kappa(u,v)\leq k$. Then $\mathcal{U}[h]$ will capture $u,v$ if (i)
$h(u),h(v)$ differ in their 1st coordinates of the rectangular grid $P$, and,
assuming this happens, (ii) $C\cap U_{s,j}=\emptyset$ where $\ell_{s,j}$ is
the unique line containing $h(u),h(v)$. The probability of (i) is
$1-p/p_{0}=1-\Theta(k/n)$ and the probability of (ii) is

$\Pr(C\cap U_{s,j}=\emptyset\mid h(u),h(v))\geq 1-\sum_{x\in C\cap
V}\Pr(h(x)\in\ell_{s,j}\mid h(u),h(v))\geq
1-k\left\lceil{p_{0}/p}\right\rceil/p_{0}\geq 1/2$

where the second last inequality is because
$|\ell_{s,j}|\leq\left\lceil{p_{0}/p}\right\rceil$, $|C|\leq k$, and $h$ is
sampled from a $3$-wise independent hash family.

Let $\mathcal{U}$ be the union of
$\mathcal{U}[h_{1}],\ldots,\mathcal{U}[h_{O(\log n)}]$ using independent hash
functions $h_{1},\ldots,h_{O(\log n)}$. It follows that
$|\mathcal{U}|=O(p^{2}\log n)=O(k^{2}\log n)$, that given $u,v$ we can
identify $U_{1},\ldots,U_{O(\log n)}\in\mathcal{U}$ in $O(\log n)$ time such
that at least one of these terminal sets captures $u,v$ w.h.p.101010Given
points $h(u),h(v)$ differing in 1st coordinate, we can clearly identify
$\ell_{s,j}$ containing them in $O(1)$ time using a table of inverses modulo
$p$.

We now turn to the load balancing condition $|U|=O(n/k)$. Note that if the
coefficients of $h$ satisfy $(a,b,c)\neq(0,0,c)$ then $h$ is at most a 2-to-1
function (as the polynomial defining $h$ has degree 2), meaning that each
$U\in\mathcal{U}$ has $|U|<2\left\lceil{p_{0}/p}\right\rceil=O(n/k)$. The
performance of the algorithm is clearly quite bad when $a=b=0$ (each terminal
set $U$ is either $\emptyset$ or $V$) so we can remove these hash functions
from the hash family and only improve the probability of success. ∎

######  Remark 4.2.

One way that $\mathcal{U}[h]$ can fail to capture $u,v$ is if $h(u)$ and
$h(v)$ agree on their 1st coordinate. This could be rectified by including the
lines with infinite slope in $L$, but this only seems to work when
$k\leq\sqrt{n}$. When $k\geq\sqrt{n}$ doing so would violate the load
balancing constraint $|U|=O(n/k)$ as some lines would necessarily have size
$\Omega(k)$.

Now, by using the collection $\mathcal{U}$ of terminal sets with additional
structure from Lemma 4.1 instead of the $O(k^{2}\log n)$ random terminal sets
generated independently as used in [IN12], we can speed up the query time from
$\tilde{O}(k)$ to $O(\log n)$. Below, we state the guarantee of our oracle
formally.

######  Theorem 4.3.

Given an undirected graph $G=(V,E)$ and $k\in[1,n]$, a data structure with
size $O(kn\log n)$ can be constructed in
$O(m)+T_{\operatorname{uflow}}(nk)\mathrm{poly}(k,\log
n)=O(m)+n^{4/3+o(1)}\mathrm{poly}(k)$ time such that
$\mathsf{v}\text{-}\mathsf{conn}(u,v)=\min\\{\kappa_{G}(u,v),k\\}$ queries can
be answered in $O(\log n)$ time. Using space $O(k^{2}n\log n)$, a
$\mathsf{v}\text{-}\mathsf{cut}(u,v)$ query can be answered in $O(1)$
_additional_ time; it returns a pointer to a $\kappa_{G}(u,v)$-size $u$-$v$
cut whenever $\kappa_{G}(u,v)<k$.

The claims of Theorem 4.3 concerning construction time are substantiated in
Section 5. In the context of our vertex connectivity oracle, note that we can
assume that our original graph has $O(nk)$ edges by applying Nagamochi-Ibaraki
algorithm [NI92] with $O(m)$ running time to reduce the number of edges to
$O(kn)$. So the construction time is $n^{4/3+o(1)}\mathrm{poly}(k)$ using the
max-flow algorithm for unit-capacity graphs by Kathuria, Liu, and Sidford
[KLS20].

##  5 Gomory-Hu Trees for Element Connectivity

The goal in this section is to prove the following:

######  Theorem 5.1.

A $k$-Gomory-Hu tree for element connectivity w.r.t. graph $G$ and terminal
set $U$ can be constructed in $\tilde{O}(k\cdot
T_{\operatorname{uflow}}(m+k\left|U\right|))$ time.

Note that, given the above theorem, we can indeed conclude Theorem 4.3 because
there are $O(k^{2}\log n)$ terminal sets in the oracle construction and we
just need to build a Gomory-Hu tree for each terminal set by calling Theorem
5.1. As $m=O(nk)$ and $|U|=O(n/k)$ by Lemma 4.1, this takes
$T_{\operatorname{uflow}}(m+k|U|)=T_{\operatorname{uflow}}(O(nk))$ for each
terminal set.

##### Obstacles in Adapting Algorithms of [LP21] for Element Connectivity.

The proof of Theorem 5.1 is obtained by adapting the Gomory-Hu tree
construction for _edge connectivity_ by Li and Panigrahi [LP21] to work for
_element connectivity_. Although we use the same high-level approach, element
connectivity introduces some extra complication that we need to deal with.

For example, given an input graph $G$, all Gomory-Hu tree algorithms for edge
connectivity proceed by finding a minimum edge cut $(A,B)$, contract one side,
say $B$, of the cut into a single vertex $b$, and recurse on the contracted
graph denoted by $G^{\prime}$. By submodularity of edge cuts, we have that the
edge connectivity between any two vertices $a_{1},a_{2}\in A$ are preserved in
$G^{\prime}$. This is crucial for the correctness of the whole algorithm.

Unfortunately, the direct analog of this statement fails completely for
element connectivity. For example, suppose $p,q\notin B$ are disconnected by
an element cut $C$ of graph $G$. Then in graph $G^{\prime}$,
$C^{\prime}=\\{b\\}\cup(C\setminus B)$ becomes an element cut disconnecting
$p$ and $q$. As long as $C$ contains more than one element in $B$ (an edge, or
a non-terminal vertex), $\left|C^{\prime}\right|<\left|C\right|$, so
$\kappa^{\prime}(p,q)$ decreased.

To bypass this complication, we actually exploit the generality of element
connectivity. When we recurse in a contracted graph, the trick is to add the
contracted node into a terminal set for element connectivity. That is, the
terminal set will change throughout the recursion so that we can preserve
element connectivity between vertices inside the subject graph.

In the rest of this section, we formally prove Theorem 5.1.

###  5.1 The Approximate Element Connectivity Gomory-Hu Tree Algorithm

Instead of proving Theorem 5.1 directly, it is more convenient to prove the
following $(1+\epsilon)$-approximation version, which is precisely the element
connectivity analog of the result in [LP21].

######  Theorem 5.2.

A $(1+\epsilon)$-approximate Gomory-Hu tree for element connectivity w.r.t.
graph $G$ and terminal set $U$ can be computed in
$\tilde{O}(\epsilon^{-1}T_{\operatorname{flow}}(m))$ time, where
$T_{\operatorname{flow}}(m)$ is the time to compute max flow in an $m$-edge
graph.

Theorem 5.1 almost follows from Theorem 5.2 just by setting $\epsilon=1/k$.
However, there is some minor things to take care of, and we give the formal
proof in Section 5.2.

Before we give the proof of Theorem 5.2, observe that as a simplifying
assumption, Lemma 2.3 (isolating cuts with forbidden terminals) required that
$I\cup F$ be an independent set. We can force any instance to satisfy this
property by subdividing all edges in $E\cap(I\cup F)^{2}$. As a consequence,
from now we can assume that all element cuts in the modified graph consist
solely of vertices.111111If $(x,y)$ is subdivided into
$(x,v_{xy}),(v_{x,y},y)$, then any vertex-only element cut containing
$v_{x,y}$ in the modified instance contains $(x,y)$ in the original instance,
and vice-versa.

####  5.1.1 Algorithm

The precise algorithm for Theorem 5.2 is described in Algorithm 1. For the
reader to better understand, we first briefly explain how the algorithm works,
how the input and the output of the algorithm relate to Definition 2.2.

The basic framework of the algorithm is a recursion. For a random set of
terminals $R^{i}$, we call Lemma 2.3 to compute its isolating cuts
$S_{v}^{i}$. We select those $v$ such that $S_{v}^{i}\leq(1+\epsilon)\lambda$
and $\left|S_{v}^{i}\cap U\right|\leq\left|U\right|/2$ into set
$R_{\operatorname{sm}}^{i}$. Now $\partial S_{v}^{i}$ is a
$(1+\epsilon)$-approximation to the minimum element cut between $S_{v}^{i}$
and $V\setminus(S_{v}^{i}\cup\partial S_{v}^{i})$, so we split the problem
into sub-graphs $G_{v}$ generated by $S_{v}^{i}$ for each $v\in
R_{\operatorname{sm}}^{i}$ and one large part, which we call
$G_{\operatorname{lg}}$. We specify the new parameters added in the algorithm.

As mentioned earlier, to make sure the element cuts represented by the sub-
trees are still exact, or of good approximation in the original graph $G$, we
add a new parameter: the forbidden set $F$. The vertices in $F$ are terminals
counted when computing the connectivity, but queries related to them are not
supported. Accordingly, the output $T$ is a $(1+\epsilon)$-approximate Gomory-
Hu tree, that represents element connectivity in $G$ with the terminal set
$U\cup F$, while the tree nodes only represent vertices from $U$.121212I.e.,
$f:U\rightarrow V(T)$ does not embed $F$ in $T$. For $u,v\in U$, the
bottleneck edge weight between $f(u)$ and $f(v)$ on $T$ is
$\kappa^{\prime}_{G,U\cup F}(u,v)$. In the top-level call $F$ is set to
$\emptyset$, but may accumulate up to $O(|U|)$ vertices in the recursion.

As will be proved in Lemma 5.3, the element connectivity between vertices
inside $U_{\operatorname{lg}}$ are preserved exactly in the contracted graph
$G_{\operatorname{lg}}$. For the small graphs $G_{v}$, by Lemma 5.4, we accept
a $(1+\epsilon)$-factor approximation to element connectivity, which accrues
to $(1+\epsilon)^{\log|U|}$ as a vertex can only appear in the _small_ branch
of the recursion $\log|U|$ times.

To link the sub-trees at correct nodes and to compute $f$, we added a tool
function $g:V\to V_{T}\cup\\{\bot\\}$ that maps vertices of $G$ into tree
nodes of $T$, or a symbol $\bot$. $g$ indicates at which tree nodes we should
link two sub-trees. Taking $G_{\operatorname{lg}}$ as example again, as the
recursion goes down, and each $y_{v}$ finally would appear in the base case
for some tree node $t_{v}$, we would set $g(y_{v})=t_{v}$. From this
construction, $t_{v}$ is the only terminal that no element cut disconnect
$y_{v}$ and $t_{v}$. Therefore, when linking the sub-tree of
$G_{\operatorname{lg}}$ with $G_{v}$, we should link at the tree node
$t_{v}=g(y_{v})$, and the same holds for $G_{v}$. Moreover, we will make sure
that at the end, $g(v)\neq\bot$ for every $v\in U$. From the definition of
$g$, $g(v)$ with $v\in U$ satisfies the properties of the embedding function
$f$ in Definition 2.2.

To summarize, to compute $(1+\epsilon)$-approximate Gomory-Hu tree, call
Algorithm 1 with desired $G,U,\epsilon,$ and $F=\emptyset$. It outputs
$(T,g,C)$. We set the embedding $f(v)=g(v)$ for all $v\in U$, and then return
$(T,f,C)$, which satisfies Definition 2.2.

input : The graph $G=(V,E)$, the terminal set $U$, the forbidden set $F$, the
approximation accuracy $\epsilon$

output : A $(1+\epsilon)$-approximate element-connectivity Gomory-Hu tree
$(T,{g},C)$

1 if  _$\left|U\right|=1$_ then // The Base Case

2 Construct $T$ with one node $t$, $g(u)\leftarrow t$ for all $u\in V(G)$ and
$C$ an empty function

3 return $(T,g,C)$

4 end if

Let $\lambda\leftarrow$ the global minimum element connectivity

// See Remark 5.7

5 Call CutThresholdStep(_$G,U,F,(1+\epsilon)\lambda$_) and store its output
$s,\\{R_{\operatorname{sm}}^{j},R^{j},S_{v}^{j}\\}$

6 Fix $i\in\\{0,1,\cdots,\lfloor\log\left|U\right|\rfloor\\}$ that maximizes
$\left|\cup_{v\in R_{\operatorname{sm}}^{i}}(S_{v}^{i}\cap U)\right|$.

7

8foreach  _$v\in R_{\operatorname{sm}}^{i}$_ do

9 Let $G_{v}\leftarrow$ the graph with $V\setminus(S_{v}^{i}\cup\partial
S_{v}^{i})$ contracted into a vertex $x_{v}$.

10 Let $U_{v}\leftarrow S_{v}^{i}\cap U$.

11 Let $(T_{v},{g}_{v},C_{v})\leftarrow$
ApproxElemConnGHTree(_$G_{v},U_{v},F\cup\\{x_{v}\\},\epsilon$_).

12

13 end foreach

14

15Let $G_{\operatorname{lg}}\leftarrow$ the graph $G$ with $S_{v}^{i}$
contracted into a vertex $y_{v}$ for each $v\in R_{\operatorname{sm}}^{i}$.

16 Let $U_{\operatorname{lg}}\leftarrow U\setminus\cup_{v\in
R_{\operatorname{sm}}^{i}}(S_{v}^{i}\cap U)$.

17 Let
$(T_{\operatorname{lg}},{g}_{\operatorname{lg}},C_{\operatorname{lg}})\leftarrow$
ApproxElemConnGHTree(_$G_{\operatorname{lg}},U_{\operatorname{lg}},F\cup\\{y_{v}\mid
v\in R_{\operatorname{sm}}^{i}\\},\epsilon$_).

18

19Initialize $T\leftarrow T_{\operatorname{lg}}\cup(\cup_{v\in
R_{\operatorname{sm}}^{i}}T_{v})$, and then add edges
$({g}_{v}(x_{v}),{g}_{\operatorname{lg}}(y_{v}))$ with weight $\left|\partial
S_{v}^{i}\right|$. Let ${g}$ inherit values from ${g}_{\operatorname{lg}}$ or
one of the $\\{{g}_{v}\\}$. If the value for $v$ is defined in more than one
such function, set ${g}(v)\leftarrow\bot$. Let $C$ inherit the assignment of
$C_{\operatorname{lg}}$ and $\\{C_{v}\\}$, and for the new edges set
$C(({g}_{v}(x_{v}),{g}_{\operatorname{lg}}(y_{v})))\leftarrow\partial
S_{v}^{i}$.

20

21return $(T,{g},C)$.

Algorithm 1 ApproxElemConnGHTree$(G=(V,E),U,F,\epsilon)$

1 Set $s\leftarrow$ a uniformly random vertex in $U$.

2 $R^{0}\leftarrow U$.

3 for  _$j$ from $0$ to $\lfloor\log\left|U\right|\rfloor$_ do

4 Call Lemma 2.3 to compute sets $\\{S^{j}_{v}:v\in R^{j}\\}$, with $I=R^{j}$
and $F=(U\backslash R^{j})\cup F_{in}$.

5 Let $R_{\operatorname{sm}}^{j}\leftarrow\\{v\in
R^{j}\setminus\\{s\\}:\left|S_{v}^{j}\cap U\right|\leq\left|U\right|/2\text{
and }\left|\partial S_{v}^{j}\right|\leq W\\}$.

6 $R^{j+1}\leftarrow$ sampling each vertex of $R^{j}$ with probability
$\frac{1}{2}$, but $s$ with probability 1.

7

8 end for

9return $s$ and, for each $j$, $\\{R_{\operatorname{sm}}^{j}$, $R^{j}$,
{$S^{j}_{v}\\}_{v\in R^{j}_{\operatorname{sm}}}\\}$.

Algorithm 2 CutThresholdStep$(G=(V,E),U,F_{in},W)$

####  5.1.2 Correctness

We prove the results needed to show the correctness of Algorithm 1. Denote
$F_{\operatorname{lg}}=F\cup\\{y_{v}|v\in R_{\operatorname{sm}}^{i}\\}$ and
$F_{v}=F\cup\\{x_{v}\\}$.

######  Lemma 5.3.

For any two vertices $p,q\in U_{\operatorname{lg}}$, we have
$\kappa^{\prime}_{G_{\operatorname{lg}},U_{\operatorname{lg}}\cup
F_{\operatorname{lg}}}(p,q)=\kappa^{\prime}_{G,U\cup F}(p,q)$.

###### Proof.

We first show that
$\kappa^{\prime}_{G_{\operatorname{lg}},U_{\operatorname{lg}}\cup
F_{\operatorname{lg}}}(p,q)\geq\kappa^{\prime}_{G,U\cup F}(p,q)$. Suppose $C$
is a minimum element cut disconnecting $p$ and $q$ in $G_{\operatorname{lg}}$
with terminal set $U_{\operatorname{lg}}\cup F_{\operatorname{lg}}$. Then $C$
does not contain any $y_{v}$, so $C$ is still an element cut for $p$ and $q$
in $G$, and therefore
$\kappa^{\prime}_{G_{\operatorname{lg}},U_{\operatorname{lg}}\cup
F_{\operatorname{lg}}}(p,q)=\left|C\right|\geq\kappa^{\prime}_{G,U\cup
F}(p,q)$.

It remains to show that
$\kappa^{\prime}_{G_{\operatorname{lg}},U_{\operatorname{lg}}\cup
F_{\operatorname{lg}}}(p,q)\leq\kappa^{\prime}_{G,U\cup F}(p,q)$. Suppose $C$
is a minimum element cut disconnecting $p$ and $q$ in $G$ with terminal set
$U\cup F$, and let $A,B$ be the sides containing $p,q$, respectively. Every
$v\in R_{\operatorname{sm}}^{i}$ is by definition not in $C$; let the side of
$C$ containing $v$ be $D_{v}$.

Without loss of generality we assume $v$ and $q$ are in different sides. For
brevity, all the following unspecified element cuts are with respect to $G$
and $U\cup F$. Let $H=D_{v}\cup A$, we have that $\partial H$ is a minimum
element cut between $\\{v,p\\}$ and $\\{q\\}$, and $\partial(H\cup S_{v}^{i})$
is an element cut between $\\{v,p\\}$ and $\\{q\\}$, so $\left|\partial(H\cup
S_{v}^{i})\right|\geq\left|\partial H\right|$. Now that $\partial S_{v}^{i}$
is also a minimum element cut between $\\{v\\}$ and $R^{i}\setminus\\{v\\}$,
and $\partial(S_{v}^{i}\cap H)$ is also an element cut between $\\{v\\}$ and
$R^{i}\setminus\\{v\\}$, we have $\left|\partial(H\cap
S_{v}^{i})\right|\geq\left|\partial S_{v}^{i}\right|$. By the submodularity of
element-connectivity,

$\left|\partial H\right|+\left|\partial
S_{v}^{i}\right|\geq\left|\partial(H\cap
S_{v}^{i})\right|+\left|\partial(H\cup S_{v}^{i})\right|.$

Hence this inequality holds with equality, so $\left|\partial(H\cap
S_{v}^{i})\right|=\left|\partial S_{v}^{i}\right|$. But by Lemma 2.3,
$S_{v}^{i}$ is also minimum in size among minimum isolating cuts, so $H\cap
S_{v}^{i}=S_{v}^{i}$, and therefore $S_{v}^{i}\subseteq H$.

If $D_{v}=A$, we already have $S_{v}^{i}\subseteq D_{v}$. If $D_{v}\neq A$,
then noticing that in $G-C$, $D_{v}$ is not connected to $A$, while
$S_{v}^{i}$ is connected to $v$, we know that $S_{v}^{i}\cap A=\emptyset$ and
$S_{v}^{i}\subseteq D_{v}$.

We have shown that $S_{v}^{i}\subseteq D_{v}$. When contracting $S_{v}^{i}$
into a vertex $x_{v}$, the cut $C=\partial D_{v}$ is not affected, so $C$ is
still an element cut between $p$ and $q$ in $G_{\operatorname{lg}}$ with
terminal set $U_{\operatorname{lg}}\cup F_{\operatorname{lg}}$, and
$\kappa^{\prime}_{G_{\operatorname{lg}},U_{\operatorname{lg}}\cup
F_{\operatorname{lg}}}(p,q)\leq\left|C\right|=\kappa^{\prime}_{G,U\cup
F}(p,q)$. ∎

######  Lemma 5.4.

For any two vertices $p,q\in U_{v}$, we have
$1\leq\kappa^{\prime}_{G_{v},U_{v}\cup F_{v}}(p,q)/\kappa^{\prime}_{G,U\cup
F}(p,q)\leq 1+\epsilon$.

###### Proof.

We first show that $\kappa^{\prime}_{G_{v},U_{v}\cup
F_{v}}(p,q)\geq\kappa^{\prime}_{G,U\cup F}(p,q)$. Suppose $C$ is a minimum
element cut disconnecting $p$ and $q$ in $G_{v}$ with terminal set $U_{v}\cup
F_{v}$. Then $C$ does not contain $x_{v}$, so $C$ is still an element cut
disconnecting $p$ and $q$ in $G$, so $\kappa^{\prime}_{G,U\cup
F}(p,q)\leq\left|C\right|=\kappa^{\prime}_{G_{v},U_{v}\cup F_{v}}(p,q)$.

Next, we show that $\kappa^{\prime}_{G_{v},U_{v}\cup
F_{v}}(p,q)\leq(1+\epsilon)\kappa^{\prime}_{G,U\cup F}(p,q)$. Suppose $C$ is a
minimum element cut disconnecting $p$ and $q$ in $G$ with terminal set $U\cup
F$ and let $A,B$ be the sides of $p,q$. Without loss of generality, suppose
$A$ does not contain $s$. The following unspecified element cuts are with
respect to $G$ and $U\cup F$.

We have that $\partial(S_{v}^{i}\cup A)$ is an element cut disconnecting $p$
and $s$. Therefore, $\left|\partial(S_{v}^{i}\cup A)\right|\geq\lambda$.
Furthermore, by the definition of $S_{v}^{i}$, $\left|\partial
S_{v}^{i}\right|\leq(1+\epsilon)\lambda$. Therefore, by the submodularity of
element cuts,

$(1+\epsilon)\lambda+\left|\partial A\right|\geq\left|\partial
S_{v}^{i}\right|+\left|\partial A\right|\geq\left|\partial(S_{v}^{i}\cup
A)\right|+\left|\partial(S_{v}^{i}\cap A)\right|\geq\lambda+\left|\partial
S_{v}^{i}\cap A\right|.$

Now that $S_{v}^{i}\cap A$ contains $p$ but not $q$, $\partial(S_{v}^{i}\cap
A)$ is an element cut disconnecting $p$ and $q$, and since it is contained in
$G_{v}$, it is still an element cut in $G_{v}$ with terminal set $U_{v}\cup
F_{v}$, so $\left|\partial(S_{v}^{i}\cap
A)\right|\geq\kappa^{\prime}_{G_{v},U_{v}\cup F_{v}}(p,q)$. And by definition
$\left|\partial A\right|=\kappa^{\prime}_{G,U\cup F}(p,q)\geq\lambda$.

Therefore,

$\kappa^{\prime}_{G_{v},U_{v}\cup
F_{v}}(p,q)\leq\epsilon\lambda+\left|\partial
A\right|\leq(1+\epsilon)\kappa^{\prime}_{G,U\cup F}(p,q).$

∎

######  Lemma 5.5.

The assignment ${g}(v)=\bot$ occurs if and only if $v$ appears in $C(e)$ for
some edge. Therefore, ${g}$ value of vertices in $U\cup F$ never equals
$\bot$.

###### Proof.

From the construction of $G_{\operatorname{lg}}$ and $G_{v}$, it can be seen
that only the vertices in $\partial
S_{v}^{i}=C(({g}_{v}(x_{v}),{g}_{\operatorname{lg}}(y_{v})))$ are defined
twice (or more), so their ${g}$-value are set to $\bot$. These are all the
vertices such that ${g}(v)=\bot$. ∎

######  Remark 5.6.

From Lemma 5.3, Lemma 5.4 and Lemma 5.5, in line 17 of Algorithm 1, the
${g}$-value of $x_{v}$, $y_{v}$ are not $\bot$, so linking the sub-trees would
be successful. And $g(v)$ for $v\in U$ equals to $\bot$.

######  Remark 5.7.

As stated the algorithm computes the global element connectivity $\lambda$. In
reality $\lambda$ is a lower bound on this quantity, which is increased once
we are sure it has increased by a $1+\epsilon$ factor. As we show in the proof
of Theorem 5.2, with high probability, the global element connectivity
increases by a factor of $1+\epsilon$ every $O(\log^{3}n)$ steps taken in the
“$G_{\operatorname{lg}}$” branch of the recursion tree. Therefore, what the
algorithm actually does is initialize $\lambda=1$, record the recursion depth
on the $G_{\operatorname{lg}}$ branch, and update
$\lambda\leftarrow(1+\epsilon)\lambda$ whenever this depth is a multiple of
$\Theta(\log^{3}n)$. In this way, $\lambda$ never exceeds the global element
connectivity w.h.p., which suffices to establish correctness.

####  5.1.3 Running Time Analysis

The running time analysis in this section closely follows Li and Panigrahi
[LP21].

######  Lemma 5.8.

Keeping definitions of $R^{i},R_{\operatorname{sm}}^{i},S_{v}^{i}$ as in line
4, 5, 6 of Algorithm 2. Keeping definitions of
$G_{\operatorname{lg}},U_{\operatorname{lg}},F_{\operatorname{lg}}$ as in line
13, 14, 15 of Algorithm 1. Define $P\subset U^{2}$ to be

$\displaystyle P$ $\displaystyle=\\{(u,v):\kappa^{\prime}_{G,U\cup F}(u,v)\leq
W,\text{ and if $A$ is the side of the minimum $u$-$v$}$ $\displaystyle\hskip
113.81102pt\text{element cut containing $u$, then $|A\cap U|\leq|U|/2$}\\}.$
Similarly define $P_{\operatorname{lg}}$ with
$G_{\operatorname{lg}},U_{\operatorname{lg}},F_{\operatorname{lg}}$ and $W$.
Then $\displaystyle{\mathbb{E}\/}(\left|P_{\operatorname{lg}}\right|)$
$\displaystyle\leq\left(1-\Omega\left(\frac{1}{\log^{2}\left|U\right|}\right)\right)\left|P\right|.$

###### Proof.

We need to lower bound the size of $Q=P\backslash P_{\operatorname{lg}}$.
Define $U_{\operatorname{sm}}^{i}=\cup_{v\in
R_{\operatorname{sm}}^{i}}(S_{v}^{i}\cap U)$,
$U_{\operatorname{sm}}=\cup_{i=1}^{\lfloor\log\left|U\right|\rfloor}U_{\operatorname{sm}}^{i}$,
and $U^{*}=\\{v\mid(v,s)\in P\\}$. We will show that
${\mathbb{E}\/}(\left|Q\right|)\geq\Omega(\frac{1}{\log^{2}n})\left|P\right|$
follows from the following three claims.

  * (1)

For each $u\in U^{*}$, there are at least $\left|U\right|/2$ vertices $v$ such
that $(u,v)\in P$.

  * (2)

${\mathbb{E}\/}(\left|U_{\operatorname{sm}}\right|)\geq\Omega(\left|U^{*}\right|/\log\left|U\right|)$.

  * (3)

For each $(u,v)\in P$, $u\in U^{*}$ with probability at least $1/2$;

For Claim (1), consider the minimum element cut disconnecting $s$ and $u\in
U^{*}$. There are at least $\left|U\right|/2$ terminals $v$ not in the same
side as $u$, and each $(u,v)\in P$. Claim (2) is proved in Lemma 5.9. Claim
(3) holds because $s$ is randomly chosen from $U$ and there are at least
$\left|U\right|-\left|U\right|/2=\left|U\right|/2$ terminals not in the side
of $u$. When $s$ is such a terminal, $u\in U^{*}$.

The algorithm fixes $i\in\\{1,2,\cdots,\lfloor\log\left|U\right|\rfloor\\}$
that maximizes $\left|U_{\operatorname{sm}}^{i}\right|$. Then,

${\mathbb{E}\/}(\left|Q\right|)\geq\frac{\left|U\right|}{2}{\mathbb{E}\/}(\left|U_{\operatorname{sm}}^{i}\right|)\geq\frac{\left|U\right|}{2\log\left|U\right|}{\mathbb{E}\/}(\left|U_{\operatorname{sm}}\right|)\geq\frac{\left|U\right|}{2\log\left|U\right|}\Omega\left(\frac{\left|U^{*}\right|}{\log\left|U\right|}\right)\geq\Omega\left(\frac{1}{\log^{2}\left|U\right|}\right)\left|P\right|.$

For the first inequality, Claim (1) implies that each $v\in
U_{\operatorname{sm}}^{*}$ is involved in $\left|U\right|/2$ pairs in $P$, all
of which do not appear in $P_{\operatorname{lg}}$ whenever $v\in
U_{\operatorname{sm}}^{i}$. The second inequality follows from the choice of
$i$. The third inequality follows from Claim (2). The fourth inequality
follows from Claim (3) and the following bound on the size of $P$.

$\left|P\right|/2\leq{\mathbb{E}\/}(\left|\\{(u,v)\in P:u\in
U^{*}\\}\right|)\leq\left|U\right|\cdot\left|U^{*}\right|.$

Note each $u$ appears in at most $\left|U\right|$ pairs of $P$. ∎

######  Lemma 5.9 (Claim (2) restated).

${\mathbb{E}\/}(|U_{\operatorname{sm}}|)=\Omega(\left|U^{*}\right|/\log\left|U\right|)$.

###### Proof.

Root the element connectivity Gomory-Hu tree $T$ at $s$. For each vertex $v\in
U$, let $U_{v}$ be the set of terminals in the subtree rooted at $v$. For a
terminal $v\in U$, we find the edge $e(v)$ along the path from $s$ to $v$ with
minimum weight, and when not unique, the one with maximum depth. Let $r(v)$ be
the deeper endpoint of $e(v)$. By the definition of $U^{*}$, a terminal $v\in
U^{*}$ if and only if $w(e(v))\leq W$ and
$\left|U_{r(v)}\right|\leq\left|U\right|/2$.

We say that a vertex $v\in U^{*}$ is _active_ if $v\in R^{i(v)}$ where
$i(v)=\lfloor\log\left|U_{r(v)}\right|\rfloor$. In addition, if $U_{r(v)}\cap
R^{i(v)}=\\{v\\}$, then we say that $v$ _hits_ all of the vertices in
$U_{r(v)}$, including itself. For completeness, we define vertices in
$U\backslash U^{*}$ to be inactive; they do not hit other vertices. Now we
show that

  * (a)

each vertex that is hit is in $U_{\operatorname{sm}}$;

  * (b)

the total number of pairs $(u,v)$ for which $v\in U^{*}$ hits $u$ is
$\Omega(\left|U^{*}\right|)$ in expectation;

  * (c)

each vertex $u$ is hit by at most $O(\log\left|U\right|)$ vertices in $v\in
U^{*}$.

For $(a)$, suppose $u$ is hit by $v$. Then by definition, $U_{r(v)}\cap
R^{i(v)}=\\{v\\}$. The isolating cut for $v$ returned by Lemma 2.3 corresponds
to the edge joining $r(v)$ to its parent, so all vertices in $U_{r(v)}$ are on
$v$’s side of the cut, and appear in $U_{\operatorname{sm}}$, because $v\in
R_{\operatorname{sm}}^{i}$, since $\left|S_{v}^{i(v)}\cap
U\right|=\left|U_{r(v)}\right|\leq\left|U\right|/2$ and $w(e(v))\leq W$.

For $(b)$, the probability that $v\in R^{i(v)}$ and $v$ is the only such
vertex is $(1-2^{-i(v)})^{\left|U_{r(v)}\right|-1}2^{-i(v)}=\Theta(1/2^{i})$,
and when it happens, it hits $\left|U_{r(v)}\right|=\Omega(2^{i(v)})$
vertices, so the contribution in the expectation is $\Omega(1)$. Since each
$v\in U^{*}$ contributes $\Omega(1)$ in expectation, their sum is
$\Omega(\left|U^{*}\right|)$.

For $(c)$, we first show that for any different vertices $v,w\in U^{*}$ that
both hit $u$, $i(v)\neq i(w)$. Since $u\in U_{r(v)}$ and $u\in U_{r(w)}$,
without loss of generality we assume $r(v)\in U_{r(w)}$, so $U_{r(v)}\subseteq
U_{r(w)}$. From the definition of $R^{i}$, $R^{0}\subseteq
R^{1}\subseteq\cdots R^{\lfloor\log\left|U\right|\rfloor}$, so $R^{i(v)}\cap
R^{i(w)}=R^{\max(i(v),i(w))}$. Then,

$\emptyset=\\{v\\}\cap\\{w\\}=(R^{i(v)}\cap U_{r(v)})\cap(R^{i(w)}\cap
U_{r(w)})=R^{\max(i(v),i(w))}\cap U_{r(v)},$

because $R^{i(v)}\cap U_{r(v)}=\\{v\\}\neq\emptyset$, we conclude that
$\max(i(v),i(w))>i(v)$, so $i(v)<i(w)$. Then, since
$i(v)\in[1,\log\left|U\right|]$ has at most $O(\log\left|U\right|)$ kinds of
choices, $u$ is hit by at most $O(\log\left|U\right|)$ vertices.

Finally, the proof follows from

$\mathbb{E}[U_{\operatorname{sm}}]\geq\mathbb{E}[\left|\\{u:u\text{ is
hit}\\}\right|]\geq\frac{\mathbb{E}[\left|\\{(u,v):v\in U^{*},u\text{ is hit
by
}v\\}\right|]}{O(\log\left|U\right|)}\geq\Omega(\frac{\mathbb{E}[U^{*}]}{\log\left|U\right|}).$

The first inequality is because claim (a); the second inequality is because
claim (c); and the third inequality is because claim (b). ∎

###  5.2 Proof of Theorem 5.2 and Theorem 5.1

Now we are ready to give the proof for Theorem 5.2 and Theorem 5.1.

###### Proof of Theorem 5.2.

The recursion makes progress in one of two ways. In the
“non-$G_{\operatorname{lg}}$” branches $\\{G_{v}\\}$, each $G_{v}$ contains at
most half the number of terminals. Suppose we follow the
“$G_{\operatorname{lg}}$” branch $\Theta(\log^{3}n)$ times, yielding
$G^{\prime},U^{\prime},F^{\prime}$ and $P^{\prime}$. By Lemma 5.8, with
$W=(1+\epsilon)\lambda$,
${\mathbb{E}\/}(|P^{\prime}|)\leq(1-\Omega(1/\log^{2}n))^{\Theta(\log^{3}n)}|P|=n^{-\Omega(1)}$,
meaning $P^{\prime}=\emptyset$ is empty w.h.p. and the global minimum element
cut of $G^{\prime},U^{\prime}\cup F^{\prime}$ has increased to at least
$(1+\epsilon)\lambda$ and we can update $\lambda$ accordingly.

This implies the total depth of recursion is $O(\epsilon^{-1}\log^{4}n)$
w.h.p. The total size of all graphs on each layer of recursion is $O(m)$,
hence by Lemma 2.3, the total time is $O(\epsilon^{-1}\log^{4}n\cdot
T_{\operatorname{flow}}(m)\log
n)=\tilde{O}(\epsilon^{-1}T_{\operatorname{flow}}(m))$.

As for the correctness, by Lemma 5.3 the $G_{\operatorname{lg}}$-branch
preserves the exact value of $\kappa^{\prime}_{G,U\cup F}$, and all the
non-$G_{\operatorname{lg}}$ branches $\\{G_{v}\\}$ introduce a
$(1+\epsilon)$-factor approximation to the element connectivity. Since the
depth of recursion in the non-$G_{\operatorname{lg}}$ branches is at most
$\log|U|$, the tree returned is a $(1+\epsilon)^{\log|U|}=1+\epsilon_{0}$
approximate Gomory-Hu tree, for $\epsilon=\epsilon_{0}/\log|U|$. Expressed in
terms of $\epsilon_{0}$, the running time is still
$\tilde{O}(\epsilon_{0}^{-1}T_{\operatorname{flow}}(m))$. ∎

###### Proof of Theorem 5.1.

The proof follows from the proof of Theorem 5.2 by setting
$\epsilon=\Theta(\frac{1}{k})$, and we only address the difference of
$k$-Gomory-Hu tree.

To prove correctness, a new base case is added131313It can be inserted between
line 5 and 6 in Algorithm 1: if $\lambda>k$, stop recursion, construct $T$
with one node $t$, set $g(u)\leftarrow t$ for all $u\in G$ and $C$ an empty
function and return $(T,g,C)$. At the final output, construct $f$ as
$f(v)\leftarrow g(v)$ for all $v\in U$. Then $(T,f,C)$ works exactly as in
Definition 2.2.

To bound running time, since we are not concerned with cut-values exceeding
$k$, when calling Lemma 2.3 we can use any unit capacity flow algorithm, which
runs in $O(T_{\operatorname{uflow}}(m+k\left|U\right|))$ time, so the total
time bound is $\tilde{O}(kT_{\operatorname{uflow}}(m+k\left|U\right|))$. ∎

##  6 Conclusion

In this paper we proved that $\Omega(kn/\log n)$ space is necessary for
encoding vertex connectivity information up to $k$. This establishes the
optimality of several previous results. For example, Nagamochi-Ibaraki [NI92]
sparsifiers encode all vertex connectivities up to $k$, but their space cannot
be improved much, _even if the format of the representation is not constrained
to be a graph_. It also implies that even the _average_ length of the Izsak-
Nutov [IN12] labeling scheme cannot be improved much. We improved [IN12] to
have near-optimal query time $O(\log n)$, independent of $k$, and improved its
the construction time to nearly max-flow time.

Here we highlight a few open problems.

  * •

There is a trivial $\Omega(kn)$ space lower bound for data structures
answering $\mathsf{v}\text{-}\mathsf{cut}$ queries. Our data structure (and
Izsak-Nutov [IN12]) can be augmented to support fast
$\mathsf{v}\text{-}\mathsf{cut}$ queries with $O(k^{2}n\log n)$ space. Is this
necessary? Note that if it is, the lower bound cannot be purely information-
theoretic; it must hinge on the requirement that queries be answered
_efficiently_.141414There are two natural ways to answer
$\mathsf{v}\text{-}\mathsf{cut}$ queries “optimally,” either enumerate their
elements in $O(k)$ time, or return a pointer in $O(1)$ time to a pre-stored
list of elements. The latter model was recently advocated by Nutov [Nut21] and
seems to be easier to characterize from a lower bound perspective.

  * •

A special case of the vertex connectivity oracle problem is answering
$\mathsf{v}\text{-}\mathsf{conn}(u,v)$ queries when $k=\kappa(G)+1$. In other
words, decide whether $u,v$ are separated by a globally minimum cut. Globally
minimum vertex cuts have plenty of structure [PY21, CDBKT93], but it is still
not clear whether $\tilde{\Omega}(kn)$ bits are necessary to answer such
queries.

  * •

Can a $k$-Gomory-Hu tree for element connectivity be constructed in
$\tilde{O}(m+n\mathrm{poly}(k))$ time, perhaps by extending the methods of
[FNY+20, PY21]?

## References

  * [AGI+19] Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemyslaw Uznanski, and Daniel Wolleb-Graf.  Faster algorithms for all-pairs bounded min-cuts.  In Proceedings 46th International Colloquium on Automata, Languages, and Programming (ICALP), pages 7:1–7:15, 2019.
  * [AKT20] Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi.  Cut-equivalent trees are optimal for min-cut queries.  In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 105–118, 2020.
  * [AKT21] Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi.  APMF $<$ APSP? Gomory-Hu tree for unweighted graphs in almost-quadratic time.  Accepted to FOCS’21, 2021.  arXiv:2106.02981.
  * [Ben95a] A. A. Benczúr.  Counterexamples for directed and node capacitated cut-trees.  SIAM J. Comput., 24(3):505–510, 1995.
  * [Ben95b] A. A. Benczúr.  A representation of cuts within 6/5 times the edge connectivity with applications.  In Proceedings 36th IEEE Symposium on Foundations of Computer Science (FOCS), pages 92–102, 1995.
  * [BG08] A. A. Benczúr and M. X. Goemans.  Deformable polygon representation and near-mincuts.  In M. Grötschel and G. O. H. Katona, editors, Building Bridges: Between Mathematics and Computer Science, volume 19 of Bolyai Society Mathematical Studies, pages 103–135. Springer, 2008.
  * [Bol11] Béla Bollobás.  Random Graphs, Second Edition, volume 73 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, 2011.
  * [BT96] G. Di Battista and R. Tamassia.  On-line maintenance of triconnected components with SPQR-trees.  Algorithmica, 15:302–318, 1996.
  * [CDBKT93] Robert F Cohen, Giuseppe Di Battista, Arkady Kanevsky, and Roberto Tamassia.  Reinventing the wheel: an optimal data structure for connectivity queries (extended abstract).  In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC), pages 194–200, 1993.
  * [CH91] Chung-Kuan Cheng and T. C. Hu.  Ancestor tree for arbitrary multi-terminal cut functions.  Ann. Oper. Res., 33(3):199–213, 1991.
  * [Cha87] B. Chazelle.  Computing on a free tree via complexity-preserving mappings.  Algorithmica, 2(3):337–361, 1987.
  * [Che15] Chandra Chekuri.  Some open problems in element connectivity.  Unpublished Survey. Available at http://chekuri. cs. illinois. edu/papers/elem-connectivity-open-probs. pdf, 2015.
  * [CK12] Julia Chuzhoy and Sanjeev Khanna.  An ${O}(k^{3}\log n)$-approximation algorithm for vertex-connectivity survivable network design.  Theory Comput., 8(1):401–413, 2012.
  * [CLL13] Ho Yee Cheung, Lap Chi Lau, and Kai Man Leung.  Graph connectivities, network coding, and expander graphs.  SIAM J. Comput., 42(3):733–751, 2013.
  * [CRX15] Chandra Chekuri, Thapanapong Rukkanchanunt, and Chao Xu.  On element-connectivity preserving graph simplification.  In Proceedings 29th Annual European Symposium on Algorithms (ESA), pages 313–324, 2015.
  * [DKL76] E. A. Dinic, A. V. Karzanov, and M. V. Lomonosov.  On the structure of the system of minimum edge cuts in a graph.  Studies in Discrete Optimization, pages 290–306, 1976.  (in Russian).
  * [DLW09] Erik D. Demaine, Gad M. Landau, and Oren Weimann.  On cartesian trees and range minimum queries.  In Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP), pages 341–353, 2009.
  * [DN95] Y. Dinitz and Z. Nutov.  A $2$-level cactus model for the system of minimum and minimum$+1$ edge-cuts in a graph and its incremental maintenance.  In Proceedings 27th ACM Symposium on Theory of Computing (STOC), pages 509–518, 1995.
  * [DN99a] Y. Dinitz and Z. Nutov.  A $2$-level cactus tree model for the system of minimum and minimum$+1$ edge cuts of a graph and its incremental maintenance. Part I: the odd case.  Unpublished manuscript, 1999.
  * [DN99b] Y. Dinitz and Z. Nutov.  A $2$-level cactus tree model for the system of minimum and minimum$+1$ edge cuts of a graph and its incremental maintenance. Part II: the even case.  Unpublished manuscript, 1999.
  * [DV94] Yefim Dinitz and Alek Vainshtein.  The connectivity carcass of a vertex subset in a graph and its incremental maintenance.  In Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC), pages 716–725, 1994.
  * [DV95] Yefim Dinitz and Alek Vainshtein.  Locally orientable graphs, cell structures, and a new algorithm for the incremental maintenance of connectivity carcasses.  In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 302–311, 1995.
  * [DV00] Yefim Dinitz and Alek Vainshtein.  The general structure of edge-connectivity of a vertex subset in a graph and its incremental maintenance. odd case.  SIAM J. Comput., 30(3):753–808, 2000.
  * [FGI+16] Donatella Firmani, Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, and Federico Santaroni.  Strong articulation points and strong bridges in large scale graphs.  Algorithmica, 74(3):1123–1147, 2016.
  * [FK16] Alan Frieze and Michał Karoński.  Introduction to Random Graphs.  Cambridge University Press, 2016.
  * [FNY+20] Sebastian Forster, Danupon Nanongkai, Liu Yang, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai.  Computing and testing small connectivity in near-linear time and queries via fast local cut algorithms.  In Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2046–2065, 2020.
  * [GH61] R. E. Gomory and T. C. Hu.  Multi-terminal network flows.  Journal of the Society for Industrial and Applied Mathematics, 9, 1961.
  * [GILP16] Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, and Nikos Parotsidis.  2-edge connectivity in directed graphs.  ACM Trans. Algorithms, 13(1):9:1–9:24, 2016.
  * [GILP18] Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, and Nikos Parotsidis.  2-vertex connectivity in directed graphs.  Inf. Comput., 261:248–264, 2018.
  * [GMW20] Pawel Gawrychowski, Shay Mozes, and Oren Weimann.  Minimum cut in ${O}(m\log^{2}n)$ time.  In Proceedings 47th International Colloquium on Automata, Languages, and Programming (ICALP), volume 168 of LIPIcs, pages 57:1–57:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [GMW21] Pawel Gawrychowski, Shay Mozes, and Oren Weimann.  A note on a recent algorithm for minimum cut.  In Proceedings 4th SIAM Symposium on Simplicity in Algorithms (SOSA), pages 74–79, 2021.
  * [GN90] D. Gusfield and D. Naor.  Efficient algorithms for generalized cut trees.  In Proceedings First ACM-SIAM Symposium on Discrete Algorithms, pages 422–433, 1990.
  * [GN93] Dan Gusfield and Dalit Naor.  Extracting maximal information about sets of minimum cuts.  Algorithmica, 10(1):64–89, 1993.
  * [HKNS15] M. Henzinger, S. Krinninger, D. Nanongkai, and T. Saranurak.  Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture.  In Proceedings 47th Annual ACM Symposium on Theory of Computing (STOC), pages 21–30, 2015.
  * [HKP07] Ramesh Hariharan, Telikepalli Kavitha, and Debmalya Panigrahi.  Efficient algorithms for computing all low $s$-$t$ edge connectivities and related problems.  In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 127–136, 2007.
  * [HL07] Refael Hassin and Asaf Levin.  Flow trees for vertex-capacitated networks.  Discrete applied mathematics, 155(4):572–578, 2007.
  * [HL09] Tai-Hsin Hsu and Hsueh-I Lu.  An optimal labeling for node connectivity.  In Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC), pages 303–310. Springer, 2009.
  * [IN12] Rani Izsak and Zeev Nutov.  A note on labeling schemes for graph connectivity.  Inf. Process. Lett., 112(1–2):39–43, 2012.
  * [JMVW02] Kamal Jain, Ion I. Mandoiu, Vijay V. Vazirani, and David P. Williamson.  A primal-dual schema based approximation algorithm for the element connectivity problem.  J. Algorithms, 45(1):1–15, 2002.
  * [Kar00] D. R. Karger.  Minimum cuts in near-linear time.  J. ACM, 47(1):46–76, 2000.
  * [KKKP04] Michal Katz, Nir A Katz, Amos Korman, and David Peleg.  Labeling schemes for flow and connectivity.  SIAM J. Comput., 34(1):23–40, 2004.
  * [KLS20] Tarun Kathuria, Yang P. Liu, and Aaron Sidford.  Unit capacity maxflow in almost ${O}(m^{4/3})$ time.  In Proceedings 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 119–130, 2020.
  * [Kor10] A. Korman.  Labeling schemes for vertex connectivity.  ACM Trans. on Algorithms, 6(2), 2010.
  * [KP09] David R. Karger and Debmalya Panigrahi.  A near-linear time algorithm for constructing a cactus representation of minimum cuts.  In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 246–255, 2009.
  * [KPP16] T. Kopelowitz, S. Pettie, and E. Porat.  Higher lower bounds from the 3SUM conjecture.  In Proceedings 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1272–1287, 2016.
  * [KTBC91] A. Kanevsky, R. Tamassia, G. Di Battista, and J. Chen.  On-line maintenance of the four-connected components of a graph.  In Proceedings 32nd IEEE Symposium on Foundations of Computer Science (FOCS), pages 793–801, 1991.
  * [LNP+21] Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai.  Vertex connectivity in poly-logarithmic max-flows.  In Proceedings of the 53rd ACM Symposium on Theory of Computing (STOC), 2021.
  * [LP20] Jason Li and Debmalya Panigrahi.  Deterministic min-cut in poly-logarithmic max-flows.  In Proceedings 61st IEEE Annual Symposium on Foundations of Computer Science, (FOCS), pages 85–92, 2020.
  * [LP21] Jason Li and Debmalya Panigrahi.  Approximate Gomory–Hu tree is faster than $n–1$ max-flows.  In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC), pages 1738––1748, 2021.
  * [LPS21] Jason Li, Debmalya Panigrahi, and Thatchaphol Saranurak.  A nearly optimal all-pairs min-cuts algorithm in simple graphs.  Accepted to FOCS’21, 2021.  arXiv:2106.02233.
  * [Men27] Karl Menger.  Zur allgemeinen kurventheorie.  Fundamenta Mathematicae, 10:96–115, 1927.
  * [MN20] Sagnik Mukhopadhyay and Danupon Nanongkai.  Weighted min-cut: sequential, cut-query, and streaming algorithms.  In Proccedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC), pages 496–509, 2020.
  * [NI92] H. Nagamochi and T. Ibaraki.  A linear-time algorithm for finding a sparse $k$-connected spanning subgraph of a $k$-connected graph.  Algorithmica, 7(5&6):583–596, 1992.
  * [Nut21] Zeev Nutov.  Data structure for node connectivity queries.  arXiv preprint arXiv:2110.09102, 2021.
  * [Pet06] Seth Pettie.  An inverse-Ackermann type lower bound for online minimum spanning tree verification.  Combinatorica, 26(2):207–230, 2006.
  * [PQ80] J.-C. Picard and M. Queyranne.  On the structure of all minimum cuts in a network and applications.  In Combinatorial Optimization II, volume 13 of Mathematical Programming Studies, pages 8–16. Springer, 1980.
  * [PY21] Seth Pettie and Longhui Yin.  The structure of minimum vertex cuts.  In Proceedings 48th International Colloquium on Automata, Languages, and Programming (ICALP), volume 198 of LIPIcs, pages 105:1–105:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [Sar21] Thatchaphol Saranurak.  A simple deterministic algorithm for edge connectivity.  In Proceedings 4th SIAM Symposium on Simplicity in Algorithms, (SOSA), pages 80–85, 2021.
  * [Sch79] C.-P. Schnorr.  Bottlenecks and edge connectivity in unsymmetrical networks.  SIAM J. Comput., 8(2):265–274, 1979.
  * [Sch03] A. Schrijver.  Combinatorial Optimization - Polyhedra and Efficiency.  Springer, 2003.
  * [vdBLL+21] Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang.  Minimum cost flows, mdps, and $\ell_{1}$-regression in nearly linear time for dense instances, 2021.