$d_{G^{ext}_{\ell+1}}(X)\geq d_{G^{ext}_{\ell}}(X)\geq\tau$. The remaining
case is that there exists a chain edge inside $X$. A chain edge connects two
maximal supreme sets (defined in $G_{\ell}$), so $X$ is not extreme in
$G_{\ell}$ and hence not extreme in $G_{\ell+1}$ by Lemma 5.10, and there
exists an extreme violator $W$ of $X$ in $G_{\ell+1}$, $d_{G_{\ell+1}}(W)\leq
d_{G_{\ell+1}}(X)$. Because $W\subsetneqq X$,
$\beta_{\ell+1}(W)\leq\beta_{\ell+1}(X)$. So

$d_{G^{ext}_{\ell+1}}(W)=d_{G_{\ell+1}}(W)+\beta_{\ell+1}(W)\leq
d_{G_{\ell+1}}(X)+\beta_{\ell+1}(X)=d_{G^{ext}_{\ell+1}}(X)$

which contradicts the assumption that $X$ is a minimal Steiner min cut in
$G^{ext}_{\ell+1}$. So this case is impossible, and the Steiner connectivity
is at least $\tau$.

####  5.2.2 Finding Augmentation Chains

Next we describe the detailed steps to find an augmentation chain efficiently.
We first establish the algorithm, with a slight modification in the heavy-
light decomposition of external augmentation, then prove it always finds
augmentation chains in Lemma 5.19.

Let $L_{2}$ be the collection of $R\in L$ such that $R$ is critical and all
ancestors of $R$ are not critical. Let $L_{high}$ be the union of paths from
nodes in $L_{2}$ to the roots, that is a sub-forest of $L$ with leaves
$L_{2}$. In the external augmentation algorithm, modify the heavy-light
decomposition step such that the heavy paths stop at nodes in $L_{2}$. More
precisely, apply heavy-light decomposition on $L_{high}$, then separately
apply heavy-light decomposition on each subtree rooted at a node in $L_{2}$,
and then merge the heavy-light decompositions. This way, a leaf to root path
still passes $O(\log n)$ heavy paths, so all proofs in Section 5.1 work for
the new definition. But now, each heavy path stops at a leaf or a node in
$L_{2}$, which is critical. We say that the heavy-light decomposition on
$L_{high}$ is _upper level_ , and the ones on the subtrees rooted at $L_{2}$
are _lower level_.

We maintain the forest $L_{high}$. For lower level heavy paths, regard them as
contracted into their ancestors in $L_{2}$. For each $R\in L_{high}$, maintain
the cut value $c(R)$, which is initialized to $d(\mu(R))$. We assign an
external edge to a heavy path if the edge is added by the external
augmentation algorithm when processing the heavy path. In each iteration, we
list all roots of $L_{high}$, and pick the roots $R_{i}$ with
$c(R_{i})\leq\tau-2$ to form a list $Q_{T}=(R_{1},\ldots,R_{r})$, such that
$c(R_{1})$ and $c(R_{r})$ are the minimum two in $Q_{T}$. Pick a chain
$F=\\{(a_{i},b_{i+1})\\}_{1\leq i\leq r-1}$, such that $a_{i},b_{i}$ are
vacant vertices (having unused external edges) assigned to heavy paths in the
tree rooted at $R_{i}$. (When $a_{i}=b_{i}$, it needs two vacant degrees.) We
use the external edges assigned to lower level paths first. The external edges
assigned to upper level paths are used only when all lower level degrees in
the tree are used.

After picking a chain, we add it to the solution, and update the vacant
degrees. Next we update $c(R)$ values. For each endpoint $u$ in the chain,
define its _representative leaf_ $U\in L_{2}$ as follows. If $u$ is assigned
to an upper level path, let $U$ be the leaf of the heavy path to which $u$ is
assigned. If $u$ is assigned to a lower level path, let $U$ be the node to
which that path is contracted. Add 1 to the values $c(R)$ for each $R$ on the
path from $U$ to the root. Next we update the structure of $L_{high}$. If some
node $R\in L_{high}\setminus L_{2}$ and its child $W$ have $c(R)\geq c(W)$,
delete $R$ in $L_{high}$ and assign its children to its parent (when $R$ is a
root, its children become new roots).

For efficiency, we use the same chain edges until they become invalid. This
occurs when either some endpoint uses up its vacant degree, or adding the
chain causes some forest node $R$ to be deleted from $Q_{T}$. This second
event occurs either when the supreme set corresponding to that forest node $R$
has demand at most 1 or when one of its children $W$ satisfies $c(R)\geq
c(W)$. The $c(R)$ values are maintained by a dynamic tree data structure. We
can use priority queues to maintain the expiration time of each endpoint and
each forest node. This speedup is identical to [11] and discussed in Section
C.

###### Theorem 5.1

Given the supreme sets forest and the cut values of the supreme sets, we can
add all augmentation chains so that all supreme sets have demand at most 1 in
time $\tilde{O}(n)$.

The rest of this section establishes correctness by proving the chain found by
the algorithm is an augmentation chain. One difficulty of the degree-
constrained setting is that the chain edges may connect nonterminals, so for a
fixed terminal set $R$, the supreme set whose projection is $R$ may change as
we add augmentation chains. This does not happen in the unconstrained setting
where we only add edges to terminals.

In the proofs, $\mu(\cdot)$ is the supreme set defined in the original graph,
and $\mu_{\ell}(\cdot)$ is the supreme set defined in $G_{\ell}$. That is, for
any $R\subseteq T$, if $R$ is the terminal projection of an extreme set in
$G_{\ell}$, then $\mu_{\ell}(R)$ is defined to be the supreme set of terminals
$R$ in $G_{\ell}$; otherwise, $\mu_{\ell}(R)$ is undefined. In particular,
$\mu_{0}(\cdot)=\mu(\cdot)$ because $G_{0}=G$. Recall that $\beta_{\ell}(u)$
is the remaining external degree after adding $\ell$ augmentation chain, so
the cut value in $G^{ext}_{\ell}$ can be expressed as
$d_{G^{ext}_{\ell}}(U)=d_{G_{\ell}}(U)+\beta_{\ell}(U)$, where
$\beta_{\ell}(U)=\sum_{u\in U}\beta_{\ell}(u)$.

###### Lemma 5.12

For $R\in L_{high}$, the $c(R)$ value maintained by the algorithm is equal to
$d_{G_{\ell}}(\mu(R))$ at every time $\ell$.

  * Proof.

