# Vertex Sparsifiers for Hyperedge Connectivity

Han Jiang  Shang-En Haung  Thatchaphol Saranurak University of Michigan Tian
Zhang

###### Abstract

Recently, Chalermsook et al. [SODA’21] introduces a notion of _vertex
sparsifiers for $c$-edge connectivity, _which has found applications in
parameterized algorithms for network design and also led to exciting dynamic
algorithms for $c$-edge st-connectivity [Jin and Sun FOCS’21].

We study a natural extension called _vertex sparsifiers for $c$-hyperedge
connectivity_ and construct a sparsifier whose size matches the state-of-the-
art for normal graphs. More specifically, we show that, given a hypergraph
$G=(V,E)$ with $n$ vertices and $m$ hyperedges with $k$ terminal vertices and
a parameter $c$, there exists a hypergraph $H$ containing only $O(kc^{3})$
hyperedges that preserves all minimum cuts (up to value $c$) between all
subset of terminals. This matches the best bound of $O(kc^{3})$ edges for
normal graphs by [Liu’20]. Moreover, $H$ can be constructed in almost-linear
$O(p^{1+o(1)}+n(rc\log n)^{O(rc)}\log m)$ time where $r=\max_{e\in E}|e|$ is
the rank of $G$ and $p=\sum_{e\in E}|e|$ is the total size of $G$, or in
$\mathrm{poly}(m,n)$ time if we slightly relax the size to
$O(kc^{3}\log^{1.5}(kc))$ hyperedges.

##  1 Introduction

Graph sparsification has played a central role in graph algorithm research in
the last two decades. Prominent examples include spanners [ADD+93], cut
sparsifiers [BK15], and spectral sparsifiers [ST11]. Recently, there has been
significant effort in generalizing the graph sparsification results to
hypergraphs. For cut sparsifiers, Kogan and Krauthgamer [KK15] generalized the
Benczúr and Karger’s cut sparsifiers [BK15] by showing that, given any
hypergraph $G=(V,E)$ with $n$ vertices, there is a $(1+\epsilon)$-approximate
cut sparsifier $H$ containing $\tilde{O}(nr/\epsilon^{2})$ hyperedges where
$r=\max_{e\in E}|e|$ denotes the _rank_ of the hypergraph. After some follow-
up work [CX18, BST19], Chen, Khanna, and Nagda [CKN20] finally improved the
sparsifier size to $\tilde{O}(n/\epsilon^{2})$ hyperedges, matching the
optimal bound for normal graphs. Another beautiful line of work generalizes
Speilman and Teng’s spectral sparsifiers [ST11] to hypergraphs [BST19, SY19,
KKTY21] and very recently results in spectral sparsifiers with
$\tilde{O}(n/\mathrm{poly}(\epsilon))$ hyperedges [KKTY22]. We also mention
that the classical sparse connectivity certificates by Nagamochi and Ibaraki
[NI92] were also generalized to hypergraphs by Chekuri and Xu [CX18].

This paper studies a graph sparsification problem called _vertex sparsifiers
for $c$-edge connectivity_ recently introduced by Chalermsook et al. [CDK+21].
It is closely related to the vertex sparsifiers for edge cuts [KR13, KR14] and
vertex cuts [KW20]. In this problem, we are given an unweighted undirected
graph $G=(V,E)$ and a set of terminals $\mathcal{T}\subseteq V$. For any
disjoint subsets $A,B\subseteq\mathcal{T}$, let $\mathrm{mincut}_{G}(A,B)$
denote the size of a minimum (edge-)cut that disconnects $A$ and $B$. Now, a
graph $H=(V_{H},E_{H})$ with $\mathcal{T}\subseteq V_{H}$ is a
_$(\mathcal{T},c)$ -sparsifier_ of $G$ if for any disjoint subsets
$A,B\subseteq\mathcal{T}$,
$\min\\{c,\mathrm{mincut}_{G}(A,B)\\}=\min\\{c,\mathrm{mincut}_{H}(A,B)\\}$.
Basically, $H$ preserves all minimum cut structures between the terminals
$\mathcal{T}$ up to the value $c$. This notion of graph sparsifiers has found
interesting applications in offline dynamic algorithms and network design
problems [CDK+21]. Moreover, the very recent breakthrough on dynamic $c$-edge
st-connectivity by Jin and Sun [JS22] is also crucially based on dynamic
algorithms for maintaining $(\mathcal{T},c)$-sparsifiers.

In the original paper by [CDK+21], they showed that, for any graph $G=(V,E)$
and terminal set $\mathcal{T}$ of size $k$, there exists a
$(\mathcal{T},c)$-sparsifier containing $O(kc^{4})$ edges (which can be
constructed in $O(m(c\log n)^{O(c)})$ time) and also showed fast algorithms
for constructing $(\mathcal{T},c)$-sparsifiers of size $k\cdot O(c)^{2c}$ in
$mc^{O(c)}\log^{O(1)}{n}$ time. Then, Liu [Liu20] improved the size bound to
$O(kc^{3})$ together with polynomial-time algorithms (no exponential
dependency on $c$) for constructing $(\mathcal{T},c)$-sparsifiers with
$O(kc^{3}\log^{1.5}n)$ edges.

A natural question is then whether these results can be extended to
hypergraphs. The notion of $(\mathcal{T},c)$-sparsifiers itself can be
naturally extended to hypergraphs by allowing $G$ and $H$ to be hypergraphs
and letting $\mathrm{mincut}_{G}(A,B)$ denote the value of the minimum
hyperedge-cut instead. However, it is conceivable that there might not exist a
$(\mathcal{T},c)$-sparsifier with $\mathrm{poly}(k,c)$. This bound might
require bad dependency on the rank $r$, for example.

In this paper, we show that the state-of-the-art for normal graphs indeed
extend to hypergraphs and we can even slightly improve the bounds:

######  Theorem 1.1.

Let $G=(V,E)$ be a hypergraph with $n$ vertices, $m$ hyperedges, rank $r$ and
total size $p$. Let $\mathcal{T}\subseteq V$ be the set of $k$ terminals.
There are algorithms for computing the following:

  1. 1.

a $(\mathcal{T},c)$-sparsifier $H$ of $G$ with $O(kc^{3})$ hyperedges in
$O(p^{1+o(1)}+n(rc\log n)^{O(rc)}\log m)$ time, which is almost-linear in the
input size when both $r$ and $c=O(1)$, and

  2. 2.

a $(\mathcal{T},c)$-sparsifier $H$ of $G$ with $O(kc^{3}\log^{1.5}(kc))$
hyperedges in $\mathrm{poly}(m,n)$ time.

The first result matches the best known bound of $O(kc^{3})$ edges for normal
graphs [Liu20]. When $r=O(1)$, the first time bound slightly improves the
$O(m(c\log n)^{O(c)})$ bound of [CDK+21] for normal graphs. The second result
removes the exponential dependency on $r$ and $c$ after relaxing the size by a
$\log^{1.5}(kc)$ factor. The number of hyperedges in our sparsifier is
completely independent from $n$, while the polynomial time algorithm by Liu
[Liu20] gives the size of $O(kc^{3}\log^{1.5}n)$. So this implies the first
polynomial time construction of sparsifiers of size near-linear in $k$ and
independent of $n$, even for normal graphs.

###### Open Problems.

Can we construct vertex sparsifiers for $c$-hyperedge connectivity of
$k\cdot\mathrm{poly}(c)$ size in near-linear time even when the rank is
unbounded? This is a prerequisite to near-linear time algorithms for computing
vertex sparsifiers for $c$-_vertex connectivity_ of $k\cdot\mathrm{poly}(c)$
size. Such a result might lead to dynamic $c$-vertex st-connectivity algorithm
similar to the previous development where a near-linear time construction of
vertex sparsifiers for $c$-edge connectivity leads to a dynamic algorithm for
$c$-edge st-connectivity [JS22]. As dynamic $c$-vertex st-connectivity is one
of the major open problems in dynamic graph algorithms (known solutions only
works for very small $c\leq 3$ [EGIN97, HDLT01, PSS19]), we view this work as
a stepping stone towards this goal.

###  1.1 Technical Challenges

There are two main obstacles that prevent us extending the results of [Liu20,
CDK+21] directly from normal graphs to hypergraphs. First, if we follow the
divide and conquer framework of Chalermsook et al. [CDK+21] in a
straightforward way, then we would end up with a much larger
$(\mathcal{T},c)$-sparsifier with $O(|\mathcal{T}|(rc)^{3})$ hyperedges. This
is because, in [CDK+21], all vertices incident to the boundary edges are
declared as new terminal vertices in the recursion. However in our case, each
hyperedge may contain $r$ vertices and this yields the dependency of $r$. To
handle this issue, we instead introduce only two _anchor vertices_ for each
boundary hyperedge. Our divide and conquer framework requires slightly more
careful analysis, but this naturally gives a $(\mathcal{T},c)$-sparsifier with
$O(|\mathcal{T}|c^{3})$ hyperedges.

The second obstacle is the near-linear time algorithm, Part (1) of Theorem
1.1. Chalermsook et al. [CDK+21] introduced _auxiliary graphs_ and apply the
$\phi$-Sparsify procedure on it to identify all _essential_ hyperedges, which
roughly are hyperedges that will be kept in the sparsifier. However, there is
a subtle small gap in [CDK+21]: their $\phi$-Sparsify procedure could
erroneously identify non-essential hyperedges as essential hyperedges. This is
explained in more detail in Figure 2. This bug results in a much larger
$(\mathcal{T},c)$-sparsifier. In this paper we fix the bug by (1) introducing
a notion of _useful_ partitions of the terminal set and (2) providing an
efficient algorithm that discards all non-useful partitions from the auxiliary
graph. Then, we show that, after our modification, this approach indeed gives
a small $(\mathcal{T},c)$-sparsifier as desired.

###  1.2 Organization

In Section 2 we review some basic definitions of hypergraphs. In Section 3 we
define contraction based $(\mathcal{T},c)$-sparsifiers and introduce the
divide and conquer framework. In Section 4 we show the existence of a
$(\mathcal{T},c)$-sparsifier with $O(|\mathcal{T}|c^{3})$ hyperedges. In
Section 5 we give a near-linear-time algorithm that computes a
$(\mathcal{T},c)$-sparsifier with $O(|\mathcal{T}|c^{3})$ hyperedges, proving
Part (1) of Theorem 1.1. At the end we prove the Part (2) of Theorem 1.1 in
Appendix D.

##  2 Preliminary

Let $G=(V,E)$ be a hypergraph. $V$ is the set of vertices and $E$ is a
multiset of hyperedges with each hyperedge $e$ being a subset of $V$. The
_rank_ $r\coloneqq\max_{e\in E}|e|$ of a hypergraph is the size of the largest
hyperedge, and the _total size_ $p\coloneqq\sum_{e\in E}|e|$ is the sum of all
edge sizes.

For any two disjoint sets of vertices $A,B\subseteq V$, let $E_{G}(A,B)$
denote the set of hyperedges with at least one endpoint in $A$ and at least
one endpoint in $B$. For any set of vertices $X\subseteq V$, we denote the
_boundary_ of $X$ of the graph $G$ by $\partial_{G}X\coloneqq
E_{G}(X,V\setminus X)$. If the context is clear then we will omit the graph
$G$ and write $\partial X$ instead.

###### Restrictions and Induced Sub-Hypergraphs.

Let $\mathcal{T}\subseteq V\cup E$ be a mixed multiset of vertices and
hyperedges, for any set of vertices $X\subseteq V$, we define the
_restriction_ of the multiset $\mathcal{T}$ on $X$ to be
$\mathcal{T}|_{X}=(\mathcal{T}\cap X)\cup\\{e\cap X\ |\ e\in(\mathcal{T}\cap
E)\text{ and }e\cap X\neq\emptyset\\}$. The _induced sub-hypergraph_ $G[X]$ is
then defined over the vertex set $X$ with the restriction of all hyperedges
$E|_{X}$, that is, $G[X]\coloneqq(X,E|_{X})$.

###### Incident Edges and Vertices.

For any set of vertices $X\subseteq V$, define $E(X)$ to be the set of all
hyperedges that incident to at least one vertex in $X$. For any set of
hyperedges $Y\subseteq E$, define $V(Y)=\bigcup_{y\in Y}y$ to be the set of
vertices incident to hyperedges in $Y$. Similarly, for any mixed set of
vertices and hyperedges $\mathcal{T}\subseteq V\cup E$ we define
$V(\mathcal{T})=(\mathcal{T}\cap V)\cup V(\mathcal{T}\cap E)$ to be the set of
all vertices that are in the set or incident to any hyperedge in the set.

##  3 Structural Properties on Hypergraphs

In this section, we explore more structural properties on hypergraphs. In
particular, we introduce _anchored separated hyperedges_ , and describe useful
properties in a divide and conquer framework that leads to a construction of
$(\mathcal{T},c)$-sparsifiers.

###  3.1 Cuts in Hypergraphs

Let $u$ and $v$ be two elements in $V$. We say that $u$ and $v$ are
_connected_ in a hypergraph $G$, if there is a path connecting $u$ and $v$.
Let $A,B\subseteq V$ be two disjoint sets of vertices. $A$ and $B$ are
_disconnected_ if for any $a\in A$ and $b\in B$, $a$ and $b$ are not
connected.

######  Definition 3.1 (Cuts and Minimum Cuts).

A _cut_ is a bipartition $(X,V\setminus X)$ of vertices. The _value_ of the
cut is $|\partial X|=|E_{G}(X,V\setminus X)|$. For any disjoint subsets
$A,B\subseteq V$, if $A\subseteq X$ and $B\subseteq(V\setminus X)$ then we say
that $(X,V\setminus X)$ is an $(A,B)$-cut. A _minimum $(A,B)$-cut_ or _$(A,B)$
-mincut_ is any $(A,B)$-cut with minimum value. Its value is denoted as
$\mathrm{mincut}_{G}(A,B)$. Given a parameter $c$, a _$c$ -thresholded
$(A,B)$-mincut cut value_ is defined as

$\mathrm{mincut}^{c}_{G}(A,B)\coloneqq\min(\mathrm{mincut}_{G}(A,B),c).$

We usually write a _$c$ -thresholded $(A,B)$-mincut_ to emphasize that the
$(A,B)$-mincut has value at most $c$. We say that a hyperedge $e$ is
_involved_ in a cut $(X,V\setminus X)$ if $e\in E(X,V\setminus X)$.

###  3.2 $(\mathcal{T},c)$-Equivalency and $(\mathcal{T},c)$-Sparsifiers

Our vertex sparsifier algorithms are based on identifying a set of hyperedges
and contract them. Given a hypergraph $G=(V,E)$ and a hyperedge $e\in E$, the
_contracted hypergraph_ $G/e$ is defined by identifying all incident vertices
$V(e)$ as one vertex, and then remove $e$ itself from the graph. For any set
of terminals $T\subseteq V$, the effect of contracting an hyperedge $e$ is
denoted as $T/e$. Similarly, for any set $\hat{E}\subseteq E$, we denote
$G/\hat{E}$ the hypergraph obtained from $G$ by contracting all hyperedges in
$\hat{E}$ (notice that all hyperedges in $\hat{E}$ are removed after the
contraction.)

######  Definition 3.2 ($(\mathcal{T},c)$-Sparsifiers).

Let $G=(V_{G},E_{G})$ and $H=(V_{H},E_{H})$ be two hypergraphs. Let
$\mathcal{T}\subseteq V_{G}$ be the set of terminals. We say $H$ is a
_contraction based $(\mathcal{T},c)$-sparsifier_ of $G$, if there exists a
surjective (onto) projection $\pi:V_{G}\to V_{H}$, such that for any $e\in
E_{H}$ there is an edge $f\in E_{G}$ such that $\pi(f)=\cup_{v\in
f}\\{\pi(v)\\}=e$, and for any two subsets $T_{1},T_{2}\subseteq\mathcal{T}$,

