the resulting digraph is indeed a $V^{\prime}(S)$-$V^{\prime}(T)$ DAG.

Lastly, we clarify what it means for a path to have its copy in
$D^{(h,\lambda)}$. Suppose $P=(a_{1},a_{2},\ldots)$ is a path in $D$ that
visits vertices $s=v_{1},v_{2},\ldots,v_{k}=t$ in $D$ and let $\tilde{w}_{i}$
and $\ell_{i}$ be the weight (according to $\tilde{w}$) and length of $P$
summed up to the $i$th vertex it visits. Then we let $a_{i}^{\prime}$ be the
arc from $v_{i}(\tilde{w}_{i},\ell_{i})$ to
$v_{i+1}(\tilde{w}_{i}+\tilde{w}_{a_{i}},\ell_{i}+\ell_{a_{i}})$. If
$a_{i}^{\prime}$ is in $D^{(h,\lambda)}$ for every $i$ then we call
$P^{\prime}=(a_{1}^{\prime},a_{2}^{\prime},\ldots)$ the copy of $P$ in
$D^{(h,\lambda)}$. Observe that a path in $D$ has at most one copy in
$D^{(h,\lambda)}$ but every path in $D^{(h,\lambda)}$ is the copy of some path
in $D$.

The following summarizes the key properties of our length-weight expanded
digraphs.

######  Lemma 11.2.

Let $D=(V,A)$ be a digraph with weights $w$, $S,T\subseteq V$ and some
$\lambda\leq d^{(h)}_{w}(S,T)$. Let $D^{(h,\lambda)}=(V^{\prime},A)$ be the
length-weight expanded digraph of $D$. Then $D^{(h,\lambda)}$ is an $h$-layer
$V^{\prime}(S)$-$V^{\prime}(T)$ DAG which satisfies

  1. 1.

Few Arc Copies: $|A^{\prime}(a)|\leq O(\frac{h^{2}}{\varepsilon})$.

  2. 2.

Forward Path Projection: For each path $P$ in $D$ from $S$ to $T$ of weight at
most $\lambda\cdot(1+\epsilon)$ according to $w$, there is a copy of $P$ in
$D^{(h,\lambda)}$ from $V^{\prime}(S)$ to $V^{\prime}(T)$.

  3. 3.

Backward Path Projection: If $P^{\prime}$ is a $V^{\prime}(S)$ to
$V^{\prime}(T)$ path in $D^{(h,\lambda)}$ then it is a copy of a path with
weight at most $(1+2\epsilon)\cdot\lambda$ according to $w$.

  4. 4.

Optimal Flow Preserving: the maximum $V^{\prime}(S)$-$V^{\prime}(T)$ flow on
$D^{(h,\lambda)}$ has value at least $\Omega(\frac{\varepsilon}{h^{2}})$ times
that of the maximum $h$-length flow on $D$.

###### Proof.

First, we argue that $D^{(h,\lambda)}$ is indeed a DAG. To see this, observe
that if $a^{\prime}$ is an arc in $A^{\prime}$ from $v(x_{1},h_{1})$ to
$v(x_{2},h_{2})$ then by construction it must be the case that $h_{1}<h_{2}$.
It follows that $D^{(h,\lambda)}$ has no cycles and has at most $h$ layers.
Next, observe that $D^{(h,\lambda)}$ is a $V^{\prime}(S)$-$V^{\prime}(T)$ DAG
by construction since we deleted any any vertices that do not lie on a path
between $V^{\prime}(S)$ and $V^{\prime}(T)$. Additionally, we have
$|A^{\prime}(a)|\leq O(\frac{h^{2}}{\varepsilon})$ for every $a$ since each
vertex has at most $O(\frac{h^{2}}{\varepsilon})$-many copies.

Next, consider an arc $a$ with weight $w_{a}$ according to $w$ and weight
$\tilde{w}_{a}$ according to $\tilde{w}$. Observe that since we are rounding
arc weights up we have $w_{a}\leq\tilde{w}_{a}$. Combining this with the fact
that we are rounding to multiples of $\frac{\epsilon}{h}\cdot\lambda$ we have
that

$\displaystyle w_{a}\leq\tilde{w}_{a}\leq
w_{a}+\frac{\epsilon}{h}\cdot\lambda$ (3)

We next argue our forward path projection property. That is, for each
$h$-length path $P$ in $D$ from $S$ to $T$ of weight at most
$\lambda\cdot(1+\epsilon)$ according to $w$, there is a copy of $P$ in
$D^{(h,\lambda)}$ from $V^{\prime}(S)$ to $V^{\prime}(T)$. First, observe that
$P$ consists of at most $h$-many edges and so applying Equation 3, its weight
according to $\tilde{w}$ is at most
$\lambda\cdot(1+\epsilon)+h\cdot\frac{\epsilon}{h}\cdot\lambda=\lambda\cdot(1+2\epsilon)$.
Next, observe that since $P$ has weight at most $\lambda\cdot(1+2\epsilon)$
according to $\tilde{w}$, it must have a copy in $D^{(h,\lambda)}$. In
particular, suppose $P=(a_{1},a_{2},\ldots)$ visits vertices
$s=v_{1},v_{2},\ldots,v_{k}=t$ in $D$ and let $\tilde{w}_{i}$ and $\ell_{i}$
be the weight (according to $\tilde{w}$) and length of $P$ up to the $i$th
vertex it visits. Then $D^{(h,\lambda)}$ always includes the arc from
$v_{i}(\tilde{w}_{i},\ell_{i})$ to
$v_{i+1}(\tilde{w}_{i}+\tilde{w}_{a_{i}},\ell_{i}+\ell_{a_{i}})$ since
$\tilde{w}_{i}\leq(1+2\epsilon)\lambda$ and $\ell_{i}\leq h$ for every $i$.

We argue our backward path projection property. That is, if $P^{\prime}$ is a
$V^{\prime}(S)$ to $V^{\prime}(T)$ path in $D^{(h,\lambda)}$ then it is a copy
of a path with weight at most $(1+2\epsilon)\cdot\lambda$ in $D$ according to
$w$. Since each arc in $D^{(h,\lambda)}$ is a copy of some arc in $D$, we know
that $P^{\prime}$ is a copy of _some_ path in $D$. Moreover, since we let
$v(x,h^{\prime})$ only range over $x\in\frac{h}{\epsilon}+2h$, it follows that
the weight of this path according to $\tilde{w}$ is at most
$(1+2\varepsilon)\cdot\lambda$. However, since weights according to
$\tilde{w}$ are only larger than those according to $w$ by Equation 3, it
follows that $P^{\prime}$ is a copy of a path with weight at most
$(1+2\varepsilon)\cdot\lambda$ according to $w$.

Lastly, to see the optimal flow preserving property notice that if $f^{*}$ is
the optimal $h$-length flow on $D$ then by how chose the capacities of
$D^{(h,\lambda)}$ we have that the flow that gives path $P^{\prime}$ in
$D^{(h,\lambda)}$ value $\Theta(\frac{\varepsilon}{h^{2}})\cdot f^{*}_{P}$
where $P^{\prime}$ is the copy of $P$ is indeed a feasible flow in
$D^{(h,\lambda)}$. ∎

###  11.2 Decongesting Flows

Part of what makes using our length-weight expanded digraph non-trivial is
that when we compute a flow in it and then project this flow back into $D$,
the projected flow might not respect capacities. However, this flow will only
violate capacities to a bounded extent and so in this section we show how to
resolve such flows at a bounded loss in the value of the flow. In the below we
say that an $h$-length flow $\hat{f}$ is $\alpha$-congested if any arc $a$
where $\hat{f}(a)>U_{a}$ satisfies $\hat{f}(a)\leq\alpha$.

######  Lemma 11.3.

There is a deterministic algorithm that, given a digraph $D=(V,A)$ with
capacities $U$, a length constraint $h\geq 1$, $S,T\subseteq V$ and an
$h$-length $\alpha$-congested $S$-$T$ integral flow $\hat{f}$, computes an
$S$-$T$ $h$-length integral flow $f$ where
$\text{val}(f)\geq\frac{1}{\alpha^{2}h^{2}}\cdot\text{val}(\hat{f})$ and
$|\text{supp}(f)|\leq|\text{supp}(f^{\prime})|$ in:

  1. 1.

Deterministic parallel time $\tilde{O}(\alpha^{2}\cdot h)$ with $m$
processors;

  2. 2.

Deterministic CONGEST time $\tilde{O}(\alpha^{3}\cdot h^{3})$.

###### Proof.

The basic idea is to consider the conflict graph induced by our flow paths and
then to compute a approximate maximum-weighted independent set among these
flow paths where flow paths are weighted according to their flow value.

Specifically, construct our conflict graph
$G^{\prime}=(V^{\prime},E^{\prime})$ of $\text{supp}(\hat{f})$ as follows.
$V^{\prime}=\text{supp}(\hat{f})$ has a vertex for each path in the support of
$\hat{f}$. We say that $P_{1}$ and $P_{2}$ in $\text{supp}(\hat{f})$
_conflict_ if there is some arc $a$ in both $P_{1}$ and $P_{2}$ such that
$\hat{f}(a)>U_{a}$. Then we add edge $\\{P_{1},P_{2}\\}$ to $E^{\prime}$ iff
$P_{1}$ and $P_{2}$ conflict.

Observe that since each path in $\text{supp}(\hat{f})$ consists of at most $h$
arcs and since $\hat{f}$ is $\alpha$-congested, we know that the maximum
degree in $G^{\prime}$ is at most $h\cdot\alpha$.

We then apply Theorem 5.1 to $G^{\prime}$ to compute a
$\frac{1}{h\alpha}$-approximate maximum independent set in $G^{\prime}$ in
deterministic CONGEST time $\tilde{O}(h\alpha)$ with the node weight of
$P\in\text{supp}(\hat{f})$ as $\hat{f}_{P}$. Let $\mathcal{I}$ be this
independent set and let $f=\sum_{P\in\mathcal{I}}\hat{f}_{P}$ be the flow
corresponding to this set. We return $f$.

We trivially have $|\text{supp}(f)|\leq|\text{supp}(f^{\prime})|$ by
construction of $f$.

We next argue that
$\text{val}(f)\geq\frac{\text{val}(\hat{f})}{\alpha^{2}h^{2}}$ Since the total
node weight in $G^{\prime}$ is $\text{val}(\hat{f})$ and the maximum degree in
$G^{\prime}$ is $\alpha\cdot h$, it follows that the maximum independent set
in $G^{\prime}$ has node weight at least $\frac{\text{val}(\hat{f})}{\alpha
h}$. Since $\mathcal{I}$ is $\frac{1}{\alpha h}$-approximate, we conclude that
$f$ has $\text{val}(f)\geq\frac{\text{val}(\hat{f})}{\alpha^{2}h^{2}}$.

Lastly, we argue that we achieve the claimed running times. Notice that the
total number of vertices in $G^{\prime}$ is at most $m\cdot\alpha$ because
each congested arc $a$ where $U_{a}<\hat{f}(a)\leq\alpha$ is contained in at
most $\alpha$ integral flow paths. Hence, we can simulate any CONGEST
algorithm in $G^{\prime}$ with at most $\alpha$ overhead. Theorem 5.1 tells us
that we can compute $\mathcal{I}$ in time at most $\tilde{O}(\alpha\cdot h)$
in $G^{\prime}$, giving our parallel running time.

It remains to describe how to simulate $G^{\prime}$ in $D$ in CONGEST. We keep
the following invariant: if a node $P_{1}$ in $G^{\prime}$ receives a message,
we make sure that all vertices $v\in P_{1}$ in $G$ receive the same message
too. Because of this, any vertex $v\in P_{1}$ in $G$ can determine what
$P_{1}$ as a node in $G^{\prime}$ will do next. Let us assume that each
message in $G^{\prime}$ from $P_{1}$ to $P_{2}$ is of the form
$(\texttt{msg},P_{1},P_{2})$. To simulate sending $(\texttt{msg},P_{1},P_{2})$
in $G$, a vertex $v_{1}\in P_{1}$ first forwards $(\texttt{msg},P_{1},P_{2})$
through $P_{1}$ to make sure that every node in $P_{1}$ gets this message. Let
$v_{2}\in P_{1}\cap P_{2}$ be a common vertex in both $P_{1}$ and $P_{2}$.
Then, $v_{2}$ forwards $(\texttt{msg},P_{1},P_{2})$ through $P_{2}$. After we
are done simulating all messages sent in $G^{\prime}$, our invariant is
maintained.

Now, we analyze the overhead of simulating one round of $G^{\prime}$ in $G$.
The dilation for simulating sending each message in $G^{\prime}$ is clearly
$O(h)$. Next, we analyze the congestion. Each arc $a$ is contained in at most
$\max\\{U_{a},\alpha\\}\leq\alpha U_{a}$ paths. For each such path $P$, there
are at most $\alpha h$ messages needed to sent through $a$ because the maximum
degree in $G^{\prime}$ at most $\alpha h$. Therefore, the congestion is at
most $\frac{\alpha U_{a}\cdot\alpha h}{U_{a}}=\alpha^{2}h$. Note that, here
(and nowhere else in this work) we rely on the fact that we may send
$O(U_{a})$ messages over an arc $a$ with capacity $U_{a}$ in one round of
CONGEST.

To conclude, the deterministic simulation overhead is at most dilation times
congestion which is at most $O(h)\cdot\alpha^{2}h=O(\alpha^{2}h^{2})$.
Combining this simulation with the $\tilde{O}(\alpha\cdot h)$ running time of
our approximate maximum independent set algorithm gives our CONGEST running
time. ∎

###  11.3 Computing $h$-Length $(1+\varepsilon)$-Lightest Path Blockers

Having described our length-weight expanded DAGs, their properties and how to
decongest flows that we compute using them, we now use these primitives to
build our $h$-length $(1+\epsilon)$-lightest path blockers. Again, the basic
idea is to compute the length-weight expanded DAG $D^{(h,\lambda)}$, compute
blocking flows in $D^{(h,\lambda)}$, project these back into $D$, decongest
the resulting flows and then repeat. Algorithm 3 gives our algorithm. We prove
its properties below.

Algorithm 3 $(1+\epsilon)$-Lightest Path Blocker

Input: $D=(V,A)$ with weights $w$, lengths $\ell$, capacities $U$, $h\geq 1$,
$S,T\subseteq V$, $\lambda>0$ and $\varepsilon>0$.

Output: $h$-length $(1+\varepsilon)$-lightest path blocker $f$.

Initialize solution $f$ to be $0$ on all paths.

Let $D^{(h,\lambda)}=(V^{\prime},A^{\prime})$ be the length-weight expanded
digraph of $D$ with capacities $\hat{U}=U$

for $\tilde{\Theta}(\frac{h^{7}}{\varepsilon^{2}})$ repetitions do

Blocking Flows: Let $f^{\prime}$ be a blocking integral flow in
$D^{(h,\lambda)}$ with capacities $\hat{U}$ (compute

using Lemma 7.2 with randomness or Lemma 9.1 deterministically).

Sparsify Flow: Sparsify $f^{\prime}$ so that
$|\text{supp}(f^{\prime})|\leq|A^{\prime}|$ (only for parallel alg., use 10.1)

Project Into $D$: Let $\tilde{f}$ be the $h$-length flow that gives path $P$
value $f^{\prime}_{P^{\prime}}$ where $P^{\prime}$ is the

copy of $P$ in $D^{(h,\lambda)}$.

Decongest Flow: Let $\hat{f}$ be the result of decongesting $\tilde{f}$ with
Lemma 11.3.

For each copy $a^{\prime}\in A^{\prime}$ of $a\in A$ update capacities as
$\hat{U}_{a^{\prime}}=\hat{U}_{a^{\prime}}-\hat{f}(a)$.

Update $f=f+\hat{f}$.

return $f$.

See 11.1

###### Proof.

We first argue that $f$ is a $h$-length $(1+\varepsilon)$-lightest path
blocker (Definition 11.1). $f$ is an integral $h$-length $S$-$T$ flow by
construction. Moreover, the support of $f$ is near-lightest by the backward
path projection property of $D^{(h,\lambda)}$, as stated in Lemma 11.2.

Also, notice that by the guarantees of 10.1 and Lemma 11.3 and the fact that
projecting into $D$ does not increase the support size (i.e.
$|\text{supp}(\tilde{f})|\leq|\text{supp}(f^{\prime})|$) tells us that
$|\text{supp}(\hat{f})|\leq|A^{\prime}|$ for each $\hat{f}$ (where, as a
reminder, $A^{\prime}$ is the arcs of $D^{(h,\lambda)}$) and so we know that

$\displaystyle|\text{supp}(f)|\leq\tilde{O}\left(\frac{h^{7}}{\varepsilon^{2}}\cdot|A^{\prime}|\right)$

for our parallel algorithm. Applying the fact that $|A^{\prime}|\leq
O(\frac{h^{2}}{\varepsilon})\cdot|A|$ by Lemma 11.2 gives our bound on the
support of $f$.

Thus, it remains to argue the near-lightest path blocking property of $f$ and,
in particular that if $P\in\mathcal{P}_{h}(S,T)$ is a path in $D$ and $P$ has
weight at most $(1+\varepsilon)\cdot\lambda$ according to $w$ then there is
some $a\in P$ where $f(a)=U_{a}$. Towards this, observe that by the forward
path projection property as stated in Lemma 11.2, such a path $P$ has copy in
$D^{(h,\lambda)}$. By how we construct $f$, it follows that to show
$f(a)=U_{a}$ for some $a$, it suffices to show that $\hat{U}_{a}=0$ by the end
of our algorithm. To show that such an $a$ exists, it suffices to show that
the maximum flow in $D^{(h,\lambda)}$ under the capacities $\hat{U}$ is $0$ by
the end of our algorithm.

We do so now. Our strategy will be to show that we have implicitly computed a
flow on $D^{(h,\lambda)}$ of near-optimal value and so after just a few
iterations it must be the case that the optimal flow on $D^{(h,\lambda)}$ is
reduced to $0$.

Consider a fixed iteration of our algorithm and let $\text{OPT}^{(h,\lambda)}$
be the value of the maximum $V^{\prime}(S)$-$V^{\prime}(T)$ flow on
$D^{(h,\lambda)}$. Since $f^{\prime}$ is a blocking flow in $D^{(h,\lambda)}$
and $D^{(h,\lambda)}$ is an $h$-layer DAG by Lemma 11.2, it follows from Lemma
9.4 that

$\displaystyle\text{val}(f^{\prime})\geq\frac{1}{h}\cdot\text{OPT}^{(h,\lambda)}.$
(4)

Continuing, we claim that $\tilde{f}$ is an
$O(\frac{h^{2}}{\varepsilon})$-congested flow. In particular, any arc $a$ with
capacity in $D$ greater than $O(\frac{h^{2}}{\varepsilon})$ is such that the
sum of its capacities across copies in $D^{(h,\lambda)}$ is at most
$\hat{U}_{a}$. Thus, such an arc is never overcongested by $\tilde{f}$. Any
arc with capacity less than $O(\frac{h^{2}}{\varepsilon})$ in $D^{\prime}$ has
up to $O(\frac{h^{2}}{\varepsilon})$ copies in $D^{(h,\lambda)}$ each of which
has capacity $1$; thus, such an arc may have flow value up to
$O(\frac{h^{2}}{\varepsilon})$ in $\tilde{f}$. Thus, by
$\text{val}(\tilde{f})=\text{val}(f^{\prime})$ and this bound on the
congestedness of $\tilde{f}$, we have from Lemma 11.3 that

$\displaystyle\text{val}(\hat{f})$
$\displaystyle\geq\frac{\varepsilon^{2}}{h^{6}}\cdot\text{val}(\tilde{f})$
$\displaystyle=\frac{\varepsilon^{2}}{h^{6}}\cdot\text{val}(f^{\prime}).$ (5)

Combining Equation 4 and Equation 5, we get

$\displaystyle\text{val}(\hat{f})\geq\frac{\varepsilon^{2}}{h^{7}}\cdot\text{OPT}^{(h,\lambda)}.$
(6)