Consider the contribution of an edge $(u,w)$ in the $\ell$-th augmentation
chain. Let $U$ be the representative leaf of $u$. If $u$ is assigned to a
upper level heavy path, $U$ is the leaf of the path, and by Lemma 5.5
$u\in\mu(U)$. If $u$ is assigned to a lower level heavy path, $U$ is the
parent of the path, and we also have $u\in\mu(R_{m})\subseteq\mu(U)$ for some
node $R_{m}$ in the path. Therefore $u$ is in $\mu(R)$ for every $R$ on the
path from $U$ to the root. Also these supreme sets do not contain $w$, because
$w$ is assigned to a different tree from $u$, and $(u,w)$ connects two maximal
supreme sets. In the algorithm, $c(R)$ is increased for $R$ on the path from
$U$ to the root, which correctly maintains $d_{G_{\ell}}(\mu(R))$.

###### Fact 5.3

If $\mu_{i}(R)$ is defined, then for any $0\leq j<i$, $\mu_{j}(R)$ exists and
$\mu_{i}(R)\subseteq\mu_{j}(R)$.

  * Proof.

$\mu_{j}(R)$ is extreme in $G_{i}$, so it is also extreme in $G_{j}$ by
repeatedly applying Lemma 5.10. The statement then follows the definition of
$\mu_{j}(R)$.

###### Lemma 5.13

For any $R\in L_{2}$, $d_{G^{ext}_{\ell}}(\mu(R))=\tau$ holds for every
$\ell$.

  * Proof.

By Lemma 5.3, the external augmentation solution is feasible, so for each
$R\in L_{2}$, $\beta(\mu(R))\geq\tau-d(\mu(R))$. Moreover, Lemma 5.3 says the
total external degree is $\sum_{R\in L_{1}}\mathrm{rdem}(R)$, which equals
$\sum_{R\in L_{2}}\tau-d(\mu(R))$ because all internal nodes in
$L_{high}\setminus L_{2}$ are not critical. Therefore
$\beta(\mu(R))=\tau-d(\mu(R))$ for each $R\in L_{2}$.

Initially, $d_{G^{ext}_{0}}(\mu(R))=\beta(\mu(R))+d(\mu(R))=\tau$.
$G^{ext}_{\ell+1}$ is formed by splitting off edges for an augmentation chain
from $G^{ext}_{\ell}$, so $d_{G^{ext}_{\ell+1}}(\mu(R))\leq
d_{G^{ext}_{\ell}}(\mu(R))$, and $d_{G^{ext}_{\ell}}(\mu(R))\leq\tau$ for each
$\ell$ by induction. Also $d_{G^{ext}_{\ell}}(\mu(R))\geq\tau$ by Lemma 5.11,
so the statement holds.

###### Lemma 5.14

For any $R\in L_{2}$, if $\mu(R)$ has vacant degree after adding the $\ell$-th
chain, then $\mu_{\ell}(R)$ is defined, and
$d_{G_{\ell}}(\mu(R))=d_{G_{\ell}}(\mu_{\ell}(R))$.

  * Proof.

Fix some $R\in L_{2}$. Assume first that $\mu_{\ell}(R)$ is defined. By Fact
5.3, $\mu_{\ell}(R)\subseteq\mu(R)$, so

(5.31) $\beta_{\ell}(\mu_{\ell}(R))\leq\beta_{\ell}(\mu(R))$

By Lemma 5.13,
$\tau=d_{G^{ext}_{\ell}}(\mu(R))=\beta_{\ell}(\mu(R))+d_{G_{\ell}}(\mu(R))$.
Combined with (5.31), we have

(5.32) $\beta_{\ell}(\mu_{\ell}(R))\leq\tau-d_{G_{\ell}}(\mu(R))$

By Lemma 5.11, $d_{G^{ext}_{\ell}}(\mu_{\ell}(R))\geq\tau$. Combined with
(5.32), we have

$\tau\leq
d_{G^{ext}_{\ell}}(\mu_{\ell}(R))=\beta_{\ell}(\mu_{\ell}(R))+d_{G_{\ell}}(\mu_{\ell}(R))\leq\tau-
d_{G_{\ell}}(\mu(R))+d_{G_{\ell}}(\mu_{\ell}(R))$

So $d_{G_{\ell}}(\mu(R))\leq d_{G_{\ell}}(\mu_{\ell}(R))$. By Lemma 3.5,
$\mu_{\ell}(R)$ is an $R$-$(T\setminus R)$ min cut in $G_{\ell}$, so
$d_{G_{\ell}}(\mu(R))=d_{G_{\ell}}(\mu_{\ell}(R))$.

It remains to prove that $\mu_{\ell}(R)$ is defined. We prove by induction on
$\ell$. For the base case $\ell=0$, $\mu(R)$ is defined because $R\in L$. Next
consider the inductive case $\ell>0$.

Assume for contradiction that there is no extreme set with terminal projection
$R$ in $G_{\ell}$. Let $X$ be an extreme violator of $\mu(R)$ in $G_{\ell}$;
then $X\subsetneqq\mu(R)$ and

(5.33) $d_{G_{\ell}}(X)\leq d_{G_{\ell}}(\mu(R))$

Because $X$ is extreme, $\rho(X)\neq R$, and $\rho(X)\subsetneqq R$ is a node
in the subtree of $R$ in $L$. In the proof of Lemma 5.3, we proved that for an
extreme set $X$ with terminal set $\rho(X)\in P_{j}$ for some heavy path
$P_{j}$, the cut value of $X$ is augmented to $\tau$ just after processing
heavy path $P_{j}$. Because $X$ is in the subtree of $R$, and we stop the
heavy paths at nodes in $L_{2}$, external edges assigned to $R$ are added
after path $P_{j}$. Let $\beta^{\prime}(\cdot)$ be the external degree in the
external edges added for heavy paths up to $P_{j}$, and
$\beta^{\prime}_{\ell}(\cdot)$ be the remaining $\beta^{\prime}$ degree in
$G_{\ell}$, so that

(5.34) $\beta^{\prime}_{\ell}(X)+d_{G_{\ell}}(X)\geq\tau$

The algorithm uses lower level degrees first, and uses upper level external
edges assigned to $R$ only after all lower level degrees in the subtree of $R$
are used. As long as $\mu(R)$ has vacant degree, we have
$\beta_{\ell}(\mu(R))>\beta^{\prime}_{\ell}(\mu(R))\geq\beta^{\prime}_{\ell}(X)$.
Combined with Lemma 5.13 and (5.33),

$\tau=\beta_{\ell}(\mu(R))+d_{G_{\ell}}(\mu(R))>\beta^{\prime}_{\ell}(X)+d_{G_{\ell}}(X),$