$\mathrm{mincut}_{G}^{c}(T_{1},T_{2})=\mathrm{mincut}_{H}^{c}(\pi(T_{1}),\pi(T_{2})).$

Furthermore, if the terminals are not affected by the projection, i.e.,
$\pi(\mathcal{T})=\mathcal{T}$, then we say that $G$ and $H$ are
_$(\mathcal{T},c)$ -equivalent_.

###### Remark.

A more general $(\mathcal{T},c)$-sparsifier would allow an arbitrary mapping
$\pi$ on both vertices and edges. However, we note that all
$(\mathcal{T},c)$-sparsifiers constructed in this paper are always contraction
based. Therefore, for the ease of the presentation we will omit the term
“contraction based” when we mention $(\mathcal{T},c)$-sparsifiers.

For the ease of the reading, we define the following set operations that allow
us to add/remove hyperedges of $G$ into a sparsifier $H$.

######  Definition 3.3.

Let $G=(V,E)$ be a hypergraph. For any multiset $X$ of hyperedges over the
vertices $V$, and any contraction based $(\mathcal{T},c)$-sparsifier $H$ with
the projection $\pi$, define

  * •

_(Adding contracted hyperedges)_ $H\cup X\coloneqq H\cup\pi(X)$, and

  * •

_(Removing contracted hyperedges)_ $H-X\coloneqq H-\pi(X)$.

###  3.3 $(\mathcal{T},c)$-Sparsifiers from a Divide and Conquer Framework

Another important concept to our contraction based
$(\mathcal{T},c)$-sparsifier construction is that we apply a divide and
conquer framework to $G$. Let $G=(V,E)$ be a hypergraph and let
$(V_{1},V_{2})$ be a bipartition of vertices. We note that our divide and
conquer framework is slightly different than just recurse on the induced sub-
hypergraphs $G[V_{1}]$ and $G[V_{2}]$. In particular, for each _separated
hyperedge_ $e$ we add two new _anchor vertices_ to $e$, ended up slightly
increasing the size of the vertex set in the next-level recursion.

###### Separated Hyperedges and Anchor Vertices.

Let $e\in E(V_{1},V_{2})$ be a hyperedge across the bipartition. The
_separated hyperedges_ of $e$ with respect to this bipartition $(V_{1},V_{2})$
is the set composed of hyperedges of $e$ restricted on both $V_{1}$ and
$V_{2}$. The _anchored separated hyperedges_ are separated hyperedges with
additional _anchor vertices_ : let $e_{1}=e|_{V_{1}}$ and $e_{2}=e|_{V_{2}}$
be the separated hyperedges of $e$, then we introduce four new anchored
vertices
$\mathdutchcal{v}_{e,1},\mathdutchcal{v}_{e,2},\mathdutchcal{v}_{e,3}$, and
$\mathdutchcal{v}_{e,4}$ and define
$\hat{e}_{1}:=e_{1}\cup\\{\mathdutchcal{v}_{e,1},\mathdutchcal{v}_{e,2}\\}$
and
$\hat{e}_{2}:=e_{2}\cup\\{\mathdutchcal{v}_{e,3},\mathdutchcal{v}_{e,4}\\}$.
Let $S=E(V_{1},V_{2})$ be the set of crossing hyperedges, in this paper the
set of anchored separated hyperedges respect to bipartition $(V_{1},V_{2})$
are denoted by $\mathit{Sep}(S,V_{1},V_{2}):=\\{\hat{e}_{1},\hat{e}_{2}\ |\
e\in S\\}$.

Let $A_{1}=\\{\mathdutchcal{v}_{e,1},\mathdutchcal{v}_{e,2}\ |\ e\in
E(V_{1},V_{2})\\}$ and let
$A_{2}=\\{\mathdutchcal{v}_{e,3},\mathdutchcal{v}_{e,4}\ |\ e\in
E(V_{1},V_{2})\\}$ be the set of newly introduced anchor vertices. These
anchor vertices will be added to the terminal set in order to correctly
preserve the mincut values. That is, the terminal sets defined for the
subproblems are $\mathcal{T}_{1}:=\mathcal{T}|_{V_{1}}\cup A_{1}$ and
$\mathcal{T}_{2}:=\mathcal{T}|_{V_{2}}\cup A_{2}$. Now, we define the anchored
induced sub-hypergraphs, which are useful when applying the divide and conquer
framework.

######  Definition 3.4 (Anchored Induced Sub-Hypergraphs).

Let $G=(V,E)$ be a hypergraph and $V_{1}\subseteq V$ be a subset of vertices.
Define $V_{2}=V\setminus V_{1}$,
$G^{\mathsf{sep}}=G\cup\mathit{Sep}(E(V_{1},V_{2}),V_{1},V_{2})-E(V_{1},V_{2})$,
and the set of anchored vertices to be $A_{1}\cup A_{2}$. Then, the _anchored
induced sub-hyperegraph_ for $V_{1}$ is defined as
$\hat{G}[V_{1}]:=G^{\mathsf{sep}}|_{V_{1}\cup A_{1}}$.

##### The Divide and Conquer Framework.

The most generic divide and conquer method works as the follows. First, a
bipartition $(V_{1},V_{2})$ are determined. Then, the algorithm performs
recursion on the anchored induced sub-hypergraphs $\hat{G}[V_{1}]$ and
$\hat{G}[V_{2}]$ with terminal sets $\mathcal{T}_{1}$ and $\mathcal{T}_{2}$
respectively. After obtaining the $(\mathcal{T}_{1},c)$-sparsifier and
$(\mathcal{T}_{2},c)$-sparsifier from the subproblems, the algorithm combines
them by replacing the anchored separated hyperedges with the original
hyperedges.

Input: Hypergraph $G$, terminal set $\mathcal{T}$, bipartition $(V_{1},V_{2})$
of vertices, parameter $c$.

Output: A $(\mathcal{T},c)$-sparsifier $H$ for $G$.

1 (Divide) Construct subproblems $(\hat{G}[V_{1}],\mathcal{T}_{1})$ and
$(\hat{G}[V_{2}],\mathcal{T}_{2})$.

2 (Conquer) For $i\in\\{1,2\\}$, obtain $H_{i}$, a
$(\mathcal{T}_{i},c)$-sparsifier of $\hat{G}[V_{i}]$.

3 (Combine) Return $H:=H_{1}\cup H_{2}\cup
E(V_{1},V_{2})-\mathit{Sep}(E(V_{1},V_{2}),V_{1},V_{2})$.

Algorithm 1 A Divide and Conquer Framework

We summarize the divide and conquer framework in Algorithm 1. The following
lemma states the correctness of the framework.

######  Lemma 3.5.

$H$ returned from Algorithm 1 is a $(\mathcal{T},c)$-sparsifier.

###### Proof.

Let $\pi_{1}:V_{1}\cup A_{1}\to V_{H_{1}}$ and $\pi_{2}:V_{2}\cup A_{2}\to
V_{H_{2}}$ be the projection maps on $H_{1}$ and $H_{2}$ respectively. Since
$V_{1}\cup A_{1}$ and $V_{2}\cup A_{2}$ are disjoint, it is natural to define
$\pi:V\to V_{H}$ by simply combining both maps where $\pi(v)=\pi_{1}(v)$ if
$v\in V_{1}$, and $\pi(v)=\pi_{2}(v)$ if $v\in V_{2}$.

Now, it suffices to show that for any two disjoint subsets
$A,B\subseteq\mathcal{T}$, we have
$\mathrm{mincut}_{G}^{c}(A,B)=\mathrm{mincut}_{H}^{c}(\pi(A),\pi(B))$.

Part 1. We first show that
$\mathrm{mincut}_{G}^{c}(A,B)\geq\mathrm{mincut}_{H}^{c}(\pi(A),\pi(B))$. Let
$(X,V\setminus X)$ be a minimum $(A,B)$-cut on $G$ with size $|\partial X|\leq
c$. Intuitively, we will construct the cuts in the subproblems
$\hat{G}[V_{1}]$ and $\hat{G}[V_{2}]$ using $(X,V\setminus X)$. Then we will
argue that the preserved mincuts in $\hat{G}[V_{1}]$ and $\hat{G}[V_{2}]$ can
be merged back, proving that there is a $(\pi(A),\pi(B))$-mincut in $H$ with
size no larger than $|\partial X|$.

Let $S=E_{G}(V_{1},V_{2})$ be the set of hyperedges across the bipartition in
the divide and conquer framework, and let $\hat{V}=V\cup A_{1}\cup A_{2}$ be
the vertex set in $G^{\mathsf{sep}}$. We define the set of vertices
$X^{\mathsf{sep}}$ that contains $X$ and all newly created anchor vertices
that belongs to the $X$ side: for any $e\in S$, we add
$\\{\mathdutchcal{v}_{e,1},\mathdutchcal{v}_{e,2},\mathdutchcal{v}_{e,3},\mathdutchcal{v}_{e,4}\\}$
to $X^{\mathsf{sep}}$ if $e\subseteq X$ (the hyperedge is fully in the $X$
side). We add $\\{\mathdutchcal{v}_{e,1},\mathdutchcal{v}_{e,3}\\}$ to
$X^{\mathsf{sep}}$ if $e\in S$. We add nothing if $e\subseteq V\setminus X$.

Now, we have $\partial X^{\mathsf{sep}}=(\partial X)\cup\mathit{Sep}((\partial
X)\cap S,V_{1},V_{2})-(\partial X)\cap S$. Moreover,
$(X^{\mathsf{sep}},\hat{V}\setminus X^{\mathsf{sep}})$ is an
$(A^{\mathsf{ext}},B^{\mathsf{ext}})$-cut in $G^{\mathsf{sep}}$ of size
$|\partial X|+|(\partial X)\cap S|$, where

$\begin{cases}A^{\mathsf{ext}}:=A\cup\\{\mathdutchcal{v}_{e,1},\mathdutchcal{v}_{e,3}\
|\ e\in((\partial X)\cap S)\\},\text{ and }\\\
B^{\mathsf{ext}}:=B\cup\\{\mathdutchcal{v}_{e,2},\mathdutchcal{v}_{e,4}\ |\
e\in((\partial X)\cap S)\\}.\end{cases}$

Intuitively, by carefully extend the pair $(A,B)$ to a larger pair
$(A^{\mathsf{ext}},B^{\mathsf{ext}})$ we ensure that _all_ separated
hyperedges $\mathit{Sep}((\partial X)\cap S,V_{1},V_{2})$ appear in every
$(A^{\mathsf{ext}},B^{\mathsf{ext}})$-mincut on $G^{\mathsf{sep}}$. See Figure
1.

Figure 1: An illustration to the proof of Lemma 3.5. The gray circles
represent hyperedges that cross the bipartition $(V_{1},V_{2})$ in the divide
and conquer framework. When these hyperedges are separated, new anchor
vertices are introduced and added to the terminal sets. The newly created
terminal vertices are forced to join different sides of the cut, if and only
if the separated hyperedge crosses the $(A,B)$-mincut $(X,V\setminus X)$.

Suppose $H_{1}$ is a $(\mathcal{T}_{1},c)$-sparsifier of $\hat{G}[V_{1}]$ and
$H_{2}$ is a $(\mathcal{T}_{2},c)$-sparsifier of $\hat{G}[V_{2}]$ obtained
from the conquer step (Algorithm 1). Let $(Y_{1},\pi(V_{1}\cup A_{1})\setminus
Y_{1})$ and $(Y_{2},\pi(V_{2}\cup A_{2})\setminus Y_{2})$ be a
$(\pi(A^{\mathsf{ext}}|_{V_{1}\cup A_{1}}),\pi(B^{\mathsf{ext}}|_{V_{1}\cup
A_{1}}))$-mincut on $H_{1}$ and a $(\pi(A^{\mathsf{ext}}|_{V_{2}\cup
A_{2}}),\pi(B^{\mathsf{ext}}|_{V_{2}\cup A_{2}}))$-mincut on $H_{2}$
respectively. Notice that every hyperedge in $\mathit{Sep}((\partial X)\cap
S,V_{1},V_{2})$ are in $\partial(Y_{1}\cup Y_{2})$. Let $Y_{0}:=Y_{1}\cup
Y_{2}$ and after removing all anchor vertices we get $Y=Y_{0}\cap V$. Now
$(Y,\pi(V)\setminus Y)$ is a $(\pi(A),\pi(B))$-cut. Since for each hyperedge
$e\in(\partial_{G}X)\cap S$, $e$ is separated into two hyperedges and both of
them are in $\partial_{H_{1}\cup H_{2}}Y_{0}$, we have

$|\partial_{H}Y|\leq|\partial_{H_{1}\cup H_{2}}Y_{0}|-|(\partial_{G}X)\cap
S|.$ (1)

Notice that the inequality in Equation 1 comes from the fact that
$\partial_{H_{1}\cup H_{2}}Y_{0}$ may or may not contain more separated
hyperedges from $\mathit{Sep}(S\setminus\partial X,V_{1},V_{2})$.

Finally we obtain

$\displaystyle\mathrm{mincut}_{H}^{c}(\pi(A),\pi(B))$
$\displaystyle\leq|\partial_{H}Y|$ ($Y$ is some $(\pi(A),\pi(B))$-cut on $H$)
$\displaystyle\leq|\partial_{H_{1}\cup H_{2}}Y_{0}|-|(\partial X)\cap S|$ (by
Equation 1)
$\displaystyle=|\partial_{H_{1}}Y_{1}|+|\partial_{H_{2}}Y_{2}|-|(\partial
X)\cap S|$ ($Y_{0}$ is the disjoint union $Y_{1}\cup Y_{2}$)
$\displaystyle\leq|\partial_{G^{\mathsf{sep}}}X^{\mathsf{sep}}|-|(\partial
X)\cap S|$ ($X^{\mathsf{sep}}$ is some
$(A^{\mathsf{ext}},B^{\mathsf{ext}})$-cut) $\displaystyle=|\partial X|$
(exactly $|(\partial X)\cap S|$ hyperedges were separated)
$\displaystyle=\mathrm{mincut}_{G}^{c}(A,B)$ ($X$ is an $(A,B)$-mincut)

as desired.

Part 2. The proof of
$\mathrm{mincut}_{H}^{c}(\pi(A),\pi(B))\geq\mathrm{mincut}_{G}^{c}(A,B)$ is
very similar to Part 1, so we defer the proof (for completeness) in Section
A.1. ∎

###  3.4 $(5c,c)$-Edge-Unbreakable Terminals

Let $G=(V,E)$ be a hypergraph and let $\mathcal{T}\subseteq V$ be the set of
terminals. By adopting the notations from [LSS20], we say that a terminal set
$\mathcal{T}$ is _$(5c,c)$ -edge-unbreakable_ on $G$ if for any bipartition
$(V_{1},V_{2})$ of $V$ with no more than $c$ crossing edges
$|E_{G}(V_{1},V_{2})|\leq c$, either $|\mathcal{T}|_{V_{1}}|<5c$ or
$|\mathcal{T}|_{V_{2}}|<5c$. That is, if there is a cut of size at most $c$,
then at least one of the sides has less than $5c$ induced terminals.

Liu [Liu20] obtained an $(\mathcal{T},c)$-sparsifier of size
$O(|\mathcal{T}|c^{2})$ with a $(5c,c)$-edge-unbreakable terminal set
$\mathcal{T}$ where each terminal vertex $v\in\mathcal{T}$ has degree $1$. It
turns out that Liu’s techniques naturally extend to hypergraphs. We prove the
following in Section A.2.