Lastly, let $f^{\prime\prime}$ be $\hat{f}$ projected back into
$D^{(h,\lambda)}$. That is, if arc $a^{\prime}$ is a copy of arc $a$ then
$f^{\prime\prime}$ assigns to $a^{\prime}$ the flow value $\sum_{P\ni
a}\hat{f}_{P}$. Observe that by construction of $\hat{f}$, we know that
$f^{\prime\prime}$ is a $V^{\prime}(S)$-$V^{\prime}(T)$ flow in
$D^{(h,\lambda)}$ of value $\text{val}(f^{\prime\prime})=\text{val}(\hat{f})$.
Thus, applying this and Equation 6 we get

$\displaystyle\text{val}(f^{\prime\prime})\geq\frac{\varepsilon^{2}}{h^{7}}\cdot\text{OPT}^{(h,\lambda)}.$

Since we decrement the value of $\hat{U}_{a}$ by $f^{\prime\prime}_{a}$ in
each iteration, it follows that after
$\tilde{O}(\frac{h^{7}}{\varepsilon^{2}})$ many repetitions of Algorithm 3, we
must decrease the value of the optimal flow in $D^{(h,\lambda)}$ by at least a
constant fraction since otherwise we would have computed a flow with value
greater than that of the optimal flow. Since initially
$\text{OPT}^{(h,\lambda)}\leq\text{poly}(n)$, we get that after
$\tilde{O}(\frac{h^{7}}{\varepsilon^{2}})$-many repetitions we have reduced
the value of the optimal flow to $0$ on $D^{(h,\lambda)}$, therefore showing
that $f$ satisfies the near-lightest path blocking property.

It remains to show our running times. The computation in each of our
iterations is dominated by constructing the length-expanded digraph
$D^{(h,\lambda)}$, computing our maximal integral flow $f^{(h)}$ in
$D^{(h,\lambda)}$ and decongesting our flow.

  * •

We can construct $D^{(h,\lambda)}$ by e.g. Bellman-Ford for $\tilde{O}(h)$
rounds for a total running time of $\tilde{O}(h)$ in either CONGEST or
parallel. Likewise projecting flows back from $D^{(h,\lambda)}$ is trivial.

  * •

It is is easy to simulate $D^{(h,\lambda)}$ in either CONGEST or in parallel
with an overhead of $O(\frac{h^{2}}{\varepsilon})$ since this is a bound on
the number copies of each vertex.

With randomization, by Lemma 7.2 computing $f^{\prime}$ takes time
$\tilde{O}(h^{3})$ in parallel with $m$ processors or $\tilde{O}(h^{4})$ in
CONGEST on $D^{(h,\lambda)}$ and so $\tilde{O}(\frac{h^{5}}{\varepsilon})$ in
parallel or $\tilde{O}(\frac{h^{6}}{\varepsilon})$ in CONGEST on $D$.

For our deterministic algorithm, by Lemma 9.1 doing so takes
$\tilde{O}(h^{3})$ in parallel with $m$ processors and CONGEST time
$\tilde{O}(h^{6}\cdot(\rho_{CC})^{10})$ on $D^{(h,\lambda)}$ and so
$\tilde{O}(\frac{1}{\varepsilon}\cdot h^{5})$ parallel time on $D$ or
$\tilde{O}(\frac{1}{\varepsilon}\cdot h^{8}\cdot(\rho_{CC})^{10})$ CONGEST
time on $D$.

  * •

Lastly, decongesting our flow by Lemma 11.3 and the fact that $\tilde{f}$ is
$O(\frac{h^{2}}{\varepsilon})$-congested takes deterministic parallel time
$\tilde{O}(\frac{h^{5}}{\varepsilon^{2}})$ and deterministic CONGEST time
$\tilde{O}(\frac{h^{9}}{\varepsilon^{3}})$.

Combining these running times with our
$\tilde{O}(\frac{h^{7}}{\varepsilon^{2}})$-many repetitions gives the stated
running times. ∎

##  12 Computing Length-Constrained Flows and Moving Cuts

Having shown how to compute an $h$-length $(1+\epsilon)$-lightest path
blocker, we now use a series of these as batches to which we apply
multiplicative-weights-type updates. The result is our algorithm which returns
both a length-constrained flow and a (nearly) certifying moving cut.

Algorithm 4 Length-Constrained Flows and Moving Cuts

Input: digraph $D=(V,A)$ with lengths $\ell$, capacities $U$, $h\geq 1$,
$S,T\subseteq V$ and $\varepsilon\in(0,1)$.

Output: $(1\pm\varepsilon)$-approximate $h$-length flow $f$ and moving cut
$w$.

Let $\epsilon_{0}=\frac{\epsilon}{6}$, let
$\zeta=\frac{1+2\varepsilon_{0}}{\varepsilon_{0}}+1$ and let
$\eta=\frac{\varepsilon_{0}}{(1+\varepsilon_{0})\cdot\zeta}\cdot\frac{1}{\log
m}$.

Initialize $w_{a}\leftarrow\left(\frac{1}{m}\right)^{\zeta}$ for all $a\in A$.

Initialize $\lambda\leftarrow\left(\frac{1}{m}\right)^{\zeta}$.

Initialize $f_{P}\leftarrow 0$ for all $P\in\mathcal{P}_{h}(S,T)$.

while $\lambda<1$ do:

for $\Theta\left(\frac{h\log_{1+\epsilon_{0}}n}{\epsilon_{0}}\right)$
iterations: do

Compute $h$-length $(1+\epsilon_{0})$-lightest path blocker $\hat{f}$ (using
11.1 with current $\lambda$).

Length-Constrained Flow (Primal) Update: $f\leftarrow f+\eta\cdot\hat{f}$.

Moving Cut (Dual) Update:
$w_{a}\leftarrow(1+\epsilon_{0})^{\hat{f}(a)/U_{a}}\cdot w_{a}$ for every
$a\in A$.

$\lambda\leftarrow(1+\varepsilon_{0})\cdot\lambda$

return $(f,w)$.

As a reminder for an $h$-length flow $f$, we let $f(a):=\sum_{P\ni a}f_{P}$.
Throughout our analysis we will refer to the innermost loop of Algorithm 4 as
one “iteration.” We begin by observing that $\lambda$ always lower bounds
$d_{w}^{(h)}(S,T)$ in our algorithm.

######  Lemma 12.1.

At the beginning of each iteration of Algorithm 4 we have $\lambda\leq
d^{(h)}_{w}(S,T)$

###### Proof.

Our proof is by induction. The statement trivially holds at the beginning of
our algorithm.

Let $\lambda_{i}$ be the value of $\lambda$ at the beginning of the $i$th
iteration. We argue that if $d^{(h)}_{w}(S,T)=\lambda_{i}$ then after
$\Theta\left(\frac{h\log_{1+\epsilon_{0}}n}{\epsilon_{0}}\right)$ additional
iterations we must have
$d^{(h)}_{w}(S,T)\geq(1+\varepsilon_{0})\cdot\lambda_{i}$. Let
$\lambda_{i}^{\prime}=(1+\epsilon_{0})\cdot\lambda$ be $\lambda$ after these
iterations. Let $\hat{f}_{j}$ be our lightest path blocker in the $j$th
iteration.

Assume for the sake of contradiction that
$d_{w}^{(h)}(S,T)<\lambda_{i}^{\prime}$ after
$i+\Theta\left(\frac{h\log_{1+\epsilon_{0}}n}{\epsilon_{0}}\right)$
iterations. It follows that there is some path $P\in\mathcal{P}_{h}(S,T)$ with
weight at most $\lambda_{i}^{\prime}$ after
$i+\Theta\left(\frac{h\log_{1+\epsilon_{0}}n}{\epsilon_{0}}\right)$ many
iterations. However, notice that by definition of an $h$-length
$(1+\epsilon_{0})$-lightest path blocker (Definition 11.1), we know that for
every
$j\in\left[i,i+\Theta\left(\frac{h\log_{1+\epsilon_{0}}n}{\epsilon_{0}}\right)\right]$
there is some $a\in P$ for which $\hat{f}_{j}(a)=U_{a}$. By averaging, it
follows that there is some single arc $a\in P$ for which
$\hat{f}_{j}(a)=U_{a}$ for at least
$\Theta\left(\frac{\log_{1+\epsilon_{0}}n}{\epsilon_{0}}\right)$ of these
$j\in[i,i+\Theta\left(\frac{h\log_{1+\epsilon_{0}}n}{\epsilon_{0}}\right)]$.
Since every such arc starts with dual value $(\frac{1}{m})^{\zeta}$ and
multiplicatively increases by a $(1+\epsilon_{0})$ factor in each of these
updates, such an arc after
$i+\Theta\left(\frac{h\log_{1+\epsilon_{0}}n}{\epsilon_{0}}\right)$ many
iterations must have $w_{a}$ value at least
$(\frac{1}{m})^{\zeta}\cdot(1+\epsilon_{0})^{\Theta\left(\frac{\log_{1+\epsilon_{0}}n}{\epsilon_{0}}\right)}\geq
n^{2}$ for an appropriately large hidden constant in our $\Theta$. However, by
assumption, the weight of $P$ is at most $\lambda_{i}^{\prime}$ after
$i+\Theta\left(\frac{h\log_{1+\epsilon_{0}}n}{\epsilon_{0}}\right)$ iterations
and this is at most $2$ since $\lambda_{i}<1$ since otherwise our algorithm
would have halted. But $2<n^{2}$ and so we have arrived at a contradiction.

Repeatedly applying the fact that
$\lambda_{i}^{\prime}=(1+\epsilon_{0})\lambda_{i}$ gives that $\lambda$ is
always a lower bound on $d^{(h)}_{w}(S,T)$. ∎

We next prove the feasibility of our solution.

######  Lemma 12.2.

The pair $(f,w)$ returned by Algorithm 4 are feasible for Length-Constrained
Flow LP and Moving Cut LP respectively.

###### Proof.

First, observe that by Lemma 12.1 we know that $\lambda$ is always a lower
bound on $d_{w}^{(h)}(S,T)$ and so since we only return once $\lambda>1$, the
$w$ we return is always feasible.

To see that $f$ is feasible it suffices to argue that for each arc $a$, the
number of times a path containing $a$ has its primal value increased is at
most $\frac{U_{a}}{\eta}$. Notice that each time we increase the primal value
on a path containing arc $a$ by $\eta$ we increase the dual value of this edge
by a multiplicative $(1+\epsilon_{0})^{1/U_{a}}$. Since the weight of our arcs
according to $w$ start at $(\frac{1}{m})^{\zeta}$, it follows that if we
increase the primal value of $k$ paths incident to arc $a$ then
$w_{a}=(1+\epsilon_{0})^{k/U_{a}}\cdot(\frac{1}{m})^{\zeta}$. On the other
hand, by assumption when we increase the dual value of an arc $a$ it must be
the case that $w_{a}<1$ since otherwise $d_{w}^{(h)}(S,T)\geq 1$,
contradicting the fact that $\lambda$ always lower bounds $d_{w}^{(h)}(S,T)$.
It follows that $(1+\epsilon_{0})^{k/U_{a}}\cdot(\frac{1}{m})^{\zeta}\leq 1$
and so applying the fact that
$\ln(1+\epsilon_{0})\geq\frac{\epsilon_{0}}{1+\epsilon_{0}}$ for
$\epsilon_{0}>-1$ and our definition of $\zeta$ and $\eta$ we get

$\displaystyle k$
$\displaystyle\leq\frac{\zeta\cdot(1+\varepsilon_{0})}{\varepsilon_{0}}\cdot
U_{a}\log m$ $\displaystyle=\frac{U_{a}}{\eta}$

as desired. ∎

We next prove the near-optimality of our solution.

######  Lemma 12.3.

The pair $(f,w)$ returned by Algorithm 4 satisfies
$(1-\epsilon)\sum_{a}w_{a}\leq\sum_{P}f_{P}$.

###### Proof.

Fix an iteration $i$ of the above while loop and let $\hat{f}$ be our lightest
path blocker in this iteration. Let $k_{i}$ be $\text{val}(\hat{f})$, let
$\lambda_{i}$ be $\lambda$ at the start of this iteration and let
$D_{i}:=\sum_{a}w_{a}$ be our total dual value at the start of this iteration.
Notice that $\frac{1}{\lambda_{i}}\cdot w$ is dual feasible and has cost
$\frac{D_{i}}{\lambda_{i}}$ by Lemma 12.1. If $\beta$ is the optimal dual
value then by optimality it follows that $\beta\leq\frac{D_{i}}{\lambda_{i}}$,
giving us the upper bound on $\lambda_{i}$ of $\frac{D_{i}}{\beta}$. By how we
update our dual, our bound on $\lambda_{i}$ and $(1+x)^{r}\leq 1+xr$ for any
$x\geq 0$ and $r\in(0,1)$ we have that

$\displaystyle D_{i+1}$
$\displaystyle=\sum_{a}(1+\epsilon_{0})^{\hat{f}(a)/U_{a}}\cdot w_{a}\cdot
U_{a}$
$\displaystyle\leq\sum_{a}\left(1+\frac{\epsilon_{0}\hat{f}(a)}{U_{a}}\right)\cdot
w_{a}\cdot U_{a}$ $\displaystyle=D_{i}+\epsilon_{0}\sum_{a}\hat{f}(a)w_{a}$
$\displaystyle\leq D_{i}+\epsilon_{0}(1+2\varepsilon_{0})\cdot
k_{i}\lambda_{i}$ $\displaystyle\leq
D_{i}\left(1+\frac{(1+2\varepsilon_{0})\varepsilon_{0}\cdot
k_{i}}{\beta}\right)$ $\displaystyle\leq
D_{i}\cdot\exp\left(\frac{(1+2\varepsilon_{0})\varepsilon_{0}\cdot
k_{i}}{\beta}\right).$

Let $T-1$ be the index of the last iteration of our algorithm; notice that
$D_{T}$ is the value of $w$ in our returned solution. Let $K:=\sum_{i}k_{i}$.
Then, repeatedly applying this recurrence gives us

$\displaystyle D_{T}$ $\displaystyle\leq
D_{0}\cdot\exp\left(\frac{(1+2\varepsilon_{0})\varepsilon_{0}\cdot
K}{\beta}\right)$
$\displaystyle=\left(\frac{1}{m}\right)^{\zeta-1}\exp\left(\frac{(1+2\varepsilon_{0})\varepsilon_{0}\cdot
K}{\beta}\right)$

On the other hand, we know that $w$ is dual feasible when we return it, so it
must be the case that $D_{T}\geq 1$. Combining this with the above upper bound
on $D_{T}$ gives us
$1\leq\left(\frac{1}{m}\right)^{\zeta}\exp\left(\frac{(1+2\varepsilon_{0})\varepsilon_{0}\cdot
K}{\beta}\right)$. Solving for $K$ and using our definition of $\zeta$ gives
us

$\displaystyle\beta\log
m\cdot\frac{\zeta-1}{(1+2\varepsilon_{0})\cdot\varepsilon_{0}}$
$\displaystyle\leq K$ $\displaystyle\beta\log
m\cdot\frac{1}{\varepsilon_{0}^{2}}$ $\displaystyle\leq K.$

However, notice that $K\eta$ is the primal value of our solution so using our
choice of $\eta$ and rewriting this inequality in terms of $K\eta$ by
multiplying by
$\eta=\frac{\varepsilon_{0}}{(1+\varepsilon_{0})\cdot\zeta}\cdot\frac{1}{\log
m}$ and applying our definition of
$\zeta=\frac{1+2\varepsilon_{0}}{\varepsilon_{0}}+1$ gives us

$\displaystyle\frac{\beta}{\varepsilon_{0}\cdot(1+\varepsilon_{0})\cdot\zeta}$
$\displaystyle\leq K\eta$
$\displaystyle\frac{\beta}{(1+\varepsilon_{0})(1+3\varepsilon_{0})}$
$\displaystyle\leq K\eta.$ (7)

Moreover, by our choice of $\varepsilon_{0}=\frac{\varepsilon}{6}$ and the
fact that $\frac{1}{1+x+x^{2}}\geq 1-x$ for $x\in(0,1)$ we get

$\displaystyle 1-\varepsilon$
$\displaystyle\leq\frac{1}{1+\varepsilon+\varepsilon^{2}}$
$\displaystyle\leq\frac{1}{(1+\frac{1}{2}\varepsilon)^{2}}$
$\displaystyle\leq\frac{1}{(1+3\varepsilon_{0})^{2}}$
$\displaystyle\leq\frac{1}{(1+\varepsilon_{0})(1+3\varepsilon_{0})}.$ (8)

Combining Equation 7 and Equation 8 we conclude that

$\displaystyle(1-\varepsilon)\cdot\beta\leq K\eta.$

∎

We conclude with our main theorem by proving that we need only iterate our
algorithm $\tilde{O}\left(\frac{h}{\epsilon^{4}}\right)$ times. See 3.1

###### Proof.

We use Algorithm 4. By Lemma 12.2 and Lemma 12.3 we know that our solution is
feasible and $(1\pm\epsilon)$-optimal so it only remains to argue the runtime
of our algorithm and that the returned flow decomposes in the stated way.

We argue that we must only run for
$O\left(\frac{h\log^{2}n}{\epsilon^{4}}\right)$ total iterations. Since
$\lambda$ increases by a multiplicative $(1+\epsilon_{0})$ after every
$\Theta\left(\frac{h\log n}{\epsilon_{0}^{2}}\right)$ iterations and starts at
at least $\left(\frac{1}{m}\right)^{\Theta(1/\varepsilon_{0})}$, it follows by
Lemma 12.1 that after $y\cdot\Theta\left(\frac{h\log
n}{\epsilon_{0}^{2}}\right)$ total iterations the $h$-length distance between
$S$ and $T$ is at least
$(1+\epsilon_{0})^{y}\cdot\left(\frac{1}{m}\right)^{\Theta(1/\varepsilon_{0})}$.
Thus, for
$y\geq\Omega\left(\frac{\log_{1+\epsilon_{0}}m}{\epsilon_{0}}\right)=\Omega\left(\frac{\log
n}{\epsilon_{0}^{2}}\right)$ we have that $S$ and $T$ are at least $1$ apart
in $h$-length distance. Consequently, our algorithm must run for at most
$O\left(\frac{h\log^{2}n}{\epsilon_{0}^{4}}\right)=O\left(\frac{h\log^{2}n}{\epsilon^{4}}\right)$
many iterations.

Our running time is immediate from the the bound of
$O\left(\frac{h\log^{2}n}{\epsilon^{4}}\right)$ on the number of iterations of
the while loop and the running times given in 11.1 for computing our
$h$-length $(1+\epsilon_{0})$-lightest path blocker.

Lastly, the flow decomposes in the stated way because we have at most
$O\left(\frac{h\log^{2}n}{\epsilon^{4}}\right)$ iterations and each $f_{j}$ is
an integral $S$-$T$ flow by 11.1. Thus, our final solution is
$\eta\cdot\sum_{j=1}^{k}f_{j}$ and
$k=\tilde{O}\left(\frac{h}{\epsilon^{4}}\right)$. Likewise we have
$|\text{supp}(f)|\leq\tilde{O}(\frac{h^{10}}{\varepsilon^{7}})$ for our
parallel algorithm since we have
$O\left(\frac{h\log^{2}n}{\epsilon^{4}}\right)$ iterations and the fact that
11.1 guarantees each $(1+\varepsilon_{0})$-lightest path blocker has support
size at most $\tilde{O}(\frac{h^{9}}{\varepsilon^{3}}\cdot|A|)$. ∎

##  13 Application: Maximal and Maximum Disjoint Paths

In this section we show that our main theorem (3.1) almost immediately gives
deterministic CONGEST algorithms for many varieties of maximal disjoint path
problems as well as essentially-optimal algorithms for many maximum disjoint
path problems. In Section 13.1 we give the variants we study. In Section 13.2
we observe that it suffices to solve the arc-disjoint directed variants of
these problems. Lastly, we give our results for maximal and maximum disjoint
path problems in Section 13.3 and Section 13.4 respectively where we observe
in Section 13.5 that our algorithms for the latter are essentially optimal.

###  13.1 Maximal and Maximum Disjoint Path Variants

We consider the following maximal disjoint path variants.

> Maximal Vertex-Disjoint Paths: Given graph $G=(V,E)$, length constraint
> $h\geq 1$ and two disjoint sets $S,T\subseteq V$, find a collection of
> $h$-length vertex-disjoint $S$ to $T$ paths $\mathcal{P}$ such that any
> $h$-length $S$ to $T$ path shares a vertex with at least one path in
> $\mathcal{P}$.