which contradicts (5.34).

###### Lemma 5.15

After adding the $\ell$-th chain, let $u$ be a vertex with vacant degree and
$U\in L_{2}$ be its representative leaf, then $u\in\mu_{\ell}(U)$.

  * Proof.

$u\in\mu(U)$ by Lemma 5.5 and the definition of representative leaf. $\mu(U)$
has a vacant degree at $u$ in $G_{\ell}$, so $\mu_{\ell}(U)$ is defined by
Lemma 5.14. Assume for contradiction that $u\notin\mu_{\ell}(U)$. Then by Fact
5.3, $\mu_{\ell}(U)\subsetneqq\mu(U)$. Because one of the vacant degrees in
$\beta_{\ell}(\mu(U))$ is at $u\notin\mu_{\ell}(U)$,
$\beta_{\ell}(\mu(U))>\beta_{\ell}(\mu_{\ell}(U))$.

$\mu(U)$ is not extreme in $G_{\ell}$, so there exists an extreme violator
$W$. $\rho(W)\subseteq U$, so $W\subseteq\mu_{\ell}(U)$, and
$d_{G_{\ell}}(\mu(U))\geq d_{G_{\ell}}(W)\geq d_{G_{\ell}}(\mu_{\ell}(U))$. By
Lemma 5.13, $d_{G_{\ell}}(\mu(U))+\beta_{\ell}(\mu(U))=\tau$. Therefore

$d_{G^{ext}_{\ell}}(\mu_{\ell}(U))=d_{G_{\ell}}(\mu_{\ell}(U))+\beta_{\ell}(\mu_{\ell}(U))<d_{G_{\ell}}(\mu(U))+\beta_{\ell}(\mu(U))=\tau,$

which contradicts Lemma 5.11.

###### Lemma 5.16

If $\mu_{\ell}(R)$ is defined for some $R\in L_{high}\setminus L_{2}$, then
$d_{G_{\ell}}(\mu_{\ell}(R))=d_{G_{\ell}}(\mu_{\ell-1}(R))$.

  * Proof.

If $\mu_{\ell}(R)=\mu_{\ell-1}(R)$, the statement is trivial. By Fact 5.3, the
remaining case is $\mu_{\ell}(R)\subsetneqq\mu_{\ell-1}(R)$.
$d_{G_{\ell-1}}(\mu_{\ell}(R))>d_{G_{\ell-1}}(\mu_{\ell-1}(R))$ since
$\mu_{\ell-1}(R)$ is extreme in $G_{\ell-1}$, but
$d_{G_{\ell}}(\mu_{\ell}(R))\leq d_{G_{\ell}}(\mu_{\ell-1}(R))$ by Lemma 3.5.
It remains to prove that $d_{G_{\ell}}(\mu_{\ell}(R))\geq
d_{G_{\ell}}(\mu_{\ell-1}(R))$. An augmentation chain adds at most 2 edges to
any supreme set. So the only nontrivial case is that the $\ell$-th chain adds
2 edges to $\mu_{\ell-1}(R)\setminus\mu_{\ell}(R)$ and no edge to
$\mu_{\ell}(R)$.

For each endpoint $u$ of the $\ell$-th chain, $u\in\mu_{\ell-1}(U)$ by Lemma
5.15, where $U\in L_{2}$ is $u$’s representative leaf. Assume the two edges
are added to $X_{1}=\mu_{\ell-1}(U_{1})$ and $X_{2}=\mu_{\ell-1}(U_{2})$,
$U_{1},U_{2}\in L_{2}$. $U_{1},U_{2}\subsetneqq R$ because $R\notin L_{2}$ and
the two edges are added to $\mu_{\ell-1}(R)$. Also the two endpoints are not
in $\mu_{\ell}(R)$, so $\mu_{\ell}(R)$ crosses $X_{1}$ and $X_{2}$.

Case 1: $U_{1}\neq U_{2}$. Since $X_{1}$ and $X_{2}$ are extreme in
$G_{\ell-1}$,

$d_{G_{\ell-1}}(X_{1}\cap\mu_{\ell}(R))>d_{G_{\ell-1}}(X_{1}),d_{G_{\ell-1}}(X_{2}\cap\mu_{\ell}(R))>d_{G_{\ell-1}}(X_{2})$

By submodularity (2.4), $d_{G_{\ell-1}}(\mu_{\ell}(R)\cup
X_{1})<d_{G_{\ell-1}}(\mu_{\ell}(R))$, $d_{G_{\ell-1}}(\mu_{\ell}(R)\cup
X_{1}\cup X_{2})<d_{G_{\ell-1}}(\mu_{\ell}(R)\cup X_{1})$ ($X_{1}$ and $X_{2}$
are disjoint by laminarity). So

$d_{G_{\ell}}(\mu_{\ell}(R))=d_{G_{\ell-1}}(\mu_{\ell}(R))\geq
d_{G_{\ell-1}}(\mu_{\ell}(R)\cup X_{1}\cup X_{2})+2\geq
d_{G_{\ell-1}}(\mu_{\ell-1}(R))+2=d_{G_{\ell}}(\mu_{\ell-1}(R))$

where the equations use the assumption that the $\ell$-th chain adds 2 edges
to $\mu_{\ell-1}(R)$ but no edge to $\mu_{\ell}(R)$.

Case 2: $U_{1}=U_{2}$. By Lemma 5.14, either $\mu_{\ell}(U_{1})$ exists and
$d_{G_{\ell}}(\mu_{\ell}(U_{1}))=d_{G_{\ell}}(\mu(U_{1}))$, or $\mu(U_{1})$
has no vacant degree at time $\ell$. Notice that
$\rho(X_{1}\cap\mu_{\ell}(R))=U_{1}$. In the former case,

$d_{G_{\ell-1}}(X_{1}\cap\mu_{\ell}(R))=d_{G_{\ell}}(X_{1}\cap\mu_{\ell}(R))\geq
d_{G_{\ell}}(\mu_{\ell}(U_{1}))=d_{G_{\ell}}(\mu(U_{1}))=d_{G_{\ell-1}}(\mu(U_{1}))+2=d_{G_{\ell-1}}(X_{1})+2$

In the latter case, $\mu(U_{1})$ has no vacant degree in $G_{\ell}$, so
$d_{G_{\ell-1}}(X_{1}\cap\mu_{\ell}(R))=d_{G_{\ell}}(X_{1}\cap\mu_{\ell}(R))\geq\tau$.
By Lemma 5.13, $\tau=d_{G_{\ell-1}}(\mu(U_{1}))+\beta_{\ell-1}(\mu(U_{1}))\geq
d_{G_{\ell-1}}(\mu(U_{1}))+2=d_{G_{\ell-1}}(X_{1})+2$, so we also have
$d_{G_{\ell-1}}(X_{1}\cap\mu_{\ell}(R))\geq d_{G_{\ell-1}}(X_{1})+2$. By
submodularity,