######  Lemma 3.6.

Let $G=(V,E)$ be a hypergraph and let $\mathcal{T}\subseteq V$ be a set of
degree-1 terminals. If $\mathcal{T}$ is $(5c,c)$-edge-unbreakable on $G$, then
there exists a subset $E^{\prime}\subseteq E$ with $O(|\mathcal{T}|c^{2})$
hyperedges, such that $G/(E-E^{\prime})$ is a $(\mathcal{T},c)$-sparsifier of
$G$.

##  4 Existence of $(\mathcal{T},c)$-Sparsifiers with $O(kc^{3})$ Hyperedges

With all the tools equipped in the previous section, we are able to prove the
existence of a $(\mathcal{T},c)$-sparsifier with $O(|\mathcal{T}|c^{3})$
hyperedges.

######  Theorem 4.1.

Let $G=(V,E)$ be a hypergraph and $\mathcal{T}\subseteq V$ be the set of
terminals. Then there is a subset $E^{\prime}\subseteq E$ such that
$|E^{\prime}|=O(|\mathcal{T}|c^{3})$ and the contracted hypergraph
$G/(E-E^{\prime})$ is $(\mathcal{T},c)$-equivalent to $G$.

To prove Theorem 4.1, it suffices to prove the following Lemma 4.2 where every
terminal vertex has degree 1:

######  Lemma 4.2.

Let $G=(V,E)$ be a hypergraph and $\mathcal{T}\subseteq V$ be the set of
degree 1 terminals. Then there is a subset $E^{\prime}\subseteq E$ such that
$|E^{\prime}|=O(|\mathcal{T}|c^{2})$ and the contracted hypergraph
$G/(E-E^{\prime})$ is $(\mathcal{T},c)$-equivalent to $G$.

###### Proof of Theorem 4.1.

Without loss of generality, we may assume that each vertex in $\mathcal{T}$
has degree at most $c$, by duplicating each terminal vertex and add $c$
parallel edges between the duplicated vertex and the original vertex. Let
$\mathcal{T}$ be the terminal set of an input instance. Now, assuming each
terminal has degree at most $c$, we can further duplicate each of these
terminals $c$ times so we have a set $\mathcal{T}^{\prime}$ of at most
$|\mathcal{T}|c$ degree-1 terminal vertices. By Lemma 4.2, there exists a
subset $E^{\prime}\subseteq E$ such that
$|E^{\prime}|=O(|\mathcal{T}^{\prime}|c^{2})=O(|\mathcal{T}|c^{3})$ and the
contracted hypergraph $G/(E-E^{\prime})$ is $(\mathcal{T},c)$-equivalent to
$G$. ∎

To prove Lemma 4.2, we first present an algorithm SparsifySlow (See Algorithm
2). The algorithm recursively apply divide and conquer framework until the
terminal set is $(5c,c)$-edge-unbreakable as the base case. After applying
Lemma 3.6 on each base case, the algorithm combines the sparsifiers from the
subproblems using Lemma 3.5.

Input: An undirected unweighted multi-hypergraph $G$, a set of degree-1 vertex
terminals $\mathcal{T}\subseteq V$, and a constant $c$.

Output: A $(\mathcal{T},c)$-sparsifier $H$ for $G$.

1 if  _$\mathcal{T}$ is $(5c,c)$-edge-unbreakable_ then

2 Construct $H$, a $(\mathcal{T},c)$-sparsifier of $G$ using Lemma 3.6.

3 return $H$.

4else

5 Let $(V_{1},V_{2})$ be a bipartition of $V(G)$ that refutes the
$(5c,c)$-edge-unbreakable property. That is, $|E_{G}(V_{1},V_{2})|\leq c$ but
$|\mathcal{T}\cap V_{1}|\geq 5c$ and $|\mathcal{T}\cap V_{2}|\geq 5c$.

6 Obtain
$\begin{cases}H_{1}\leftarrow\textsc{SparsifySlow}(\hat{G}[V_{1}],\mathcal{T}_{1},c),\text{
and }\\\
H_{2}\leftarrow\textsc{SparsifySlow}(\hat{G}[V_{2}],\mathcal{T}_{2},c).\end{cases}$.

7 return $H\leftarrow H_{1}\cup H_{2}\cup
E(V_{1},V_{2})-\mathit{Sep}(S,V_{1},V_{2})$.

8 end if

Algorithm 2 SparsifySlow $\textsc{SparsifySlow}(G,\mathcal{T},c)$

Lemma 4.3 and Lemma 4.4 give the correctness proof and the size to the
returned $(\mathcal{T},c)$-sparsifier from Algorithm 2.

######  Lemma 4.3.

Algorithm 2 returns a $(\mathcal{T},c)$-sparsifier of $G$.

###### Proof.

First we notice that all vertices in $\mathcal{T}_{1}$ and $\mathcal{T}_{2}$
have degree 1 in $\hat{G}[V_{1}]$ and $\hat{G}[V_{2}]$ respectively: the
anchor vertices have degree 1 and so the recursive calls in Algorithm 2 are
valid. The correctness is then recursively guaranteed by Lemma 3.5 (divide-
and-conquer step) and Lemma 3.6 (base case). ∎

######  Lemma 4.4.

Let $G$ be a hypergraph, $\mathcal{T}\subseteq V$ is the set of degree-1
terminal vertices, and let $c$ be a constant. Let
$H=\textsc{SparsifySlow}(G,\mathcal{T},c)$ be the output of Algorithm 2. Then
$H$ has at most $O(|\mathcal{T}|c^{2})$ hyperedges.

The proof to Lemma 4.4 is via a potential function similarly defined in Liu
[Liu20].

###### Proof.

The execution to Algorithm 2 defines a recursion tree. If $|\mathcal{T}|<5c$,
then the recursion terminates immediately because $\mathcal{T}$ is trivially
$(5c,c)$-edge-unbreakable by definition and a $(\mathcal{T},c)$-sparsifier of
$O(|\mathcal{T}|c^{2})$ hyperedges is returned by Lemma 3.6. Assume that
$|\mathcal{T}|\geq 5c$, then each recursive call on the subproblem
$(G^{\prime},\mathcal{T}^{\prime})$ guarantees that
$|\mathcal{T}^{\prime}|\geq 5c$.

Now, it suffices to use the following potential function to prove that the
total number of terminal vertices in all recursion tree leaves can be bounded
by $O(|\mathcal{T}|)$. Define a potential function for each subproblem
$(G^{\prime},\mathcal{T}^{\prime})$ to be
$\Phi(G^{\prime},\mathcal{T}^{\prime}):=|\mathcal{T}^{\prime}|-5c$. Then,
according to Algorithm 2, whenever $(G^{\prime},\mathcal{T}^{\prime})$ splits
into two subproblems $(\hat{G^{\prime}}[V_{1}],\mathcal{T}^{\prime}_{1})$ and
$(\hat{G^{\prime}}[V_{2}],\mathcal{T}^{\prime}_{2})$ we have

$\displaystyle\Phi(\hat{G^{\prime}}[V_{1}],\mathcal{T}^{\prime}_{1})+\Phi(\hat{G^{\prime}}[V_{2}],\mathcal{T}^{\prime}_{2})$
$\displaystyle\leq|\mathcal{T}^{\prime}\cap V_{1}|+|\mathcal{T}^{\prime}\cap
V_{2}|+4|E_{G^{\prime}}(V_{1},V_{2})|-10c$
$\displaystyle\leq\Phi(G^{\prime},\mathcal{T}^{\prime})-c.$

Since every subproblem has a non-negative potential, and the sum of potential
decreases by $c$ at each divide-and-conquer step, the total number of leaf
cases do not exceed $\Phi(G,\mathcal{T})/c\leq|\mathcal{T}|/c$. Hence, the
total size from the base case is at most
$\sum_{(G^{\prime},\mathcal{T}^{\prime})\text{: base
case}}|\mathcal{T}^{\prime}|\leq\Phi(G,\mathcal{T})+(5c)(\\#\text{ of leaf
cases})=O(|\mathcal{T}|)$.

By Lemma 3.6, the total number of hyperedges returned from Algorithm 2 is at
most $O(|\mathcal{T}|c^{2})$. The total number of hyperedges added back at
Algorithm 2 is at most the number of divide-and-conquer steps times the cut
size, which is at most $|\mathcal{T}|$. Therefore, the output
$(\mathcal{T},c)$-sparsifier $H$ has at most $O(|\mathcal{T}|c^{2})$
hyperedges as desired. ∎

###### Proof of Lemma 4.2.

Lemma 4.2 follows immediately after the correctness proof (Lemma 4.3) and
upper bounding the number of hyperedges (Lemma 4.4). ∎

##  5 An Almost-linear-time Algorithm Constructing a Sparsifier

This section is devoted to proving part (1) in Theorem 1.1. That is, we give a
almost-linear-time (assuming a constant rank) algorithm that constructs a
contraction based $(\mathcal{T},c)$-sparsifier of $O(|\mathcal{T}|c^{3})$
hyperedges which matches with Theorem 4.1 up to a constant factor. We
summarize the result in Theorem 5.1.

######  Theorem 5.1.

Let $G=(V,E)$ be a hypergraph with $n$ vertices, $m$ hyperedges, and rank
$r=\max_{e\in E}|e|$. Let $\mathcal{T}\subseteq V$ be a terminal set
$\mathcal{T}\subseteq V$. Then there exists a randomized algorithm which
constructs a $(\mathcal{T},c)$-sparsifier with $O(|\mathcal{T}|c^{3})$
hyperedges in $O(p+n(rc\log n)^{O(rc)}\log m)$ time.

###### Overview of the algorithm.

Although Algorithm 2 can construct a $(\mathcal{T},c)$-sparsifier with
$O(|\mathcal{T}|c^{3})$ hyperedges, it is slow because we do not have an
efficient algorithm searching for a bipartition that violates the
$(5c,c)$-edge-unbreakable property.

To construct our contraction-based $(\mathcal{T},c)$-sparsifier, all we need
to do is identifying _essential_ hyperedges and contract non-essential ones.
Essential hyperedges are indispensable to maintaining $\mathrm{mincut}$
between terminals (See Definition 5.6). It seems to be challenging to identify
essential hyperedges on an arbitrary graph without a $(5c,c)$-edge-unbreakable
guarantee. Fortunately, we notice there is an efficient way to identify
essential hyperedges in an expander.

Naturally, we can utilize ExpanderDecompose (where the version for hypergraphs
is explicitly stated in [LS22]) which splits a hypergraph into expanders.
Expander decomposition not only guarantees expander sub-hypergraphs, but also
fits in the divide-and-conquer framework indicated by Lemma 3.5 with a
favorable almost-linear time. Then, we can focus on identifying essential
hyperedges in an expander.

To identify essential hyperedges in an expander, we first enumerate all
_connected cuts_ 111In Chalermsook et al. [CDK+21], the concept of connected
cuts is not explicitly defined. We give a formal definition in Definition 5.4
and hope it clarifies some ambiguity in their paper. with value at most $c$ —
the sub-hypergraph induced by the smaller side of a connected cut is
connected. Then, we build a _pruned auxiliary graph_ based on the cuts we have
enumerated. The pruned auxiliary graph leads to an efficient way identifying
essential hyperedges. Finally, we contract all detected non-essential
hyperedges. We call the above procedure that sparsifies an expander
$\phi$-Sparsify.

With ExpanderDecompose and $\phi$-Sparsify procedures introduced above, we are
able to construct the $(\mathcal{T},c)$-sparsifier on general hypergraphs of
size $O(|\mathcal{T}|c^{3})$ efficiently. Our algorithm (Algorithm 6) is based
on Chalermsook et al. [CDK+21] and consists of iterations of ExpanderDecompose
and $\phi$-Sparsify. Each iteration implements the divide-and-conquer
framework shown by Algorithm 1: we first apply ExpanderDecompose and decompose
the hypergraph into $\phi$-expanders. Then we apply $\phi$-Sparsify to
sparsify the $\phi$-expanders. Finally, we glue all sparsifiers of the
$\phi$-expanders by recovering the inter-cluster hyperedges between the
$\phi$-expanders. Similar to [CDK+21], we prove that $O(\log m)$ iterations
suffice to obtain a $(\mathcal{T},c)$-sparsifier of $O(|\mathcal{T}|c^{3})$
hyperedges.

##### Overview of this section.

In Section 5.1, we first describe the settings of the expander decomposition,
and then we present an algorithm for enumerating all connected cuts with value
at most $c$ in an expander. In Section 5.2, we build a pruned auxiliary graph
using connected cuts where the algorithm can identify non-essential hyperedges
easily. Then we give an algorithm $\phi$-Sparsify that produces a sparsifier
of an expander with the help of the auxiliary graph. Finally, Theorem 5.1 can
be directly proved by combining expander decomposition and the $\phi$-Sparsify
algorithm, which is Algorithm 6 and it is presented in Section 5.3.

###  5.1 Enumeration of Small Cuts in an Expander

To illustrate what an expander is, we first define _conductance_.

######  Definition 5.2 (Conductance of hypergraphs).

Let $G=(V,E)$ be a hypergraph and a proper subset $S\subsetneq V$. We define
the $conductance$ of $S$ to be

$\Phi_{G}(S)=\frac{|\partial{S}|}{\min{(|E(S)|,|E(V\setminus S)|)}}$

and the define conductance of $G$ to be the minimum conductance over all
proper subsets of vertices:

$\Phi(G)=\min_{S:\emptyset\subsetneq S\subsetneq V}{\Phi_{G}(S)}$

We call a hypergraph with conductance $\phi$ an _$\phi$ -expander_. Long and
Saranurak [LS22] give an almost-linear-time algorithm ExpanderDecompose that
partitions a hypergraph into $\phi$-expanders.

######  Lemma 5.3 ([LS22]).

There exists a randomized algorithm ExpanderDecompose that, given any
unweighted hypergraph $G=(V,E)$ with $n$ vertices, $m$ hyperedges, and total
size $p=\sum_{e\in E}|e|$, and any parameter $\phi>0$, with high probability
computes in $p^{1+o(1)}$ time a partition $\\{V_{1},\dots,V_{k}\\}$ of $V$
such that

  * •

for all $i$, $\Phi(G[V_{i}])\geq\phi$, and

  * •

the number of crossing hyperedges is at most $\phi m\,\mathrm{polylog}(n)$ (we
say that an edge $e$ is crossing if $e$ contains vertices from at least two
parts $V_{i}$ and $V_{j}$ for some $i\neq j$).

We also note that any cut $(X,V\setminus X)$ of value at most $c$ in a
$\phi$-expander, according to Definition 5.2, satisfies

$\min\\{|E(X)|,|E(V\setminus X)|\\}\leq c\phi^{-1}.$ (2)

For now, we will focus on constructing $(\mathcal{T},c)$-sparsifiers on
$\phi$-expanders. This is because ExpanderDecompose can be easily incorporated
into the divide-and-conquer framework (Algorithm 1) as will be formally shown
in Algorithm 6 near the end of the section.

Given a $\phi$-expander $G$ with terminal set $\mathcal{T}$, our goal is to
identify an _essential_ hyperege $e$, that is, to check whether $e$ is in
_every_ $(A,B)$-$\mathrm{mincut}$s with value at most $c$ for some disjoint
terminal sets $A$ and $B$. In a general hypergraph there could be as many as
$O(2^{n})$ mincuts with value at most $c$ to check but in a $\phi$-expander
there is much less. It turns out that finding all _connected cuts_ with value
at most $c$ suffices to identify essential hyperedges:

######  Definition 5.4 (Connected Cuts).