> Maximal Edge-Disjoint Paths: Given graph $G=(V,E)$, length constraint $h\geq
> 1$ and two disjoint sets $S,T\subseteq V$, find a collection of $h$-length
> edge-disjoint $S$ to $T$ paths $\mathcal{P}$ such that any $h$-length $S$ to
> $T$ path shares an edge with at least one path in $\mathcal{P}$.

> Maximal Vertex-Disjoint Directed Paths: Given digraph $D=(V,A)$, length
> constraint $h\geq 1$ and two disjoint sets $S,T\subseteq V$, find a
> collection of $h$-length vertex-disjoint $S$ to $T$ paths $\mathcal{P}$ such
> that any $h$-length $S$ to $T$ path shares a vertex with at least one path
> in $\mathcal{P}$.

> Maximal Arc-Disjoint Directed Paths: Given digraph $D=(V,A)$, length
> constraint $h\geq 1$ and two disjoint sets $S,T\subseteq V$, find a
> collection of $h$-length arc-disjoint $S$ to $T$ paths $\mathcal{P}$ such
> that any $h$-length $S$ to $T$ path shares an arc with at least one path in
> $\mathcal{P}$.

As discussed in Section 1.1, the existence of efficient deterministic
algorithms for the above problems (specifically the maximal vertex-disjoint
paths problem) in CONGEST was stated as an open question by Chang and
Saranurak [18] and the lack of these algorithms is a major barrier to simple
deterministic constructions of expander decompositions.

We consider the following maximum disjoint path variants.

> Maximum Vertex-Disjoint Paths: Given graph $G=(V,E)$, length constraint
> $h\geq 1$ and disjoint sets $S,T\subseteq V$, find a max cardinality
> collection of $h$-length vertex-disjoint $S$ to $T$ paths.

> Maximum Edge-Disjoint Paths: Given graph $G=(V,E)$, length constraint $h\geq
> 1$ and disjoint sets $S,T\subseteq V$, find a max cardinality collection of
> $h$-length edge-disjoint $S$ to $T$ paths.

> Maximum Vertex-Disjoint Directed Paths: Given digraph $D=(V,A)$, length
> constraint $h\geq 1$ and disjoint sets $S,T\subseteq V$, find a max
> cardinality collection of $h$-length vertex-disjoint $S$ to $T$ paths.

> Maximum Arc-Disjoint Directed Paths: Given digraph $D=(V,A)$, length
> constraint $h\geq 1$ and disjoint sets $S,T\subseteq V$, find a max
> cardinality collection of $h$-length arc-disjoint $S$ to $T$ paths.

###  13.2 Reducing Among Variants

We begin by observing that the arc-disjoint directed paths problem is the
hardest of the above variants and so it will suffice to solve this problem.
The reductions we use are illustrated in Figure 8.

(a) Vertex-disjoint paths.

(b) Edge-disjoint paths.

(c) Vertex-disjoint directed paths.

Figure 8: Illustration of our reduction on a single edge or arc between $u$
and $v$ for reducing maximal or maximum vertex-disjoint paths, edge-disjoint
paths or vertex-disjoint directed paths to arc-disjoint directed paths.

######  Lemma 13.1.

If there is a deterministic algorithm for maximal arc-disjoint directed paths
in CONGEST running in time $T$ then there are deterministic CONGEST algorithms
for maximal vertex-disjoint paths, edge-disjoint paths and vertex-disjoint
directed paths all running in time $O(T)$.

Likewise, if there is a deterministic (resp. randomized) parallel with $m$
processors or CONGEST algorithm for maximum arc-disjoint directed paths in
CONGEST running in time $T$ with approximation ratio $\tilde{O}(h)$ then there
are deterministic (resp. randomized) parallel with $m$ processors and CONGEST
algorithms for maximum vertex-disjoint paths, edge-disjoint paths and vertex-
disjoint directed paths all running in time $O(T)$ with approximation ratio
$\tilde{O}(h)$.

###### Proof.

We reduce each of maximal vertex-disjoint paths, maximal edge-disjoint paths
and maximal vertex-disjoint directed paths to maximal arc-disjoint directed
paths and do the same for the maximum variants of these problems.

##### Reducing from maximal/maximum vertex-disjoint paths.

Consider an instance of maximal or maximum vertex-disjoint paths on graph
$G=(V,E)$ with length constraint $h$ and vertex sets $S$ and $T$. We create a
digraph $D=(V^{\prime},A)$ as follows:

  * •

Vertices: $V^{\prime}$ is constructed as follows: for each $v\in V$ we add to
$V^{\prime}$ vertex $v^{(i)}$ and $v^{(o)}$.

  * •

Arcs: For each $v\in V$ we add an arc from $v^{(i)}$ to $v^{(o)}$.
Furthermore, for each $e=\\{u,v\\}\in E$ we add to $A$ the arcs
$(u^{(o)},v^{(i)})$ and $(v^{(o)},u^{(i)})$.

A collection of arc-disjoint paths in $D$ from $S^{\prime}=\\{s^{(i)}:s\in
S\\}$ to $T^{\prime}=\\{t^{(o)}:t\in T\\}$ with length constraint $2h-1$
uniquely corresponds to an equal cardinality collection of $S$-$T$ vertex-
disjoint paths in $G$ with length constraint $h$. Thus, an $\tilde{O}(h)$
approximation on $D$ for the maximum $S^{\prime}$-$T^{\prime}$ arc-disjoint
directed paths problem gives an $\tilde{O}(h)$ approximation for the maximum
vertex-disjoint paths problem on $G$. Likewise, a maximal collection of arc-
disjoint $S^{\prime}$-$T^{\prime}$ paths on $D$ with length constraint $2h-1$
corresponds to a maximal collection of vertex-disjoint $S$-$T$ paths with
length constraint $h$. Lastly, a $T$-time CONGEST algorithm on $D$ can be
simulated on $G$ in time $O(T)$ since each $v\in V$ can simulate $v^{(o)}$ and
$v^{(i)}$.

##### Reducing from maximal/maximum edge-disjoint paths.

Consider an instance of maximal or maximum edge-disjoint paths on graph
$G=(V,E)$ with length constraint $h$ and vertex sets $S$ and $T$. We create a
digraph $D=(V^{\prime},A)$ as follows:

  * •

Vertices: $V^{\prime}$ consists of $V$ along with two vertices for each edge
$e$, namely $x_{e}^{(i)}$ and $v_{e}^{(o)}$ for each $e\in E$.

  * •

Arcs: For each $e\in\\{u,v\\}\in E$ we add to $A$ an arc from $x_{e}^{(i)}$ to
$x_{e}^{(o)}$ as well as an arc from $u$ and $v$ to $x_{e}^{(i)}$ and an arc
from $x_{e}^{(o)}$ to $u$ and $v$.

A collection of arc-disjoint $S$-$T$ paths in $D$ with length constraint $3h$
uniquely corresponds to an equal cardinality collection of $S$-$T$ edge-
disjoint paths in $G$ with length constraint $h$. Thus, an $\tilde{O}(h)$
approximation on $D$ for the maximum $S$-$T$ arc-disjoint directed paths
problem gives an $\tilde{O}(h)$ approximation for the maximum edge-disjoint
paths problem on $G$. Likewise, a maximal collection of arc-disjoint $S$-$T$
paths on $D$ with length constraint $3h$ corresponds to a maximal collection
of edge-disjoint $S$-$T$ paths with length constraint $h$ on $G$. Lastly, a
$T$-time CONGEST algorithm on $D$ can be simulated on $G$ in time $O(T)$ since
the endpoints of $e\in E$ can simulate $x_{e}^{(i)}$ and $x_{e}^{(o)}$ with
constant overhead.

##### Reducing from maximal/maximum vertex-disjoint directed paths.

Consider an instance of maximal or maximum vertex-disjoint directed paths on
graph $D=(V,A)$ with length constraint $h$ and vertex sets $S$ and $T$. We
create a digraph $D^{\prime}=(V^{\prime},A^{\prime})$ as follows:

  * •

Vertices: $V^{\prime}$ consists of vertices $v^{(o)}$ and $v^{(i)}$ for each
$v\in V$.

  * •

Arcs: For each $v\in V$ we add to $A^{\prime}$ the arc $(v^{(i)},v^{(o)})$.
For each arc $a=(u,v)\in A$ we add to $A^{\prime}$ the arc
$(u^{(o)},v^{(i)})$.

A collection of arc-disjoint paths in $D^{\prime}$ from
$S^{\prime}=\\{s^{(i)}:s\in S\\}$ to $T^{\prime}=\\{t^{(o)}:t\in T\\}$ with
length constraint $2h-1$ uniquely corresponds to an equal cardinality
collection of $S$-$T$ vertex-disjoint paths in $D$ with length constraint $h$.
Thus, an $\tilde{O}(h)$ approximation on $D^{\prime}$ for the maximum
$S^{\prime}$-$T^{\prime}$ arc-disjoint directed paths problem gives an
$\tilde{O}(h)$ approximation for the maximum $S$-$T$ vertex-disjoint directed
paths problem on $D$. Likewise, a maximal collection of arc-disjoint
$S^{\prime}$-$T^{\prime}$ paths on $D^{\prime}$ with length constraint $2h-1$
corresponds to a maximal collection of vertex-disjoint $S$-$T$ paths with
length constraint $h$ on $D$. Lastly, a $T$-time CONGEST algorithm on
$D^{\prime}$ can be simulated on $D$ in time $T$ each $v\in V$ can simulate
$v^{(i)}$ and $v^{(o)}$. ∎

###  13.3 Maximal Disjoint Path Algorithms

We now observe that our length-constrained flow algorithms allow us to solve
maximal arc-disjoint directed paths and therefore all of the above variants
efficiently.

######  Theorem 13.2.

There are deterministic CONGEST algorithms for maximal vertex-disjoint paths,
edge-disjoint paths, vertex-disjoint directed paths and arc-disjoint directed
paths running in time
$\tilde{O}\left(h^{18}+h^{17}\cdot(\rho_{CC})^{10}\right)$.

###### Proof.

By Lemma 13.1, it suffices to show that maximal arc-disjoint directed paths
can be solved in time
$\tilde{O}\left(h^{18}+h^{17}\cdot(\rho_{CC})^{10}\right)$. We proceed to do
so on digraph $D$ with length constraint $h$ and vertex sets $S$ and $T$ for
the rest of this proof.

Specifically, we repeat the following until no path between $S$ and $T$
consists of $h$ or fewer edges. Apply 3.1 to compute a
$(1-\epsilon)$-approximate $h$-length $S$-$T$ flow $f$ in $D$ for
$\epsilon=.5$ (any constant would suffice) with unit capacities. By the
properties of $f$ as guaranteed by 3.1, we have that
$f=\eta\cdot\sum_{j=1}^{k}f_{j}$ for $\eta=\tilde{\Theta}(1)$ and
$k=\tilde{O}\left(h\right)$ where each $f_{j}$ is an integral flow. For each
vertex $v$ we let $f_{j}^{(v)}$ be $f_{j}$ restricted to its flow paths out of
$v$ and let
$f_{j^{*}}^{(v)}:=\operatorname*{arg\,max}_{f_{j}^{(v)}}\text{val}(f_{j}^{(v)})$.
Then, we let $f_{j^{*}}:=\sum_{v}f_{j^{*}}^{(v)}$ (notice that we cannot
simply define $f_{j^{*}}$ as
$\operatorname*{arg\,max}_{f_{j}}\text{val}(f_{j})$ since we cannot compute
$\text{val}(f_{j})$ efficiently in CONGEST because $D$ may have diameter much
larger than $h$). Observe that since $f_{j^{*}}$ is integral and $h$-length,
it exactly corresponds to an arc-disjoint collection of $S$-$T$ paths
$\mathcal{P}^{\prime}$ in $D$ each of which consists of at most $h$ edges. We
add $\mathcal{P}^{\prime}$ to $\mathcal{P}$, delete from $D$ any arc incident
to a path of $\mathcal{P}^{\prime}$ and continue to the next iteration.

As the above algorithm removes at least one path from $S$ to $T$ each time, it
clearly terminates with a feasible solution for the maximal arc-disjoint
directed paths problem.

Stronger, though, we claim that we need only iterate the above
$\tilde{O}(h)$-many times until $S$ and $T$ are disconnected. Specifically,
fix one iteration and let $\mathcal{P}^{*}$ be the collection of vertex-
disjoint paths from $S$ to $T$ of maximum cardinality at the beginning of this
iteration. By the $(1-\epsilon)$-optimality of our flow and an averaging
argument we have that
$\text{val}(f_{j^{*}})\geq\tilde{\Omega}\left(\frac{1}{h}\right)\cdot|\mathcal{P}^{*}|$
which is to say that
$|\mathcal{P}^{\prime}|\geq\tilde{\Omega}\left(\frac{1}{h}\right)\cdot|\mathcal{P}^{*}|$.
However, it follows that after $\tilde{\Theta}(h)$-many iterations for a large
hidden constant we must at least halve $|P^{*}|$ since otherwise we would have
computed a collection of vertex-disjoint $S$-$T$ paths whose cardinality is
larger than the largest cardinality of any set of vertex-disjoint $S$-$T$
paths. Since initially $|P^{*}|\leq n$, it follows that after iterating the
above $\tilde{O}(h)$-many times we have reduced $|P^{*}|$ to $0$ which is to
say we have solved the maximal arc-disjoint directed paths problem.

Our running time is immediate from 3.1 and the above bound we provide on the
number of required iterations of $\tilde{O}(h)$ as well as the fact that each
vertex can easily compute $f_{j^{*}}^{(v)}$ and $\mathcal{P}$
deterministically in parallel or CONGEST time $\tilde{O}(h)$ since our flows
are $h$-length. ∎

Applying the fact that it is known that $\rho_{CC}\leq 2^{O(\sqrt{\log n})}$
(see Section 5.4), the above gives deterministic CONGEST algorithms running in
time $\tilde{O}(\text{poly}(h)\cdot 2^{O(\sqrt{\log n})})$. If $\rho_{CC}$
where improved to be poly-log in $n$ then we would get a
$\tilde{O}(\text{poly}(h))$ running time.

###  13.4 Maximum Disjoint Path Algorithms

Lastly, we observe that our length-constrained flow algorithms allow us to
$\tilde{O}(h)$-approximate maximum arc-disjoint directed paths and therefore
all of the above variants efficiently.

######  Theorem 13.3.

There are $\tilde{O}(h)$-approximation algorithms for maximum vertex-disjoint
paths, edge-disjoint paths, vertex-disjoint directed paths and arc-disjoint
directed paths running in:

  * •

Deterministic parallel time $\tilde{O}(h^{17})$ with $m$ processors;

  * •

Randomized CONGEST time $\tilde{O}(h^{17})$ with high probability;

  * •

Deterministic CONGEST time
$\tilde{O}\left(h^{17}+h^{16}\cdot(\rho_{CC})^{10}\right)$.

###### Proof.

By Lemma 13.1, it suffices to provide a $\tilde{O}(h)$-approximate algorithm
for maximum arc-disjoint directed paths with the stated running times. We do
so for the rest of this proof. Let the input be digraph $D=(V,A)$ with length
constraint $h\geq 1$ and disjoint sets $S,T\subseteq V$.

We apply 3.1 to compute an $\epsilon$-approximate $h$-length constrained flow
$f$ in $D$ for $\epsilon=.5$ (any constant would suffice) and capacities
$U_{a}=1$ for every $a$. By the properties of $f$ as guaranteed by 3.1, we
have that $f=\eta\cdot\sum_{j=1}^{k}f_{j}$ for $\eta=\Theta(1)$ and
$k=\tilde{O}\left(h\right)$ where each $f_{j}$ is an integral flow. For each
vertex $v$ we let $f_{j}^{(v)}$ be $f_{j}$ restricted to its flow paths out of
$v$ and let
$f_{j^{*}}^{(v)}:=\operatorname*{arg\,max}_{f_{j}^{(v)}}\text{val}(f_{j}^{(v)})$.
Then, we let $f_{j^{*}}:=\sum_{v}f_{j^{*}}^{(v)}$. Observe that since
$f_{j^{*}}$ is integral and $h$-length, it exactly corresponds to an arc-
disjoint collection of paths $\mathcal{P}$ in $D$ each of which consists of at
most $h$ edges. We return $\mathcal{P}$ as our solution.

Letting $\mathcal{P}^{*}$ be the optimal solution to the input problem we have
by $k=\tilde{O}(h)$ and an averaging argument that

$\displaystyle|\mathcal{P}|=\text{val}(f_{j^{*}})\geq\tilde{\Omega}\left(\frac{1}{h}\right)\cdot|\mathcal{P}^{*}|$

and so our solution is $\tilde{\Omega}(\frac{1}{h})$-approximate.

For our running time, observe that each vertex can easily compute
$f_{j^{*}}^{(v)}$ and $\mathcal{P}$ deterministically in parallel or CONGEST
time $\tilde{O}(h)$ since our flows are $h$-length. Thus, our running time is
dominated by 3.1. ∎

###  13.5 On the Hardness of Maximum Disjoint Paths

Guruswami et al. [35] give hardness results for a variety of length-
constrained maximum disjoint path problems. In their work they state hardness
of approximation result in terms of $m$, the number of edges in the graph. In
the following we restate these results but in terms of $h$, the length-
constraint.

######  Theorem 13.4 (Adaptation of Theorem 1 of Guruswami et al. [35]).

Assume the strong exponential time hypothesis (SETH). Then there does not
exist a polynomial-time $O(h)$-approximation algorithm solving the maximum
arc-disjoint directed paths problem for instances where $h=\Omega(\log n)$.

Observe that it follows that assuming SETH, the parallel algorithm in Theorem
13.3 is optimal up to poly-logs.

##  14 Application: Simple Distributed Expander Decompositions

In this section, we explain how our maximal disjoint path algorithm can
significantly simplify the distributed deterministic expander decomposition of
Chang and Saranurak [18].

The key algorithmic primitive of [18] in their distributed deterministic
expander decomposition is their Lemma D.8. Instead of computing maximal
bounded-hop disjoint paths, they were only be able to compute a set of paths
that are “nearly maximal”. The formal statement is as follows:

######  Lemma 14.1 (Nearly maximal disjoint paths (Lemma D.8 of [18]).

Consider a graph $G=(V,E)$ of maximum degree $\Delta$. Let $S\subseteq V$ and
$T\subseteq V$ be two subsets. There is an
$O(d^{3}\beta^{-1}\log^{2}\Delta\log n)$-round deterministic algorithm that
finds a set $P$ of $S-T$ vertex-disjoint paths of length at most $d$, together
with $a$ vertex set $B$ of size at most $\beta|V\setminus T|<\beta|V|$, such
that any $S-T$ path of length at most $d$ that is vertex-disjoint to all paths
in $P$ must contain a vertex in $B$.

The set $P$ from the lemma is nearly maximal in the sense that if $B$ is
deleted from $G$, then $P$ would be maximal. However, we can see that there
might possibly be many additional disjoint paths that go through $B$. This set
$B$ complicates all of their later algorithmic steps.

The high-level summary of the issue is that all their flow primitives that are
based on Lemma D.8 must work with source/sink sets that are very big only.
Otherwise, the guarantee becomes meaningless or the running time becomes very
slow.

Now, we explain in more details. Given two sets $S$ and $T$ where
$|S|\leq|T|$, normally if the matching player from the cut-matching game does
not return a sparse cut, then it returns an embedding of a matching where
every vertex in $S$ is matched to some vertex in $T$. However, in Lemma D.9 of
[18], the matching player based on Lemma D.8 may return an embedding that
leaves as many as $\approx\beta|V\setminus T|$ vertices in $S$ unmatched. This
is called the “left-over” set. We think of $\beta\geq 1/n^{o(1)}$ as the round
complexity of Lemma D.8 is proportional to $\beta^{-1}$. Therefore, it is only
when $|S|,|T|\geq 2\beta|V|\geq|V|/n^{o(1)}$ that Lemma D.9 in [18] may give
some meaningful guarantee, yet this is still weaker than normal.

The same issue holds for their multi-commodity version of the matching player
(i.e. Lemma D.11 of [18]). For the same reasoning, the lemma is meaningful
only when the total number of source and sink is at least $\Omega(\beta|V|)$.
The issue propagates to their important subroutine (Theorem 4.1 of [18]) for
computing most balanced sparse cut. The guarantee holds when only the returned
cut $C$ is such that $|C|\geq\Omega(\beta|V|)$. At the end, they managed to
obtain an deterministic expander decomposition (just treat the edges incident
to the left-over part as inter-cluster edges at the end). However, they need
to keep track of this left-over parameter from the first basic primitive until
the end result.