$d_{G_{\ell-1}}(\mu_{\ell}(R)\cup X_{1})+2\leq d_{G_{\ell-1}}(\mu_{\ell}(R))$

$\mu_{\ell}(R)\subseteq\mu_{\ell-1}(R)$ by Fact 5.3, and
$X_{1}=\mu_{\ell-1}(U_{1})\subseteq\mu_{\ell-1}(R)$ by laminarity. Therefore,
since $\mu_{\ell-1}(R)$ is extreme,

$d_{G_{\ell}}(\mu_{\ell}(R))=d_{G_{\ell-1}}(\mu_{\ell}(R))\geq
d_{G_{\ell-1}}(\mu_{\ell}(R)\cup X_{1})+2\geq
d_{G_{\ell-1}}(\mu_{\ell-1}(R))+2=d_{G_{\ell}}(\mu_{\ell-1}(R))$

In conclusion we have $d_{G_{\ell}}(\mu_{\ell}(R))\geq
d_{G_{\ell}}(\mu_{\ell-1}(R))$ in both cases, so
$d_{G_{\ell}}(\mu_{\ell}(R))=d_{G_{\ell}}(\mu_{\ell-1}(R))$.

###### Lemma 5.17

After processing the $\ell$-th chain, if a node $R$ in $L_{high}$ is not
deleted, then either $\mu_{\ell}(R)$ is defined and
$d_{G_{\ell}}(\mu(R))=d_{G_{\ell}}(\mu_{\ell}(R))$, or $R\in L_{2}$ and
$\mu(R)$ has no vacant degree in $G_{\ell}$.

  * Proof.

We prove by induction first on time $\ell$, then bottom-up on the forest. The
base case $\ell=0$ holds trivially, and the base case $R\in L_{2}$ is handled
by Lemma 5.14. Next consider the inductive case $\ell>0$ and $R$ is an
internal node in $L_{high}\setminus L_{2}$.

By inductive hypothesis, $\mu_{\ell-1}(R)$ is defined in $G_{\ell-1}$, and
$d_{G_{\ell-1}}(\mu(R))=d_{G_{\ell-1}}(\mu_{\ell-1}(R))$.
$\mu(R)\supseteq\mu_{\ell-1}(R)$ by Fact 5.3. If chain $\ell$ does not add
edges to $\mu(R)$, then $d_{G_{\ell}}(\mu(R))=d_{G_{\ell}}(\mu_{\ell-1}(R))$.
Next assume chain $\ell$ adds edges to $\mu(R)$. Because $R$ is a forest node,
for each chain edge $(u,w)$, at most one endpoint $u$ is assigned to a leaf
$U$ in the subtree of $R$. $u\in\mu_{\ell-1}(U)\subseteq\mu_{\ell-1}(R)$ by
Lemma 5.15 and laminarity of supreme sets in $G_{\ell-1}$. The other endpoint
$w$ is assigned to leaves outside the tree of $R$, so $w\notin\mu(R)$.
Therefore we also have $d_{G_{\ell}}(\mu(R))=d_{G_{\ell}}(\mu_{\ell-1}(R))$
because they increase by the same amount from $G_{\ell-1}$. In both cases we
have $d_{G_{\ell}}(\mu(R))=d_{G_{\ell}}(\mu_{\ell-1}(R))$. By Lemma 5.16, if
$\mu_{\ell}(R)$ is defined, then
$d_{G_{\ell}}(\mu(R))=d_{G_{\ell}}(\mu_{\ell-1}(R))=d_{G_{\ell}}(\mu_{\ell}(R))$.
It remains to prove that $\mu_{\ell}(R)$ is defined.

Assume for contradiction that there is no extreme set with terminal set $R$ in
$G_{\ell}$. Let $X\subsetneqq\mu(R)$ be an extreme violator of $\mu(R)$ in
$G_{\ell}$ with $d_{G_{\ell}}(X)\leq d_{G_{\ell}}(\mu(R))$. Let $W=\rho(X)$,
then $W\subsetneqq R$ because $X$ is extreme.
$d_{G_{\ell}}(\mu(R))<d_{G_{\ell}}(\mu(W))$ because $R$ is not deleted, so

$d_{G_{\ell}}(X)<d_{G_{\ell}}(\mu(W))$

By inductive assumption, either $\mu_{\ell}(W)$ exists and
$d_{G_{\ell}}(\mu_{\ell}(W))=d_{G_{\ell}}(\mu(W))$, or $\mu(W)$ has no vacant
degree. In the former case, $d_{G_{\ell}}(X)<d_{G_{\ell}}(\mu_{\ell}(W))$,
which contradicts the fact that $\mu_{\ell}(W)$ is extreme. In the latter
case, $X\subseteq\mu(W)$ because $X$ is extreme, so $X$ has no vacant degree.
But by Lemma 5.13,

$\tau=d_{G^{ext}_{\ell}}(\mu(W))\geq d_{G_{\ell}}(\mu(W))>d_{G_{\ell}}(X)$

So $X$ should have vacant degree in a feasible external solution, a
contradiction.

###### Lemma 5.18

If a node $R$ is deleted after processing the $\ell$-th chain, then
$\mu_{\ell}(R)$ is not defined in $G_{\ell}$.

  * Proof.

The algorithm only deletes internal nodes of $L_{high}$, so $R\in
L_{high}\setminus L_{2}$. Because $R$ is not deleted at time $\ell-1$, by
Lemma 5.17, $d_{\ell-1}(\mu(R))=d_{\ell-1}(\mu_{\ell-1}(R))$. If $(u,w)$ is a
chain edge and $u\in\mu(R)$, then $w$ is not assigned to the tree of $R$ and
$w\notin\mu(R)$. By Lemma 5.15 and laminarity of supreme sets in $G_{\ell-1}$,
all endpoints in $\mu(R)$ in the $\ell$-th chain are in $\mu_{\ell-1}(R)$.
Therefore the cut values of $\mu(R)$ and $\mu_{\ell-1}(R)$ increase by the
same amount from $G_{\ell-1}$ to $G_{\ell}$, and
$d_{G_{\ell}}(\mu(R))=d_{G_{\ell}}(\mu_{\ell-1}(R))$.