For a hypergraph $G=(V,E)$, let $(X,V\setminus X)$ be a cut where $X\subseteq
V$ and $|E(X)|\leq|E(V\setminus X)|$. We say $(X,V\setminus X)$ is a
_connected cut_ if and only if $G[X]$ is connected.

Suppose there is a connected cut $(X,V\setminus X)$ with value at most $c$,
then by the property of the $\phi$-expander we know that $|E(X)|\leq
c\phi^{-1}$ (Equation 2). Using the assumption that $G[X]$ is connected, we
can reach any boundary hyperedge in $\partial X$ by invoking a DFS traversal
from a vertex $v_{\text{seed}}\in X$ within $c\phi^{-1}$ steps. Since there
are at most $c$ boundary hyperedges, their sizes add up to at most $rc$. Then,
we recursively “guess and trim” these boundary hyperedges for at most $rc$
times on $G$, obtaining $G[X]$ at the end. EnumerateCuts (Algorithm 3) tries
every possible $v_{\text{seed}}$ and invokes the helper function
EnumerateCutsHelp (Algorithm 4) that performs the “guess and trim” procedure.
We summarize the guarantee of EnumerateCuts in Lemma 5.5:

Input: A $\phi$-expander hypergraph $G=(V,E)$ with $\mathrm{rank}$ $r$, and a
threshold parameter $c$.

Output: All connected cuts with value at most $c$.

$\mathcal{C}\leftarrow\emptyset$. // Stores all found connected cuts.

1 for  _each $v_{\text{seed}}\in V$ _ do

/* Invokes a helper function to find all connected cuts involving
$v_{\text{seed}}$. */

$\mathcal{C}\leftarrow\mathcal{C}\cup\textsc{EnumerateCutsHelp}(0,G,G,\phi,r,c,v_{\text{seed}})$.

// See Algorithm 4.

2

3 end for

return $\mathcal{C}$.

Algorithm 3 EnumerateCuts $(G,\phi,r,c)$

1

Input: The current recursion depth $\mathit{depth}$. A hypergraph $H=(V,E)$
with rank $r$. The original hypergraph $G$. Parameters $c$ and $\phi$. A seed
vertex $v_{\rm seed}\in V$.

Output: All connected cut with value at most $c$ so that $v_{seed}$ is in the
smaller side.

2 if  _$\mathit{depth}\leq rc$_ then

3 Run DFS from $v_{\rm seed}$ on $H$ and stop as soon as visiting
$c\phi^{-1}+1$ hyperedges.

4 Let $\hat{E}$ be the set of visited hyperedges and $X$ be the set of visited
vertices.

5 if  _DFS gets stuck before visiting $c\phi^{-1}+1$ hyperedges_ then

6 if  _$|\partial_{G}X|\leq c$ _ then

return $\\{(X,V\setminus X)\\}$. /* Some connected cut with value at most $c$
is found. */

7

8 else

9 return $\emptyset$.

10 end if

11

12 else

13 $\mathcal{S}\leftarrow\emptyset$.

14 for  _each $e\in\hat{E}$ and for each $v\in e$, $v\neq v_{\rm seed}$_ do

Let $e^{\prime}\leftarrow e\setminus v$./* modify the boundary hyperedge into
a smaller one. */

// A recursive call with $v$ being removed from $e$.

15
$\mathcal{S}\leftarrow\mathcal{S}\cup\textsc{EnumerateCutsHelp}(\mathit{depth}+1,H-e+e^{\prime},G,\phi,r,c,v_{\rm
seed})$

16 end for

17 return $\mathcal{S}$.

18 end if

19

20else

21 return $\emptyset$.

22 end if

23

Algorithm 4 EnumerateCutsHelp $(\mathit{depth},H,G,\phi,r,c,v_{\rm seed})$

######  Lemma 5.5.

Given a $\phi$-expander hypergraph $G=(V,E)$, there are at most
$|V|(rc\phi^{-1})^{rc}$ connected cuts with value at most $c$. Moreover,
Algorithm 3 enumerates all of them in $O(|V|(rc\phi^{-1})^{rc+1})$ time.

###### Proof.

We will first show that (1) all connected cuts with value at most $c$ can be
found by Algorithm 3 and that (2) all the returned cuts from Algorithm 3 are
connected cuts with value at most $c$. Then, we show that the running time of
Algorithm 3 is $O(n(rc\phi^{-1})^{rc+1})$ in part (3).

###### Part (1).

We first show that all connected cuts with value at most $c$ can be found by
Algorithm 3. For an arbitrary connected cut $(X,V\setminus X)$ with value at
most $c$ containing some vertex $v_{seed}$ in $G=(V,E)$ where
$|E(X)|\leq|E(V\setminus X)|$, we have $|\partial X|\leq c$ and $G[X]$ is
connected. According to Equation 2, we have $|E(X)|\leq c\phi^{-1}$. So, if a
DFS starting from $v_{seed}\in X$ yields after visiting $c\phi^{-1}+1$
hyperedges, then there must exist a hyperedge $e_{cut}$ among the visited
hyperedges such that $e_{cut}\in\partial X$, which implies $e_{cut}\setminus
X\not=\emptyset$. Thus, Algorithm 4 removes some $v\in e_{cut}\setminus X$
from $e_{cut}$ in Algorithm 4. The algorithm recursively removes vertices in
$V\setminus X$ from hyperedges in $\partial X$. As a result, all vertices in
$V\setminus X$ and the boundary hyperedges will be removed from all boundary
hyperedges at some point in the recursion. That means the boundary hyperedges
only contains vertices in $X$ and the DFS will get stuck before visiting
$c\phi^{-1}+1$ hyperedges. Notice that the total number of vertices in
boundary edges that gets removed is less than $r|\partial X|\leq rc$. In
addition, since $G[X]$ is connected, the DFS gets stuck after visiting all
vertices in $X$ and then Algorithm 4 returns the cut $(X,V\setminus X)$.
Algorithm 3 iterates over all vertices in $V$ as a seed vertex, therefore, it
returns all connected cuts with value at most $c$ in $G$.

###### Part (2).

We show that all the cuts that Algorithm 3 finds are connected cuts with value
at most $c$. The value of all the cuts the algorithm finds is less than $c$
according to Algorithm 4 in Algorithm 4. Now, we observe that DFS only probes
adjacent vertices. When DFS gets stuck, the cut $(X,V\setminus X)$ that DFS
gives is a connected cut in the modified hypergraph. Since the modified
hypergraph is obtained only via removing vertices from hyperedges, it is not
hard to see that $G[X]$ is connected.

###### Part (3).

Algorithm 4 is invoked $|V|$ times. The runtime per execution of Algorithm 4
can be upper bounded by the size of the recursion tree multiplied with the
worst case time needed for DFS (Algorithm 4). From the for-loop in Algorithm
4, each node in the recursion tree has at most $rc\phi^{-1}$ children and the
depth of the recursion tree is bounded by $rc$. So, the size of the recursion
tree is at most $(rc\phi^{-1})^{rc}$. Moreover, each DFS (Algorithm 4) takes
$O(rc\phi^{-1})$ time since at most $c\phi^{-1}+1$ hyperedges with rank $r$
are visited. Thus, the runtime can be bounded by $O(|V|(rc\phi^{-1})^{rc+1})$.
∎

###  5.2 Sparsification via an Auxiliary Graph

We now introduce the algorithm $\phi$-Sparsify which constructs a
$(\mathcal{T},c)$-sparsifier with $O(|\mathcal{T}|c^{3})$ hyperedges from a
$\phi$-expander. Our algorithm $\phi$-Sparsify detects the hyperedges that are
not _essential_ to some $(\mathcal{T},c)$-sparsifier and contracts them. The
formal definition of essential hyperedges is as follows.

######  Definition 5.6 (Essential and Non-essential Hyperedges).

A hyperedge $e$ is said to be _essential_ if there exists a partition of
terminals $(A,\mathcal{T}\setminus A)$ such that all $(A,\mathcal{T}\setminus
A)$-mincuts with value at most $c$ contain $e$. Otherwise, the hyperedge is
non-essential.

Notice that all essential hyperedges cannot be contracted or removed as they
will affect $(A,\mathcal{T}\setminus A)$-mincut value for some
$A\subset\mathcal{T}$. Hence, any $(\mathcal{T},c)$-sparsifier of $G$ must
include all essential hyperedges in $G$. That said, by the existence theorem
(Theorem 4.1), the number of essential hyperedges on $G$ is at most
$O(|\mathcal{T}|c^{3})$.

####  5.2.1 Auxiliary Graph (and its Subtle Issue)

According to Definition 5.6, a hyperedge $e$ is non-essential if for each
partition of terminals $(A,\mathcal{T}\setminus A)$, there exists a
$(A,\mathcal{T}\setminus A)$-mincut with value at most $c$ that does not
contain $e$ in the boundary. A straightforward way to check whether a
hyperedge is non-essential, is to check whether the value of a
$(A,\mathcal{T}\setminus A)$-mincut for some $A\subset\mathcal{T}$ would be
affected after the hyperedge is removed.

Chalermsook et al. [CDK+21] utilize EnumerateCuts (the normal graph version)
to check whether an edge is non-essential. In particular, they introduced the
notion of _auxiliary graph_ on a $\phi$-expander that helps identifying non-
essential edges. Unfortunately, their definition (and the construction) to the
auxiliary graph does not have the desired property that leads to a sufficient
criterion recognizing an essential edge. To illustrate this, we first formally
state the definition of an auxiliary graph from Chalermsook et al., which
naturally extends to hypergraphs.

######  Definition 5.7 (Auxiliary Graph).

Let hypergraph $G=(V,E)$ be a $\phi$-expander. An _auxiliary graph_
$G^{\mathsf{aux}}=(V^{\mathsf{aux}},E^{\mathsf{aux}})$ for $G$ has its vertex
set $V^{\mathsf{aux}}$ consisting of three disjoint parts
$V^{\mathsf{aux}}=P_{0}\cup C_{0}\cup E_{0}$. Each edge in $E^{\mathsf{aux}}$
either connects the elements between $P_{0}$ and $C_{0}$, or connects the
elements between $C_{0}$ and $E_{0}$. The elements in the three parts and the
edges between them are defined as follows:

  * •

$C_{0}$ contains the cuts returned by Algorithm 3 with value at most $c$ on
$G$.

  * •

Each cut $c=(X,V\setminus X)\in C_{0}$ induces a terminal partition
$p=(\mathcal{T}\cap X,\mathcal{T}\setminus X)$. Let $P_{0}$ be the collection
of all such terminal partitions (excluding the trivial partitions where
$\mathcal{T}\cap X=\emptyset$ or $\mathcal{T}\subseteq X$). Moreover, we add
$(p,c)$ to $E^{\mathsf{aux}}$ if $c$ is a $p$-mincut.

  * •

$E_{0}=E$. For each $c=(X,V\setminus X)\in C_{0}$, we add $(c,e)$ to
$E^{\mathsf{aux}}$ for all $e\in\partial X$.

##### A Subtle Issue in [CDK+21].

Chalermsook et al. [CDK+21] proposed the algorithm that recognizes an edge
$e\in E_{0}$ to be essential iff there is a partition $p\in P_{0}$ such that
$N(p)\subseteq N(e)$. That is, all $p$-mincuts in $C_{0}$ neighboring to $p$
contains $e$. Unfortunately, this algorithm has a subtle issue. Indeed, if $e$
is an essential edge then there exists such a partition. However, it is not
the case conversely. The statement would have been true if $C_{0}$ is the set
of _all_ cuts with value at most $c$. However, the cuts returned by Algorithm
3 are connected cuts only. Only considering connected cuts will result in
recognizing non-essential edges to be essential (even in normal graphs). We
give an example below.

##### An Example.

Consider the example shown in Figure 2. The graph has $7$ vertices
$v_{1},v_{2},\ldots,v_{7}$ and $3$ of them are terminal vertices
$\mathcal{T}=\\{v_{1},v_{2},v_{7}\\}$. There are $3$ proper partitions of
$\mathcal{T}$, which separates each of $v_{1}$, $v_{2}$, and $v_{7}$ from the
rest of terminals respectively. For the terminal partitions
$p_{1}:=(\\{v_{1}\\},\\{v_{2},v_{7}\\})$ and
$p_{2}:=(\\{v_{2}\\},\\{v_{1},v_{7}\\})$, there are a unique $p_{1}$-mincut
$(\\{v_{1}\\},V\setminus\\{v_{1}\\})$ and a unique $p_{2}$-mincut
$(\\{v_{2}\\},V\setminus\\{v_{2}\\})$. Therefore, the cutting edges $a$ and
$b$ respectively are essential by Definition 5.6. For the terminal partition
$p_{7}:=(\\{v_{7}\\},\\{v_{1},v_{2}\\})$, there are two $p_{7}$-mincuts:
$(\\{v_{1},v_{2}\\},\\{v_{3},v_{4},v_{5},v_{6},v_{7}\\})$ and
$(\\{v_{1},v_{2},v_{3},v_{4}\\},\\{v_{5},v_{6},v_{7}\\})$. The edges crossing
these mincuts are $\\{a,b\\}$ and $\\{d,e\\}$ respectively. So, by Definition
5.6, edges $d$ and $e$ are non-essential since none of the terminal partition
has $d$ or $e$ appearing in every mincut.

However, Algorithm 3 does not report one of the $p_{7}$-mincut
$(\\{v_{1},v_{2}\\},\\{v_{3},v_{4},v_{5},v_{6},v_{7}\\})$ since this cut is
not a connected cut. Therefore, Algorithm 3 returns only one $p_{7}$-mincut
and $d$ and $e$ will be erroneously recognized as essential edges in the
auxiliary graph.

Figure 2: A graph $G$ and its auxiliary graph
($\mathcal{T}=\\{v_{1},v_{2},v_{7}\\},V_{1}=\\{v_{1},v_{2}\\},V_{2}=\\{v_{1},v_{2},v_{3},v_{4}\\}$).
Notice that in the auxiliary graph, edges $d$ and $e$ are incorrectly
considered as essential.

To resolve the problem of incorrectly recognizing unessential hyperedges to be
essential, we _prune_ the auxiliary graph. The intuition is to prune some
partitions as well as their incident nodes and edges in the auxiliary graph so
that the unessential edges are removed. For instance, the terminal partition
$(\\{v_{1},v_{2}\\},\\{v_{7}\\})$ is one of the partitions that should be
pruned with its incident nodes and hyperedges from the auxiliary graph. The
partitions that should be preserved are called _useful_ terminal partitions
(For instance, $(\\{v_{1}\\},\\{v_{2},v_{7}\\})$ and
$(\\{v_{2}\\},\\{v_{1},v_{7}\\})$), which will be elaborated on in the next
section.

####  5.2.2 Pruned Auxiliary Graph

Let us now formally define _useful_ terminal partitions and describe the
_pruned auxiliary graph_ that helps us to correctly identify all essential
hyperedges. This subsection contains one of the main technical contributions
of this paper.

######  Definition 5.8 (Useful Terminal Partition).

A terminal partition of terminals $(A,B)$ is _useful_ if
$\mathrm{mincut}_{G}(A,B)\leq c$ and for all $(A,B)$-mincut $(X,V\setminus
X)$, $G[X]$ is connected.

With Definition 5.8, we can prune unnecessary partitions from the auxiliary
graph $G^{\mathsf{aux}}$: we only keep the partitions in $P_{0}$ that are
useful, and discard all the related mincuts from $C_{0}$ and the isolated
elements in $E_{0}$.

Henceforth, we refer $G^{\mathsf{aux}}$ to be the _pruned auxiliary graph_ and
$P_{0},C_{0},E_{0}$ are pruned as well. The following lemma shows that, by
working on the pruned auxiliary graph, the characterization of all essential
hyperedges on $G$ proposed in [CDK+21] is now correct.