In contrast, in their randomized algorithm for computing expander
decomposition, this issues does not appear anyway because of the randomized
maximal disjoint path algorithm. Therefore, by plugging in our deterministic
maximal disjoint path algorithm into the expander decomposition of [18], all
these issue will be resolved immediately.

##  15 Application: $(1-\epsilon)$-Approximate Distributed Bipartite
$b$-Matching

In this section we give the first efficient $(1-\epsilon)$-approximate CONGEST
algorithms for maximum cardinality bipartite $b$-matching. In fact, our
results are for the slightly more general edge-capacitated maximum bipartite
$b$-matching problem, defined as follow.

> Edge-Capacitated Maximum Bipartite $b$-Matching: Given bipartite graph
> $G=(V,E)$, edge capacities $U$ and function $b:V\to\mathbb{Z}_{>0}$ compute
> an integer $x_{e}\in[0,U_{e}]$ for each $e\in E$ maximizing $\sum_{e}x_{e}$
> so that for each $v\in V$ we have $\sum_{e\in\delta(v)}x_{e}\leq b(v)$.

Notice that the case where $b(v)=1$ for every $v$ is just the classic maximum
cardinality matching problem. “$b$-matching” seems to refer to two different
problems in the literature depending on whether edges can be chosen with
multiplicity: either it is the above problem where $U_{e}=1$ for every $e\in
E$ or it is the above problem where $U_{e}=\max_{v}b_{v}$ for each $e\in E$.
Our algorithms will work for both of these variants since they solve the above
problem which generalizes both of these problems.

The following theorem summarizes our main result for bipartite $b$-matching in
CONGEST. Again, recall that $\rho_{CC}$ is defined in Definition 5.7 and is
known to be at most $2^{O(\sqrt{\log n})}$.

######  Theorem 15.1.

There is a deterministic $(1-\epsilon)$-approximation for edge-capacitated
maximum bipartite $b$-matching running in CONGEST time
$\tilde{O}\left(\frac{1}{\varepsilon^{9}}+\frac{1}{\varepsilon^{7}}\cdot(\rho_{CC})^{10}\right)$.

###### Proof.

Our algorithm works in two steps. First, we reduce edge-capacitated
$b$-matching to length-constrained flow and use our length constrained flow
algorithm to efficiently compute a fractional flow. Then, we apply the flow
rounding technology we developed in Section 9.2 to round this flow to an
integral flow which, in turn, corresponds to an integral $b$-matching.

More formally our algorithm is as follows. Suppose we are given an instance of
edge-capacitated $b$-matching on bipartite graph $G=(V,E)$. Let $L$ and $R$ be
the corresponding bipartition of vertices of $G$. We construct the following
instance of length-constrained flow on digraph $D=(V^{\prime},A)$ with $h=3$
as follows. Each $v\in V$ has two copies $v^{(i)}$ and $v^{(o)}$ in
$V^{\prime}$. We add arc $(v^{(i)},v^{(o)})$ to $A$ with capacity $b(v)$. If
$\\{u,v\\}\in E$ where $u\in L$ and $v\in R$ then we add arc
$(u^{(o)},v^{(i)})$ with capacity $U_{e}$ to $A$. Lastly, we let
$S=\\{u^{(i)}:u\in L\\}$, $T=\\{v^{(o)}:v\in R\\}$ and the length of each arc
in $D$ be $1$. Next, we apply 3.1 to compute a
$(1-\varepsilon_{1})$-approximate maximum $3$-length $S$-$T$ flow $f$ on $D$
for some small $\varepsilon_{1}$ to be chosen later. Since $D$ is a $3$-layer
$S$-$T$ DAG we may interpret this as a (non-length-constrained) flow where the
flow value on arc $a$ is $f(a)$.

We then apply Lemma 9.6 to this non-length-constrained flow to get integral
$S$-$T$ flow $f^{\prime}$ satisfying
$\text{val}(f^{\prime})\geq(1-\varepsilon_{2})\cdot\text{val}(f)$ for some
small $\varepsilon_{2}$ to be chosen later. We return as our solution the
$b$-matching which naturally corresponds to $f^{\prime}$. Namely, if
$e=\\{u,v\\}$ then since $f^{\prime}$ is integral it assigns arc
$(u^{(o)},v^{(i)})$ a value in $\\{0,1,\ldots,U_{e}\\}$. We let $x_{e}$ be
this value for $e=\\{u,v\\}$ and we return as our $b$-matching solution
$\\{x_{e}\\}_{e}$.

$f^{\prime}$ is a $(1-\varepsilon_{1})(1-\varepsilon_{2})$-approximate maximum
$S$-$T$ flow. Letting OPT be the value of the optimal $b$-matching solution,
it is easy to see that the maximum $S$-$T$ flow has value OPT and so the
solution we return has value at least
$(1-\varepsilon_{1})(1-\varepsilon_{2})\cdot\text{OPT}$. Letting
$\varepsilon_{1}=\varepsilon_{2}=\Theta(\varepsilon)$ for an appropriately
small hidden constant we get that
$(1-\varepsilon_{1})(1-\varepsilon_{2})\cdot\text{OPT}\geq(1-\varepsilon)\cdot\text{OPT}$.

Lastly, we argue our running time. Our running time is dominated by one call
to 3.1 with $\varepsilon_{1}=\Theta(\varepsilon)$ which takes
$\tilde{O}\left(\frac{1}{\varepsilon^{9}}+\frac{1}{\varepsilon^{7}}\cdot(\rho_{CC})^{10}\right)$
and one call to Lemma 9.6 with $\varepsilon_{2}=\Theta(\varepsilon)$ which
takes $\tilde{O}(\frac{1}{\varepsilon^{5}}\cdot(\rho_{CC})^{10})$. Combining
these running times gives the overall running time of our algorithm. ∎

##  16 Application: Length-Constrained Cutmatches

As it captures low-latency communication subject to bandwidth constraints, the
problem of computing low-congestion $h$-length paths between two set of nodes
$S$ and $T$ occurs often in network optimization.

In this section we give algorithms that find a low-congestion $h$-length
collection of paths between two sets of nodes and certify that there is no
low-congestion way of extending the current collection of paths with a moving
cut. Such a construction is called a length-constrained cutmatch. A recent
work [39] uses the algorithms we give for cutmatches to give the first
efficient constructions of a length-constrained version of expander
decompositions. These constructions were then used to give the first
distributed CONGEST algorithms for many problems including MST,
$(1+\epsilon)$-min-cut and $(1+\epsilon)$-lightest paths that are guaranteed
to run in sub-linear rounds as long as such algorithms exist on the input
network.

We now formalize cutmatches. In what follows, for a vertex subset $W\subseteq
V$ we let $U^{+}(W)=\sum_{v\in W}\sum_{a\in\delta^{+}(v)}U_{a}$ and
$U^{-}(W)=\sum_{v\in W}\sum_{a\in\delta^{-}(v)}U_{a}$. We also let
$\delta^{\pm}(S,T):=\bigcup_{v\in S}\delta^{+}(v)\cup\bigcup_{v\in
T}\delta^{-}(T)$. Note that throughout this section we assume that each
$S$-$T$ path in the support of an $h$-length flow contains exactly one vertex
from $S$ and one vertex from $T$ (this is without loss of generality since any
such flow can be made to satisfy this property without changing its value).

######  Definition 16.1 ($h$-Length Cutmatch).

Given digraph $D=(V,A)$ with capacities $U$ and lengths $\ell$, an $h$-length
$\phi$-sparse cutmatch of congestion $\gamma$ between disjoint node sets
$S,T\subseteq V$ consists of:

  * •

An integral $h$-length $S$-$T$ flow $f$ in $D$ with capacities
$\\{U_{a}\\}_{a\in\delta^{\pm}(S,T)}\cup\\{\gamma\cdot
U_{a}\\}_{a\not\in\delta^{\pm}(S,T)}$ and lengths $\ell$;

  * •

A moving cut $w$ of value $\sum_{a}w_{a}\cdot
U_{a}\leq\phi\left(U^{+}(S)-\text{val}(f)\right)$ such that
$d_{\ell^{\prime}}(S,T)>h$ where

$\displaystyle\ell^{\prime}_{a}:=\begin{cases}h+1&\text{if
$a\in\delta^{\pm}(S,T)$ and $f(a)=U_{a}$}\\\ \ell_{a}+h\cdot
w_{a}&\text{otherwise}\end{cases}$

Our main theorem of this sections shows how to efficiently compute length-
constrained cutmatches.

######  Theorem 16.1.

Suppose we are given a digraph $D=(V,A)$ with capacities $U$ and lengths
$\ell$. There is an algorithm that, given two node sets $S,T\subseteq V$,
$h\geq 1$ and $\phi\leq 1$, outputs an $h$-length $\phi$-sparse cutmatch
$(\hat{f},\hat{w})$ of congestion $\gamma$ between $S$ and $T$, where
$\gamma=\tilde{O}(\frac{1}{\phi})$. This algorithm runs in:

  1. 1.

Deterministic parallel time $\tilde{O}(h^{17})$ with $m$ processors where
$|\text{supp}(\hat{f})|\leq\tilde{O}(h^{10}\cdot|A|)$;

  2. 2.

Randomized CONGEST time $\tilde{O}(h^{17})$ with high probability.

Before moving onto details of the algorithm, we give a high level description
of how we prove the above. Our proof is based on a structural result which may
be interesting in its own right. This structural result shows that one can
always substantially reduce the value of an optimal length-constrained flow
through one of two operations. Specifically, given an optimal flow and
certifying moving cut pair $(f,w)$, either:

  1. 1.

The flow $f$ covers most of the cut mass of $w$ on arcs in
$\delta^{\pm}(S,T)$. Consequently, if we reduce the capacities of arcs in
$\delta^{\pm}(S,T)$ by the amount of flow that $f$ sends over them, then we
substantially reduce the cost of $w$. Since $w$ is a feasible moving cut this,
in turn, multiplicatively reduces the value of the optimal flow by a constant;
or

  2. 2.

One can apply the cut $w$ on arcs not in $\delta^{\pm}(S,T)$ (increasing the
length of $a\not\in\delta^{\pm}(S,T)$ by about $h\cdot w_{a}$) to reduce the
optimal flow by a constant.

This result is formalized by Lemma 16.4 in Section 16.1; there, we show that
this holds even for approximately-optimal length-constrained flow, moving cut
pairs.

Our algorithm for length-constrained cutmatches scales the capacities of all
arcs in $A\setminus\delta^{\pm}(S,T)$ up by about $\frac{1}{\phi}$, computes a
series of flows and moving cuts and then adds to our cutmatch from the
computed flow or the computed moving cut depending on which of the two
operations reduces the optimal value by a constant. This allows us to compute
a cutmatch because: (1) scaling back down these capacities guarantees that the
moving cut we compute is sufficiently cheap; and (2) we only have to do the
above $\tilde{O}(1)$-many times since each time we reduce the optimal value by
a multiplicative constant which, in turn, allows us to argue our low
congestion. We note, however, that the fact that we must scale capacities
prevents us from using our deterministic flow algorithms. Implementing this in
CONGEST requires using a sparse neighborhood cover.

The above strategy is slightly complicated by the fact that we would like our
flows in our cutmatches to be integral but each flow we compute is fractional.
Crucially, however, by the properties of the flows we compute, if we compute
an $O(1)$-approximate flow, then scale up this flow by $\Theta(1)$ the result
becomes integral while increasing congestion by at most an $O(1)$ factor. In
Section 16.2 we show how to eliminate this congestion on arcs in
$\delta^{\pm}(S,T)$ while only reducing the value of our flow by a bounded
amount. We do not need to resolve this extra congestion on arcs not in
$\delta^{\pm}(S,T)$ since our cutmatches may have large congestion on such
arcs. We describe this in more detail in Section 16.2.

###  16.1 Flow Mostly Covers $\delta^{\pm}(S,T)$ or Can Reduce Optimal by
Cutting $A\setminus\delta^{\pm}(S,T)$

In this section we show the main structural result on which our cutmatch
algorithm relies: given a flow, moving cut pair $(f,w)$, either $f$ covers
most of $w$ on arcs in $\delta^{\pm}(S,T)$ or $w$ can be applied to arcs in
$A\setminus\delta^{\pm}(S,T)$ to reduce the optimal flow value by a constant.

The sense of $f$ covering $w$ will makes use of the following notion of
saturated arcs.

######  Definition 16.2 (Saturated Arcs).

Let $(f,w)$ be an $h$-length $S$-$T$ flow, moving cut pair. We say that arc
$a\in A$ is $c$-saturated for $c\in[0,1]$ with respect to $(f,w)$ if

$\displaystyle c\cdot U_{a}\leq f(a).$

The following simple helper lemma shows that any near-optimal length-
constrained flow, moving cut pair must be such that most of $w$’s mass lies on
saturated arcs.

######  Lemma 16.3 ($h$-Length Flows Saturate Moving Cuts).

Let $(f,w)$ be a $(1\pm\varepsilon)$-approximate $h$-length $S$-$T$ flow,
moving cut pair. Fix any $c_{1}\in[0,1]$ and let $c_{2}\in[0,1]$ be

$\displaystyle c_{2}:=\sum_{c_{1}\text{-saturated }a}U_{a}\cdot
w_{a}\bigg{/}\sum_{a}U_{a}\cdot w_{a}.$

Then $c_{2}\geq 1-\frac{\varepsilon}{1-c_{1}}$.

###### Proof.

The proof is by a simple averaging argument. Recall that the fact that $(f,w)$
is $(1\pm\varepsilon)$-approximate means

$\displaystyle\left(1-\varepsilon\right)\cdot\sum_{a}U_{a}\cdot
w_{a}\leq\text{val}(f).$ (9)

Next, applying the feasibility of $w$, $f(a)\leq U_{a}$ for every $a$ and the
definition of $c_{1}$-saturated arcs and $c_{2}$, we have

$\displaystyle\text{val}(f)$ $\displaystyle=\sum_{P}f_{P}$
$\displaystyle\leq\sum_{P}f_{P}\sum_{a\in P}w_{a}$
$\displaystyle=\sum_{a}f(a)\cdot w_{a}$
$\displaystyle=\sum_{c_{1}\text{-saturated }a}f(a)\cdot w_{a}+\sum_{\text{not
}c_{1}\text{-saturated }a}f(a)\cdot w_{a}$
$\displaystyle\leq\sum_{c_{1}\text{-saturated }a}U_{a}\cdot
w_{a}+c_{1}\cdot\sum_{\text{not }c_{1}\text{-saturated }a}U_{a}\cdot w_{a}$
$\displaystyle=(c_{2}+(1-c_{2})\cdot c_{1})\cdot\sum_{a}U_{a}\cdot w_{a}.$

and so $\text{val}(f)<(c_{2}+(1-c_{2})\cdot c_{1})\cdot\sum_{a}U_{a}\cdot
w_{a}$ which when combined with Equation 9 implies $c_{2}+(1-c_{2})\cdot
c_{1}\geq 1-\varepsilon$. ∎

We now show the main structural result of this section.

######  Lemma 16.4.

Let $(f,w)$ be a $(1\pm\varepsilon)$-approximate $h$-length $S$-$T$ flow,
moving cut pair in digraph $D=(V,A)$ with capacities $U$ and lengths $\ell$.
Then either:

  1. 1.

Flow Mostly Covers Cut on $\delta^{\pm}(S,T)$: $\sum_{a\in
A^{\prime}}U_{a}\cdot
w_{a}\geq\left(\frac{1}{2}-3\varepsilon\right)\cdot\sum_{a}U_{a}\cdot w_{a}$
where $A^{\prime}=\\{a\in\delta^{\pm}(S,T):\text{$a$ is
}\frac{1}{2}\text{-saturated by $f$}\\}$;

  2. 2.

Reduce Optimal with Moving Cut on $A\setminus\delta^{\pm}(S,T)$:
$\text{OPT}_{w}\leq\frac{1}{2}\cdot\text{OPT}$ where $\text{OPT}_{w}$ is the
maximum value of an $h$-length $S$-$T$ flow in $D$ with capacities $U$ and
lengths
$\ell^{\prime}:=\\{\ell_{a}\\}_{a\in\delta^{\pm}(S,T)}\cup\\{\ell_{a}+\frac{1}{\varepsilon}\cdot
h\cdot w_{a}\\}_{a\not\in\delta^{\pm}(S,T)}$.

###### Proof.

The proof idea is as follows. We case on whether most of the cut mass of $w$
lies in $\delta^{\pm}(S,T)$ or not. If it does then by Lemma 16.3 arcs in
$\delta^{\pm}(S,T)$ have a lot of flow over them. On the other hand, if most
of the cut mass of $w$ does not lie in $\delta^{\pm}(S,T)$ then increasing
lengths of arcs in $A\setminus\delta^{\pm}(S,T)$ according to $w$ greatly
reduces the maximum $h$-length flow; in particular, any flow which is
$h$-length after these increases must be incident to a lot of mass of $w$ on
arcs in $\delta^{\pm}(S,T)$ but by assumption this mass is bounded and so we
can bound the total size of said flow. More formally, we case on whether or
not $\sum_{a\in\delta^{\pm}(S,T)}U_{a}\cdot
w_{a}\geq\frac{(1-\varepsilon)^{2}}{2}\cdot\sum_{a}U_{a}\cdot w_{a}$.

Suppose that $\sum_{a\in\delta^{\pm}(S,T)}U_{a}\cdot
w_{a}\geq\frac{(1-\varepsilon)^{2}}{2}\cdot\sum_{a}U_{a}\cdot w_{a}$. Letting
$c_{1}:=\frac{1}{2}$ and applying Lemma 16.3 we know that

$\displaystyle\sum_{a\text{ $c_{1}$-saturated}}U_{a}\cdot
w_{a}\geq\left(1-2\varepsilon\right)\cdot\sum_{a}U_{a}\cdot w_{a}.$ (10)

On the other hand applying Equation 10 and our assumption that
$\sum_{a\in\delta^{\pm}(S,T)}U_{a}\cdot
w_{a}\geq\frac{(1-\varepsilon)^{2}}{2}\cdot\sum_{a}U_{a}\cdot w_{a}$, it
follows that

$\displaystyle\sum_{a\in A^{\prime}}U_{a}\cdot
w_{a}\geq\left(\frac{(1-\varepsilon)^{2}}{2}-2\varepsilon\right)\cdot\sum_{a}U_{a}\cdot
w_{a}\geq\left(\frac{1}{2}-3\varepsilon\right)\cdot\sum_{a}U_{a}\cdot w_{a}$

as required.

Next, suppose that $\sum_{a\in\delta^{\pm}(S,T)}U_{a}\cdot
w_{a}<\frac{(1-\varepsilon)^{2}}{2}\cdot\sum_{a}U_{a}\cdot w_{a}$. Let
$f^{\prime}$ be an optimal $h$-length $S$-$T$ flow in $D$ with capacities $U$
and lengths $\ell^{\prime}$. Observe that since $f^{\prime}$ is $h$-length
according to $\ell^{\prime}$ we know that every path $P\in\text{supp}(f)$
satisfies $\sum_{a\in P\cap A\setminus\delta^{\pm}(S,T)}w_{a}\leq\varepsilon$.
On the other hand, since $w$ is a feasible moving cut we know that $\sum_{a\in
P}w_{a}\geq 1$ for any $P\in\text{supp}(f)$. It follows that for each
$P\in\text{supp}(f^{\prime})$ we know that

$\displaystyle\sum_{a\in P\cap\delta^{\pm}(S,T)}w_{a}\geq 1-\varepsilon.$ (11)

Thus, applying Equation 11 and our assumption that
$\sum_{a\in\delta^{\pm}(S,T)}U_{a}\cdot
w_{a}<\frac{(1-\varepsilon)^{2}}{2}\cdot\sum_{a}U_{a}\cdot w_{a}$ we have