Assume for contradiction that $\mu_{\ell}(R)$ is defined. Then by Lemma 5.16,
$d_{G_{\ell}}(\mu_{\ell-1}(R))=d_{G_{\ell}}(\mu_{\ell}(R))$, so
$d_{G_{\ell}}(\mu(R))=d_{G_{\ell}}(\mu_{\ell}(R))$. Because $R$ is deleted at
time $\ell$, $d_{G_{\ell}}(\mu(R))\geq d_{G_{\ell}}(\mu(W))$ for some $W\in
ch(R)$. By Lemma 3.5, $\mu_{\ell}(R)$ is an $R$-$(T\setminus R)$ min cut in
$G_{\ell}$, so

$d_{G_{\ell}}(\mu_{\ell}(R)\cup\mu(W))\geq
d_{G_{\ell}}(\mu_{\ell}(R))=d_{G_{\ell}}(\mu(R))\geq d_{G_{\ell}}(\mu(W))$

Since $\mu_{\ell}(R)$ is extreme in $G_{\ell}$
($\rho(\mu_{\ell}(R)\cap\mu(W))=W\subsetneqq R$),

$d_{G_{\ell}}(\mu_{\ell}(R)\cap\mu(W))>d_{G_{\ell}}(\mu_{\ell}(R))$

Adding these two inequalities contradicts submodularity (2.1).

###### Lemma 5.19

The chains picked by the algorithm are augmentation chains.

  * Proof.

By Lemma 5.12, the $c(R)$ value maintained by the algorithm equals
$d_{G_{\ell}}(\mu(R))$ for all $R\in L_{high}$ at each time $\ell$. By Lemma
5.17 and Lemma 5.18, the algorithm keeps a node $R$ in $L_{high}$ if and only
if $R$ remains a projection of an extreme set, or $R\in L_{2}$ and $\mu(R)$
has no vacant degree. For the latter case, $c(R)=d_{G_{\ell}}(\mu(R))=\tau$ at
time $\ell$ by Lemma 5.13. Therefore the roots $R_{i}$ with
$c(R_{i})\leq\tau-2$ picked by the algorithm are exactly the terminal sets of
all maximal supreme sets with demand at least 2.

The algorithm picks endpoints with vacant degrees. By Lemma 5.15, the
endpoints are in the current supreme sets of their representative leaves,
which are in corresponding maximal supreme sets by laminarity. In conclusion
the algorithm picks an augmentation chain.

###  5.3 Augment Connectivity by One in the Degree-Constrained Setting

Similar to the unconstrained degree case, we are left with the problem of
augmenting Steiner connectivity by 1 (from $\tau-1$ to $\tau$) after
augmentation chains have been added. As input to this problem, we are given
the graph $G$ with Steiner connectivity $\tau-1$, degree constraint $\beta$,
and the family $K$ of the terminal sets of all supreme sets. We solve this
problem by a reduction to the unconstrained setting and a modification of
Algorithm 3.

The sets in $K$ with demand $1$ correspond to the terminal sets of minimal
Steiner minimum cuts in $G$. These are also the nodes in the skeleton
structure described in Section 4.4. Let $K^{\prime}$ be the sub-family of $K$
of sets with demand 1. That is, each $k\in K^{\prime}$ is the terminal set of
a minimal Steiner min cut. We do not know the supreme sets of an arbitrary
terminal projection, but in this special case we can find the supreme sets
efficiently for terminal sets in $K^{\prime}$ using isolating cuts as follows.
Given a graph with terminals, isolating cuts framework finds the minimum cuts
separating each terminal from all other terminals in $O(\log n)$ max flow
calls [37, 3].

Contract each set $k\in K^{\prime}$, and also contract $T\setminus
K^{\prime}$. Run isolating cuts with these contracted nodes as terminals. By
Lemma 3.5, for each $k\in K^{\prime}$, $\mu(k)$ is the earliest
$k$-$(T\setminus k)$ min cut. Therefore, if we find minimal isolating cuts, we
get the supreme sets $\mu(k)$ for each $k\in K^{\prime}$.

###### Lemma 5.20

If the degree-constrained augmenting connectivity by 1 problem is feasible,
then for each $k\in K^{\prime}$, there exists $v_{k}\in\mu(k)$ such that
$\beta(v_{k})\geq 1$.

  * Proof.

Because the problem is feasible and $\mu(k)$ is a Steiner cut,
$d(\mu(k))+\beta(\mu(k))\geq\tau$, where
$\beta(\mu(k))=\sum_{u\in\mu(k)}\beta(u)$. $d(\mu(k))=\tau-1$ by definition of
$K^{\prime}$, so there exists a $v_{k}\in\mu(k)$ with $\beta(v_{k})\geq 1$.

Recall that in Algorithm 3, we randomly match a pair of demand-1 extreme sets
$\mu(k),\mu(k^{\prime})$, and add a matching edge connecting arbitrary
terminals in $k$ and $k^{\prime}$. Consider modifying the algorithm in the
following way. For each $k\in K^{\prime}$, choose a surrogate $v_{k}\in\mu(k)$
according to Lemma 5.20. When matching a pair of extreme sets $\mu(k)$ and
$\mu(k^{\prime})$, instead of connecting arbitrary terminals, we add an edge
$(v_{k},v_{k^{\prime}})$ connecting the surrogates. Lemma 5.21 shows that this
new matching on surrogates is an optimal solution.

###### Lemma 5.21

Given an instance of degree-constrained augmentation by 1 problem, remove the
degree constraint and run Algorithm 3 to get an output $F$. If we replace
every edge in $F$ by its surrogate edge to form a new matching $F^{\prime}$,
then $F^{\prime}$ is an optimal solution to the degree-constrained
augmentation by 1 problem.

  * Proof.

For any Steiner min cut $S$, we prove that it is augmented by $F^{\prime}$, so
that $F^{\prime}$ is a feasible solution. Because $S$ is augmented by $F$,
there exists an edge $(u,v)\in F$ across $S$, for some
$u\in\mu(k),v\in\mu(k^{\prime})$, where $\mu(k),\mu(k^{\prime})$ are demand-1
supreme sets. Then $k,k^{\prime}\in K^{\prime}$. By Lemma 4.8, $S$ does not
cross $\mu(k)$ and $\mu(k^{\prime})$. So for surrogates $v_{k}\in\mu(k)$ and
$v_{k^{\prime}}\in\mu(k^{\prime})$, edge $(v_{k},v_{k^{\prime}})\in
F^{\prime}$ also augments $S$. The surrogates have vacant degree by Lemma
5.20. Therefore $F^{\prime}$ is a feasible solution.