######  Lemma 5.9.

A hyperedge $e\in E$ is essential if and only if $e\in E_{0}$ and there exists
useful $p\in P_{0}$ such that $N(p)\subseteq N(e)$.

###### Proof.

The backward direction ($\Leftarrow$) follows from Definition 5.6, now we show
the forward direction.

##### ($\Rightarrow$):

Suppose $e\in E$ is an essential hyperedge. Then by Definition 5.6, we know
that there are at least one partition $p=(A,B)$ such that all $c$-thresholded
$(A,B)$-mincuts involve $e$. If $(A,B)$ is useful then we are done. Now,
assume that $p$ is not useful, then there exists at least one $(A,B)$-mincut
$(X,V\setminus X)$ such that $G[X]$ is not connected. Without loss of
generality we may further assume that $|A|$ is the smallest among all non-
useful partitions $(A^{\prime},B^{\prime})$ with
$\mathrm{mincut}_{G}(A^{\prime},B^{\prime})\leq c$ such that $e$ is involved
in every $(A^{\prime},B^{\prime})$-mincut.

Since $G[X]$ is not connected, $G[X]$ has at least two connected components.
Therefore, there exists a partition on $X=X_{1}\cup X_{2}$ such that
$E(X_{1})\cap E(X_{2})=\emptyset$ and, without loss of generality, assume
$e\in E(X_{1},V\setminus X_{1})$. Notice that $A\cap X_{1}\neq\emptyset$
(otherwise $(X_{2},V\setminus X_{2})$ is also a $(A,B)$-mincut but does not
involve $e$,) and for the same reason $A\cap X_{2}\neq\emptyset$. Now, the new
terminal partition $p_{new}=(A\cap X_{1},B\cup(A\setminus X_{1}))$ has the
property that every $p_{new}$-mincut $(X_{new},V\setminus X_{new})$ involves
$e$ — otherwise $(X_{new}\cup X_{2},V\setminus X_{new}\setminus X_{2})$ would
be a $(A,B)$-mincut that does not involve $e$. Finally, using $|A\cap
X_{1}|<|A|$ and the assumption to minimality of $|A|$, we know that $p_{new}$
is useful so the statement holds. ∎

###### Pruning the Auxiliary Graph.

Here, we show how to efficiently test whether a terminal partition
$(A,\mathcal{T}\setminus A)$ is useful. All we need to do is to find the _$A$
-minimal $(A,\mathcal{T}\setminus A)$-mincut_ $(X^{*},V\setminus X^{*})$ and
check whether $G[X^{*}]$ is connected. To illustrate the idea, we first define
the $A$-minimal $(A,B)$-mincut. Then we will show that we can check whether
$(A,\mathcal{T}\setminus A)$ is useful by checking whether $G[X^{*}]$ is
connected (Lemma 5.12). Lastly, to algorithmically find the $A$-minimal
$(A,\mathcal{T}\setminus A)$-mincut in the hypergrpah, we resort to an
algorithm called LocalMinCut in [FNY+20].

######  Definition 5.10 ($A$-minimal $(A,B)$-mincut).

Let $G=(V,E)$ be a hypergraph and $A,B\subseteq V$ be disjoint subsets. We say
an $(A,B)$-mincut $(X^{*},V\setminus X^{*})$ is the $A$-minimal
$(A,B)$-mincut, if, for any other $(A,B)$-mincut $(X,V\setminus X)$, we have
$X^{*}\subseteq X$.

For any $A,B$, an $A$-minimal $(A,B)$-mincut is unique. This standard fact
follows from submodularity of cut functions on hypergraphs. For completeness,
we give the proof in appendix B.

######  Proposition 5.11.

Let $G=(V,E)$ be a hypergraph. For two disjoint subsets $A,B\subseteq V$, the
$A$-minimal $(A,B)$-mincut always exists and is unique.

Since the $A$-minimal $(A,B)$-mincut always exists and is unique, we can check
the $A$-minimal $(A,\mathcal{T}\setminus A)$-mincut to see whether the
terminal partition $(A,\mathcal{T}\setminus A)$ is useful via the following
lemma.

######  Lemma 5.12.

Let $H=(V,E)$ be a connected hypergraph and $\mathcal{T}\subset V$ be a
terminal set, a terminal partition $(A,\mathcal{T}\setminus A)$ is useful, if
and only if the $A$-minimal $(A,\mathcal{T}\setminus A)$-mincut
$(X^{*},V\setminus X^{*})$ is connected and $|\partial X^{*}|\leq c$.

###### Proof.

One direction is trivial: The $A$-minimal $(A,\mathcal{T}\setminus A)$-mincut
is one of $(A,\mathcal{T}\setminus A)$-mincuts, so it is connected and its
value is at most $c$. It remains to prove another direction.

Suppose $A$-minimal $(A,\mathcal{T}\setminus A)$-mincut $(X^{*},V\setminus
X^{*})$ is connected and $|\partial X^{*}|\leq c$. As clearly
$\mathrm{mincut}_{G}(A,\mathcal{T}\setminus A)\leq c$, we need to show that
all $(A,\mathcal{T}\setminus A)$-mincuts are connected. Assume for the sake of
contradiction that there exists a disconnected $(A,\mathcal{T}\setminus
A)$-mincut, which consists of $(X_{1},V\setminus(X_{1}\cup X_{2}))$ and
$(X_{2},V\setminus(X_{1}\cup X_{2}))$ where $E(X_{1},X_{2})=\emptyset$. We
claim that that both $X^{*}\cap X_{1}$ and $X^{*}\cap X_{2}$ are nonempty. If
the claim holds, we are done because $G[X^{*}]$ is connected, so
$E(X_{1},X_{2})\not=\emptyset$, contradicting with $E(X_{1},X_{2})=\emptyset$.
Thus, all $(A,\mathcal{T}\setminus A)$-mincuts are connected.

Finally, to see the claim, assume for contradiction without loss of generality
that $X^{*}\cap X_{1}=\emptyset$. Notice that by Definition 5.10, $A\subseteq
X^{*}\subseteq X_{1}\cup X_{2}$ and thus $A\subseteq X^{*}\subseteq X_{2}$. So
$(X_{2},V\setminus X_{2})$ is a $(A,\mathcal{T}\setminus A)$-cut of value
$|\partial X_{2}|$. But the $(A,\mathcal{T}\setminus A)$-mincut
$(X^{*},V\setminus X^{*})$ has greater value of $|\partial X_{1}|+|\partial
X_{2}|>|\partial X_{2}|$ (where $|\partial X_{1}|>0$ because the hypergraph
$H$ is connected). This is a contradiction. ∎

Lemma 5.12 reduces the problem of testing whether a terminal partition
$(A,\mathcal{T}\setminus T)$ is useful to checking whether the $A$-minimal
$(A,\mathcal{T}\setminus A)$-cut is connected. A randomized algorithm called
LocalMinCut can efficiently find the $A$-minimal $(A,\mathcal{T}\setminus
A)$-mincut. More details about Theorem 5.13 can be found in Appendix C.

######  Theorem 5.13.

Suppose that the $A$-minimal $(A,B)$-mincut $(S,V\setminus S)$ has size at
most $c$ and volume $\mathrm{vol}(S)=\sum_{v\in S}\deg(v)\leq\nu$. Then, there
is an algorithm $\textsc{LocalMinCut}(A,\nu,c)$ that finds $S$ in $O(\nu
c^{3}\log n)$ time with high probability.

To analyze the runtime of constructing a pruned auxiliary graph for an
expander, we first discuss about the runtime of pruning a given auxiliary
graph.

###### Runtime of pruning auxiliary graph.

To prune an auxiliary graph, for all terminal partitions
$(A,\mathcal{T}\setminus A)$, we use LocalMinCut to find the $A$-minimal
$(A,\mathcal{T}\setminus A)$-mincut and check whether it is connected. There
are at most $(rc\phi^{-1})^{rc}$ terminal partitions in an auxiliary graph.
Let $(S,V\setminus S)$ be the $A$-minimal $(A,\mathcal{T}\setminus A)$-mincut.
Because $\mathrm{vol}(S)=\sum_{v\in S}\deg(v)\leq|E(S)|\max_{e\in
E}{|e|}=rc\phi^{-1}$, by setting $\nu=rc\phi^{-1}$ and applying Theorem 5.13,
each terminal partition needs $O(rc\phi^{-1}c^{3}\log{n})$ time to check.
Therefore, the total time of pruning the auxiliary graph is
$O((rc\phi^{-1})^{rc+1}c^{3}\log{n})$.

We now analyze the runtime of constructing a pruned auxiliary graph.

######  Lemma 5.14.

Given a $\phi$-expander $G$, there is an algorithm that constructs a pruned
auxiliary graph in $n(rc\phi^{-1})^{O(rc)}$ time.

###### Proof.

EnumerateCuts runs in $O(n(rc\phi^{-1})^{rc+1})$ time. It produces at most
$n(rc\phi^{-1})^{rc}$ of connected cuts, so the construction of (unpruned)
auxiliary graph takes $O(nc(rc\phi^{-1})^{rc})=O(n(rc\phi^{-1})^{rc+1})$ time.
With the discussion above, we know that pruning the auxiliary graph takes
additional $O((rc\phi^{-1})^{rc+1}c^{3}\log n)$ time. Hence, the total runtime
is $O((n+c^{3}\log n)(rc\phi^{-1})^{rc+1})=n(rc\phi^{-1})^{O(rc)}$ time. ∎

An interesting property about usefulness of a partition is that this
definition is robust against contraction of any non-essential hyperedge, which
is useful in the next section.

######  Lemma 5.15.

Let $G=(V,E)$ be a hypergraph and let $\mathcal{T}\subseteq V\cup E$ be the
set of terminals. Let $(A,B)$ be a terminal partition of $\mathcal{T}$ so that
there exists a $(A,B)$-mincut of size at most $c$. Consider any non-essential
hyperedge $e\in E$. Then, $(A,B)$ is useful on $G$ if and only if $(A/e,B/e)$
is useful on $G/e$.

###### Proof.

On one hand, in a connected component of $G$, contracting a hyperedge will
results in all of the vertices in the hyperedge being contracted to a single
vertex, and the vertex will be in all of the hyperedges that share at least
one vertex with the contracted hyperedge. Therefore, the component remains
connected. On the other hand, if we uncontract a vertex in a connected
component (which means the vertex is connected to all other vertices in the
component) the hyperedge, the all of the newly introduced vertices will also
be connected to all the other vertices through the new hyperedge resulted from
the uncontraction. To conclude, contracting and uncontracting hyperedges will
not result in changes in connectedness in the hypergraph, we only need to show
that if $e$ is an non-essential hyperedge, then (We only need to show one
direction since the lemma states that $\mathrm{mincut}_{G}(A,B)\leq c$)

$\mathrm{mincut}_{G}(A,B)\leq c\Rightarrow\mathrm{mincut}_{G/e}(A/e,B/e)\leq
c$

Since $e$ is non-essential we just fix an $(A,B)$-mincut that does not contain
$e$, this cut will remain have cut value at most $c$ after contracting $e$
thus $\mathrm{mincut}_{G/e}(A/e,B/e)\leq c$. ∎

####  5.2.3 The $\phi$-Sparsify Procedure

Once we obtain the pruned auxiliary graph of a $\phi$-expander $G$, a simple
greedy $\phi$-Sparsify procedure (Algorithm 5) can be applied for constructing
a $(\mathcal{T},c)$-sparsifier $H$ of $G$.

Input: $\phi$-expander hypergraph $G=(V,E)$ with $\mathrm{rank}$ $r$, terminal
set $\mathcal{T}$, threshold parameter $c$.

Output: A $(\mathcal{T},c)$-sparsifier of $G$.

1 Run EnumerateCuts and construct the pruned auxiliary graph
$G^{\mathsf{aux}}=(V^{\mathsf{aux}},E^{\mathsf{aux}})$, where
$V^{\mathsf{aux}}=P_{0}\cup C_{0}\cup E_{0}$.

2 Let $E^{\prime}\leftarrow E\setminus E_{0}$.

3 for  _each $e\in E_{0}$ (in any order)_ do

/* Use Lemma 5.9 to check and identify non-essential edges. */

4 Compute the set of partitions $P^{\prime}_{e}:=P_{0}\cap N(N(e))$ who has at
least one mincut that contains the edge $e$.

5 if  _$\forall$ $p\in P^{\prime}_{e}$, $N(p)\not\subseteq N(e)$_ then

6 Remove $N(e)$ and all incident edges from $G^{\mathsf{aux}}$ and then Remove
all independent vertices from $G^{\mathsf{aux}}$.

7

$E^{\prime}\leftarrow E^{\prime}\cup\\{e\\}$.

// $e$ is non-essential.

8

9 end if

10

11 end for

return $G/E^{\prime}$.

Algorithm 5 $\phi$-Sparsify $(G,\mathcal{T},\phi,r,c)$

To analyze Algorithm 5, we first introduce Lemma 5.16, Corollary 5.17, and
Lemma 5.18. Finally, Lemma 5.19 summarizes Algorithm 5 based on the previous
lemmas and corollary.

Lemma 5.16 guarantees that after each update of the auxiliary graph, the
hypergraph represented by the updated auxiliary graph is still viable for the
$\phi$-Sparsify algorithm.

######  Lemma 5.16.

Let $e$ be the first edge that triggers Algorithm 5 of Algorithm 5. Suppose
that $G^{\mathsf{aux}}_{1}$ is the updated auxiliary graph with vertex set
$V_{1}^{\mathsf{aux}}=P_{1}\cup C_{1}\cup E_{1}$, and let $G_{1}=G/e$. Then,
$G^{\mathsf{aux}}_{1}$ is exactly the pruned auxiliary graph of $G_{1}$.

###### Proof.

Let $G^{\mathsf{aux}}_{*}$ be the pruned auxiliary graph of $G_{1}$ with the
vertex set $V_{*}^{\mathsf{aux}}=P_{*}\cup C_{*}\cup E_{*}$. To prove
$G^{\mathsf{aux}}_{*}=G^{\mathsf{aux}}_{1}$, it suffices to prove
$C_{*}=C_{1}$ as the pruned auxiliary graph is uniquely defined (via
Definition 5.7 and Lemma 5.15) by the connected cuts of value at most $c$.

Notice that given an arbitrary cut $(X,V\setminus X)$ in a hypergraph,
contracting a _non-cutting_ hyperedge from $E\setminus E(X,V\setminus X)$ does
not invalidate the cut nor change the cut value. Therefore, the contraction of
a hyperedge $e$ invalidates every cut that involves $e$. Moreover, no new
connected cut of value at most $c$ joins $C_{*}$ because contracting a
hyperedge in a connected cut does not decrease the cut value. Hence, $C_{*}$
contains all the cuts in $C_{0}$ except the cuts involving $e$. On the other
hand, $C_{1}=C_{0}\setminus N(e)$, which exactly contains all the cuts in
$C_{0}$ except the cuts that involve $e$ as well. ∎

######  Corollary 5.17.

Right before returning $G/E^{\prime}$ from Algorithm 5 at Algorithm 5, the
modified $G^{\mathsf{aux}}$ is the pruned auxiliary graph of $G/E^{\prime}$.

###### Proof.

The statement is true by applying Lemma 5.16 iteratively whenever the
algorithm adds an hyperedge to $E^{\prime}$ and modifies $G^{\mathsf{aux}}$. ∎

######  Lemma 5.18.

Essential hyperedges remains essential under contractions of non-essential
hyperedges.

###### Proof.

For an arbitrary essential hyperedge $e$, there is a terminal partition $p$
such that all the $p$-mincuts contain $e$. After contractions of some non-
essential hyperedges, all the $p$-mincuts still contain $e$, because
contractions never introduce new cuts to a hypergraph. ∎