$\displaystyle\text{val}(f^{\prime})$
$\displaystyle=\sum_{P\in\text{supp}(f^{\prime})}f_{P}$
$\displaystyle\leq\frac{1}{1-\varepsilon}\sum_{P\in\text{supp}(f^{\prime})}f_{P}\sum_{a\in
P\cap\delta^{\pm}(S,T)}w_{a}$
$\displaystyle=\frac{1}{1-\varepsilon}\cdot\sum_{a\in\delta^{\pm}(S,T)}w_{a}\cdot
f(a)$
$\displaystyle\leq\frac{1}{1-\varepsilon}\cdot\sum_{a\in\delta^{\pm}(S,T)}w_{a}\cdot
U_{a}$ $\displaystyle\leq\frac{1-\varepsilon}{2}\cdot\sum_{a}U_{a}\cdot
w_{a}.$

Lastly, by our assumption that $(f,w)$ is $(1\pm\varepsilon)$-approximate, we
know that $(1-\varepsilon)\cdot\sum_{a}U_{a}\cdot
w_{a}\leq\text{val}(f)\leq\text{OPT}$ meaning $\sum_{a}U_{a}\cdot
w_{a}\leq\frac{1}{1-\varepsilon}\cdot\text{OPT}$ and so

$\displaystyle\text{val}(f^{\prime})\leq\frac{1}{2}\cdot\text{OPT}$

as required. ∎

###  16.2 Decongesting our Flows on Arcs in $\delta^{\pm}(S,T)$

We now introduce a helper procedure which will allow us to turn our computed
fractional flows into integral flows that respect the capacities of arcs in
$\delta^{\pm}(S,T)$ (while maybe violating the capacities of arcs not in
$\delta^{\pm}(S,T)$).

######  Lemma 16.5.

Suppose we are given a digraph $D=(V,A)$ with capacities $U$ and lengths
$\ell$. Fix $\eta>0$, $S,T\subseteq V$ and $h\geq 1$. Let
$f=\eta\cdot\sum_{j}f_{j}$ where each $f_{j}$ is an integral $h$-length
$S$-$T$ flow in $D$ with capacities $U$ and lengths $\ell$. Fix
$A^{\prime}\subseteq\delta^{\pm}(S,T)$ and a moving cut $w$. Then one can
compute an $h$-length $S$-$T$ flow $f^{\prime}$ on $D$ with lengths $\ell$ and
capacities $\\{U_{a}\\}_{a\in\delta^{\pm}(S,T)}\cup\\{\eta\cdot
U_{a}\\}_{a\not\in\delta^{\pm}(S,T)}$ such that $\sum_{a\in
A^{\prime}}f^{\prime}(a)\cdot w_{a}\geq\frac{\eta}{8}\cdot\sum_{a\in
A^{\prime}}f(a)\cdot w_{a}$ in:

  1. 1.

Deterministic parallel time $O(h)$ with $m$ processors;

  2. 2.

Deterministic CONGEST time $O(h)$.

###### Proof.

The basic idea is to scale up the input flow $f$ by $\eta$ and then remove
flow paths that overcapacitate edges in $\delta^{\pm}(S,T)$. In particular, we
first resolve over capacitated arcs in $\delta^{+}(S)$ by greedily choosing
flows that send the most over each edge in $\delta^{+}(S)$ and then do the
same for $\delta^{-}(T)$ but using the remaining flow.

More formally, we begin by describing how to construct $f^{\prime}$. We begin
by dealing with over capacitated arcs in $\delta^{+}(S)$. For arc
$a\in\delta^{+}(S)$ order the $f_{j}$ in descending order according to
$f_{j}(a)$ as $f^{(1)}_{a},f_{a}^{(2)},\ldots$. Let $k_{a}$ be the largest
integer such that $\sum_{i\leq k_{a}}f_{a}^{(i)}(a)\leq U_{a}$ and if
$f_{j}\in\\{f_{a}^{(i)}:i\leq k_{a}\\}$ then say that $a$ prefers flow
$f_{j}$. Lastly, let $f_{j}^{\mid a}$ be $f_{j}$ restricted to paths going
through $a$. That is, the value of $f^{\mid a}_{j}$ on path $P$ is

$\displaystyle\left(f^{\mid
a}_{j}\right)_{P}:=\begin{cases}\left(f_{j}\right)_{P}&\text{if $P\cap
a\neq\emptyset$}\\\ 0&\text{otherwise}\end{cases}$

Then, we resolve congestion on arcs in $\delta^{+}(S)$ by turning each $f_{j}$
into another flow $f_{j}^{\prime}$. Specifically, let $f^{\prime}_{j}$ be
$f_{j}$ restricted only to paths where $f_{j}$ is preferred. That is,
$f_{j}^{\prime}$ is

$\displaystyle f_{j}^{\prime}:=\sum_{a\in\delta^{+}(S):a\text{ prefers
}f_{j}}f^{\mid a}_{j}.$

We now resolve over capacitated edges in $\delta^{-}(T)$ in a symmetric way
but using the $f_{j}^{\prime}$ flows rather than the $f_{j}$ flows and taking
the $w$ values into account. Specifically, fix $a\in\delta^{-}(T)$ and let
$x_{j,a}$ be the amount of flow sent over arc $a$ by $f_{j}$, scaled
appropriately by $w$. That is, we let

$\displaystyle
x_{a,j}:=\sum_{P=(a^{\prime},\ldots,a)}\left(f_{j}\right)_{P}\cdot
w_{a^{\prime}}.$

Then, order the $f_{j}^{\prime}$ in descending order according to $x_{a,j}$ as
$f^{(1)}_{a},f_{a}^{(2)},\ldots$. Let $k_{a}$ be the largest integer such that
$\sum_{i\leq k}f_{a}^{(i)}(a)\leq U_{a}$ and if
$f_{j}^{\prime}\in\\{f_{a}^{(i)}:i\leq k\\}$ then say that $a$ prefers flow
$f_{j}^{\prime}$. Lastly, let $f_{j}^{\mid a}$ be $f_{j}^{\prime}$ restricted
to paths going through $a$. That is, the value of $f^{\mid a}_{j}$ on path $P$
is

$\displaystyle\left(f^{\mid
a}_{j}\right)_{P}:=\begin{cases}\left(f_{j}^{\prime}\right)_{P}&\text{if
$P\cap a\neq\emptyset$}\\\ 0&\text{otherwise}\end{cases}$

Then, we let $f_{S}^{\prime}$ be the flow which is all of our $f_{j}^{\prime}$
flows appropriately restricted and preferred by arcs in $\delta^{-}(T)$

$\displaystyle
f^{\prime}_{S}:=\sum_{a\in\delta^{-}(T)}\sum_{f_{j}^{\prime}:\text{ preferred
by }a}f^{\mid a}_{j}.$

We construct flow $f_{T}^{\prime}$ symmetrically to $f_{S}^{\prime}$
(switching the roles of $S$ and $T$) and let our final flow $f^{\prime}$ be

$\displaystyle
f^{\prime}:=\frac{1}{2}\left(f_{S}^{\prime}+f_{T}^{\prime}\right).$

$f^{\prime}$ is trivially $h$-length (according to $\ell$) and from $S$ to $T$
since $f$ is such a flow. Similarly, $f_{S}^{\prime}$ and $f_{T}^{\prime}$ are
each feasible for capacities
$\\{U_{a}\\}_{a\in\delta^{\pm}(S,T)}\cup\\{\eta\cdot
U_{a}\\}_{a\not\in\delta^{\pm}(S,T)}$: arcs not in $\delta^{\pm}(S,T)$ are not
over capacitated since $\sum_{j}f_{j}$ is feasible for capacities $\eta\cdot
U$ and arcs in $\delta^{\pm}(S,T)$ are not over capacitated by construction of
$f^{\prime}$. It follows that $f^{\prime}$ is also feasible for these
capacities.

We now argue that $\sum_{a\in A^{\prime}}f^{\prime}(a)\cdot
w_{a}\geq\frac{\eta}{8}\cdot\sum_{a\in A^{\prime}}f(a)\cdot w_{a}$. To do so,
observe that it suffices to show that

$\displaystyle\sum_{a\in
A^{\prime}}f_{S}^{\prime}(a)\geq\frac{\eta}{4}\cdot\sum_{a\in
A^{\prime}\cap\delta^{+}(S)}f(a)\cdot w_{a}$ and symmetrically
$\displaystyle\sum_{a\in
A^{\prime}}f_{T}^{\prime}(a)\geq\frac{\eta}{4}\cdot\sum_{a\in
A^{\prime}\cap\delta^{-}(T)}f(a)\cdot w_{a}$

We will argue $\sum_{a\in
A^{\prime}}f_{S}^{\prime}(a)\geq\frac{\eta}{4}\cdot\sum_{a\in
A^{\prime}\cap\delta^{+}(S)}f(a)\cdot w_{a}$ (the other inequality for
$f_{T}^{\prime}$ is symmetric).

Let $\hat{f}:=\sum_{j}f_{j}$ and let
$\hat{f}^{\prime}:=\sum_{j}f_{j}^{\prime}$. We begin by arguing that our
$f_{j}^{\prime}$ retain $\eta/2$ of the mass of $\hat{f}$. Observe that by
definition we have

$\displaystyle\eta\cdot\sum_{a\in A^{\prime}\cap\delta^{+}(S)}\hat{f}(a)\cdot
w_{a}=\sum_{a\in A^{\prime}\cap\delta^{+}(S)}f(a)\cdot w_{a}$

Furthermore, observe by a standard bin-packing-type argument we know that

$\displaystyle\sum_{a\in A^{\prime}\cap\delta^{+}(S)}\hat{f}^{\prime}(a)\cdot
w_{a}\geq\frac{\eta}{2}\sum_{a\in A^{\prime}\cap\delta^{+}(S)}\hat{f}(a)\cdot
w_{a}$

and so it follows that

$\displaystyle\sum_{a\in A^{\prime}\cap\delta^{+}(S)}\hat{f}^{\prime}(a)\cdot
w_{a}\geq\frac{1}{2}\cdot\sum_{a\in A^{\prime}\cap\delta^{+}(S)}f(a)\cdot
w_{a}$ (12)

Likewise, by another standard bin-packing-type argument we know that

$\displaystyle\sum_{a\in
A^{\prime}}f_{S}^{\prime}(a)\geq\frac{\eta}{2}\cdot\sum_{a\in
A^{\prime}\cap\delta^{+}(S)}\hat{f}^{\prime}(a)\cdot w_{a}$

which when combined with Equation 12 shows $\sum_{a\in
A^{\prime}}f_{S}^{\prime}(a)\geq\frac{\eta}{4}\cdot\sum_{a\in
A^{\prime}\cap\delta^{+}(S)}f(a)\cdot w_{a}$ as required.

We now argue the runtime. Observe that each $f_{j}^{\prime}$ can be computed
in a distributed manner by iterating over each $f_{j}$, having each arc
$a\in\delta^{+}(S)$ decide if it prefers this flow and then forwarding the
value of $f^{\mid a}_{j}$ along its flow paths. Since all $f_{j}$ are
$h$-length by assumption this takes at most $h$ rounds of forwarding. This
forwarding takes $O(h)$ rounds of CONGEST or parallel time. Computing
$f_{S}^{\prime}$ and $f_{T}^{\prime}$ from the $f_{j}^{\prime}$ is symmetric.
Lastly, computing $f^{\prime}$ is trivial to do from $f_{S}^{\prime}$ and
$f_{T}^{\prime}$. ∎

###  16.3 Our Length-Constrained Cutmatch Algorithm

We conclude this section by giving our length-constrained cutmatch algorithm
and its guarantees. See 16.1

###### Proof.

We iteratively build up the flow $\hat{f}$ and cut $\hat{w}$ for our cutmatch
as follows. The basic idea is to use 3.1 to compute moving cuts and length-
constrained flows and then to either add to $\hat{w}$ using our moving cut or
to add our flow to $\hat{f}$ depending on which case of Lemma 16.4 we are in.
Getting this to run in CONGEST will require using sparse neighborhood covers
since we cannot efficiently check which of the two cases of Lemma 16.4 we are
in in CONGEST.

More formally, we initialize as follows.

  * •

We fix $\varepsilon=.01$ for the course of our algorithm.

  * •

We initialize $\hat{f}$ to assign $0$ to every path and $\hat{w}$ to assign
$0$ to every arc. We will update these values over the course of our
algorithm.

  * •

We initialize the capacities we work with $U^{\prime}$ to scale all arcs in
$A\setminus\delta^{\pm}(S,T)$ by $\gamma^{\prime}$ for
$\gamma^{\prime}\leq\gamma$ to be described later. That is, initially
$U^{\prime}:=\\{U_{a}\\}_{a\in\delta^{\pm}(S,T)}\cup\\{\gamma^{\prime}\cdot
U_{a}\\}_{a\not\in\delta^{\pm}(S,T)}$. We will update $U^{\prime}$ over the
course of our algorithm.

  * •

Given $\hat{w}$ we will always let
$\ell^{\prime}:=\\{\ell_{a}\\}_{a\in\delta^{\pm}(S,T)}\cup\\{\ell_{a}+h\cdot\hat{w}_{a}\\}_{a\not\in\delta^{\pm}(S,T)}$
be the lengths that we work with. Note that initially $\ell=\ell^{\prime}$.

Next, our algorithm runs in phases each of which consists of iterations. At
the beginning of each phase we compute a moving cut $w$ using 3.1 with the
above value of $\varepsilon$ so that $\eta=\tilde{\Theta}(1)$. In each
iteration of our phase we apply 3.1 to compute an $h$-length flow $f$ using
lengths $\ell^{\prime}$ and capacities $U^{\prime}$ with $\varepsilon$ as
above. We next check if $(f,w)$ is a $(1\pm 2\varepsilon)$-approximate
$h$-length $S$-$T$ flow, moving cut pair in $D$ with capacities $U^{\prime}$
and lengths $\ell^{\prime}$ (note that the $w$ we are using here is the one
from the beginning of the phase, not the one we compute when we also compute
$f$ using 3.1). If it is not then we move onto the next phase. If it is then
by Lemma 16.4 we know one of two things must be true. Specifically, letting
OPT be the maximum value of an $h$-length $S$-$T$ flow in $D$ with capacities
$U^{\prime}$ and lengths $\ell^{\prime}$ at the beginning of our iteration
then we have either:

  1. 1.

Flow Mostly Covers Cut on $\delta^{\pm}(S,T)$: $\sum_{a\in
A^{\prime}}U_{a}^{\prime}\cdot
w_{a}\geq\left(\frac{1}{2}-6\varepsilon\right)\cdot\sum_{a}U_{a}^{\prime}\cdot
w_{a}$ where $A^{\prime}=\\{a\in\delta^{\pm}(S,T):\text{$a$ is
}\frac{1}{2}\text{-saturated by $f$}\\}$; or

  2. 2.

Reduce Optimal with Moving Cut on $A\setminus\delta^{\pm}(S,T)$:
$\text{OPT}_{w}\leq\frac{1}{2}\cdot\text{OPT}$ where $\text{OPT}_{w}$ is the
maximum value of an $h$-length $S$-$T$ flow in $D$ with capacities
$U^{\prime}$ and lengths
$\\{\ell_{a}\\}_{a\in\delta^{\pm}(S,T)}\cup\\{\ell_{a}^{\prime}+\frac{1}{2\varepsilon}\cdot
h\cdot w_{a}\\}_{a\not\in\delta^{\pm}(S,T)}$.

If the former case (1) is true then we add to our flow $\hat{f}$ and in the
latter case (2) we add to $\hat{w}$ using $w$ and move onto the next phase.
More formally, in the former case (1) we apply Lemma 16.5 to $f$ to get
integral flow $f^{\prime}$ using
$A^{\prime}=\\{a\in\delta^{\pm}(S,T):\text{$a$ is }\frac{1}{2}\text{-saturated
by $f$}\\}$ as above. We then update $\hat{f}$ to $\hat{f}+f^{\prime}$.
Likewise, for each arc $a\in\delta^{\pm}(S,T)$ we update $U^{\prime}_{a}$ to
$U^{\prime}_{a}-f^{\prime}(a)$ and delete $a$ if we now have
$U^{\prime}_{a}=0$; for each arc $a\not\in\delta^{\pm}(S,T)$ we let
$U^{\prime}_{a}$ be unchanged (observe that it follows for each arc
$a\not\in\delta^{\pm}(S,T)$ we always have $U_{a}^{\prime}=U_{a}$). In the
former case we stay in this phase. In the latter case (2), we let

$\displaystyle w^{\prime}_{a}=\begin{cases}\frac{1}{2\varepsilon}\cdot
w_{a}&\text{if $a\not\in\delta^{\pm}(S,T)$}\\\ 0&\text{otherwise}\end{cases}$

and then update $\hat{w}$ to be $\hat{w}+w^{\prime}$. In the latter case we
then move onto the next phase. We repeat this until the optimal $h$-length
$S$-$T$ flow has value $0$.

We now analyze this process. First, we claim that the number of iterations in
each phase is at most $\tilde{O}(1)$. To do so, it suffices to show that in
(1) we reduce the cost of $w$ by a multiplicative $1-1/\tilde{O}(1)$; this is
because the cost of $w$ is polynomially-bounded and so this can happen at most
$\tilde{O}(1)$-many times. Towards this, fix an iteration and let $U^{\prime}$
and $U^{\prime\prime}$ be our working capacities before and after updating for
(1) in this iteration. We claim that $w$ has its cost reduced by a
multiplicative $\left(1-1/\tilde{O}(1)\right)$, namely

$\displaystyle\sum_{a}U_{a}^{\prime\prime}\cdot
w_{a}\leq\left(1-1/\tilde{O}(1)\right)\cdot\sum_{a}U_{a}^{\prime}\cdot w_{a}.$
(13)

To see why this holds, observe that combining the guarantees of Lemma 16.5 and
the fact that $\eta=\tilde{\Theta}(1)$ by 3.1 we know that

$\displaystyle\sum_{a\in A^{\prime}}f(a)\cdot
w_{a}\leq\tilde{O}(1)\cdot\sum_{a\in A^{\prime}}f^{\prime}(a)\cdot w_{a}.$

But by definition of $A^{\prime}$ and the fact that we are in (1) for every
$a$ we know that

$\displaystyle\left(\frac{1}{2}-6\varepsilon\right)\cdot\sum_{a}U_{a}^{\prime}\cdot
w_{a}\leq\sum_{a\in A^{\prime}}U_{a}^{\prime}\cdot w_{a}\leq 2\sum_{a\in
A^{\prime}}f(a)\cdot w_{a}.$

Combining these inequalities and our choice of $\varepsilon$, we get that

$\displaystyle\frac{1}{\tilde{O}(1)}\cdot\sum_{a}U_{a}^{\prime}\cdot
w_{a}\leq\sum_{a\in A^{\prime}}f^{\prime}(a)\cdot w_{a}.$

Thus we get,

$\displaystyle\sum_{a}U_{a}^{\prime\prime}\cdot w_{a}$
$\displaystyle=\sum_{a}\left(U_{a}^{\prime}-f^{\prime}(a)\right)\cdot w_{a}$
$\displaystyle\leq\sum_{a\not\in A^{\prime}}U_{a}^{\prime}\cdot
w_{a}+\sum_{a\in A^{\prime}}\left(U_{a}^{\prime}-f^{\prime}(a)\right)\cdot
w_{a}$ $\displaystyle=\sum_{a}U^{\prime}_{a}\cdot w_{a}-\sum_{a\in
A^{\prime}}f^{\prime}(a)\cdot w_{a}$
$\displaystyle\leq\left(1-1/\tilde{O}(1)\right)\cdot\sum_{a}U^{\prime}_{a}\cdot
w_{a}$

as desired.

We now claim that the number of phases is at most $\tilde{O}(1)$.
Specifically, recall that a phase ends when either $(f,w)$ is not a $(1\pm
2\varepsilon)$-approximate $h$-length $S$-$T$ flow, moving cut pair or we are
in (2). We claim that in either case we multiplicatively reduce the value of
the optimal $h$-length $S$-$T$ flow by at least a fixed constant strictly
larger than $0$.

  1. 1.

Suppose $(f,w)$ is not a $(1\pm 2\varepsilon)$-approximate $h$-length $S$-$T$
flow. Let $U^{\prime}$ and $\ell^{\prime}$ be the capacities and lengths when
$w$ is computed and let $U^{\prime\prime}$ be the capacities according to
which $f$ is computed. Let $\text{OPT}_{0}$ be the the value of the optimal
$h$-length $S$-$T$ flow when $w$ is computed and let $\text{OPT}_{0}^{\prime}$
be the optimal such length-constrained flow when $f$ is computed. Since $f$ is
part of a $(1\pm\varepsilon)$-approximate pair we know that