Notice that removing the degree constraint cannot decrease the optimal value,
because an optimal solution to degree-constrained augmentation by 1 problem is
also feasible to the corresponding unconstrained problem. Because $F$ is an
optimal solution to the unconstrained problem, and $F^{\prime}$ has the same
value as $F$, $F^{\prime}$ is an optimal solution.

Next we analyze the running time. Finding the surrogates $v_{k}$ takes time
$\tilde{O}(F(m,n))$ for isolating cuts and $O(n)$ for picking the surrogates.
Running Algorithm 3 takes $\tilde{O}(F(m,n))$. So the total running time is
$\tilde{O}(F(m,n))$.

## References

  * [1] Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, and Ohad Trabelsi.  Breaking the cubic barrier for all-pairs max-flow: Gomory-hu tree in nearly quadratic time.  In FOCS 2022: 63rd IEEE Symposium on Foundations of Computer Science, 2022.
  * [2] Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi.  Cut-equivalent trees are optimal for min-cut queries.  In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, pages 105–118. IEEE, 2020.
  * [3] Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi.  Subcubic algorithms for Gomory–Hu tree in unweighted graphs.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 1725–1737, 2021.
  * [4] András A. Benczúr.  Augmenting undirected connectivity in rnc and in randomized $\tilde{O}(n^{3})$ time.  In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC ’94, page 658–667. ACM, 1994.
  * [5] András A. Benczúr and David R. Karger.  Augmenting undirected edge connectivity in $\tilde{O}(n^{2})$ time.  J. Algorithms, 37(1):2–36, October 2000.
  * [6] Attila Bernáth, Satoru Iwata, Tamás Király, Zoltán Király, and Zoltán Szigeti.  Recent results on well-balanced orientations.  Discrete Optimization, 5(4):663–676, 2008.
  * [7] Anand Bhalgat, Ramesh Hariharan, Telikepalli Kavitha, and Debmalya Panigrahi.  Fast edge splitting and edmonds’ arborescence construction for unweighted graphs.  In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’08, page 455–464. SIAM, 2008.
  * [8] Jarosław Byrka, Fabrizio Grandoni, and Afrouz Jabal Ameli.  Breaching the 2-approximation barrier for connectivity augmentation: a reduction to steiner tree.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 815–825, 2020.
  * [9] Guo-Ray Cai and Yu-Geng Sun.  The minimum augmentation of any graph to a k-edge-connected graph.  Networks, 19(1):151–172, 1989.
  * [10] Federica Cecchetto, Vera Traub, and Rico Zenklusen.  Bridging the gap between tree and connectivity augmentation: unified and stronger approaches.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 370–383, 2021.
  * [11] Ruoxu Cen, Jason Li, and Debmalya Panigrahi.  Augmenting edge connectivity via isolating cuts.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3237–3252, 2022.
  * [12] Ruoxu Cen, Jason Li, and Debmalya Panigrahi.  Edge connectivity augmentation in near-linear time.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pages 137–150. ACM, 2022.
  * [13] Yuk Hei Chan, Wai Shing Fung, Lap Chi Lau, and Chun Kong Yung.  Degree bounded network design with metric costs.  SIAM Journal on Computing, 40(4):953–980, 2011.
  * [14] Chandra Chekuri and Nitish Korula.  A graph reduction step preserving element-connectivity and packing steiner trees and forests.  SIAM Journal on Discrete Mathematics, 28(2):577–597, 2014.
  * [15] Chandra Chekuri and F. Bruce Shepherd.  Approximate integer decompositions for undirected network design problems.  SIAM Journal on Discrete Mathematics, 23(1):163–177, 2009.
  * [16] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva.  Maximum flow and minimum-cost flow in almost-linear time.  In FOCS 2022: 63rd IEEE Symposium on Foundations of Computer Science, 2022.
  * [17] Yefim Dinitz and Alek Vainshtein.  The connectivity carcass of a vertex subset in a graph and its incremental maintenance.  In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC ’94, page 716–725. ACM, 1994.
  * [18] András Frank.  Augmenting graphs to meet edge-connectivity requirements.  SIAM Journal on Discrete Mathematics, 5(1):25–53, February 1992\.
  * [19] András Frank and Zoltán Király.  Graph orientations with edge-connection and parity constraints.  Combinatorica, 22(1):47–70, 2002.
  * [20] András Frank and Tibor Jordán.  Directed vertex-connectivity augmentation.  Mathematical Programming, 84(3):537–553, 1999.
  * [21] András Frank and Tamás Király.  Combined connectivity augmentation and orientation problems.  Discrete Applied Mathematics, 131(2):401–419, 2003.
  * [22] Greg N. Frederickson and Joseph Ja’Ja’.  Approximation algorithms for several graph augmentation problems.  SIAM Journal on Computing, 10(2):270–283, 1981.
  * [23] Harold N. Gabow.  Efficient splitting off algorithms for graphs.  In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC ’94, page 696–705. ACM, 1994.
  * [24] Harold N. Gabow.  The minset-poset approach to representations of graph connectivity.  ACM Trans. Algorithms, 12(2):24:1–24:73, 2016.
  * [25] Zhihan Gao.  On the metric s–t path traveling salesman problem.  SIAM Review, 60(2):409–426, 2018.
  * [26] Fabrizio Grandoni, Afrouz Jabal Ameli, and Vera Traub.  Breaching the 2-approximation barrier for the forest augmentation problem.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1598–1611, 2022.
  * [27] Fabrizio Grandoni, Christos Kalaitzis, and Rico Zenklusen.  Improved approximation for tree augmentation: saving by rewiring.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 632–645, 2018.
  * [28] Ramesh Hariharan, Telikepalli Kavitha, and Debmalya Panigrahi.  Efficient algorithms for computing all low _s-t_ edge connectivities and related problems.  In Nikhil Bansal, Kirk Pruhs, and Clifford Stein, editors, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, pages 127–136. SIAM, 2007.
  * [29] Toshimasa Ishii.  Minimum augmentation of edge-connectivity with monotone requirements in undirected graphs.  Discrete Optimization, 6(1):23–36, 2009.
  * [30] Toshimasa Ishii and Masayuki Hagiwara.  Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs.  Discrete Applied Mathematics, 154(16):2307–2329, 2006.
  * [31] Bill Jackson and Tibor Jordán.  Independence free graphs and vertex connectivity augmentation.  Journal of Combinatorial Theory, Series B, 94(1):31–77, 2005.
  * [32] Kamal Jain.  A factor 2 approximation algorithm for the generalized steiner network problem.  Combinatorica, 21(1):39–60, 2001.
  * [33] David R. Karger and Debmalya Panigrahi.  A near-linear time algorithm for constructing a cactus representation of minimum cuts.  In Proceedings of the 2009 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 246–255. SIAM, 2009.
  * [34] Kristine Vitting Klinkby, Pranabendu Misra, and Saket Saurabh.  Strong connectivity augmentation is fpt.  In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’21, page 219–234, USA, 2021. SIAM.
  * [35] Lap Chi Lau.  An approximate max-steiner-tree-packing min-steiner-cut theorem.  Combinatorica, 27(1):71–90, 2007.
  * [36] Lap Chi Lau and Chun Kong Yung.  Efficient edge splitting-off algorithms maintaining all-pairs edge-connectivities.  SIAM J. Comput., 42(3):1185–1200, 2013.
  * [37] Jason Li and Debmalya Panigrahi.  Deterministic min-cut in poly-logarithmic max-flows.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 85–92. IEEE, 2020.
  * [38] Jason Li and Debmalya Panigrahi.  Approximate gomory–hu tree is faster than _n_ – 1 max-flows.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 1738–1748. ACM, 2021.
  * [39] László Lovász.  Combinatorial Problems and Exercises.  North-Holland Publishing Company, Amsterdam, 1979.
  * [40] W. Mader.  A reduction method for edge-connectivity in graphs.  In B. Bollobás, editor, Advances in Graph Theory, volume 3 of Annals of Discrete Mathematics, pages 145–164. Elsevier, 1978.
  * [41] Dániel Marx and László A. Végh.  Fixed-parameter algorithms for minimum-cost edge-connectivity augmentation.  ACM Trans. Algorithms, 11(4), apr 2015.
  * [42] Martin Merker.  Decomposing highly edge-connected graphs into homomorphic copies of a fixed tree.  Journal of Combinatorial Theory, Series B, 122:91–108, 2017.
  * [43] Hiroshi Nagamochi and Toshihide Ibaraki.  Deterministic õ(nm) time edge-splitting in undirected graphs.  Journal of Combinatorial Optimization, 1(1):5–46, 1997.
  * [44] Dalit Naor, Dan Gusfield, and Charles U. Martel.  A fast algorithm for optimally increasing the edge connectivity.  SIAM J. Comput., 26(4):1139–1165, 1997.
  * [45] Zoltán Szigeti.  Edge-splittings preserving local edge-connectivity of graphs.  Discrete Applied Mathematics, 156(7):1011–1018, 2008.
  * [46] Vera Traub and Rico Zenklusen.  A better-than-2 approximation for weighted tree augmentation.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1–12. IEEE, 2022.
  * [47] László A. Végh and András A. Benczúr.  Primal-dual approach for directed vertex connectivity augmentation and generalizations.  ACM Trans. Algorithms, 4(2), may 2008.
  * [48] Toshimasa Watanabe and Akira Nakamura.  Edge-connectivity augmentation problems.  Journal of Computer and System Sciences, 35(1):96–144, 1987.