With Lemma 5.16, Corollary 5.17, and Lemma 5.18, we are able to prove the
following lemma which summarizes $\phi$-Sparsify.

######  Lemma 5.19.

Let $G$ be a $\phi$-expander with $n$ vertices and $\mathcal{T}$ be a terminal
set. Then, Algorithm 5 produces a $(\mathcal{T},c)$-sparsifier with
$O(|\mathcal{T}|c^{3})$ hyperedges and runs in $O(p+n(rc\phi^{-1})^{O(rc)})$
time, where $p=\sum_{e\in E}|e|$ is the total size of the hypergraph $G$.

###### Proof.

We show correctness of $\phi$-Sparsify, the size of the returned
$(\mathcal{T},c)$-Sparsifier, and the runtime of $\phi$-Sparsify respectively.

###### Correctness.

According to Lemma 5.16 and Corollary 5.17, the modified $G^{\mathsf{aux}}$ is
always the pruned auxiliary graph of $G/E^{\prime}$ at the beginning of each
iteration of Algorithm 5. By Lemma 5.9, only non-essential hyperedges will be
contracted. Therefore, by Definition 5.6, the values of $p$-mincuts for all
useful partition $p$ are not affected and thus the returned hypergraph is a
$(\mathcal{T},c)$-sparsifier.

###### Size of the $(\mathcal{T},c)$-Sparsifier.

Since all essential hyperedges cannot be contracted as they will affect
$(A,\mathcal{T}\setminus A)$-mincut value for some $A\subset\mathcal{T}$, any
$(\mathcal{T},c)$-sparsifier of $G$ must include all essential hyperedges in
$G$. By the existence theorem (Theorem 4.1), the number of essential
hyperedges in $G$ is at most $O(|\mathcal{T}|c^{3})$. By Lemma 5.18, after
contracting all non-essential hyperedges detected by $\phi$-Sparsify, all the
remaining hyperedges are essential. Therefore, the number of hyperedges in the
$(\mathcal{T},c)$-sparsifier returned by $\phi$-Sparsify is at most
$O(|\mathcal{T}|c^{3})$.

###### Runtime of $\phi$-Sparsify.

Algorithm 5 runs in $n(rc\phi^{-1})^{O(rc)}$ time by Lemma 5.14. Since
$|P^{\prime}_{e}|\leq|N(e)|$ for any $e\in E_{0}$, we know that Algorithm 5
contributes a total runtime of at most

$\displaystyle\sum_{e\in E_{0}}|N(e)|\leq c|C_{0}|=n(rc\phi^{-1})^{O(rc)}.$

To implement Algorithm 5, we create a hash table marking all vertices in
$N(e)$ and for each $x\in P^{\prime}_{e}$ the algorithm iterates through
$N(x)$ until the first neighbor that is not in $N(e)$. The whole process takes
$O(|N(e)|)$ time. Hence, the total runtime contributed by Algorithm 5 takes
$n(rc\phi^{-1})^{O(rc)}$ as well. Now, since each cut in $C_{0}$ will be
removed at most once, so the total runtime contributed by Algorithm 5 is at
most $c|C_{0}|=n(rc\phi^{-1})^{O(rc)}$.

Finally, contracting all hyperedges in $E\setminus E^{\prime}$ on $G$ takes
linear time in the total hypergraph size $O(p)$. Hence, the total time for
$\phi$-Sparsify is $O(p+n(rc\phi^{-1})^{O(rc)})$. ∎

###  5.3 The Almost-linear-time Algorithm of $(\mathcal{T},c)$-Sparsifiers

Finally, we combine all the tools from previous subsections and formally prove
Theorem 1.1 (1).

To construct a $(\mathcal{T},c)$-sparsifier for a hypergraph $G=(V,E)$ with
$O(|\mathcal{T}|c^{3})$ hyperedges under the divide-and-conquer scheme, we
first split the hypergrpah $G$ into $\phi$-expanders
$\\{G_{i}=(V_{i},E_{i})\\}$ via ExpanderDecompose. All boundary hyperedges in
$\cup_{i}\partial V_{i}$ will be separated, and we add two anchor vertices per
separated hyperedge.

For each $\phi$-expander, we enumerate all the connected terminal cuts with
value at most $c$ via Algorithm 3. Then, we construct the auxiliary graph and
prune it. Next we contract non-essential hyperedges with the help of the
pruned auxiliary graph. Lastly, we glue all the sparsifiers of the
$\phi$-expanders together by replacing all anchored separated hyperedges with
the original hyperedges.

The above procedure described in the previous two paragraphs is one iteration
of sparsifying. The following algorithm Algorithm 6 repeats the procedure
until there has been $\log m$ iterations. Finally, Algorithm 6 returns a
$(\mathcal{T},c)$-sparsifier with $O(|\mathcal{T}|c^{3})$ hyperedges.

Input: hypergraph $G=(E,V)$ with rank $r$, terminal set $\mathcal{T}$,
threshold parameter $c$, constant $C^{\prime}$.

Output: a $(\mathcal{T},c)$-sparsifier $H$.

1 $H\leftarrow G$.

$iter\leftarrow 0$. /* Number of iterations of the following while-loop. */

2 do

3 $G\leftarrow H$

4 $\phi^{-1}\leftarrow 4C^{\prime}rc^{4}\log^{3}{n}$.

5 $\\{V_{i}\\}_{i=1}^{t}\leftarrow\textsc{ExpanderDecompose}(G,\phi)$.

$G^{\prime}\leftarrow G$ /* Anchored sub-hypergraphs will be separated from
$G^{\prime}$ one by one. */

6 for  _each $i=1,2,\ldots,t$_ do

7 Apply the divide step in Algorithm 1 to $G^{\prime}$ with terminal
$\mathcal{T}$ and bipartition $(V_{i},\bigcup_{\ell=i+1}^{t}V_{\ell})$, and
get $G_{i}\leftarrow\hat{G^{\prime}}[V_{i}]$ and
$G^{\prime}\leftarrow\hat{G^{\prime}}[\bigcup_{\ell=i+1}^{t}V_{\ell}]$.

8 (For each boundary hyperedge $e$ with anchor vertices
$\mathdutchcal{v}_{e,3}$ and $\mathdutchcal{v}_{e,4}$ created on the
$\bigcup_{\ell=i+1}^{t}V_{\ell}$ side, we assign both $\mathdutchcal{v}_{e,3}$
and $\mathdutchcal{v}_{e,4}$ to an arbitrary $V_{j}$ such that $j>i$ and
$e\cap V_{j}\neq\emptyset$.)

$\\{H_{i}\\}_{i=1}^{t}\leftarrow\\{\textsc{$\phi$-Sparsify}(G_{i},V_{i}\cap\mathcal{T},\phi,r,c)\\}_{i=1}^{t}$.
/* The conquer step. */

$H\leftarrow H_{t}$ /* Each sparsifier $H_{i}$ will be merged with $H$ one by
one. */

9 for  _each $i=t-1,\ldots,1$_ do

10 Apply the combine step in Algorithm 1 to merge $H_{i}$ with $H$. That is,
all anchor vertices introduced at the divide step are removed and all
separated hyperedges are replaced by the boundary hyperedges before separating
$V_{i}$ from $\bigcup_{\ell=i}^{t}V_{\ell}$.

11 $iter=iter+1$.

12while  _$iter <\log{m}$._

return $H$.

Algorithm 6 SparsifyFast $(G,r,\mathcal{T},c,C^{\prime})$

With Algorithm 6, we are ready to prove Theorem 5.1.

###### Proof.

We show the correctness of Algorithm 6, the size of the sparsifier the
algorithm returns, and the time complexity.

###### Correctness.

We note that any $\phi$-expander graph $G$, adding new (anchor) vertices to
any existing hyperedge on $G$, is still an $\phi$-expander. Each iteration of
Algorithm 6 adopts the divide-and-conquer scheme described by Algorithm 1 is
justified by Lemma 3.5. Similarly, sparsifying $\phi$-expanders using
$\phi$-Sparsify described by Algorithm 5 is justified by Lemma 5.19.

###### Size of the sparsifier.

We first focus on how much Algorithm 6 can sparsify a hypergraph in one
iteration. Since ExpanderDecompose guarantees there are at most
$O(m\phi\log^{3}{n})$ inter-cluster hyperedges, in one iteration, there are at
most $O(rm\phi\log^{3}{n})$ separated hyperedges. Therefore, the total number
of all terminals (including the originally given terminals and additional
anchor terminals) is bounded by $|\mathcal{T}|+C^{\prime}rm\phi\log^{3}{n}$
for some constant $C^{\prime}$. In each iteration, let the algorithm set
$\phi=1/(4C^{\prime}rc^{4}\log^{3}{n})$, so
$\phi(C^{\prime}rc^{4}\log^{3}{n}+C^{\prime}\log^{3}{n})\leq\frac{1}{2}$.
Denote the total number of hyperedges after iteration $i$ as $m_{i}$, we have

$\displaystyle m_{i+1}$
$\displaystyle=(|\mathcal{T}|+C^{\prime}m_{i}r\phi\log^{3}{n})c^{3}+C^{\prime}m_{i}\phi\log^{3}{n}$
$\displaystyle=|\mathcal{T}|c^{3}+m_{i}\phi(C^{\prime}rc^{3}\log^{3}{n}+C^{\prime}\log^{3}{n})$
$\displaystyle\leq|\mathcal{T}|c^{3}+\frac{m_{i}}{2}.$

Notice that $m_{0}=m$. Therefore, after $\ell$ iterations, the number of
hyperedges is less than

$|\mathcal{T}|c^{3}\sum_{i=0}^{\ell-1}(\frac{1}{2^{i}})+\frac{m}{2^{\ell}}.$

After $O(\log{m})$ iterations, the algorithm returns a
$(\mathcal{T},c)$-sparsifier with $O(|\mathcal{T}|c^{3})$ hyperedges.

###### Time complexity.

In each iteration, the time is dominated by ExpanderDecompose and
$\phi$-Sparsify, which take $O(p^{1+o(1)})$ and $O(p+n(rc\phi^{-1})^{O(rc)})$
time repectively by Lemma 5.3 and Lemma 5.19. Notice that there are $\log m$
iterations, but in each iteration the number of hyperedges are halved.
Therefore we obtain the total running time
$O(p^{1+o(1)}+n(r^{2}c^{5}\log^{3}{n})^{O(rc)}\log{m})$ $=$
$O(p^{1+o(1)}+n(rc\log{n})^{O(rc)}\log m)$. ∎

This conclude the proof of Theorem 1.1 (1). For Part (2) of Theorem 1.1, we
observe that, by working with appropriate notions of expansion in hypergraphs,
the construction of Liu [Liu20] naturally extends to hypergraphs. We give the
proof for completeness in Appendix D.

## Acknowledgement

We thank Sorrachai Yingchareonthawornchai, Yang Liu, Yunbum Kook, and Richard
Peng for the discussion that inspires the notion of the pruned auxiliary graph
in this paper. We also thank anonymous reviewers for their valuable comments.