$\displaystyle(1-\varepsilon)\cdot\text{OPT}_{0}^{\prime}\leq\text{val}(f)$

On the other hand, since $(f,w)$ is not a $(1\pm 2\varepsilon)$-approximate
pair we know that

$\displaystyle\text{val}(f)<(1-2\varepsilon)\cdot\sum_{a}U^{\prime\prime}_{a}\cdot
w_{a}$

and so combining these inequalities we get

$\displaystyle\text{OPT}_{0}^{\prime}\leq\frac{1-2\varepsilon}{1-\varepsilon}\cdot\sum_{a}U_{a}^{\prime\prime}\cdot
w_{a}.$ (14)

Furthermore, recall that when $w$ was computed it was part of a
$(1\pm\varepsilon)$-approximate pair with capacities $U^{\prime}$ and
$\ell^{\prime}$, meaning that

$\displaystyle\sum_{a}U^{\prime}_{a}\cdot
w_{a}\leq\frac{1}{1-\varepsilon}\cdot\text{OPT}_{0}$ (15)

Combining Equations 14 and 15 along with the fact that
$U^{\prime\prime}_{a}\leq U^{\prime}_{a}$ for every $a$ since we only decrease
capacities over the course of a phase, we get

$\displaystyle\text{OPT}_{0}^{\prime}\leq\frac{1-2\varepsilon}{(1-\varepsilon)^{2}}\cdot\text{OPT}_{0}.$

By our choice of $\varepsilon$ we have
$\frac{1-2\varepsilon}{(1-\varepsilon)^{2}}\in(0,1)$ as required.

  2. 2.

Suppose that a phase ends because we are in (2). Recall that, as described
above, in (2) we know that we reduce the optimal flow by a multiplicative
$\frac{1}{2}$; that is, as described above,
$\text{OPT}_{w}\leq\frac{1}{2}\cdot\text{OPT}_{0}$.

Since the number of phases is at most $\tilde{O}(1)$ and the number of
iterations in each phase is at most $\tilde{O}(1)$, we have that the maximum
number of iterations across all phases is at most $\tilde{O}(1)$. Letting $x$
be this upper bound on the number of possible iteration, we now set
$\gamma^{\prime}$ be $\Theta\left(x\cdot\frac{1}{\phi}\right)$ for a
sufficiently large hidden constant.

The fact that $\hat{f}$ is feasible for capacities
$\\{U_{a}\\}_{a\in\delta^{\pm}(S,T)}\cup\\{\gamma\cdot
U_{a}\\}_{a\not\in\delta^{\pm}(S,T)}$ where
$\gamma=\tilde{O}(\gamma^{\prime})=\tilde{O}(\frac{1}{\phi})$ is then
immediate: arcs in $\delta^{\pm}(S,T)$ are not over capacitated by
construction of $\hat{f}$ and arcs not in $\delta^{\pm}(S,T)$ are not over
capacitated since each $f^{\prime}$ is feasible for capacities
$\\{U_{a}\\}_{a\in\delta^{\pm}(S,T)}\cup\\{\gamma^{\prime}\cdot
U_{a}\\}_{a\not\in\delta^{\pm}(S,T)}$ and we add such a flow to $\hat{f}$ at
most the total-number-of-iterations-times, which, as argued above, is
$\tilde{O}(1)$. Likewise, $\hat{f}$ is trivially $h$-length according to
$\ell$ since we only increase the lengths of arcs. Next, observe that our
bound on the support size of $\hat{f}$ of
$|\text{supp}(\hat{f})|\leq\tilde{O}(h^{10}\cdot|A|)$ for our parallel
algorithm is immediate from the support size bound of 3.1 and the fact that we
have $\tilde{O}(1)$-many iterations.

We now argue that $\hat{w}$ satisfies the required properties. Specifically,
we argue that $\hat{w}$ is indeed a moving cut of value
$\sum_{a}\hat{w}_{a}\cdot
U_{a}\leq\phi\left(U^{+}(S)-\text{val}(\hat{f})\right)$ such that
$d_{\ell^{\prime}}(S,T)>h$ where

$\displaystyle\ell^{\prime}_{a}:=\begin{cases}\ell_{a}+h\cdot\hat{w}_{a}&\text{if
$f(a)<U_{a}$}\\\ 0&\text{otherwise}.\end{cases}$

Observe that since our algorithm runs until the optimal $h$-length $S$-$T$
flow has value $0$, we know that when our algorithm completes we indeed have
$d_{\ell^{\prime}}(S,T)>h$. It remains to argue that

$\displaystyle\sum_{a}\hat{w}_{a}\cdot
U_{a}\leq\phi\left(U^{+}(S)-\text{val}(\hat{f})\right).$ (16)

Towards showing Equation 16, we define the following quantities for the $i$th
iteration. Let $\hat{f}_{i}$ be $\hat{f}$ in the $i$th iteration and let
$w^{(i)}$ be $w^{\prime}$ in the $i$th iteration (recall $w^{\prime}$ is equal
to $\frac{1}{2\varepsilon}\cdot w$ on arcs not in $\delta^{\pm}(S,T)$ and $0$
otherwise). Let $\text{OPT}_{i}$ be the maximum $h$-length $S$-$T$ in the
$i$th iteration and let $U^{(i)}$ be our capacities in this iteration.

Observe that we trivially have

$\displaystyle\text{OPT}_{i}\leq\sum_{a\in\delta^{+}(S)}U_{a}^{(i)}=\sum_{a\in\delta^{+}(S)}U_{a}-\hat{f}_{i}(a)$
(17)

since the maximum value of a flow is at most the total capacity of arcs
leaving $S$. We also trivially have $\hat{f}(a)\leq\sum_{i}\hat{f}_{i}(a)$ for
any arc $a$ and, in particular, it follows that

$\displaystyle\frac{1-2\varepsilon}{2\varepsilon\cdot\gamma^{\prime}}\cdot\sum_{i}\sum_{a\in\delta^{+}(S)}\hat{f}_{i}(a)\geq\phi\cdot\sum_{a\in\delta^{+}(S)}\hat{f}(a)$
(18)

Similarly, since in each iteration we reduce the optimal value by a constant
and since we do not scale arcs in $\delta^{\pm}(S,T)$ we have

$\displaystyle\frac{1-2\varepsilon}{2\varepsilon\cdot\gamma^{\prime}}\cdot\sum_{i}\sum_{a\in\delta^{+}(S)}U_{a}^{(i)}=\frac{1-2\varepsilon}{\gamma^{\prime}}\cdot\sum_{i}\sum_{a\in\delta^{+}(S)}U_{a}\leq\phi\cdot\sum_{a\in\delta^{+}(S)}U_{a}.$
(19)

Applying Equations 17, 18 and 19, the fact that the support of $\hat{w}$ is
contained in $A\setminus\delta^{\pm}(S,T)$, $w$ is part of a $(1\pm
2\varepsilon)$-approximate pair when we apply it and how we initially scaled
the capacity of arcs in $A\setminus\delta^{\pm}(S,T)$ by $\gamma^{\prime}$ we
get that

$\displaystyle\sum_{a}\hat{w}_{a}\cdot U_{a}$
$\displaystyle=\frac{1}{\gamma^{\prime}}\cdot\sum_{i}\sum_{a\not\in\delta^{\pm}(S,T)}w_{a}^{(i)}\cdot
U_{a}^{(i)}$
$\displaystyle\leq\frac{1-2\varepsilon}{2\varepsilon\cdot\gamma^{\prime}}\cdot\sum_{i}\text{OPT}_{i}$
$\displaystyle\leq\frac{1-2\varepsilon}{2\varepsilon\cdot\gamma^{\prime}}\cdot\sum_{i}\sum_{a\in\delta^{+}(S)}U_{a}^{(i)}-\hat{f}_{i}(a)$
$\displaystyle\leq\phi\cdot\sum_{a\in\delta^{+}(S)}U_{a}-\hat{f}(a),$

showing Equation 16 as required.

It remains to discuss how to implement our algorithm in the stated times.
Implementing the above algorithm in parallel in the stated running time is
trivial by Lemma 16.5 and 3.1 and the fact that we have $\tilde{O}(1)$ total
iterations.

Our CONGEST algorithm requires more work and, in particular, the use of sparse
neighborhood covers. Specifically, we first apply Lemma 5.5 to compute a
sparse $h$-neighborhood cover
$\mathcal{V}_{1},\mathcal{V}_{2},\ldots,\mathcal{V}_{s}$. For $j\in[s]$, we
let $S_{j}$ be a set of nodes whose $h$-neighborhood is contained in a single
part of $\mathcal{V}_{j}$ (where we put each $v\in S$ in exactly one $S_{j}$).
Then, we run the above algorithm to compute an $h$-length $S_{j}$-$T$ cutmatch
$(\hat{f}_{j},\hat{w}_{j})$ in $D$ with $S\setminus S_{j}$ deleted for
$j=1,\ldots,s$ where for each cutmatch we keep the length increases of the
previous cutmatch. That is, we compute $(\hat{f}_{j},\hat{w}_{j})$ with
initial capacities $U^{(j)}$ and lengths $\ell^{(j)}$ where $U^{(1)}=U$ and
$\ell^{(1)}=\ell$ and for $j>1$ and each $a$ we have

$\displaystyle U^{(j)}_{a}=\begin{cases}U_{a}&\text{if
$a\not\in\delta^{\pm}(S,T)$}\\\
U^{(j-1)}_{a}-\hat{f}_{j}(a)&\text{otherwise}\end{cases}$

and

$\displaystyle\ell_{a}^{(j)}=\ell_{a}+h\cdot\sum_{j^{\prime}<j}(\hat{w}_{j^{\prime}})_{a}.$

$(\hat{f},\hat{w})$ is an $h$-length $S$-$T$ cutmatch by construction.
Furthermore, it is easy to verify that the above process increases the
congestion of this cutmatch and the support size of $\hat{f}$ by at most
$s=\tilde{O}(1)$. To bound the cost of $\hat{w}$ observe that applying our
guarantees on each $\hat{w}_{j}$ from above and the fact that the $S_{j}$
partition $S$ we get that the cost of $\hat{w}$ is

$\displaystyle\sum_{j}\sum_{a}(\hat{w}_{j})_{a}\cdot U_{a}$
$\displaystyle\leq\sum_{j}\phi\left(\left(U^{(j)}\right)^{+}(S_{j})-\text{val}(\hat{f}_{j})\right)$
$\displaystyle=\sum_{j}\phi\left(U^{+}(S_{j})-\text{val}(\hat{f}_{j})\right)$
$\displaystyle=\phi\cdot\left(U^{+}(S)-\text{val}(\hat{f})\right)$

as required.

We now discuss how to compute one of the cutmatches in the above process.
Updating $\hat{w}_{j}$ and $\hat{f}_{j}$ in each iteration is trivial. The
non-trivial steps to implement our algorithm are:

  * •

Computing moving cut $w$ at the beginning of the phase;

  * •

Computing flow $f$ in each iteration of the phase and decongested flow
$f^{\prime}$ from $f$;

  * •

Checking if $(f,w)$ is a $(1\pm 2\varepsilon)$-approximate pair; and

  * •

Checking which of (1) and (2) holds.

Computing each moving cut $w$ and each length-constrained flow $f$ can be done
by 3.1 in $\tilde{O}(h^{17})$ randomized CONGEST time. Computing $f^{\prime}$
from $f$ can be done in deterministic $O(h)$ CONGEST time by Lemma 16.5.
Checking if $(f,w)$ is a $(1\pm 2\varepsilon)$-approximate pair and checking
which of which of (1) and (2) we are in can be done in time $\tilde{O}(h)$ by
Lemma 5.5. Thus, each of our $\tilde{O}(1)$ iterations has its running time
dominated by our call to 3.1, giving the stated running times. ∎

##  17 Conclusion and Future Work

In this work we gave the first efficient randomized and deterministic
algorithms for computing $(1-\epsilon)$-approximate length-constrained flows
both in parallel and in the CONGEST model of distributed computation. We used
these algorithms to give new results in maximal and maximum disjoint path
problems, expander decompositions, bipartite $b$-matching and length-
constrained cutmatches. We conclude with several open questions and directions
for future work.

  1. 1.

Our length-constrained flow algorithms have a dependence of $\text{poly}(h)$
which when plugged into the techniques of Haeupler et al. [39] give CONGEST
algorithms for many distributed problems, e.g. MST, whose running time is
$\text{poly}(\text{OPT})$ (up to sub-linear factors) where OPT is the optimal
CONGEST running time for the input problem. It would be exciting to improve
the dependence on $h$ of our algorithms to, say, $O(h)$ as this result when
combined with those of Haeupler et al. [39] would give CONGEST algorithms
running in time $O(\text{OPT})$ (up to sub-linear factors).

  2. 2.

The running time of many of our algorithms depends on $\rho_{CC}$, the best
quality of a CONGEST algorithm for cycle cover (as defined in Definition 5.7).
It is known that $\rho_{CC}\leq 2^{O(\sqrt{\log n})}$ but it would be
extremely interesting to show that $\rho_{CC}\leq\tilde{O}(1)$. Such an
improvement would immediately improve the dependency on $n$ from $n^{o(1)}$ to
$\tilde{O}(1)$ for our CONGEST algorithms for deterministic length-constrained
flows, deterministic maximal and maximum disjoint paths,
$(1-\epsilon)$-approximate $b$-matching and length-constrained cutmatches.
Such a result does not seem to be known even for the randomized case.

  3. 3.

Lastly, many classic problems can be efficiently solved by reducing to flows
but, in particular, by reducing to length-constrained flows with a length-
constraint $h=O(1)$. Indeed this is how we were able to give new algorithms
for $b$-matching in this work. It would be interesting to understand which
additional classic problems our length-constrained flow algorithms give new
algorithms for in CONGEST.

##  Appendix A Generalizing Our Results to Multi-Commodity

In this section we generalize our main result for computing length-constrained
flows and moving cuts to the setting where have many source sink pairs and we
are trying to maximize the total flow between corresponding pairs subject to
congestion constraints. We also generalize our cutmatch algorithms to the
multi-commodity setting.

###  A.1 Multi-Commodity Flows, Cutmatches and Results

We now more formally define a multi-commodity length-constrained flow and
moving cut. Suppose we are given a digraph $D=(V,A)$ with arc capacities $U$,
lengths $\ell$ and $\kappa$ source set, sink set pairs
$\\{(S_{i},T_{i})\\}_{i}$. Then, we have the following LP with a variable
$f_{P}^{\\{i\\}}$ for each $i$ and path $P\in\mathcal{P}_{h}(S_{i},T_{i})$. We
let $f^{\\{i\\}}$ gives the entire flow for commodity $i$.

$\displaystyle\max\sum_{i}\sum_{P\in\mathcal{P}_{h}(S_{i},T_{i})}f_{P}^{\\{i\\}}\text{
s.t.}$ (Multi Length-Constrained Flow LP) $\displaystyle\sum_{i}\sum_{P\ni
a}f_{P}^{\\{i\\}}\leq U_{a}$ $\displaystyle\qquad\forall a\in A$
$\displaystyle 0\leq f_{P}^{\\{i\\}}$ $\displaystyle\qquad\forall
i\in[\kappa],P\in\mathcal{P}_{h}(S_{i},T_{i})$

For a multi-commodity length-constrained flow $f$, we will use the shorthand
$f(a)=\sum_{i}\sum_{P\ni a}f_{P}^{\\{i\\}}$. Likewise we let
$\text{val}(f)=\sum_{i}\text{val}(f^{\\{i\\}})$ be the total flow we send. An
$h$-length multi-commodity flow, then, is simply a feasible solution to this
LP.

######  Definition A.1 (Multi-Commodity $h$-Length Flow).

Given digraph $D=(V,A)$ with lengths $\ell$, capacities $U$ and source, sink
pairs $\\{(S_{i},T_{i})\\}_{i}$, an $h$-length $\\{(S_{i},T_{i})\\}_{i}$ flow
is any feasible solution to Multi Length-Constrained Flow LP.

With the above definition of multi-commodity length-constrained flows we can
now define moving cuts as the dual of length-constrained flows. In particular,
taking the dual of the above LP we get the multi-commodity moving cut LP with
a variable $w_{a}$ for each $a\in A$ and a variable $y_{i}$ for every
$i\in[\kappa]$.

$\displaystyle\min\sum_{a\in A}U_{a}\cdot w_{a}\quad\text{s.t.}$ (Multi Moving
Cut LP) $\displaystyle\sum_{a\in P}w_{a}\geq 1$ $\displaystyle\qquad\forall
i\in[\kappa],P\in\mathcal{P}_{h}(S_{i},T_{i})$ $\displaystyle 0\leq w_{a}$
$\displaystyle\qquad\forall a\in A,i\in[\kappa]$

A multi-commodity $h$-length moving cut is simply a feasible solution to this
LP.

######  Definition A.2 (Multi-Commodity $h$-Length Moving Cut).

Given digraph $D=(V,A)$ with lengths $\ell$, capacities $U$ and source, sink
pairs $\\{(S_{i},T_{i})\\}_{i}$, a multi-commodity $h$-length moving cut is
any feasible solution to Multi Moving Cut LP.

We will use $f$ and $w$ to stand for solutions to Multi Length-Constrained
Flow LP and Multi Moving Cut LP respectively. We say that $(f,w)$ is a
feasible pair if both $f$ and $w$ are feasible for their respective LPs and
that $(f,w)$ is $(1\pm\epsilon)$-approximate for $\epsilon>0$ if the moving
cut certifies the value of the length-constrained flow up to a $(1-\epsilon)$;
i.e. if $(1-\epsilon)\sum_{a}U_{a}\cdot
w_{a}\leq\min_{i}\text{val}(f^{\\{i\\}})$.

When we are working in CONGEST we will say that $f$ is computed if each vertex
$v$ stores the value
$f_{a}^{(h^{\prime},i)}:=\sum_{P\in\mathcal{P}_{h,h^{\prime}}(s,a,t)}f_{P}^{\\{i\\}}$.
Here, we let $\mathcal{P}_{h,h^{\prime}}(s,a,t)$ be all paths in
$\mathcal{P}_{h}(S,T)$ of the form $P^{\prime}=(a_{1},a_{2},\ldots
a,b_{1},b_{2},\ldots)$ where the path $(a,b_{1},b_{2},\ldots)$ has length
exactly $h^{\prime}$ according to $l$. We say multi-commodity moving cut $w$
is computed in CONGEST if each vertex $v$ knows the value of $w_{a}$ for every
arc incident to $v$. Likewise, we imagine that each node in the first round
knows the capacities and lengths of its incident edges.

With the above notions, we can now state our main result for multi-commodity
length-constrained flows and moving cuts which say that one can compute a
feasible pair $(f,w)$ in parallel and distributedly. In the following we say
that length-constrained flow $f$ is integral if $f_{P}^{\\{i\\}}$ is an
integer for every path in $\mathcal{P}_{h}(S_{i},T_{i})$ for every $i$.

More generally than $\kappa$ commodities, we solve the problem provided our
commodoties can be grouped into $\kappa$ batches that are far apart.

######  Definition A.3 ($\kappa$-Batchable).

Given digraph $D$ with lengths $\ell$ and source, sink set pairs
$\\{S_{i},T_{i}\\}_{i}$ we say that a $\\{S_{i},T_{i}\\}_{i}$ is
$\kappa$-batchable if the pairs of $\\{S_{i},T_{i}\\}_{i}$ can be partitioned
into batches $\\{\mathcal{S}_{j},\mathcal{T}_{j}\\}_{j}$ if

  1. 1.

Covering: For each $i$ there some $j$ such that $S_{i}\in\mathcal{S}_{j}$ and
$T_{i}\in\mathcal{T}_{j}$;

  2. 2.

Well-Separated: For each $i$ and $i^{\prime}$, if $v\in S_{i}\cup T_{i}$ and
$v^{\prime}\in S_{i^{\prime}}\cup T_{i^{\prime}}$ and
$S_{i},S_{i^{\prime}}\in\mathcal{S}_{j}$ for some $j$ then
$d_{\ell}(v,v^{\prime})>2h$.

Observe that if the number of commodities is $\kappa$ then the set of source,
sink pairs is trivially $\kappa$-batchable.

The following summarizes our main result for computing multi-commodity length-
constrained flows and moving cuts.