##  A Example of Graph with Exponentially Many Extreme Sets

The example is given in Figure 3. All vertex sets of the form
$\\{s\\}\cup\\{v_{i}:i\in S\\}$ for any $S\subseteq[n-2]$ are extreme sets.
This is because their cut size is $n-|S|+1$ whereas any strict subset
containing terminals must be of the form $\\{s\\}\cup\\{v_{i}:i\in
S^{\prime}\\}$ for some $S^{\prime}\subset S$. The latter vertex set has cut
value $n-|S^{\prime}|+1$, which is strictly larger than $n-|S|+1$.

Figure 3: A graph with exponentially many extreme sets. The solid vertices
$s,t$ are terminals and the empty vertices $v_{1},v_{2},\ldots,v_{n-2}$ are
nonterminals.

##  B Augmenting Connectivity by Matching: Illustrative Example of a Cycle

(a) Here $C_{1}$ is augmented by one edge $v_{1}-v_{3}$. After this edge is
added, augmenting $C_{2}$ to connectivity 3 gives an augmentation of $C_{1}$
to connectivity 3, so we have reduced our problem to an augmentation on a
smaller graph.

(b) First add $v_{1}-v_{3}$ to $C_{1}$ to result in a reduction of augmenting
$C_{1}$ to connectivity 3 to augmenting $C_{2}$ as in Figure 4(a). Then adding
the edge $v_{2}-v_{5}$ to $C_{2}$ reduces the augmentation of $C_{1}$ to
connectivity 3 further to augmenting $C_{3}$ to connectivity 3.

(c) After adding the edge $v_{1}-v_{3}$ we reduce augmenting $C_{1}$ to
augmenting $C_{2}$. But now, the edge $v_{2}-v_{4}$ does not result in a good
reduction of augmentation of $C_{2}$ to a smaller problem because $v_{2}$ and
$v_{4}$ are adjacent.

Figure 4: Augmenting the connectivity of a cycle by 1

We are interested in how to augment the connectivity of a cycle from $2$ to
$3$. Our running example will be the cycle graph on 8 vertices, which we call
$C_{1}$. Figure 4(a) shows a case in which we add one edge to a cycle graph as
a partial solution. Then we claim that after adding the edge $(v_{1},v_{3})$,
in order to augment the connectivity of $C_{1}$ to 3, it suffices to augment
the connectivity of $C_{2}$ to 3. This is because the presence of the
$(v_{1},v_{3})$ edge allows us to shortcut the edges $(v_{2},v_{8})$ and
$(v_{2},v_{4})$, since all cuts of value 2 in $C_{1}\cup\\{(v_{1},v_{3})\\}$
are accounted for as cuts of value 2 in $C_{2}$.

The same reasoning applies to any edge $(v_{i},v_{j})$ between non-adjacent
vertices in the cycle. However, notice that since $v_{i}$ and $v_{i+1}$ are
adjacent in $C_{1}$, adding the edge $(v_{i},v_{i+1})$ does not allow us to
shortcut both vertices by deleting $v_{i}$ and $v_{i+1}$ and adding the edge
$(v_{i-1},v_{i+2})$, since $\\{v_{i},v_{i+1}\\}$ would be a cut of value 2 not
accounted for in the shortcut version.

In Algorithm 3 we actually add edges in batches of $\lceil\frac{n}{4}\rceil$
edges at a time, where $n$ is the number of vertices in the cycle, so it is
important to understand which edges are compatible with each other. Consider
the example in Figure 4(b). After adding the edge $(v_{1},v_{3})$ we can
delete and shortcut those two vertices as discussed previously, and
effectively work with $C_{2}$ instead. Now, the second edge given in the
example is $(v_{2},v_{5})$, which in $C_{2}$ connects two non-adjacent
vertices. Then, applying the same reasoning, we can delete and shortcut
$v_{2}$ and $v_{5}$, and work with $C_{3}$ from Figure 4(b) instead. This is
because the two edges to be added were compatible with each other in the sense
that there is a sequence of them such that in the sequence of deletions and
shortcuts, each edge connects non-adjacent vertices in the sequence of
simplified cycles.