## References

  * [ADD+93] Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares.  On sparse spanners of weighted graphs.  Discrete & Computational Geometry, 9(1):81–100, 1993.
  * [BK15] András A Benczúr and David R Karger.  Randomized approximation schemes for cuts and flows in capacitated graphs.  SIAM Journal on Computing, 44(2):290–319, 2015.
  * [BST19] Nikhil Bansal, Ola Svensson, and Luca Trevisan.  New notions and constructions of sparsification for graphs and hypergraphs.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 910–928. IEEE, 2019.
  * [CDK+21] Parinya Chalermsook, Syamantak Das, Yunbum Kook, Bundit Laekhanukit, Yang P Liu, Richard Peng, Mark Sellke, and Daniel Vaz.  Vertex sparsification for edge connectivity.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1206–1225. SIAM, 2021.
  * [CKN20] Yu Chen, Sanjeev Khanna, and Ansh Nagda.  Near-linear size hypergraph cut sparsifiers.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 61–72. IEEE, 2020.
  * [CX18] Chandra Chekuri and Chao Xu.  Minimum cuts and sparsification in hypergraphs.  SIAM Journal on Computing, 47(6):2118–2156, 2018.
  * [EGIN97] David Eppstein, Zvi Galil, Giuseppe F Italiano, and Amnon Nissenzweig.  Sparsification—a technique for speeding up dynamic graph algorithms.  Journal of the ACM (JACM), 44(5):669–696, 1997.
  * [FHL08] Uriel Feige, MohammadTaghi Hajiaghayi, and James R. Lee.  Improved approximation algorithms for minimum weight vertex separators.  SIAM J. Comput., 38(2):629–657, 2008.
  * [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 Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2046–2065. SIAM, 2020.
  * [HDLT01] Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup.  Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity.  Journal of the ACM (JACM), 48(4):723–760, 2001.
  * [JS22] Wenyu Jin and Xiaorui Sun.  Fully dynamic st edge connectivity in subpolynomial time.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 861–872. IEEE, 2022.
  * [KK15] Dmitry Kogan and Robert Krauthgamer.  Sketching cuts in graphs and hypergraphs.  In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 367–376, 2015.
  * [KKTY21] Michael Kapralov, Robert Krauthgamer, Jakab Tardos, and Yuichi Yoshida.  Towards tight bounds for spectral sparsification of hypergraphs.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 598–611, 2021.
  * [KKTY22] Michael Kapralov, Robert Krauthgamer, Jakab Tardos, and Yuichi Yoshida.  Spectral hypergraph sparsifiers of nearly linear size.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1159–1170. IEEE, 2022.
  * [KR13] Robert Krauthgamer and Inbal Rika.  Mimicking networks and succinct representations of terminal cuts.  In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 1789–1799. SIAM, 2013.
  * [KR14] Arindam Khan and Prasad Raghavendra.  On mimicking networks representing minimum terminal cuts.  Information Processing Letters, 114(7):365–371, 2014.
  * [KW20] Stefan Kratsch and Magnus Wahlström.  Representative sets and irrelevant vertices: New tools for kernelization.  J. ACM, 67(3):16:1–16:50, 2020.
  * [Liu20] Yang P. Liu.  Vertex sparsification for edge connectivity in polynomial time.  CoRR, abs/2011.15101, 2020.
  * [Lov77] László Lovász.  Flats in matroids and geometric graphs.  Combinatorial Surveys, Proc. Sixth British Combinatorial Conf., Royal Holloway Coll., Egham, pages 45–86, 1977.
  * [LS22] Yaowei Long and Thatchaphol Saranurak.  Near-optimal deterministic vertex-failure connectivity oracles.  CoRR, abs/2205.03930, 2022.
  * [LSS20] Daniel Lokshtanov, Saket Saurabh, and Vaishali Surianarayanan.  A parameterized approximation scheme for min $k$-cut.  In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS, 2020.
  * [Mar09] Dániel Marx.  A parameterized view on matroid optimization problems.  Theor. Comput. Sci., 410(44):4471–4479, 2009.
  * [NI92] Hiroshi Nagamochi and Toshihide Ibaraki.  A linear-time algorithm for finding a sparsek-connected spanning subgraph of ak-connected graph.  Algorithmica, 7(1):583–596, 1992.
  * [PSS19] Richard Peng, Bryce Sandlund, and Daniel D Sleator.  Optimal offline dynamic 2, 3-edge/vertex connectivity.  In Workshop on Algorithms and Data Structures, pages 553–565. Springer, 2019.
  * [ST11] Daniel A Spielman and Shang-Hua Teng.  Spectral sparsification of graphs.  SIAM Journal on Computing, 40(4):981–1025, 2011.
  * [SY19] Tasuku Soma and Yuichi Yoshida.  Spectral sparsification of hypergraphs.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2570–2581. SIAM, 2019.

##  Appendix A Omitted Content from Section 3

###  A.1 Proof of Lemma 3.5 Part 2

In this subsection we show that
$\mathrm{mincut}_{H}^{c}(\pi(A),\pi(B))\geq\mathrm{mincut}_{G}^{c}(A,B)$.

We first assume that $(Y,\pi(V)\setminus Y)$ is a $(\pi(A),\pi(B))$-mincut of
value at most $c$.

Let $S=E_{G}(V_{1},V_{2})$. We know that $H$ is defined by $H_{1}\cup
H_{2}\cup S-\mathit{Sep}(S,V_{1},V_{2})$, where $H_{1}$ is a
$(\mathcal{T}_{1},c)$-sparsifier of $\hat{G}[V_{1}]$ and $H_{2}$ is a
$(\mathcal{T}_{2},c)$-sparsifier of $\hat{G}[V_{2}]$. Again, we define the
cuts $Y_{1}$ and $Y_{2}$ respectively. We first add $Y\cap\pi(V_{1})$ to
$Y_{1}$, then for each separated hyperedge $\pi(e)$ where $e\in S$ there are
three cases for adding the terminal vertices into $Y_{1}$: we add
$\\{\pi(\mathdutchcal{v}_{e,1}),\pi(\mathdutchcal{v}_{e,2})\\}$ to $Y_{1}$ if
$\pi(e)\subseteq Y$; we add $\pi(\mathdutchcal{v}_{e,1})$ to $Y_{1}$ if
$\pi(e)\not\subseteq Y$ and $\pi(e)\cap Y\neq\emptyset$; we add nothing if
$\pi(e)\cap Y=\emptyset$. Similarly we define $Y_{2}$ by adding
$Y\cap\pi(V_{2})$ and corresponding anchor vertices.

Now we have two cuts $(Y_{1},\pi(\hat{V}_{1})\setminus Y_{1})$ and
$(Y_{2},\pi(\hat{V}_{2})\setminus Y_{2})$ with values $y_{1}$ and $y_{2}$.
Each of them has value at most the value to the cut $(Y,\pi(V)\setminus Y)$ so
we know that both $y_{1},y_{2}\leq c$. They are
$(\pi(A^{\mathsf{ext}}|_{V_{1}\cup A_{1}}),\pi(B^{\mathsf{ext}}|_{V_{1}\cup
A_{1}}))$-cut and $(\pi(A^{\mathsf{ext}}|_{V_{2}\cup
A_{2}}),\pi(B^{\mathsf{ext}}|_{V_{2}\cup A_{2}}))$-cut respectively.

By definition of $(\mathcal{T}_{1},c)$-sparsifier and
$(\mathcal{T}_{2},c)$-sparsifier, there exists a
$(A^{\mathsf{ext}}|_{V_{1}\cup A_{1}},B^{\mathsf{ext}}|_{V_{1}\cup
A_{1}})$-mincut $(X_{1},\hat{V}_{1}\setminus X_{1})$ and a
$(A^{\mathsf{ext}}|_{V_{2}\cup A_{2}},B^{\mathsf{ext}}|_{V_{2}\cup
A_{2}})$-mincut $(X_{2},\hat{V}_{2}\setminus X_{2})$ whose cut values are
$x_{1}\leq y_{1}$ and $x_{2}\leq y_{2}$.

Now, notice that $y_{1}+y_{2}=|\partial Y|+|\partial Y\cap\pi(S)|$. Here we
emphasize that $\partial Y\cap\pi(S)$ may be a multiset, as there could be
many hyperedges being contracted into the same subset of vertices. Again, let
$X=X_{1}\cup X_{2}\cup S-\mathit{Sep}(S,V_{1},V_{2})$, we know that $|\partial
X|=x_{1}+x_{2}-|(\partial X)\cap S|$. Since all edge $e\in S$ such that
$\pi(e)\in\partial Y$ were not contracted (they must be essential as such
edges appear in every $(A^{\mathsf{ext}}|_{V_{i}\cup
A_{i}},B^{\mathsf{ext}}|_{V_{i}\cup A_{i}})$-mincut for both $i\in\\{1,2\\}$),
we know that $|(\partial X)\cap S|\geq|\partial Y\cap\pi(S)|$. Hence, we have

$\displaystyle\mathrm{mincut}_{G}^{c}(A,B)$ $\displaystyle\leq|\partial X|$
$\displaystyle=x_{1}+x_{2}-|(\partial X)\cap S|$ $\displaystyle\leq
y_{1}+y_{2}-|(\partial Y)\cap\pi(S)|$ $\displaystyle=|\partial Y|$
$\displaystyle=\mathrm{mincut}_{H}^{c}(\pi(A),\pi(B))$

as desired. $\square$

###  A.2 Proof of Lemma 3.6

See 3.6

###### Proof to Lemma 3.6.

Let $k=|\mathcal{T}|$. It suffices to show that whenever $G$ has $6kc^{2}+1$
edges, there exists one hyperedge $e$ so that $G/e$ is a
$(\mathcal{T},c)$-sparsifier of $G$ and that $\mathcal{T}$ is still
$(5c,c)$-edge-unbreakable in $G/e$.

Intuitively, to find such an hyperedge, we start with reducing the
$c$-thresholded hyperedge connectivity into vertex $c$-connectivity by
carefully constructing the graph $G_{\mathsf{split}}$ from $G$. Then, we apply
the powerful technique discovered by Kratsch and Wahlström [KW20] on
$G_{\mathsf{split}}$, which defines a representable matroid
$\mathcal{M}_{1}\oplus\mathcal{M}_{2}\oplus\mathcal{M}_{3}$ based on
$G_{\mathsf{split}}$ and its two variants $G_{\mathsf{split}}^{\prime}$ and
$G_{\mathsf{split}}^{\prime\prime}$. Followed by a carefully chosen collection
of subsets $\mathcal{J}$, there exists a representative set
$\mathcal{J}^{*}\subseteq\mathcal{J}$ of size at most
$\mathrm{rank}(\mathcal{M}_{1})\mathrm{rank}(\mathcal{M}_{2})\mathrm{rank}(\mathcal{M}_{3})\leq
6kc^{2}$. Moreover, the elements of $\mathcal{J}$ corresponds to vertices and
hyperedges in $G$. Since $G$ has at least $6kc^{2}+1$ hyperedges, at least one
hyperedge $e$ on $G$ is not _essential_ , and hence contractable. The above
process for finding a contractable edge $e$ will be repeated until there are
at most $6kc^{2}$ hyperedges left.

Let $G=(V,E)$ be a hypergraph and let $\mathcal{T}\subseteq V$ be a set
terminal vertices. We first construct the undirected _incidence_ bipartite
graph $G^{\textsf{inc}}=(V^{\textsf{inc}},E^{\textsf{inc}})$ as the following:

$\displaystyle V^{\textsf{inc}}$ $\displaystyle=V\cup E$ $\displaystyle
E^{\textsf{inc}}$ $\displaystyle=\\{\\{v,e\\}\ |\ v\in V,e\in E,\text{ and
}v\in e\\}.$

Now, we perform a reduction from hyperedge cuts on $G$ to $c$-thresholded
vertex cuts on $G^{\textsf{inc}}$ similar to [Liu20] and construct a directed
graph $G_{\mathsf{split}}$ based on the incidence graph $G^{\textsf{inc}}$:
for each vertex $v\in V^{\textsf{inc}}\cap V$ we split $v$ into a
$(c+1)$-clique on $G^{\textsf{inc}}$, then we replace each undirected edge
$\\{v,e\\}$ in $E^{\textsf{inc}}$ with two directed edges $(v,e)$ and $(e,v)$.
In A.1 we show that all $c$-thresholded hyperedge mincuts on $G$ correspond to
some $c$-thresholded vertex mincuts on $G_{\mathsf{split}}$. The definition of
$G_{\mathsf{split}}$ inherently defines a mapping $\pi:V\cup E\to
V_{\textsf{split}}$ where for each $v\in V$, $\pi(v)$ is assigned to be any of
the $c+1$ vertices split from $v$.

######  Claim A.1.

Let $A,B\subseteq V$ with $\mathrm{mincut}_{G}(A,B)\leq c$. Let
$A_{\textsf{split}}=\pi(A)$ and $B_{\textsf{split}}=\pi(B)$. Then the minimum
vertex cut $C_{\textsf{split}}\subseteq V_{\textsf{split}}$ that separates
$A_{\textsf{split}}$ and $B_{\textsf{split}}$ on $G_{\mathsf{split}}$ has size
$|C_{\textsf{split}}|=\mathrm{mincut}_{G}(A,B)$.

###### Proof of A.1.

First, it is straightforward to check that
$|C_{\textsf{split}}|\leq\mathrm{mincut}_{G}(A,B)$: let $(X,V\setminus X)$ be
an $(A,B)$-mincut on $G$ with $|\partial X|=\mathrm{mincut}_{G}(A,B)$. Hence,
$\pi(\partial X)$ is a vertex cut that separates $\pi(A)$ and $\pi(B)$ on
$G^{\textsf{inc}}$ of the same size.

Now we show that $|C_{\textsf{split}}|\geq\mathrm{mincut}_{G}(A,B)$. Notice
that since $|C_{\textsf{split}}|\leq\mathrm{mincut}_{G}(A,B)\leq c$,
$C_{\textsf{split}}$ does not contain split vertices from $V$. Hence,
$\pi^{-1}(C_{\textsf{split}})$ is a $(A,B)$-cut on $G$, and the result
follows. ∎

Now, we define $G_{\mathsf{split}}^{\prime}$ and
$G_{\mathsf{split}}^{\prime\prime}$ from $G_{\mathsf{split}}$. Both
$G_{\mathsf{split}}^{\prime}$ and $G_{\mathsf{split}}^{\prime\prime}$ are
initialized as $G_{\mathsf{split}}$. For each vertex $v\in
G_{\mathsf{split}}$, we create an sink-copy $v^{\prime}$ in
$G_{\mathsf{split}}^{\prime}$ and for each edge $(u,v)\in G_{\mathsf{split}}$
we add an edge $(u,v^{\prime})$ to $G_{\mathsf{split}}^{\prime}$. Similarly,
for each vertex $v\in G_{\mathsf{split}}$, we create an source-copy
$v^{\prime\prime}$ in $G_{\mathsf{split}}^{\prime\prime}$ and for each edge
$(v,w)\in G_{\mathsf{split}}$ we add an edge $(v^{\prime\prime},w)$ to
$G_{\mathsf{split}}^{\prime\prime}$. In order to define gammoid we specify the
terminal set $\mathcal{T}_{\textsf{split}}=\pi(\mathcal{T})$ on both
$G_{\mathsf{split}}^{\prime}$ and $G_{\mathsf{split}}^{\prime\prime}$.

###### Matroid Construction.

We define a representable matroid
$\mathcal{M}=\mathcal{M}_{1}\oplus\mathcal{M}_{2}\oplus\mathcal{M}_{3}$ as
follows.

  * •

Let $\mathcal{M}_{1}=(V_{\textsf{split}},{V_{\textsf{split}}\choose{\leq c}})$
be the uniform matroid of rank $c$ over the vertices on $V_{\textsf{split}}$.

  * •

Let $\mathcal{M}_{2}$ be the gammoid over $G_{\mathsf{split}}^{\prime}$ with
respect to the terminal set $\mathcal{T}_{\textsf{split}}$.

  * •

Let $\mathcal{M}_{3}$ be the gammoid over $G_{\mathsf{split}}^{\prime\prime}$
with respect to the terminal set $\mathcal{T}_{\textsf{split}}$ but
restricting the rank to $6c$ (getting rid of all independent sets larger than
$6c$).

$\mathcal{M}_{1}$ has rank $c$, $\mathcal{M}_{2}$ has rank at most $k$, and
$\mathcal{M}_{3}$ has rank at most $6c$. Let
$\mathcal{J}=\\{(v,v^{\prime},v^{\prime\prime})\ |\ v\in
V_{\textsf{split}}\cap E\\}$ be a collection of subsets in $\mathcal{M}$.
According to the theorem of representative set (Lemma A.2), there exists a
representative set $\mathcal{J}^{*}$ of size at most
$\mathrm{rank}(\mathcal{M}_{1})\mathrm{rank}(\mathcal{M}_{2})\mathrm{rank}(\mathcal{M}_{3})\leq
6kc^{2}$.

######  Lemma A.2 ([Liu20, Mar09, Lov77]).

Let $\mathcal{M}_{i}=(S_{i},\mathcal{I}_{i})$ be representable matroids over a
field $\mathbb{F}$ for $1\leq i\leq p$, and let
$\mathcal{M}=\mathcal{M}_{1}\oplus\mathcal{M}_{2}\oplus\cdots\oplus\mathcal{M}_{p}$
be their direct sum. Define

$S_{1}\times S_{2}\times\cdots\times S_{p}=\\{\\{x_{1},x_{2},\ldots,x_{p}\\}\
:\ x_{i}\in S_{i}\\}.$

That is, the collection of subsets of $S$ that have exactly one element from
each $S_{i}$. Then every subset $\mathcal{J}\subseteq(S_{1}\times
S_{2}\times\cdots\times S_{p})$ has a representative set $\mathcal{J}^{*}$ of
size at most $\prod_{i=1}^{p}\mathrm{rank}(\mathcal{M}_{i})$, and
$\mathcal{J}^{*}$ is computable in time $|\mathcal{J}|^{O(1)}$.

###### Essential Vertices.

We say that a vertex $v$ is _essential_ if there exists a bipartition
$(A_{\textsf{split}},B_{\textsf{split}})$ of $\mathcal{T}_{\textsf{split}}$
with the minimum vertex cut between $A_{\textsf{split}}$ and
$B_{\textsf{split}}$ at most $c$ and that $v$ appears in every minimum vertex
cut between $A_{\textsf{split}}$ and $B_{\textsf{split}}$.

Now the key observation is that for each essential vertex $v$, the
corresponding triple $(v,v^{\prime},v^{\prime\prime})$ must appear in any
representative set $\mathcal{J}^{*}$. Let $v$ be an essential vertex with
respect to the bipartition $(A_{\textsf{split}},B_{\textsf{split}})$. By the
definition of $(5c,c)$-edge-unbreakable we may assume that
$|B_{\textsf{split}}|<5c$. Fix any minimum
$(A_{\textsf{split}},B_{\textsf{split}})$-cut $C_{\textsf{split}}$, and
consider the following independent set
$I=(C_{\textsf{split}}\setminus\\{v\\},A_{\textsf{split}}\cup
C_{\textsf{split}},B_{\textsf{split}}\cup C_{\textsf{split}})$ in
$\mathcal{M}$. Now, if there is another
$(u,u^{\prime},u^{\prime\prime})\in\mathcal{J}^{*}$ with $u\notin
C_{\textsf{split}}$ then we must have
$(C_{\textsf{split}}\setminus\\{v\\}\cup\\{u\\},A_{\textsf{split}}\cup
C_{\textsf{split}}\cup\\{u^{\prime}\\},B_{\textsf{split}}\cup
C_{\textsf{split}}\cup\\{u^{\prime\prime}\\})\notin\mathcal{M}$ because of the
following reason: (1) the first component disallows $u\in C_{\textsf{split}}$,
(2) since $u\notin C_{\textsf{split}}$, $u$ is not essential, and it is
impossible to have vertex disjoint paths going from
$\mathcal{T}_{\textsf{split}}$ to $A_{\textsf{split}}\cup
C_{\textsf{split}}\cup\\{u^{\prime}\\}$ and vertex disjoint paths going from
$\mathcal{T}_{\textsf{split}}$ to $B_{\textsf{split}}\cup
C_{\textsf{split}}\cup\\{u^{\prime\prime}\\}$ at the same time (otherwise
$C_{\textsf{split}}$ does not separate $A_{\textsf{split}}$ and
$B_{\textsf{split}}$). In addition, since $v$ is essential, there no other
mincut closer to $A_{\textsf{split}}$ or closer to $B_{\textsf{split}}$ that
does not include $v$. Hence, adding $(v,v^{\prime},v^{\prime\prime})$ to $I$
will result in independent set. Therefore, $(v,v^{\prime},v^{\prime\prime})$
is required to appear in any representatitve set. By Lemma A.2, the number of
essential hyperedges is at most $6kc^{2}=O(kc^{2})$ as desired. ∎

We can extend the proof to Lemma 3.6 when we allow $(d,c)$-edge-unbreakable
terminal sets with an arbitrary value $d$. The same proof holds except that we
restrict $\mathcal{M}_{3}$ to have rank at most $(d+c)$. So the total number
of essential edges are at most $O(|\mathcal{T}|c(d+c))$ and they can be
constructed in polynomial time.

######  Corollary A.3.

Let $G=(V,E)$ be a hypergraph and let $\mathcal{T}\subseteq V$ be a set of
degree-1 terminals. If $\mathcal{T}$ is $(d,c)$-edge-unbreakable on $G$, then
there exists a subset $E^{\prime}\subseteq E$ with $O(|\mathcal{T}|c(d+c))$
hyperedges, such that $G/(E-E^{\prime})$ is a $(\mathcal{T},c)$-sparsifier of
$G$. Moreover, the set $E^{\prime}$ can be computed in $\text{poly}(m,n)$
time.

##  Appendix B Existence and Uniqueness of $A$-minimal $(A,B)$-mincut

In this section, we show the proof of Proposition 5.11

See 5.11

###### Proof.

Let $f_{G}:2^{V}\to\mathbb{R}$ be a function and $f_{G}(X)=|\partial X|$. We
write $f_{G}$ as $f$ for simplicity and claim that $f$ is a submodular
function: For arbitrary $X,Y\subseteq V$, we separate the hypergraph into
disjoint four parts $Y\setminus X$, $X\setminus Y$, $X\cap Y$, and
$V\setminus(X\cup Y)$. By identifying $\partial X$ and $\partial Y$ as
disjoint unions of crossing hyperedges between the four parts, we have

$\displaystyle f(X)+f(Y)$ $\displaystyle=|\partial X|+|\partial Y|$
$\displaystyle=(|E(X\setminus Y,V\setminus(Y\cup X))|+|E(X\setminus
Y,Y\setminus X)|$ $\displaystyle\quad+|E(X\cap Y,V\setminus(Y\cup
X))|+|E(X\cap Y,Y\setminus X)|)$ $\displaystyle\quad+(|E(Y\setminus
X,V\setminus(X\cup Y))|+|E(Y\setminus X,X\setminus Y)|$
$\displaystyle\quad+|E(Y\cap X,V\setminus(X\cup Y))|+|E(Y\cap X,X\setminus
Y)|)$

On the other hand, similarly we have

$\displaystyle f(X\cup Y)+f(X\cap Y)$ $\displaystyle=|\partial{(X\cup
Y)}|+|\partial{(X\cap Y)}|$ $\displaystyle=(|E(X\setminus Y,V\setminus(X\cup
Y))|+|E(X\cap Y,V\setminus(X\cup Y))|$ $\displaystyle\quad+|E(Y\setminus
X,V\setminus(X\cup Y))|)+(|E(X\cap Y,Y\setminus X)|$
$\displaystyle\quad+|E(X\cap Y,X\setminus Y)|+|E(Y\cap X,V\setminus(X\cup
Y))|)$

Therefore, $f(X)+f(Y)-f(X\cup Y)-f(X\cup Y)=2|E(X\setminus Y,Y\setminus
X)|\geq 0$ and finally get

$f(X)+f(Y)\geq f(X\cup Y)+f(X\cap Y)$

$f$ is submodular function.

If $(X,V\setminus X)$ and $(Y,V\setminus Y)$ are $(A,B)$-mincuts, by the
submodular property, $f(X\cup Y),f(X\cap Y)$ are also equal to the
$(A,B)$-mincut size, which indicates $(X\cup Y,V\setminus(X\cup Y))$ and
$(X\cap Y,V\setminus(X\cap Y))$ are also $(A,B)$-mincuts. Giving that $(X\cap
Y,V\setminus(X\cap Y))$ is a $(A,B)$-mincut, the $X^{*}$ of the $A$-minimal
partition$(X^{*},V\setminus X^{*})$ is simply the intersection of all
$X\subset V$ such that $(X,V\setminus X)$ is a $(A,B)$-mincut. The existence
and uniqueness of $A$-minimal partition are verified by construction. ∎

##  Appendix C Use LocalMinCut to find $A$-minimal $(A,B)$-mincut

In this section we describe how to apply [FNY+20] to prove Theorem 5.13.

Lemma 5.12 reduces the problem of testing whether a terminal partition
$(A,\mathcal{T}\setminus A)$ is useful to checking whether the $A$-minimal
$(A,\mathcal{T}\setminus A)$-mincut is connected. In this subsection, we show
how to further reduce the problem from a hypergraph setting to a normal
directed graph setting, so that results in [FNY+20] can directly solve it.

We first convert the hypergraph into an _incidence graph_ ,

######  Definition C.1 (Incidence Graph of a Hypergraph).

We say a normal graph $G=(V^{\prime},E^{\prime})$ is the incidence graph of a
hypergraph $H=(V,E)$ if $V^{\prime}=V\cup E$ and $E^{\prime}=\\{(v,e)|v\in
V,e\in E,v\in e\ in\ H\\}$.

We note that $G$ is a bipartite graph. The incidence graph is a normal graph
and also inherits the connectivity of the hypergraph.

Then we replace each vertex by an in-vertex and an out-vertex in $G$. We
connect a pair of in-vertex and out-vertex with 1 (c + 1) edge if the vertex
represents a hyperedge (vertex) in $H$. Lastly we replace each edge by two
directed edge of reverse directions. The above reduction is a common way to
reduce edge to vertex connectivity and undirected to directed setting, except
that we add $(c+1)$ multi-edges between certain in-vertices and out-vertices
to prevent all $v\in V$ from being cut vertex in $G$.

From the above manipulation to $G$, we get a normal directed graph
$G^{\prime}$. An important observation is that the $A$-minimal $(A,B)$-mincut
in $G$ exactly corresponds to the $A$-minimal $(A,B)$-mincut in $H$.
Therefore, the problem of finding the $A$-minimal $(A,B)$-mincut in $H$ is
reduced to finding the $A$-minimal $(A,B)$-mincut in $G^{\prime}$, which can
be directly solved by the following result in [FNY+20].

######  Lemma C.2 ([FNY+20]).

Let $G^{\prime}$ be a normal graph. Suppose that the $A$-minimal
$(A,B)$-mincut $S$ has size at most $c$ and volume $\mathrm{vol}(S)=\sum_{v\in
S}\deg_{G^{\prime}}(v)\leq\nu$ in a normal directed graph. Then, there is an
algorithm that finds $S$ in $O(\nu c^{2}\log n)$ time with high probability.

###### Proof of Theorem 5.13..

Notice that each vertex in $G^{\prime}$ may have $c$ more incident edges than
$G$. Hence, the volume of the same $A$-minimal $(A,\mathcal{T}\setminus
A)$-mincut in $G^{\prime}$ is boosted up by at most a factor of $c$. ∎

##  Appendix D Proof of Part (2) of Theorem 1.1

In this section we extend Liu’s result [Liu20] and prove the following
theorem.

######  Theorem D.1.

Let $G$ be a hypergraph with $n$ vertices, $m$ hyperedges, and a set
$\mathcal{T}\subseteq V$ of degree-1 terminals with $|\mathcal{T}|\leq kc$.
There exists an algorithm that constructs a $(\mathcal{T},c)$-sparsifier of
$G$ with $O(kc^{3}\log^{1.5}(kc))$ hyperedges in $\mathrm{poly}(m,n)$ time.

The main runtime bottleneck to SparsifySlow (Algorithm 2) is in Algorithm 2.
That is, it is not known if there is an polynomial time algorithm that tests
whether the current terminal set $\mathcal{T}^{\prime}$ is $(5c,c)$-edge-
unbreakable in the subproblem $G^{\prime}$. Fortunately, this problem can be
modeled as a sparsest cut problem with a non-uniform demand. If we allow a
$\text{polylog}(k)$ factor on the number of hyperedges in the final
$(\mathcal{T},c)$-sparsifer, we don’t have to apply divide and conquer
framework until we have a $(5c,c)$-edge-unbreakable terminal set. For example,
a $(c\log^{1.5}(kc),c)$-edge-unbreakable terminal set suffices to obtain a
sparsifier of $O(kc^{2}\log^{1.5}(kc))$ hyperedges by Corollary A.3.

Let us now describe the sparsest cut problem (with non-uniform demand) we are
reducing to. We first define _terminal expansion_ :

######  Definition D.2 (terminal expansion).

A hypergraph $G=(V,E)$ with terminal set $\mathcal{T}\subseteq V$ is a
$\phi$-terminal expander if

$\frac{|\partial X|}{\min\\{|X\cap\mathcal{T}|,|(V\setminus
X)\cap\mathcal{T}|\\}}\geq\phi\ \ \text{for any subset of vertices $X\subseteq
V$.}$

We remark that whenever $\phi=O(\log^{-1.5}(kc))$, if the graph $G$ with a
terminal set $\mathcal{T}$ is a $\phi$-terminal expander, then $\mathcal{T}$
is $(O(c\log^{1.5}(kc)),c)$-edge-unbreakable. Therefore, the base cases are
solved. All we have to do now is to find a proper way to check if the
hypergraph in a subproblem is a $\phi$-terminal expander. Furthermore, if it
is not the case, we should be able to identify a good-enough sparse cut
$(V_{1},V_{2})$ that enables the divide and conquer approach.

Let us now translate the edge cuts in this hypergraph $G$ to vertex cuts in
the incidence graph representation (see Definition C.1). On this incidence
graph $G^{\textsf{inc}}=(V^{\textsf{inc}}=V\cup E,E^{\textsf{inc}})$ we define
two functions over $V^{\textsf{inc}}$:

$\begin{array}[]{ll}\pi_{1}(x)=\begin{cases}1&\text{if $x\in E$,}\\\
\infty&\text{otherwise, $x\in
V$.}\end{cases}&\pi_{2}(x)=\begin{cases}1&\text{if $x\in\mathcal{T}$,}\\\
0&\text{otherwise.}\end{cases}\end{array}$

It is straightforward to check that among all vertex partition
$(A,B,S\subseteq E)$,

$\mathsf{OPT}:=\min_{A^{\prime},B^{\prime},S^{\prime}}\frac{\pi_{1}(S^{\prime})}{\pi_{2}(A^{\prime}\cup
S^{\prime})\pi_{2}(B^{\prime}\cup S^{\prime})}$

is 2-approximating the terminal expansion. The following theorem gives a
sparsest vertex cut solver that returns an
$O(\sqrt{\log(kc)})$-approximated222The approximate ratio is actually
$\sqrt{\log|\text{supp}(\pi_{2})|}$. Notice that the support of $\pi_{2}$ is
$|\mathcal{T}|\leq kc$. sparse cut in polynomial time.

######  Theorem D.3 ([FHL08] Theorem 3.12).

Given a graph $G=(V,E)$ and vertex weights
$\pi_{1},\pi_{2}:V\to\mathbb{R}_{+}$, there exists a polynomial-time algorithm
which computes a vertex separator $(A,B,S)$ for which

$\frac{\pi_{1}(S)}{\pi_{2}(A\cup S)\pi_{2}(B\cup
S)}\leq\beta\cdot\mathsf{OPT},$

where $\beta=O(\sqrt{\log(kc)})$ is the approximation ratio.

Now, we can use an approximate sparsest cut solver that either (1) certifies
that the $\mathcal{T}^{\prime}$ is $(c\log^{1.5}(kc),c)$-edge-unbreakable, or
(2) finds a violating partition $(V_{1},V_{2})$ such that the number of
crossing hyperedges is at most $\frac{1}{2\log(kc)}|\mathcal{T}^{\prime}\cap
V_{i}|$ for both $i\in\\{1,2\\}$. Notice that it implies that in the
subproblems the amount of terminal vertices are increased by only a
$1/\log(kc)$ factor since we add 2 anchor vertices to each separated
hyperedge. We summarize the algorithm in Algorithm 7.

PolyTimeSparsifier$(G,\mathcal{T},c)$

Input: hypergraph $G=(V,E)$, terminal set $\mathcal{T}$, constant $c$.

Output: a $(\mathcal{T},c)$-sparsifier $H$.

1 $\phi\leftarrow 1/(4\beta\log(kc))$.

2 Run a sparse cut solver and obtain a bipartition $(V_{1},V\setminus V_{2})$.

3 Compute terminal expansion $\hat{\phi}:=\frac{|\partial
V_{1}|}{\min\\{|V_{1}\cap\mathcal{T}|,|V_{2}\cap\mathcal{T}|\\}}$.

4 if  _$\hat{\phi}\geq 2\beta\phi$_ then

// guaranteed $\phi$-terminal expander.

5 return a $(\mathcal{T},c)$-sparsifier using Corollary A.3.

6else

// found a sparse cut.

7 Apply divide and conquer framework (Algorithm 1) on $(V_{1},V_{2})$.

Algorithm 7 PolyTimeSparsifier

###### Proof of Theorem D.1.

The correctness is entirely based on the divide and conquer framework (Lemma
3.5). The runtime is $\text{poly}(mn)$ because of Corollary A.3 and Theorem
D.3. Now, in order to give an upper bound of hyperedges from the returned
$(\mathcal{T},c)$-sparsifier, it suffices to bound the total number of
terminal vertices over all base cases.

Let $f(x)$ be an upper bound of total number of terminal vertices over all
base cases when started with a terminal set of $x$ vertices. We first assume
that $f$ is a non-decreasing function and $f$ is concave. So, according to the
divide and conquer criteria, we know that if a terminal set of $x$ vertices is
split into $y$ terminal vertices and $x-y$ terminal vertices (without loss of
generality $y\leq x-y$), the number of hyperedges crossing the cut is at most

$\hat{\phi}y\leq 2\beta\phi y=\frac{1}{2\log(kc)}y.$

Hence, by adding 2 anchor vertices to each separated hyperedge we have

$\displaystyle f(x)$ $\displaystyle\leq
f\left(y+2\textstyle\frac{1}{2\log(kc)}y\right)+f\left(x-y+2\textstyle\frac{1}{2\log(kc)}y\right)$
$\displaystyle\leq
2f\left(\left(1+\textstyle\frac{1}{\log(kc)}\right)\frac{x}{2}\right)$ (by
concavity and non-decreasing) $\displaystyle\leq 2^{\log
x}f\left(\textstyle\left(1+\frac{1}{\log(kc)}\right)^{\log x}\right)$
(induction on $x$) $\displaystyle\leq 2^{\log x}f(\exp(1))$ (as long as $x\leq
kc$) $\displaystyle=\Theta(x).$

So, choosing $f:[1,kc]\to\mathbb{R}$ to be a linear function serves as an
upper bound. By Corollary A.3 the total number of hyperedges in the returned
$(\mathcal{T},c)$-sparsifier is then
$O(|\mathcal{T}|c^{2}\log^{1.5}(kc))=O(kc^{3}\log^{1.5}(kc))$. ∎