######  Theorem A.1.

Given a digraph $D=(V,A)$ with capacities $U$, lengths $\ell$, length
constraint $h\geq 1$, $0<\varepsilon<1$ and source and sink vertices
$S,T\subseteq V$, and $\kappa$-batchable source, sink pairs
$\\{S_{i},T_{i}\\}_{i}$, one can compute a feasible multi-commodity $h$-length
flow, moving cut pair $(f,w)$ that is $(1\pm\epsilon)$-approximate in:

  1. 1.

Deterministic parallel time
$\tilde{O}(\kappa\cdot\frac{1}{\varepsilon^{9}}\cdot h^{17})$ with $m$
processors where
$|\text{supp}(f)|\leq\tilde{O}(\kappa\cdot\frac{h^{9}}{\varepsilon^{3}}\cdot|A|)$;

  2. 2.

Randomized CONGEST time $\tilde{O}(\kappa\cdot\frac{1}{\varepsilon^{9}}\cdot
h^{17})$ with high probability;

  3. 3.

Deterministic CONGEST time
$\tilde{O}\left(\kappa\cdot\frac{1}{\varepsilon^{9}}\cdot
h^{17}+\kappa\cdot\frac{1}{\varepsilon^{7}}\cdot
h^{16}\cdot(\rho_{CC})^{10}\right)$.

Furthermore, $f=\eta\cdot\sum_{j=1}^{k}f_{j}$ where
$\eta=\tilde{\Theta}(\epsilon^{2})$,
$k=\tilde{O}\left(\kappa\cdot\frac{h}{\epsilon^{4}}\right)$ and $f_{j}$ is an
integral $h$-length $S_{i}$-$T_{i}$ flow for some $i$.

Using the above algorithm, we can compute a multi-commodity version of
cutmatches. As before, for a vertex subset $W\subseteq V$ we let
$U^{+}(W)=\sum_{v\in W}\sum_{a\in\delta^{+}(v)}U_{a}$ and $U^{-}(W)=\sum_{v\in
W}\sum_{a\in\delta^{-}(v)}U_{a}$. We also let
$\delta^{\pm}(S,T):=\bigcup_{v\in S}\delta^{+}(v)\cup\bigcup_{v\in
T}\delta^{-}(T)$. The following formalizes the object we compute.
Symmetrically to the single-commodity setting, below we assume that each path
in the support of each $f_{i}$ contains exactly one vertex of $S_{i}$ and one
vertex of $T_{i}$.

######  Definition A.4 (Multi-Commodity $h$-Length Cutmatch).

Given digraph $D=(V,A)$ with capacities $U$ and lengths $\ell$, an $h$-length
$\phi$-sparse cutmatch of congestion $\gamma$ between disjoint source, sink
node set pairs $\\{(S_{i},T_{i})\\}_{i}$ where $S_{i},T_{i}\subseteq V$ for
each $i$ consists of:

  * •

An integral $h$-length flow $f=\sum_{i}f_{i}$ in $D$ with capacities
$\gamma\cdot U$ and lengths $\ell$ where each $f_{i}$ is an $S_{i}$-$T_{i}$
flow satisfying $f_{i}(a)\leq U_{a}$ for each $a\in\delta^{\pm}(S_{i},T_{i})$;

  * •

A moving cut $w$ in $D$ of value $\sum_{a}w_{a}\cdot
U_{a}\leq\phi\cdot\left(\sum_{i}U^{+}(S_{i})-\text{val}(f_{i})\right)$ such
that for every $i$ we have $d_{\ell_{i}}(S_{i},T_{i})>h$ where

$\displaystyle(\ell_{i})_{a}:=\begin{cases}h+1&\text{if
$a\in\delta^{\pm}(S_{i},T_{i})$ and $f_{i}(a)=U_{a}$}\\\ \ell_{a}+h\cdot
w_{a}&\text{otherwise}\end{cases}$

Using the above algorithm for multi-commodity $h$-length flows, we can
efficiently compute multi-commodity $h$-length cutmatches.

######  Theorem A.2.

Suppose we are given a digraph $D=(V,A)$ with capacities $U$ and lengths
$\ell$. There is an algorithm that, given $\kappa$-batchable source sink pairs
$\\{(S_{i},T_{i})\\}_{i}$ where $S_{i},T_{i}\subseteq V$ for every $i$ and two
integer parameters $h\geq 1$ and $\phi\leq 1$, outputs a multi-commodity
$h$-length $\phi$-sparse cutmatch $(\hat{f},\hat{w})$ of congestion $\gamma$
between $S$ and $T$, where $\gamma=\tilde{O}(\frac{1}{\phi})$. This algorithm
runs in:

  1. 1.

Deterministic parallel time $\tilde{O}(\kappa\cdot h^{17})$ with $m$
processors with $|\text{supp}(\hat{f})|\leq\tilde{O}(\kappa\cdot
h^{10}\cdot|A|)$;

  2. 2.

Randomized CONGEST time $\tilde{O}(\kappa\cdot h^{17})$ with high probability;

###  A.2 Computing Multi-Commodity Length-Constrained Flows and Moving Cuts

We proceed to use our $(1+\epsilon)$-lightest path blockers and multiplicative
weights to compute multi-commodity length-constrained flows and moving cuts.
Our strategy is more or less that of Section 12 but now we iterate through our
batches of commodities; our analysis is mostly unchanged but we include it
here for completeness.

Formally, our algorithm is given in Algorithm 5. Throughout our analysis we
will refer to the innermost loop of Algorithm 5 as one “iteration.”

Algorithm 5 Multi-Commodity Length-Constrained Flows and Moving Cuts

Input: digraph $D=(V,A)$ with lengths $\ell$, capacities $U$, length
constraint $h$ and $\kappa$-batchable source, sink pairs
$\\{S_{i},T_{i}\\}_{i}$ where $S_{i},T_{i}\subseteq V$ for every $i$ and an
$\varepsilon\in(0,1)$.

Output: $(1\pm\epsilon)$-approximate $h$-length multi-commodity flow $f$ and
moving cut $w$.

Let $\epsilon_{0}=\frac{\epsilon}{6}$, let
$\zeta=\frac{1+2\varepsilon_{0}}{\varepsilon_{0}}+1$ and let
$\eta=\frac{\varepsilon_{0}}{(1+\varepsilon_{0})\cdot\zeta}\cdot\frac{1}{\log
m}$.

Initialize $w_{a}\leftarrow\left(\frac{1}{m}\right)^{\zeta}$ for all $a\in A$.

Initialize $\lambda\leftarrow\left(\frac{1}{m}\right)^{\zeta}$.

Initialize $f_{P}^{\\{i\\}}\leftarrow 0$ for all $i$ and
$P\in\mathcal{P}_{h}(S_{i},T_{i})$.

while $\lambda<1$ do:

for $j\in[\kappa]$ and each batch $(\mathcal{S}_{j},\mathcal{S}_{j})$ do

for each $(S_{i},T_{i})$ with $S_{i}\in\mathcal{S}_{j}$ and
$T_{i}\in\mathcal{T}_{j}$ in parallel do

for $\Theta\left(\frac{h\log_{1+\epsilon_{0}}n}{\epsilon_{0}}\right)$
repetitions do

Compute an $h$-length $(1+\epsilon_{0})$-lightest path blocker $\hat{f}$
(using 11.1 with $\lambda$).

Length-Constrained Flow (Primal) Update: $f^{\\{i\\}}\leftarrow
f^{\\{i\\}}+\eta\cdot\hat{f}$.

Moving Cut (Dual) Update:
$w_{a}\leftarrow(1+\epsilon_{0})^{\hat{f}(a)/U_{a}}\cdot w_{a}$ for every
$a\in A$.

$\lambda\leftarrow(1+\epsilon_{0})\cdot\lambda$

return $(f,w)$.

We begin by observing that $\lambda$ always lower bounds
$d^{(h)}_{w}(S_{i},T_{i})$ for every $i$.

######  Lemma A.5.

It always holds that $\lambda\leq d^{(h)}_{w}(S_{x},T_{x})$ for every $x$ in
Algorithm 5.

###### Proof.

Fix an $x$ and a value of $\lambda$ and let $S=S_{x}$ and $T=T_{x}$. Our proof
is by induction. The statement trivially holds at the beginning of our
algorithm.

Let $\lambda_{i}$ be the value of $\lambda$ at the beginning of the $i$th
iteration. We argue that if $d^{(h)}_{w}(S,T)=\lambda_{i}$ then after
$\Theta\left(\frac{h\log_{1+\epsilon_{0}}n}{\epsilon_{0}}\right)$ additional
iterations we must have
$d^{(h)}_{w}(S,T)\geq(1+\varepsilon_{0})\cdot\lambda_{i}$. Let
$\lambda_{i}^{\prime}=(1+\epsilon_{0})\cdot\lambda$ be $\lambda$ after these
iterations. Let $\hat{f}_{j}$ be our lightest path blocker in the $j$th
iteration for $(S_{x},T_{x})$.

Assume for the sake of contradiction that
$d_{w}^{(h)}(S,T)<\lambda_{i}^{\prime}$ after
$i+\Theta\left(\frac{h\log_{1+\epsilon_{0}}n}{\epsilon_{0}}\right)$
iterations. It follows that there is some path $P\in\mathcal{P}_{h}(S,T)$ with
weight at most $\lambda_{i}^{\prime}$ after
$i+\Theta\left(\frac{h\log_{1+\epsilon_{0}}n}{\epsilon_{0}}\right)$ many
iterations. However, notice that by definition of an $h$-length
$(1+\epsilon_{0})$-lightest path blocker $\hat{f}_{j}$ (Definition 11.1), we
know that for every
$j\in\left[i,i+\Theta\left(\frac{h\log_{1+\epsilon_{0}}n}{\epsilon_{0}}\right)\right]$
there is some $a\in P$ for which $\hat{f}_{j}(a)=U_{a}$. By averaging, it
follows that there is some single arc $a\in P$ for which
$\hat{f}_{j}(a)=U_{a}$ for at least
$\Theta\left(\frac{\log_{1+\epsilon_{0}}n}{\epsilon_{0}}\right)$ of these
$j\in[i,i+\Theta\left(\frac{h\log_{1+\epsilon_{0}}n}{\epsilon_{0}}\right)]$.
Since every such arc starts with dual value $(\frac{1}{m})^{\zeta}$ and
multiplicatively increases by a $(1+\epsilon_{0})$ factor in each of these
updates, such an arc after
$i+\Theta\left(\frac{h\log_{1+\epsilon_{0}}n}{\epsilon_{0}}\right)$ many
iterations must have $w_{a}$ value at least
$(\frac{1}{m})^{\zeta}\cdot(1+\epsilon_{0})^{\Theta\left(\frac{\log_{1+\epsilon_{0}}n}{\epsilon_{0}}\right)}\geq
n^{2}$ for an appropriately large hidden constant in our $\Theta$. However, by
assumption, the weight of $P$ is at most $\lambda_{i}^{\prime}$ after
$i+\Theta\left(\frac{h\log_{1+\epsilon_{0}}n}{\epsilon_{0}}\right)$ iterations
and this is at most $2$ since $\lambda_{i}<1$ since otherwise our algorithm
would have halted. But $2<n^{2}$ and so we have arrived at a contradiction.

Repeatedly applying the fact that
$\lambda_{i}^{\prime}=(1+\epsilon_{0})\lambda_{i}$ gives that $\lambda$ is
always a lower bound on $d^{(h)}_{w}(S,T)$. ∎

We next prove the feasibility of our solution.

######  Lemma A.6.

The pair $(f,w)$ returned by Algorithm 5 are feasible for Multi Length-
Constrained Flow LP and Multi Moving Cut LP respectively.

###### Proof.

First, observe that by Lemma A.5 we know that $\lambda$ is always a lower
bound on $d_{w}^{(h)}(S_{i},T_{i})$ for every $i$ and so since we only return
once $\lambda>1$, the $w$ we return is always feasible.

To see that $f$ is feasible it suffices to argue that for each arc $a$, the
number of times a path containing $a$ has its primal value increased is at
most $\frac{U_{a}}{\eta}$. Notice that each time we increase the primal value
on a path containing arc $a$ by $\eta$ we increase the dual value of this edge
by a multiplicative $(1+\epsilon_{0})^{1/U_{a}}$. Since the weight of our arcs
according to $w$ start at $(\frac{1}{m})^{\zeta}$, it follows that if we
increase the primal value of $k$ paths incident to arc $a$ then
$w_{a}=(1+\epsilon_{0})^{k/U_{a}}\cdot(\frac{1}{m})^{\zeta}$. On the other
hand, by assumption when we increase the dual value of an arc $a$ it must be
the case that $w_{a}<1$ since otherwise $d_{w}^{(h)}(S,T)\geq 1$,
contradicting the fact that $\lambda$ always lower bounds $d_{w}^{(h)}(S,T)$.
It follows that $(1+\epsilon_{0})^{k/U_{a}}\cdot(\frac{1}{m})^{\zeta}\leq 1$
and so applying the fact that
$\ln(1+\epsilon_{0})\geq\frac{\epsilon_{0}}{1+\epsilon_{0}}$ for
$\epsilon_{0}>-1$ and our definition of $\zeta$ and $\eta$ we get

$\displaystyle k$
$\displaystyle\leq\frac{\zeta\cdot(1+\varepsilon_{0})}{\varepsilon_{0}}\cdot
U_{a}\log m$ $\displaystyle=\frac{U_{a}}{\eta}$

as desired. ∎

We next prove the near-optimality of our solution.

######  Lemma A.7.

The pair $(f,w)$ returned by Algorithm 5 satisfies
$(1-\epsilon)\sum_{a}w_{a}\leq\sum_{i}\sum_{P\in\mathcal{P}_{h}(S_{i},T_{i})}f_{P}$.

###### Proof.

Fix an iteration $i$ which is an iteration for the $j$th batch and let
$\hat{f}$ be the sum of all lightest path blockers that we compute in parallel
for each $(S_{i},T_{i})\in(\mathcal{S}_{j},\mathcal{T}_{j})$ in this
iteration. Let $k_{i}$ be $\text{val}(\hat{f})$, let $\lambda_{i}$ be
$\lambda$ at the start of this iteration and let $D_{i}:=\sum_{a}w_{a}$ be our
total dual value at the start of this iteration. Notice that
$\frac{1}{\lambda_{i}}\cdot w$ is dual feasible and has cost
$\frac{D_{i}}{\lambda_{i}}$ by Lemma A.5. If $\beta$ is the optimal dual value
then by optimality it follows that $\beta\leq\frac{D_{i}}{\lambda_{i}}$,
giving us the upper bound on $\lambda_{i}$ of $\frac{D_{i}}{\beta}$. By how we
update our dual, our bound on $\lambda_{i}$ and $(1+x)^{r}\leq 1+xr$ for any
$x\geq 0$ and $r\in(0,1)$ we have that

$\displaystyle D_{i+1}$
$\displaystyle=\sum_{a}(1+\epsilon_{0})^{\hat{f}(a)/U_{a}}\cdot w_{a}\cdot
U_{a}$
$\displaystyle\leq\sum_{a}\left(1+\frac{\epsilon_{0}\hat{f}(a)}{U_{a}}\right)\cdot
w_{a}\cdot U_{a}$ $\displaystyle=D_{i}+\epsilon_{0}\sum_{a}\hat{f}(a)w_{a}$
$\displaystyle\leq D_{i}+\epsilon_{0}(1+2\varepsilon_{0})\cdot
k_{i}\lambda_{i}$ $\displaystyle\leq
D_{i}\left(1+\frac{(1+2\varepsilon_{0})\varepsilon_{0}\cdot
k_{i}}{\beta}\right)$ $\displaystyle\leq
D_{i}\cdot\exp\left(\frac{(1+2\varepsilon_{0})\varepsilon_{0}\cdot
k_{i}}{\beta}\right).$

Let $T-1$ be the index of the last iteration of our algorithm; notice that
$D_{T}$ is the value of $w$ in our returned solution. Let $K:=\sum_{i}k_{i}$.
Then, repeatedly applying this recurrence gives us

$\displaystyle D_{T}$ $\displaystyle\leq
D_{0}\cdot\exp\left(\frac{(1+2\varepsilon_{0})\varepsilon_{0}\cdot
K}{\beta}\right)$
$\displaystyle=\left(\frac{1}{m}\right)^{\zeta-1}\exp\left(\frac{(1+2\varepsilon_{0})\varepsilon_{0}\cdot
K}{\beta}\right)$

On the other hand, we know that $w$ is dual feasible when we return it, so it
must be the case that $D_{T}\geq 1$. Combining this with the above upper bound
on $D_{T}$ gives us
$1\leq\left(\frac{1}{m}\right)^{\zeta}\exp\left(\frac{(1+2\varepsilon_{0})\varepsilon_{0}\cdot
K}{\beta}\right)$. Solving for $K$ and using our definition of $\zeta$ gives
us

$\displaystyle\beta\log
m\cdot\frac{\zeta-1}{(1+2\varepsilon_{0})\cdot\varepsilon_{0}}$
$\displaystyle\leq K$ $\displaystyle\beta\log
m\cdot\frac{1}{\varepsilon_{0}^{2}}$ $\displaystyle\leq K.$

However, notice that $K\eta$ is the primal value of our solution so using our
choice of $\eta$ and rewriting this inequality in terms of $K\eta$ by
multiplying by
$\eta=\frac{\varepsilon_{0}}{(1+\varepsilon_{0})\cdot\zeta}\cdot\frac{1}{\log
m}$ and applying our definition of
$\zeta=\frac{1+2\varepsilon_{0}}{\varepsilon_{0}}+1$ gives us

$\displaystyle\frac{\beta}{\varepsilon_{0}\cdot(1+\varepsilon_{0})\cdot\zeta}$
$\displaystyle\leq K\eta$
$\displaystyle\frac{\beta}{(1+\varepsilon_{0})(1+3\varepsilon_{0})}$
$\displaystyle\leq K\eta.$ (20)

Moreover, by our choice of $\varepsilon_{0}=\frac{\varepsilon}{6}$ and the
fact that $\frac{1}{1+x+x^{2}}\geq 1-x$ for $x\in(0,1)$ we get

$\displaystyle 1-\varepsilon$
$\displaystyle\leq\frac{1}{1+\varepsilon+\varepsilon^{2}}$
$\displaystyle\leq\frac{1}{(1+\frac{1}{2}\varepsilon)^{2}}$
$\displaystyle\leq\frac{1}{(1+3\varepsilon_{0})^{2}}$
$\displaystyle\leq\frac{1}{(1+\varepsilon_{0})(1+3\varepsilon_{0})}.$ (21)

Combining Equation 20 and Equation 21 we conclude that

$\displaystyle(1-\varepsilon)\cdot\beta\leq K\eta.$

∎

We conclude with our main theorem by proving that we need only iterate our
algorithm $\tilde{O}\left(\kappa\cdot\frac{h}{\epsilon^{4}}\right)$ times. See
A.1

###### Proof.

By Lemma A.6 and Lemma A.7 we know that our solution is feasible and
$(1\pm\epsilon)$-optimal so it only remains to argue the runtime of our
algorithm and that the returned flow decomposes in the stated way.

We argue that we must only run for
$O\left(\kappa\cdot\frac{h\log^{2}n}{\epsilon^{4}}\right)$ total iterations.
Since $\lambda$ increases by a multiplicative $(1+\epsilon_{0})$ after every
$\Theta\left(\kappa\cdot\frac{h\log n}{\epsilon_{0}^{2}}\right)$ iterations
and starts at least
$\left(\frac{1}{m}\right)^{\Theta(\frac{1}{\epsilon_{0}})}$, it follows by
Lemma A.5 that after $y\cdot\Theta\left(\kappa\cdot\frac{h\log
n}{\epsilon_{0}^{2}}\right)$ total iterations the $h$-length distance between
every $S_{i}$ and $T_{i}$ is at least
$(1+\epsilon_{0})^{y}\cdot\left(\frac{1}{m}\right)^{\Theta(1/\epsilon_{0})}$.
Thus, for
$y\geq\Omega\left(\frac{\ln_{1+\epsilon_{0}}m}{\epsilon_{0}}\right)=\Omega\left(\frac{\ln
n}{\epsilon_{0}^{2}}\right)$ we have that every $S_{i}$ and $T_{i}$ are at
least $1$ apart in $h$-length distance. Consequently, our algorithm must run
for at most
$O\left(\kappa\cdot\frac{h\log^{2}n}{\epsilon_{0}^{4}}\right)=O\left(\kappa\cdot\frac{h\log^{2}n}{\epsilon^{4}}\right)$
many iterations.