On the other hand, Figure 4(c) displays an example in which two edges are not
compatible. That is, once we add one edge and apply deletion and the shortcut,
the other edge connects adjacent vertices in the resulting graph.

In Section 4.4 we show that any compatible sequence of additional edges can be
completed to an optimal connectivity augmentation of any graph by 1. Then, we
analyze the probability that a randomly selected partial matching is
compatible in the sense that we have just described.

##  C Data Structures for Lazy Updates

In this section, we sketch the running time analysis using lazy data
structures in Cen et al. [11] for maintaining supreme sets tree while the
algorithm adds augmentation chains. That gives proofs for Theorem 4.2 and
Theorem 5.1.

  * Proof.

[Proof of Theorem 4.2] We begin with an initial augmentation chain
$\\{(a_{i},b_{i+1})\\}_{1\leq i\leq r-1}$ with $a_{i},b_{i}\in R_{i}$, where
each $R_{i}$ is a root in the supreme sets forest with demand at least 2. This
chain can be calculated in $O(n)$ time. We add it until it is no longer an
augmentation chain, in which case we say it expires. This happens when one of
the following occurs:

    1. 1.

Some vertex $a_{i}$ uses up all of its vacant degree.

    2. 2.

For some $i\leq r$, $\text{dem}(R_{i})\leq 1$.

    3. 3.

For some $i$ and $W\in\text{ch}(R_{i})$, $d(W)\geq d(R_{i})$.

At this point, we replace $\\{(a_{i},b_{i+1})\\}_{1\leq i\leq r-1}$ with a new
augmentation chain $\\{(a_{i}^{\prime},b_{i+1}^{\prime})\\}_{1\leq i\leq r-1}$
and keep using the new chain until it expires again. Each of the three cases
can occur at most $n$ times because each vertex can use up degree once, and
each node in the supreme sets forest can be deleted once.

Given that an expiration occurred, we first show how to select a new
augmentation chain. If expiration occurred because of Case 1, we replace the
terminal $a_{i}$ with no more vacant degree by another vacant vertex in the
same supreme set. This takes constant time. If Case 2 occurs so that some
$X_{i}$ has demand at most 1, then we remove the edges $(a_{i},b_{i+1})$ and
$(a_{i-1},b_{i})$ from the augmentation chain and replace them by an edge
$(a_{i-1},b_{i+1})$. This also takes constant time. If Case 3 occurs for some
$R_{i}$, then we replace $(a_{i},b_{i+1})$ and $(a_{i-1},b_{i})$ by a partial
augmentation chain connecting all children of $R_{i}$. The running time is
proportional to the number of children. Since each node is added at most once,
the total cost of Case 3 is $O(n)$.

When some edge expires and gets updated, other chain edges remain and
contribute to the cut values. So instead of maintaining the exact cut values
of the supreme sets, we maintain them lazily by recording the linear growth
(in the number of times an augmentation chain is added) of cut values. The
expiration time does not change as long as the incident chain edges remain the
same. When an edge of the augmentation chain is modified, we calculate the new
expiration time of the chain as follows in time $O(\log(n))$. Each update of
chain edges costs constant data structure operations, and there are $O(n)$
chain updates in total, so the total running time is $O(n\log n)$.

Now we show how to determine the expiration time of a new augmentation chain
given by modifying one edge of an old augmentation chain. This is easy given
the correct cut values for all supreme terminal sets, because we have that the
expiration time for the chain $F$ is $t_{F}=\min(t_{1},t_{2},t_{3})$, where

$\displaystyle t_{1}$ $\displaystyle=\min_{v\in
V}\lfloor{\frac{\beta(v)}{d_{F}(v)}}\rfloor,$ $\displaystyle t_{2}$
$\displaystyle=\min_{i\in[r]}\lfloor\frac{\tau-d(X_{i})}{d_{F}(X_{i})}\rfloor,$
$\displaystyle t_{3}$
$\displaystyle=\min_{i\in[r]}\min_{W\in\text{ch}(X_{i})}\lceil\frac{d(W)-d(X_{i})}{d_{F}(X_{i})-d_{F}(W)}\rceil.$

The values $t_{1},t_{2},t_{3}$ can be maintained by priority queues, so
finding these minimums can be done in $O(\log(n))$ time.

Finally, we need to maintain the expiration time under an update of
augmentation chain. When adding a new chain edge, we first carry out previous
lazy updates of relevant nodes to the current time, and then apply new lazy
updates. The updates are uniformly adding a constant to the vacant degree and
cut values of nodes on a tree path, so they can be handled in constant dynamic
tree operations. (For each edge $(a_{i},b_{i+1})$ in the chain $F$, the
supreme sets that have their corresponding cut values increased are those on
the forest path in $L$ from $a_{i}$ to $b_{i+1}$ excluding the least common
ancestor of $a_{i}$ and $b_{i+1}$.)

  * Proof.

[Proof of Theorem 5.1] We show that the degree-constrained augmentation
algorithm behaves in the same way as the unconstrained augmentation algorithm
in terms of maintaining the supreme sets tree while greedily adding
augmentation chains, despite several differences in algorithm details. It
follows that we can use the same lazy data structures as in the unconstrained
setting to get $\tilde{O}(n)$ running time.

We summarize the differences and remedies below.

    1. 1.

The algorithm works on the forest $L_{high}$ instead of $L$. So the data
structure maintains the part of supreme sets forest corresponding to
$L_{high}$.

    2. 2.

Because the chain edges incident on nonterminals and the supreme sets will
change during the algorithm, we do not know whether an edge contributes to a
supreme sets in degree-constrained setting. However, Lemma 5.15 shows that we
can locate each vacant degree in a current supreme set projected to a node in
$L_{2}$, so by laminarity of current supreme sets, we know the contribution of
an edge to all supreme sets of projection in $L_{high}$.

    3. 3.

The algorithm needs to remove a forest node when it is no longer the terminal
projection of a supreme set. By Lemma 5.17 and Lemma 5.18, this is detected by
the algorithm. Moreover, the operation is the same as in unconstrained
setting: by comparing whether $c(R)\geq c(W)$ for any node $R$ and its child
$W$. So the same data structures can be applied to maintain the forest
structure in degree-constrained setting.