Our running time is immediate from the the bound of
$O\left(\kappa\cdot\frac{h\log^{2}n}{\epsilon^{4}}\right)$ on the number of
iterations of the while loop, the fact that commodities in the same batch can
be updated in parallel and the running times given in 11.1 for computing our
$h$-length $(1+\epsilon_{0})$-lightest path blocker.

Lastly, the flow decomposes in the stated way because we have at most
$O\left(\kappa\cdot\frac{h\log^{2}n}{\epsilon^{4}}\right)$ iterations and each
$f_{j}$ is an integral $S$-$T$ flow by 11.1. Thus, our final solution is
$\eta\cdot\sum_{j=1}^{k}f_{j}$ and
$k=\tilde{O}\left(\frac{h}{\epsilon^{4}}\right)$. Likewise we have
$|\text{supp}(f)|\leq\tilde{O}(\kappa\cdot\frac{h^{10}}{\varepsilon^{7}})$ for
our parallel algorithm since we have
$O\left(\kappa\cdot\frac{h\log^{2}n}{\epsilon^{4}}\right)$ iterations and the
fact that 11.1 guarantees each $(1+\varepsilon_{0})$-lightest path blocker has
support size at most $\tilde{O}(\frac{h^{9}}{\varepsilon^{3}}\cdot|A|)$. ∎

###  A.3 Computing Multi-Commodity Length-Constrained Cutmatches

We proceed to compute multi-commodity length-constrained cutmatches.

See A.2

###### Proof.

The proof is entirely analogous to that of 16.1 except we use A.1 instead of
3.1 to compute our flows and moving cuts. The only very minor difference is in
order to ensure that $f_{i}(a)\leq U_{a}$ for every
$a\in\delta^{\pm}(S_{i},T_{i})$ we must slightly change the graph in which we
work. Specifically, for each $S_{i}$ and each $s\in S_{i}$ where
$\delta^{+}(s)=\\{(s,t_{1}),(s,t_{2}),\ldots\\}$ we add new vertices
$s_{1},s_{2},\ldots$ and new arcs $(s_{1},s),(s_{2},s)$ each of length $0$ and
respective capacities $U_{(s,t_{1})},U_{(s,t_{2})},\ldots$. We then replace
$s$ in $S_{1}$ with $s_{1},s_{2},\ldots$. We do the same symmetric thing for
each $T_{i}$. As a result of this we know that every set in
$\\{S_{i}\\}_{i}\cup\\{T_{i}\\}_{i}$ is pairwise vertex disjoint. Also note
that we can simulate any parallel or CONGEST algorithm on $D$ in this new
graph with $O(1)$ time overhead. It is easy to verify that running the
algorithm from 16.1 on the resulting graph using A.1 instead of 3.1 then gives
the result. ∎

##  Appendix B Deferred Proofs

See 7.1

###### Proof.

The basic idea is to have each path $P$ sample about $U(P)/\tilde{\Delta}$
copies of itself.

More formally, we do the following. Consider the (multi) digraph $D^{\prime}$
that is created by starting with $D$ and replacing each arc $a$ with $U_{a}$
copies. For a given path $P$ in $D^{\prime}$ from $S$ to $T$, we let
$\Delta_{P}^{\prime}$ be the number of distinct $S$ to $T$ paths in
$D^{\prime}$ which share an arc with $P$. Likewise, we let
$\Delta^{\prime}=\max_{P}\Delta_{P}^{\prime}$ where this max is taken over all
$S$ to $T$ paths in $D^{\prime}$. We let $\mathcal{P}_{\approx\max}^{\prime}$
be all paths $P$ for which $\Delta_{P}^{\prime}\geq\Delta^{\prime}/2$. By how
we defined the degree of paths in $D$, if a given path $P$ is in
$\mathcal{P}_{\approx\max}^{\prime}$ then so too is its corresponding path in
$D$ in $\mathcal{P}_{\approx\max}$. Lastly, we let $N(P)$ be all paths from
$S$ to $T$ in $D^{\prime}$ which share an arc with $P$ other than $P$ itself
and let $N^{+}(P):=N(P)\cup\\{P\\}$.

In what follows we show how to sample a collection of arc-disjoint paths
$\mathcal{P}_{2}$ in $D^{\prime}$ where each
$P\in\mathcal{P}_{\approx\max}^{\prime}$ is such that with probability at
least $\frac{1}{1024}$ the set $\mathcal{P}_{2}\cap N^{+}(P)$ is non-empty.
Before doing so, we observe that this suffices to show our claim. In
particular, we can construct a flow $f$ by setting its value on arc $a$ to be
$|\\{P\in\mathcal{P}_{2}:a\in P\\}|$. Observe that by the arc-disjointness of
$\mathcal{P}_{2}$ and how we constructed $D^{\prime}$, $f$ is indeed a
feasible $S$-$T$ flow. Moreover, we claim that for a given
$\tilde{P}\in\mathcal{P}_{\approx\max}$ in $D$ we have
$\prod_{a\in\tilde{P}}(U_{a}-f_{a})\leq\frac{1}{2}U(\tilde{P})$ with
probability $\Omega(1)$. In particular, let $X_{P}$ be the indicator of
whether a given path $P$ in $D^{\prime}$ from $S$ to $T$ is such that
$N^{+}(P)\cap\mathcal{P}_{2}=\emptyset$ so that
$\mathbb{E}[X_{P}]\leq\frac{1023}{1024}$. Also, let $\tilde{\mathcal{P}}$ be
all the paths in $D^{\prime}$ that visit the same vertices as $\tilde{P}$ in
$D$. Then we have

$\displaystyle\prod_{a\in\tilde{P}}(U_{a}-f_{a})=\sum_{P\in\tilde{\mathcal{P}}}X_{P}.$

But, looking at the expectation of this, we have

$\displaystyle\mathbb{E}\left[\sum_{P\in\tilde{\mathcal{P}}}X_{P}\right]$
$\displaystyle\leq\sum_{P\in\tilde{\mathcal{P}}}\frac{1023}{1024}$
$\displaystyle=\frac{1023}{1024}\cdot U(\tilde{P})$

Thus, by Markov’s inequality we have that
$\sum_{P\in\tilde{\mathcal{P}}}X_{P}\geq\frac{2047}{2046}\cdot\mathbb{E}\left[\sum_{P\in\tilde{\mathcal{P}}}X_{P}\right]$
with probability at most $\frac{2046}{2047}$ and so with probability
$\Omega(1)$ we get that
$\sum_{P\in\tilde{\mathcal{P}}}X_{P}\leq\frac{2047}{2046}\cdot\mathbb{E}\left[\sum_{P\in\tilde{\mathcal{P}}}X_{P}\right]\leq\frac{2047}{2048}\cdot
U(\tilde{P})$.

Thus, it remains to show how to sample our collection of arc-disjoint paths
$\mathcal{P}_{2}$ in $D^{\prime}$ where each
$P\in\mathcal{P}_{\approx\max}^{\prime}$ is such that with probability at
least $\frac{1}{1024}$ the set $\mathcal{P}_{2}\cap N^{+}(P)$ is non-empty. We
will sample $\mathcal{P}_{2}$ as follows. Imagine that $s$ initially receives
$B\left(n_{s}^{+},\frac{1}{64\tilde{\Delta}}\right)$-many balls where $B(n,p)$
is a binomial with $n$ trials each with probability of success $p$. We let
$n_{a}$ and $n_{v}^{+}$ be as defined in Section 6 for $D^{\prime}$ where
$U_{a^{\prime}}=1$ for every arc $a^{\prime}$ in $D^{\prime}$.

When a vertex $v$ receives a ball, it tosses it to vertex $u\in N^{+}(v)$ with
probability $n^{+}_{u}/n_{v}^{+}$. As $n_{v}^{+}=\sum_{w\in
N^{+}(v)}n_{w}^{+}$ this induces a valid probability distribution. Let
$\mathcal{P}_{1}$ be the (multi) set of all paths traced out by balls. We will
let $\mathcal{P}_{2}$ be all paths in $\mathcal{P}_{1}$ which are arc-disjoint
(in $D^{\prime}$) from all other paths in $\mathcal{P}_{1}$.

We first consider this process from the perspective of a single path $P$ from
$S$ to $T$ in $D^{\prime}$. Specifically, notice that the probability that a
ball traces out a path $P=(s=v_{1},v_{2},\ldots,v_{h+1}=t)$ where $s\in S$ and
$t\in T$ is uniform over paths. In particular, the probability that a given
ball traces out path $P$ in $D^{\prime}$ from $s$ to $t$ nicely telescopes as

$\displaystyle\frac{n^{+}_{v_{2}}}{n_{v_{1}}^{+}}\cdot\frac{n^{+}_{v_{3}}}{n_{v_{2}}^{+}}\cdot\ldots\cdot\frac{n^{+}_{v_{h+1}}}{n_{v_{h}}^{+}}$
$\displaystyle=\frac{n_{v_{h+1}}^{+}}{n_{v_{1}}^{+}}$
$\displaystyle=\frac{1}{n_{s}^{+}}.$

Thus, each ball that starts at $s$ traces out a uniformly random path incident
to $s$ in $\mathcal{P}(S,T)$. Applying the parameters of our binomial
distribution, it follows that the expected number of times a given path $P$ is
included in $\mathcal{P}_{1}$ is $\frac{1}{64\cdot\tilde{\Delta}}$. Markov’s
inequality then shows that a given path has some copy in $\mathcal{P}_{1}$
with probability at most
$\frac{1}{64\cdot\tilde{\Delta}}\leq\frac{1}{32\cdot\Delta}$. On the other
hand, $P$ has exactly one copy included in $\mathcal{P}_{1}$ with probability
$\frac{1}{64\tilde{\Delta}}n^{+}_{s}\cdot\frac{1}{n^{+}_{s}}\left(1-\frac{1}{n_{s}^{+}}\right)^{n^{+}-1}\geq\frac{1}{128\tilde{\Delta}}$.
Thus, $P$ has at least one copy in $\mathcal{P}_{1}$ with probability at least
$\frac{1}{128\tilde{\Delta}}\geq\frac{1}{128\Delta}$.

We proceed to bound two simple probabilities regarding how paths are sampled.
In particular, fix a path $P\in\mathcal{P}^{\prime}_{\approx\max}$ in
$D^{\prime}$ from $S$ to $T$. Next, fix a $P^{\prime}\in N^{+}(P)$. Then, let
$\mathcal{E}_{1}(P^{\prime})$ be the event that some copy of $P^{\prime}$ is
in $\mathcal{P}_{1}$ and no other path in $N^{+}(P)$ has a copy in
$\mathcal{P}_{1}$. Likewise, let $\mathcal{E}_{2}(P^{\prime})$ be the event
that no path in $N(P^{\prime})$ is in $\mathcal{P}_{1}$. Notice that if
$\mathcal{E}_{1}(P^{\prime})$ and $\mathcal{E}_{2}(P^{\prime})$ hold then we
have $P^{\prime}\in\mathcal{P}_{2}$.

  * •

Bounding $\Pr(\mathcal{E}_{1}(P^{\prime}))$. We will argue that
$\Pr(\mathcal{E}_{1}(P^{\prime}))\geq\frac{1}{256\Delta}$.

Notice that since $N^{+}(P)\setminus\\{P^{\prime}\\}$ consists of at most
$\Delta$-many paths, the expected number of copies of paths in
$N^{+}(P)\setminus\\{P^{\prime}\\}$ in $\mathcal{P}_{1}$ is at most
$\frac{1}{32}$. It follows by a Markov bound that with probability at least
$\frac{1}{2}$ we have
$N^{+}(P)\setminus\\{P^{\prime}\\}\cap\mathcal{P}_{1}=\emptyset$.

Next, imagine that we condition on the event
$N^{+}(P)\setminus\\{P^{\prime}\\}\cap\mathcal{P}_{1}=\emptyset$. Conditioning
on this event can only increase the probability that a ball traces out
$P^{\prime}$. Since some copy of $P^{\prime}$ is included in $\mathcal{P}_{1}$
with probability at least $\frac{1}{128\Delta}$ when we don’t condition on
this event, we conclude that

$\displaystyle\Pr(\mathcal{E}_{1}(P^{\prime}))$
$\displaystyle=\Pr(N^{+}(P)\setminus\\{P^{\prime}\\}\cap\mathcal{P}_{1}=\emptyset)\cdot\Pr(P^{\prime}\in\mathcal{P}_{1}\mid
N^{+}(P)\setminus\\{P^{\prime}\\}\cap\mathcal{P}_{1}=\emptyset)$
$\displaystyle\geq\Pr(N^{+}(P)\setminus\\{P^{\prime}\\}\cap\mathcal{P}_{1}=\emptyset)\cdot\Pr(P^{\prime}\in\mathcal{P}_{1})$
$\displaystyle\geq\frac{1}{256\Delta}.$

  * •

Bounding $\Pr(\mathcal{E}_{2}(P^{\prime})\mid\mathcal{E}_{1}(P^{\prime}))$. We
argue that
$\Pr(\mathcal{E}_{2}(P^{\prime})\mid\mathcal{E}_{1}(P^{\prime}))\geq\frac{1}{2}$.

Notice that $\Pr(\mathcal{E}_{2}(P^{\prime})\mid\mathcal{E}_{1}(P^{\prime}))$
is minimized when $N^{+}(P)$ is of size exactly $\Delta+1$. However, in this
case we have
$\Pr(\mathcal{E}_{2}(P^{\prime})\mid\mathcal{E}_{1}(P^{\prime}))\geq\Pr(\mathcal{E}_{2}(P^{\prime}))$.
Thus, we conclude by a union bound that in general
$\Pr(\mathcal{E}_{2}(P^{\prime})\mid\mathcal{E}_{1}(P^{\prime}))\geq\Pr(\mathcal{E}_{2}(P^{\prime}))\geq
1-\Delta\cdot\frac{1}{32\Delta}\geq\frac{1}{2}$.

Putting these facts together and applying the fact that
$P\in\mathcal{P}^{\prime}_{\approx\max}$, we have that there is path in
$N^{+}(P)$ included in $\mathcal{P}_{2}$ with probability at least

$\displaystyle\sum_{P^{\prime}\in
N^{+}(P)}\Pr(\mathcal{E}_{1}(P^{\prime}))\cdot\Pr(\mathcal{E}_{2}(P^{\prime})\mid\mathcal{E}_{2}(P^{\prime}))$
$\displaystyle\geq\sum_{P^{\prime}\in N^{+}(P)}\frac{1}{512\Delta}$
$\displaystyle\geq\frac{1}{1024}.$

as required.

It remains to argue that we can accomplish the above sampling of
$\mathcal{P}_{1}$ and the construction of our flow $f$ in the stated times.
Constructing $f$ from $\mathcal{P}_{1}$ is trivial to do in parallel and
CONGEST so we focus on sampling $\mathcal{P}_{1}$. By Lemma 6.1 we can compute
$n^{+}_{v}$ in the stated times. Passing balls to construct $\mathcal{P}_{1}$
and then $\mathcal{P}_{2}$ and constructing the above flow is trivial to do in
the stated parallel time. For the CONGEST algorithm, we note that expected
number of balls to cross any one arc in $D^{\prime}$ when constructing
$\mathcal{P}_{1}$ is at most $1$ and so a Chernoff and union bound shows that
with high probability we never need to transmit more than $O(\log n)$ balls
across an arc in $D^{\prime}$ when constructing $\mathcal{P}_{1}$, with high
probability. It follows that we never need to transmit more than
$\tilde{O}(U_{\max})$ balls across any one arc in $D$. Since it suffices to
just transmit the number of balls, this can be done in $\tilde{O}(\log
U_{\max})=\tilde{O}(1)$ rounds with high probability. Thus we can pass all
balls from one layer to the next in $\tilde{O}(1)$ rounds of CONGEST with high
probability. Lastly, constructing $\mathcal{P}_{2}$ from $\mathcal{P}_{1}$ is
trivial to do in $O(h)$ rounds of CONGEST. ∎

See 7.2

###### Proof.

Our algorithm simply repeatedly calls Lemma 7.1. In particular we initialize
our output flow $\hat{f}$ to be $0$ on all arcs and our working capacities on
$D$ to be $\hat{U}=U$. Then for each $\tilde{\Delta}=(n\cdot
U_{\max})^{h},(n\cdot U_{\max})^{h}/2,(n\cdot U_{\max})^{h}/4,\ldots$ we
repeat the following $\Theta(h\cdot\log n\cdot\log U_{\max})$ times. Let $f$
be the flow computed according to Lemma 7.1. Update
$\hat{U}_{a}=\hat{U}_{a}-f_{a}$ for every $a$ and update $\hat{f}=\hat{f}+f$.
Clearly $\hat{f}$ is an integral $S$-$T$ flow.

We need only verify that $\hat{f}$ is blocking. Since initially
$\Delta\leq(n\cdot U_{\max})^{h}$, to do so it suffices to argue that when we
fix a value of $\tilde{\Delta}$ for which
$\frac{\Delta}{2}\leq\tilde{\Delta}\leq\Delta$, then over the course of the
$\Theta(h\cdot\log n\cdot\log U_{\max})$ iterations where we use this value of
$\tilde{\Delta}$ we have that $\Delta$ decreases by at least a factor of $2$
with high probability.

Consider $\Theta(h\cdot\log n\cdot\log U_{\max})$ contiguous iterations of the
above with a $\tilde{\Delta}$ that satisfies
$\frac{\Delta}{2}\leq\tilde{\Delta}\leq\Delta$ at the beginning of these
iterations. Let $\mathcal{P}_{0}$ be $\mathcal{P}_{\approx\max}$ at the
beginning of these iterations. To show that $\Delta$ decreases by at least a
factor of $2$ over the course of these $\Theta(h\cdot\log n\cdot\log
U_{\max})$ iterations it suffices to show that no path in $\mathcal{P}_{0}$ is
in $\mathcal{P}_{\approx\max}$ for all of these iterations. Suppose for the
sake of contradiction that some path $P\in\mathcal{P}_{0}$ is in
$\mathcal{P}_{\approx\max}$ for all of these iterations. Then, applying the
guarantees of Lemma 7.1, we get that with high probability $U(P)$ decreases by
a $\frac{2047}{2048}$ factor at least $\Theta(h\cdot\log U_{\max}))$ times.
However, since $U(P)\leq O((U_{\max})^{h})$, we get that after these
iterations we would have reduced $U(P)$ to $0$ with high probability by a
union bound, i.e. $\Delta$ must have reduced by at least a factor of $2$.

The running time of our algorithm is immediate from the fact that we simply
invoke Lemma 7.1 $\tilde{O}(h^{2})$ times.∎

## References

  * Ahmadi et al. [2018] Mohamad Ahmadi, Fabian Kuhn, and Rotem Oshman.  Distributed approximate maximum matching in the congest model.  In _International Symposium on Distributed Computing (DISC)_. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
  * Altmanová et al. [2019] Kateřina Altmanová, Petr Kolman, and Jan Voborník.  On polynomial-time combinatorial algorithms for maximum l-bounded flow.  In _Algorithms and Data Structures Symposium (WADS)_ , pages 14–27. Springer, 2019.
  * Andoni et al. [2020] Alexandr Andoni, Clifford Stein, and Peilin Zhong.  Parallel approximate undirected shortest paths via low hop emulators.  In _Annual ACM Symposium on Theory of Computing (STOC)_ , pages 322–335, 2020.
  * Arora et al. [2015] Sanjeev Arora, Boaz Barak, and David Steurer.  Subexponential algorithms for unique games and related problems.  _Journal of the ACM (JACM)_ , 62(5):1–25, 2015\.
  * Awerbuch and Khandekar [2007] Baruch Awerbuch and Rohit Khandekar.  Distributed network monitoring and multicommodity flows: a primal-dual approach.  In _ACM Symposium on Principles of Distributed Computing (PODC)_ , pages 284–291, 2007.
  * Awerbuch and Khandekar [2008] Baruch Awerbuch and Rohit Khandekar.  Greedy distributed optimization of unsplittable multicommodity flows.  In _ACM Symposium on Principles of Distributed Computing (PODC)_ , pages 439–439, 2008.