Using alg-ultra, we now prove ultra as follows. Let $S\s E$ be the corresponding spanner in $G$ sharing the same edges as $\LS\s\LE$ (with possibly different weights). Intuitively, since $\LG$ approximates the edge weights of $G$ up to factor $k$, the $k$-spanner $S$ should be a $k^2$-spanner on $G$. More formally, given an edge $(u,v)\in E$, let $u=v_0,v_1,\lds,v_\el=v$ be the shortest path in $\LS$. We have

\[ d_S(u,v) \le \sum_{i=1}^\el d_S(v_{i-1},v_i) \le \sum_{i=1}^\el k\cd d_{\LS}(v_{i-1},v_i) = k \cd d_{\LS}(u,v) \le k \cd kd_{\LG}(u,v) \le k^2d_G(u,v) .\]

Therefore, $S$ is a $k^2$-spanner of $G$.

§ SHERMAN'S FRAMEWORK VIA MULTIPLICATIVE WEIGHTS

In this section, we provide a self-contained proof of sherman using the multiplicative weights updates framework at the loss of an additional $\log(n/\e)$, which can be disregarded in our parallel algorithms.

We begin with the following classical result on solving linear programs approximately with multiplicative weights update framework. We state it without proof, since the result is a staple in advanced algorithms classes.

[Solving LPs with Multiplicative Weights Update]mwu
Let $\de\le1$ and $\om>0$ be parameters.
Consider a convex set $K\s \R^n$, a matrix $M\in\R^{m\times n}$, and a vector $c\in\R^m$. (We want to investigate approximate feasibility of the set $\{y\in K:My\le c\}$.) Let $\m O$ be an oracle that, given any vector $p\in\De_m$, either outputs a vector $y\in K$ satisfying $p^TMy\le p^Tc$ and $\norm{My-c}_\infty\le \om$, or determines that the set $\{y\in K:p^TMy\le p^Tc\}$ is infeasible. Then, consider the following algorithm:
Set $p_0\gets\f1m\mathbbm1\in\De_m$
For $t=1,2,\lds,T$ where $T = O(\om^2\log m/\de^2)$:
Call oracle $\m O$ with $p_{t-1}\in\De_m$, obtaining vector $y^{(t)}$
If $\m O$ determines that no $y\in K$ exists, then output $p_{t-1}$ and exit
For each $j\in[m]$, set $w^{(t)}_j\gets w^{(t-1)}_j\cd\exp(\de \cd (My^{(t)}-c)_j) = \exp(\de\cd\sum_{i\in[t]}(My^{(i)}-c)_j)$
For each $j\in[m]$, set $p^{(t)}_j\gets w^{(t)}_j/\sum_{i\in[m]}w^{(t)}_i$
Output $\f1T\sum_{i\in[T]}y^{(i)}\in K$
If this algorithm outputs a vector $p\in\De_m$ on step 2(b), then the set $\{x\in K:Mx\le c\}$ is infeasible. Otherwise, if the algorithm outputs a vector $x\in K$ on step 3, then we have $Mx \le c + \de\mathbbm1$.

Consider a transshipment instance with demands $b$ and a parameter $t \ge \opt(b)/2$. Let $r$ be a parameter, and let $R\in\R^{[r]\times V}$ be a matrix satisfying  kappa for some parameter $\ka$. Then, there is an algorithm that performs $O((\ka/\e)^2\logn)$ matrix-vector multiplications with $A$, $A^T$, $R$, and $R^T$, as well as $O((\ka/\e)^2\logn)$ operations on vectors in $\R^r$, and outputs either
an acyclic flow $f$ satisfying $\1{Cf}\le t$ and $\1{RAf-Rb} < \e t$, or
a potential $\phi$ with value $b^T\phi=t$.

We will run Multiplicative Weights Update (mwu) to determine feasibility of the region

\[ \{ y\in\R^r : \norm{y^TRAC\inv}_\infty + \f1ty^TRb \le -\e \text{ and } \norm{y}_\infty\le1 \} ,\]

which is modeled off the dual LP formulation for ; this connection will become clearer once output-2 is proved.

We set $c:=\e\mathbbm1$ and $K:=\{y\in\R^r:\norm y_\infty\le1\}$ in mwu. As for matrix $M$, the constraint $\norm{y^TRAC\inv}_\infty+\f1ty^TRb\le-\e$ can be expanded into

\[ \pm y^TRAc_e\inv\chi_e + \f1ty^TRb \le -\e \quad \forall e\in E , \]

so the rows of matrix $M$ consist of the $2m$ vectors $(\pm RAc_e\inv\chi_e+\f1tRb)^T$ for each $e\in E$.

We now specify the oracle $\m O$. On each iteration, the algorithm of mwu computes values $p_e^+,p_e^-\ge0$ for each $e\in E$ satisfying $\sum_e(p_e^++p_e^-)=1$. The oracle needs to compute a vector $y$ satisfying $\norm y_\infty\le1$ and

\[ \sum_{e\in E}\lp p_e^+\big(y^TRAc_e\inv\chi_e+\f1ty^TRb\big)  + p_e^-\big({-y^TRAc_e\inv\chi_e}+\f1ty^TRb\big)  \rp \le -\e .\]

This inequality can be rewritten as

\[ y^T\bigg(RA\sum_{e\in E}c_e\inv(p_e^+\chi_e-p_e^-\chi_e)+ \f1tRb\bigg) \le -\e .\]

Observe that a solution $y$ exists iff

\begin{gather}
\1{RA\sum_{e\in E}c_e\inv(p_e^+\chi_e-p_e^-\chi_e)+\f1tRb} \ge \e , \label{eq:p}
\end{gather}

and if the inequality is true, then the vector $y:=-\text{sign}(RA\sum_{e\in E}c_e\inv(p_e^+\chi_e-p_e^-\chi_e)+\f1tRb)$ is a solution, so the oracle outputs it.

We set the error parameter $\de$ to be $\e/(2\ka)$. Then, either the algorithm of mwu outputs $p$ that violates (<ref>) on some iteration, or after a number of iterations (depending on $\rho$, which we have yet to bound), the average of all vectors $y$ computed over the iterations satisfies

\begin{gather}
\pm y^TRAc_e\inv\chi_e + \f1ty^TRb \le -\e + \f\e{2}=-\f\e{2} \quad \forall e\in E \quad\iff\quad \norm{y^TRAC\inv}_\infty + \f1ty^TRb \le -\f\e{2} . \eqnl{yy}
\end{gather}

First, suppose that the second case holds:
Suppose mwu outputs a vector $y$ satisfying yy. Then, we can compute a potential $\phi$ satisfying condition (2).
Consider the vector $\phi_0:=-(y^TR)^T$. We have

\[ \norm{\phi_0^TAC\inv}_\infty - \f1t\phi_0^Tb \le -\f\e{2\ka} < 0 .\]

In particular, $\f1t\phi_0^Tb>0$. Let $\phi$ be the vector $\phi_0$ scaled up so that $\f1t\phi^Tb=1$. Then,

\[ \norm{\phi^TAC\inv}_\infty - \f1t\phi^Tb  < 0 \implies \norm{\phi^TAC\inv}_\infty < \f1t\phi^Tb = 1 .\]

Since $\phi$ satisfies the transshipment dual constraints, it is a potential. Moreover, $\phi^Tb=t$, so $\phi$ satisfies condition (2).

Let us now consider the first case:
Suppose mwu outputs values $p_e^+,p_e^-\ge0$ satisfying  $\sum_e(p_e^++p_e^-)=1$ and

\[ \1{RA\sum_{e\in E}c_e\inv(p_e^+\chi_e-p_e^-\chi_e)+\f1tRb} < \e. \]

Then, we can compute an acyclic flow satisfying condition (1).
Let us construct a flow $f\in\R^E$ defined as $f := -t\sum_ec_e\inv(p_e^+\chi_e-p_e^-\chi_e)$. We have
\[\1{Cf}=\1{-t\sum_{e\in E}(p_e^+\chi_e-p_e^-\chi_e)}=-t\sum_{e\in E}|p_e^+-p_e^-|\le t\sum_{e\in E}(p_e^++p_e^-)= t\]

\[ \1{-RAf+Rb} < \e t ;\]

it remains to show that $f$ is acyclic. Fix an edge $e=(u,v)$, so that $A\chi_e=\chi_u-\chi_v$. We have that $f$ flows from $u$ to $v$ iff

\[ f_e>0 \iff -tc_e\inv ( p^+_e - p^-_e ) > 0 \iff p^+_e < p^-_e .\]

By the construction of $p^\pm_e$ from mwu,

\begin{align*}
p^+_e < p^-_e &\iff \sum_{i\in[t]}\big((RAc_e\inv\chi_e + \f1tRb)^Ty^{(i)}-\e\big) < \sum_{i\in[t]}\big((-RAc_e\inv\chi_e + \f1tRb)^Ty^{(i)}-\e\big)
\\&\iff (RAc_e\inv\chi_e)^T\sum_{i\in[t]}y^{(i)} < (-RAc_e\inv\chi_e)^T\sum_{i\in[t]}y^{(i)}
\end{align*}

Let $\overline y:=\sum_{i\in[t]}y^{(i)}$, so that this becomes

\begin{align*}
(RAc_e\inv \chi_e)^T\overline y < (-RAc_e\inv\chi_e)^T\overline y &\iff \overline y^TRc_e\inv(\chi_u-\chi_v) < -\overline y^TRc_e\inv(\chi_u-\chi_v) \\&\iff \overline y^TRc_e\inv\chi_u < \overline y^TRc_e\inv\chi_v.
\end{align*}

Therefore, $f$ will only flow from $u$ to $v$ if $(\overline y^TR)_u < (\overline y^TR)_v$; it follows that such a flow cannot produce any cycles.
We now bound the value $\om$ needed for mwu, which in turn bounds the number of iterations $T$.
In mwu, we can set $\om:=3\ka$.
Consider an iteration where mwu outputs values $p_e^+,p_e^-$, and define  $f := -t\sum_ec_e\inv(p_e^+\chi_e-p_e^-\chi_e)$ as before, so that $\1{Cf}\le t$. Let $f^*$ be an optimal flow for demand vector $b$, and by assumption, $\1{Cf^*}=\opt(b)\le2t$. We have

\begin{align*}
\1{RAf-Rb} &= \1{RAf^*-Rb+RA(f-f^*)}
\\&= \1{RA(f-f^*)}.
\end{align*}

The flow $f-f^*$ has cost $\1{C(f-f^*)}\le\1{Cf}+\1{Cf^*}\le t+2t=3t$ and satisfies demand $A(f-f^*)$. By (<ref>),

\[ \1{RAf-Rb} = \1{RA(f-f^*)}\le\ka\cd\textsf{opt}(A(f-f^*))\le\ka\cd3t ,\]

which implies that

\[ \1{RA\sum_{e\in E}c_e\inv(p_e^+\chi_e-p_e^-\chi_e)+\f1tRb} \le 3\ka. \]

Since any vector $y$ the algorithm chooses must satisfy $\norm y_\infty\le1$, we must have

\[ \left| y^T\bigg(RA\sum_{e\in E}c_e\inv(p_e^+\chi_e-p_e^-\chi_e)+ \f1tRb\bigg) \right| \le 3\ka ,\]

so $\om=3\ka$ works, as promised.

We only used the upper bound in (<ref>); the lower bound will become useful when we work with condition (1) in the lemma. Moreover, we will not need that the flow $f$ is acyclic, but this property may be useful in other applications.

We now claim that sherman-para follows from sherman-mwu. We apply sherman-mwu $O(\log(n/\e))$ times by binary-searching on the value of $t$, which we ensure is always at least $\opt(b)/2$ as required by sherman-mwu. Begin with $t=\poly(n)$, an upper bound on $\opt(b)$. First, while sherman-mwu outputs a flow $f$ (case (1)), set $t\gets \f{1+\e}2t$ for the next iteration. We claim that the new $t':=\f{1+\e}2t$ still satisfies $t'\ge \opt(b)/2$:

\[ \opt(b) \le \1{f}+\opt(Af-b) \le \1{f}+\1{RAf-Rb}\le t+\e t \implies \f{\opt(b)}2 \le \lp\f{1+\e}2\rp t=t' .\]

Repeat this until sherman-mwu outputs a potential $\phi$ instead, which signifies that $\opt(b) \ge b^T\phi=t$. At this point, we know that $\opt(b)\in[t,2t]$, and we can properly run binary search in this range, where a flow $f$ returned for parameter $t$ signifies that $\opt(b)\le t+\e t$, and a potential $\phi$ returned means that $\opt(b)\ge t$. Through binary search, we can compute two values $t_\el,t_r$ such that $t_r-t_\el\le\e\,\opt(b)$ and $\opt(b) \in (t_\el,t_r)$.

Then, run sherman-mwu with parameter $t=t_\el/(1+\e)$. We claim that we must obtain a potential $\phi$, not a flow $f$: if we obtain a flow $f$ instead, then

\[ \opt(b) \le \1{f}+\opt(Af-b) \le \1{f}+\1{RAf-Rb} \le t+\e t=t_\el ,\]

contradicting the assumption that $\opt(b)>t_\el$. This potential $\phi$ satisfies
$b^T\phi=\f{t_\el}{1+\e} \ge \f{t_r-\e\,\opt(b)}{1+\e}\ge \f{\opt(b)-\e\,\opt(b)}{1+\e} = (1-O(\e))\opt(b)$, which is almost optimal. At this point, we can compute a $(1+\e)$-approximation of $\opt(b)$, but we still need a transshipment flow $f$.

Next, run sherman-mwu with parameter $t=t_r$; we claim that we must obtain a flow $f$ this time: if we obtain a potential $\phi$ instead, then $\opt(b)\ge b^T\phi=t_r$, contradicting the assumption that $\opt(b)<t_r$. This flow satisfies $\1{f}\le t_r\le t_\el+\e\,\opt(b)\le\opt(b)+\e\,\opt(b)=(1+\e)\opt(b)$. However, we are not done yet, since $f$ does not satisfy $Af=b$; rather, we only know that $\opt(Af-b)\le\1{R(Af-b)}\le \e\,\opt(b)$. The key idea is to solve transshipment again with demands $b_1:=Af-b$; if we can obtain a $(1+\e)$-approximate flow $f_1$ satisfying $\1{f_1}\le\opt(b_1)=\opt(Af-b)\le\e\,\opt(b)$ and $\1{R(Af_1-b_1)} \le \e\,\opt(b_1)\le\e^2\opt(b)$, then the composed flow $f+f_1$ has cost

\[ \1{f+f_1}\le\1{f}+\1{f_1}\le(1+\e)\opt(b) + (1+\e)\opt(b_1) \le (1+\e)\opt(b)+(1+\e)\e\,\opt(b),\]

which is $(1+O(\e))\opt(b)$. We can continue this process, defining $b_i:=Af_{i-1}-b_{i-1}$ and computing  a flow $f_i$ satisfying $\1{f_i}\le\opt(b_i)=\opt(Af_{i-1}-b_{i-1})\le \e\,\opt(b_{i-1})\le\e^i\opt(b)$ and $\1{R(Af_i-b_i)}\le\e\,\opt(b_i) \le \e^{i+1}\opt(b)$ and adding it on to $f+f_1+f_2+\cds+f_{i-1}$. Assuming $\e\le1/2$, say, we can stop after $T:=O(\logn)$ iterations, so that the leftover demands $b_{T+1}$ satisfies $\opt(b_{T+1}) \le \f1{n^3}\opt(b)$. At this point, we can simply run an $n$-approximate algorithm to demands $b_{T+1}$ by routing through a minimum spanning tree (see <Ref>), computing a flow $f_{T+1}$ satisfying $\1{f_{T+1}}\le n\cd\f1{n^3}\opt(b)\le\e\,\opt(b)$, assuming $\e\ge1/n^2$. (If $\e=O(1/n^2)$, then a transshipment algorithm running in time $\tO(1/\e^2)\ge\tO(n^4)$ is trivial.) The final flow $f+f_1+f_2+\cds+f_{T+1}$ has cost at most $(1+O(\e))\opt(b)$.

We have thus computed $\phi$ satisfying $\1{f} \le (1+O(\e))\opt(b) \le (1+O(\e))b^T\phi$, so $(f,\phi)$ is an $(1+O(\e))$-approximate flow-potential pair. Finally, we can reset $\e$ a constant factor smaller to obtain a $(1+\e)$-approximation. This concludes the algorithm of sherman-para; it remains to bound the running time.

In each iteration of mwu, we perform $O(1)$ matrix-vector multiplications with $A$, $A^T$, $R$, and $R^T$, as well as an additional $O(m)$ work and $\pl(m)$ time, and the same holds for the oracle $\m O$. This requires $O(n+m+M)$ total work. By mwu, there are $O(\om^2\log m/\de^2) = O((\ka/\e)^2\logn)$ iteration inside sherman-mwu to compute one flow $f$ or potential $\phi$. Finally, sherman-mwu is called $\pl(n)$ times as described above, hence the promised running time.

§ TRANSSHIPMENT TO EXPECTED SSSP: SEQUENTIAL

In this section, we devise an algorithm that solves the approximate expected single-source shortest path problem, defined below, using multiple sequential calls to approximate transshipment. The fact that the recursive calls are made sequentially does not immediately imply a parallel algorithm, but in parallel-esssp, we show how to save enough computation between the recursive calls to ensure a parallel algorithm. This extra step is more technical than insightful, hence its deferral to a separate subsection.

Finally, in sample-tree, we show how to reduce SSSP to this expected version of SSSP [5]. Together, <Ref> form a complete proof of sample-tree. We remark that while sample-tree is simply a rephrasing of a similar routine in [5] and only included for self-containment, this section is novel, albeit still inspired by [5].

[Approximate expected $s$-SSSP Tree]
Given a graph $G=(V,E)$, a source $s$, and a demand vector $b$ satisfying $b_v\ge0$ for all $v\ne s$, an $\al$-approximate expected $s$-SSSP tree is a randomized (not necessarily spanning) tree $T$ satisfying

\[ \E\lb\sum_{v:b_v>0} b_v \cd  d_T(s,v) \rb  \le \al \sum_{v:b_v>0}b_v \cd d_G(s,v) .\]

If $b_v>0$ for all $v\ne s$, then the tree $T$ must in fact be spanning. We also remark that the term expected has two meanings here. First, the tree $T$ is randomized, so the guarantee

\[ \sum_{v:b_v>0} b_v \cd  d_T(s,v)  \le \al \sum_{v:b_v>0}b_v \cd d_G(s,v) \]

is only satisfied in expectation. However, even if this guarantee is satisfied with probability $1$, the distances $d_T(s,v)$ are not automatically $\al$-approximate distances for every $v$; rather, they only hold on average (weighted by $b_v$). Note that in the exact setting $\al=1$, all distances $d_T(s,v)$ are indeed exact, but this property breaks down as soon as $\al>1$.

Define $\TES(n,m,\al)$ as the work to compute an $\al$-approximate expected SSSP with arbitrary demand vector $b$ satisfying $b_v\ge0$ for all $v\ne s$. Our algorithm <ref> is itself recursive and satisfies the following recursion:

$\TES(n,m,(1+3\e)\al) \le \WTS(m,\e) + \TES(n/2,m,\al)$.

Of course, we can solve expected SSSP exactly ($\al=1$) in constant time on constant-sized graphs, so this recursion has depth at most $\log_2n$.
Unraveling this recursion, the algorithm calls transshipment at most $\log_2n$ times, and the error $(1+3\e)$ blows up multiplicatively over each recursion level, obtaining

\[ \TES(n,m,(1+3\e)^{\log_2n}) \le \log_2n\cd \WTS(m,\e) + \tO(m) .\]

Resetting the value $\e$, we can rewrite it as

\begin{gather} \TES(n,m,1+\e) \le O(\logn)\cd \WTS(m,\Th(\e/\logn)) + \tO(m) ,\eqnl{esssp-rec}\end{gather}

which is our targeted recursion for our algorithm <ref> below.

Assumption: demand vector $b$ satisfies $b_s>0$ and $b_t\le0$ for all $t\in V\sm s$
[1]
Compute a $(1+\e$)-approximate transshipment $f$ on $G$ with demand vector $b$
Initialize the digraph $\orA\gets\emptyset$
Every vertex $u\in V\sm s$ with $\In(u)\ne\emptyset$ independently samples a random neighbor $v\in\Out(u)$ with probability $\orf(u,v)/\FOut(u)$ and adds arc $(u,v)$ to $\orA$ sample-edge
Add a self-loop $(s,s)$ of zero weight to $\orA$
Let $A$ be the undirected version of $\orA$
Initialize $G'\gets(\emptyset,\emptyset)$ as an empty undirected graph Graph to be recursed on, with $\le n/2$ vertices
Initialize $b'$ as an empty vector Demands to be recursed on
each connected component $C$ of $A$
$c(C)\gets$ total weight of edges in the (unique) cycle in $C$ (possibly the self-loop $(s,s)$)
Let $T_C$ be the graph $C$ with its (unique) cycle contracted into a single vertex $r_C$ $T_C$ is a tree
Add a vertex $v_C$ to $G'$, and set demand $b'_{v_C}\gets\sum_{v\in V(C)}b_v$
each edge $(u,u')$ in $E$
Let $C$ and $C'$ be the connected components of $A$ containing $u$ and $u'$, respectively
$C\ne C'$
Add an edge between $v_C$ and $v_{C'}$ with weightaddedge $w(u,u')+d_{T_C}(u,r_C)+d_{T_{C'}}(u',r_{C'})+c(C)+c(C')$
Let $s'\gets v_{C_s}$, where $C_s$ is the component of $A$ containing $s$
Collapse parallel edges of $G'$ by only keeping the parallel edge with the smallest weight
Recursively call $\ref{esssp}(G',s',b',\al)$, obtaining an $\al$-approximate expected SSSP tree $T'$ of $G'$ recurse
Initialize $T\gets\emptyset$ The expected SSSP tree
each edge $(v,v')$ in $T'$start-T
Let $(u,u')\in E$ be the edge responsible for adding edge $(v,v')$ to $G'$
Add edge $(u,u')$ to $T$
each connected component $C$ of $A$
Remove an arbitrary edge from the (unique) cycle inside $C$, and add the resulting tree to $T$end-T

Throughout the section, fix a $(1+\e)$-approximate transshipment flow $f$ satisfying the given demand vector $b$ (with $b_v\ge0$ for all $v\ne s$). The key insight in our analysis is to focus on a random walk based on a slight modification of the transshipment flow $f$. Define a digraph $\orG=(V\cup\{\bot\},\orE,\orw)$ as follows: start from $G$ by bidirecting each edge of $E$, keeping the same weight in both directions. Then, add a new vertex $\bot$ and a single arc $(s,\bot)$ of weight $0$. Let $\overrightarrow C$ denote the diagonal matrix indexed by $\orE$, where diagonal entry $\overrightarrow C_{(u,v),(u,v)}$ is the cost of arc $(u,v)\in\orE$ under the weights $\orw$.

Next, define a flow $\orf$ on digraph $\orG$ as follows: for each edge $(u,v)\in E$, if $f_{(u,v)}>0$, then add $f_{(u,v)}$ flow to $\orf$ along the arc $(u,v)$, and if $f_{(u,v)}<0$, then add $-f_{(u,v)}$ flow to $\orf$ along the arc $(v,u)$. Lastly, add $-b_s$ flow to $\orf$ along arc $(s,\bot)$. Observe that this flow satisfies the demands $b_v$ for each $v\in V\sm s$, demand $0$ for $s$, and demand $b_s$ for $\bot$. Moreover, the cost $\1{\overrightarrow C\orf}$ of the flow $\orf$ equals $\1{Cf}$.

For each vertex $v\in V$, define $\In(v):=\{u\in V:\orf{(u,v)}>0\}$ as the neighbors of $v$ that send flow to $v$, and define $\Out(v):=\{u\in V:\orf{(v,u)}>0\}$ as the neighbors of $v$ that receive flow from $v$. For convenience, define $\FIn(v):=\sum_{u\in\In(v)}\orf(u,v)$ and $\FOut(v):=\sum_{u\in\Out(v)}\orf(v,u)$.

Define $b^+(v):=\max\{b_v,0\}$, so that $b^+(s)=0$ and $b^+(v)=b(v)$ for all $v\ne s$. Define $V^*\s V$ as the vertices $t$ for which there exists a $t\to\bot$ path using only arcs supported by the flow $\orf$ (that is, arcs $(u,v)$ with $\orf(u,v)>0$). We will only be considering vertices in $V^*$ for the rest of this section.

For all vertices $t\in V$, if $b(t)=b^+(t)>0$, then $t\in V^*$. Moreover, for all $v\in V^*\cup\{\bot\}$, we have $\In(v)\s V^*\cup\{\bot\}$ and $\Out(v)\in V^*\cup\{\bot\}$. In other words, the vertices in $V^*\cup\{\bot\}$ are separated from the vertices in $V\sm V^*$ by arcs supported by $\orf$.

For the first claim, let $R\s V\cup\{\bot\}$ be all vertices reachable from $t$ along arcs supported by $\orf$; we need to show that $\bot\in R$. Since there are no arcs in $\orf$ going out of $R$, by conservation of flow, we must have $\sum_{v\in R}b(v)\le0$. Since $t\in R$ and $b^+(t)=b(t)>0$, we have $\sum_{v\in R\sm t}b(v)<0$. But the only vertex in $V\cup\{\bot\}$ with negative demand is $\bot$, so it must hold that $\bot\in R$, as desired.

We now prove the second statement. If suffices to show that there are no arcs between $V^*\cup\{\bot\}$ and $V\sm V^*$. There cannot be an arc $(u,v)$ supported by $\orf$ with $u\notin V^*\cup\{\bot\}$ and $v\in V^*\cup\{\bot\}$, since that would mean $u$ can reach $\bot$ by first traveling to $v$. Suppose for contradiction that there is an arc from $V^*\cup\{\bot\}$ to $V\sm V^*$. Since there is no arc the other way, by conservation of flow, it must follow that $\sum_{v\notin V^*\cup\{\bot\}}b(v)<0$. But the only vertex $\bot$ with negative demand is $\bot$, so it cannot be that $\sum_{v\notin V^*\cup\{\bot\}}b(v)<0$, a contradiction.

For each vertex $t\in V^*$, consider the natural random walk from $t$ to $\bot$ in $\orG$, weighted by the flow $\orf$: start from $t$, and if the walk is currently at vertex $u\in V$, then travel to vertex $v\in\Out(v)$ with probability $\orf(u,v)/\FOut(u)$ (independent of all previous steps); stop when $\bot$ is reached. Let this random walk be the random variable $W_t$, which is guaranteed to stay within $V^*\cup\{\bot\}$ by vstar.

Given a walk $W$ in $\orG$, define $\len(W)$ to be the length of the walk under the weights $\orw$. In particular, $\len(W_t)$ is the length of the random walk $W_t$ from $t$ to $\bot$.

The claim below relates the transshipment cost to the expected lengths of the random walks $W_t$ for $t\in V^*$. This allows us to later charge our expected SSSP distances to the lengths of these concrete random walks, which are easier to work with than the transshipment flow itself.

We have

\[ \sum_{t\in V^*} b^+(t)\cd\E[\len(W_t)] \le \1{\overrightarrow C\orf} .  \]

In other words, if, for each $t\in V^*$, we sample a random walk from $t$ to $\bot$ and multiply its length by $ b^+(t)$, then the sum of the multiplied lengths over all $t$ is at most $\1{\overrightarrow C\orf}$ in expectation.
For each vertex $v\in V^*\cup\{\bot\}$, let $\freq_t(v)$ be the expected number of times $v$ appears in $W_t$. We first prove the following:
For all vertices $v\in V^*$, $\sum_{t\in V^*}b^+(t)\cd\E[\freq_t(v)]=\FOut(v)$.
For each $t\in V^*$, treat $\E[\freq_t(v)]$ as a function from $V^*\cup\{\bot\}$ to $\R_{\ge0}$, which satisfies the following equations:

\begin{align}
\E[\freq_t(t)] &= 1+\sum_{u\in \In(t)}\E[\freq_t(u)]\cd\f{\orf(u,t)}{\FOut(u)} \eqnl{e1} \\
\E[\freq_t(v)] &= \sum_{u\in \In(v)}\E[\freq_t(u)]\cd\f{\orf(u,v)}{\FOut(u)} \qquad \forall v\in (V^*\cup\{\bot\})\setminus t \eqnl{e2} \\
\E[\freq_t(\bot)] &= 1 \nonumber
\end{align}

Note that the equations are well-defined, since by vstar, all vertices $u\in\In(t)$ are in $V^*$ if $t\in V^*$.
Define the function $f(v):=\sum_{t\in V^*}b^+(v)\cd\E[\freq_t(v)]$, so our goal is to show that $f(v)=\FOut(v)$ for each $v\in V^*$. We sum <Ref> as follows:
for each $t$, multiply <Ref> by $b^+(t)$, and then sum over all $t$, obtaining

\begin{align}
f(v)&= b^+(v)+\sum_{u\in \In(t)}f(u)\cd\f{\orf(u,t)}{\FOut(u)} \qquad \forall v\in V^*\cup\{\bot\} \eqnl{e3} \\
f(\bot) &= \sum_{t\in V^*}b^+(t) \eqnl{e4}
\end{align}

We first show that the solution $f(v)=\FOut(v)$ for $v\in V^*$ and $f(\bot)= \sum_{t\in V^*}b^+(t)$ satisfies the above system of equations. <Ref> is clearly satisfied, and for e3, we have

\[ \FOut(v) = b^+(v)+\FIn(v)= b^+(v)+\sum_{u\in\In(v)}\orf(u,v)= b^+(v)+\sum_{u\in \In(v)}\FOut(u)\cd\f{\orf(u,v)}{\FOut(u)} .\]

We now claim that there is a unique solution to $f$, which is enough to prove the claim. Suppose there are two solutions $f$ and $f'$ that satisfy e3 and e4. Let $g$ be their difference: $g(v):=f(v)-f'(v)$ for all $v\in V^*$, which satisfies

\begin{align}
g(v)&= \sum_{u\in \In(t)}g(u)\cd\f{\orf(u,t)}{\FOut(u)}  \qquad \forall v\in V^*\cup\{\bot\} \eqnl{e5} \\
g(\bot) &= 0 \eqnl{e6}
\end{align}

We want to show that $g(v)=0$ for all $v\in V^*$. It suffices to show that $g(v)\le0$ for all $v\in V^*$, since <Ref> are satisfied with $g(v)$ replaced by $-g(v)$, so we would prove both $g(v)\le0$ and $-g(v)\le0$, which would give $g(v)=0$.

To show that $g(v)\le0$ for all $v\in V^*$, let $v^*:=\arg\max_{v\in V^*}g(v)$. By e5, $g(v^*)$ is a weighted average of $g(u)$ over vertices $u\in\In(v^*)$, so

\[ g(v^*) =  \sum_{u\in \In(v^*)}g(u)\cd\f{\orf(u,t)}{\FOut(u)} \le  \sum_{u\in \In(v^*)}g(v^*)\cd\f{\orf(u,t)}{\FOut(u)} = g(v^*) ,\]

so the inequality must be satisfied with equality, and $g(u)=g(v^*)$ for all $u\in\In(v^*)$. Continuing this argument, any vertex $u$ for which there exists a (possibly empty) $u\to v^*$ path in $\orf$ satisfies $g(u)=g(v^*)$. Define $R:=\{u\in V^*:\text{exists }u\to v^*\text{ path in }\orf\}$ as these vertices. Suppose for contradiction that $g(v^*)>0$, or equivalently, $g(u)>0$ for all $u\in R$.  Then, summing e5 over all $v\in R$, we obtain

\begin{align}
\sum_{v\in R}g(v) &= \sum_{v\in R}\sum_{u\in\In(v)}g(v)\cd\f{\orf(u,v)}{\Out(u)} \nonumber\\
&= \sum_{v\in R}\sum_{u\in\In(v) \cap R}g(v)\cd\f{\orf(u,v)}{\Out(u)} \nonumber\\
&= \sum_{u\in R}\lp \f{g(u)}{\Out(u)}\sum_{v\in R:u\in\In(v)}\orf(u,v) \rp \nonumber\\
&\stackrel{\mathclap{g(u)\ge0}}\le \ \, \sum_{u\in R}\lp \f{g(u)}{\Out(u)}\sum_{v\in V^*}\orf(u,v) \rp \eqnl{e7} \\
&= \sum_{u\in R}\lp \f{g(u)}{\Out(u)}\,\Out(v) \rp \nonumber\\
&= \sum_{u\in R}g(u).\nonumber
\end{align}

Since $v^*\in V^*$, there exists a $v^*\to\bot$ path in $\orf$. Since $v^*\in R$ and $\bot\notin R$, there exists an arc $(u',v')$ on the path with $u'\in R$ and $v'\notin R$ (and $\orf(u',v')>0$). Consider the inequality at e7. The inequality holds for each $u\in R$ in the outer summation, but for $u=u'$ in particular, we have $\sum_{v\in R:u\in\In(v)}\orf(u',v)<\sum_{v\in V^*}\orf(u,v)$. Since $g(u)>0$ by assumption, the inequality at e7 is actually strict, which gives the contradiction $\sum_{v\in R}g(v)<\sum_{u\in R}g(u)$. It follows that $g(v)\le g(v^*)\le0$ for all $v\in V^*$.

We now resume the proof of len. For all $t\in V^*$, by linearity of expectation,

\[ \E[\len(W_t)] = \sum_{u\in V^*}\freq_t(u)\cd\sum_{v\in\Out(u)}\f{\orf(u,v)}{\FOut(u)}\,\orw(u,v) . \]

For each $t\in V^*$, multiply the equation by $ b^+(t)$, and sum the equations, obtaining

\begin{align*}
\sum_{t\in V^*}   b^+(t)\cd\E[\len(W_t)] &= \sum_{t\in V^*} b^+(t) \lp \sum_{u\in V^*}\freq_t(u)\cd\sum_{v\in\Out(u)}\f{\orf(u,v)}{\FOut(u)}\,\orw(u,v) \rp \\
&= \sum_{u\in V^*}\lp\bigg(\sum_{t\in V^*} b^+(t)\cd\freq_t(u)\bigg) \sum_{v\in\Out(u)}\f{\orf(u,v)}{\FOut(u)}\,\orw(u,v) \rp \\
&\stackrel{\mathclap{\text{Sub.\,\ref{clm:out}}}}=\ \ \sum_{u\in V^*}\lp\FOut(u) \cd\sum_{v\in\Out(u)}\f{\orf(u,v)}{\FOut(u)}\,\orw(u,v) \rp \\
&= \sum_{u\in V^*}\sum_{v\in\Out(u)}{\orf(u,v)}\,\orw(u,v)\\
&\le \sum_{u\in V}\sum_{v\in\Out(u)}{\orf(u,v)}\,\orw(u,v)\\
&= \1{\overrightarrow C\orf} .
\end{align*}

This concludes len.

We remark that all our claims so far are in expectation, and therefore do not care about dependencies between the walks $W_t$ for different $t\in V^*$.

For each walk $W_t$, we can imagine sampling it as follows: for each vertex $u\in V^*$, sample an infinite sequence of arcs $(u,v)$ for $v\in\Out(u)$, each independent of the others and with probability $\orf(u,v)/\FOut(u)$; let these arcs be $e_1^u,e_2^u,\lds$. Once the arcs are sampled for each $u\in V^*$, the random walk $W_t$ is determined as follows: start at $t$, and if the walk is currently at $u\in V^*$, then travel along the next unused arc in the sequence $e_1^u,e_2^u,\lds$; in other words, if we have visited vertex $u$ on the walk $k$ times before the current visit, then travel along the arc $e^{u}_{k+1}$. It is easy to see that the distribution of this random walk is exactly $W_t$.

Let us first sample the set of sequences $e^u_1,e^u_2,\lds$ for each $u\in V^*$, and then determine the walks $W_t$ using this set of sequences for all $t$; note that the walks $W_t$ are heavily dependent on each other this way. Furthermore, observe that the arcs $\{e^u_1:u\in V^*\}$ are distributed the same way as the arcs in $\orA$ from <ref>.

Suppose we execute sample-edge of <ref>, so that each vertex $u$ has (independently) sampled a neighbor $v^u$ and added arc $(u,v^u)$ is added to $\orA$. Let $E$ be the event that in the infinite sequences $e^u_1,e^u_2,\lds$, we have $e^u_1=(u,v^u)$ for all $u\in V^*$.
Let $\opt=\opt_G(b)$ be the optimum transshipment cost with demands $b$ in $G$, and let $\opt'=\opt_{G'}(b')$ be the optimum transshipment cost in the recursive call at recurse. Then, by conditioning on $E$ in the random walks $W_t$, we obtain

\begin{gather} \sum_{t\in V^*} b^+(t)\cd\E[\len(W_t)\mid E] + 2\e\cd\opt \ge \E\left[\sum_{t\in V^*} ( b^+(t) \cd d_{T_C}(u,r_C) )\bigg\lvert E \right]+ \opt' \eqnl{bound-esssp} .\end{gather}

Consider the following “greedy” cycle-finding algorithm for walks:
given a walk $W$, travel along the walk in the forward direction, and whenever a cycle is found, immediately remove the cycle; output the set of all cycles removed. Let $\cyc(W_t)$ be the total length of all cycles removed, where length is measured by the weights $\orw$.
We first show that $\cyc(W_t)$ must be small compared to $\opt$, so that we can later charge to arcs in these cycles.

Given a walk $W$, let $\cyc(W)$ be the total length of cycles computed by the cycle-finding algorithm, where length is measured by the weights $\orw$. Recall that the transshipment flow $\orf$ is a $(1+\e)$-approximation of the optimum $\opt$ (that is, $\1{\overrightarrow C\orf}\le(1+\e)\opt$); then, we have

\[ \sum_{t\in V^*} b^+(t)\cd\E[\cyc(W_t)] \le \e\cd\opt .\]

For each walk $W_t$ sampled, remove the cycles computed by the algorithm to obtain another walk $W'_t$, still from $t$ to $\bot$.  Then, let $W^-_t$ be the walk $W'_t$ minus the last vertex $\bot$, whose new last vertex must be $s$. The flow obtained by sending $ b^+(t)$ flow along the walk $W^-_t$ for each $t\in V^*\sm s$ is a transshipment flow satisfying the demands $ b^+(t)$ for each $t\ne s$. Therefore,

\begin{align*}
\opt &\le \sum_{t\in V^*\sm s} b^+(t)\cd\E[\len(W^-_t)] \\
&= \sum_{t\in V^*\sm s} b^+(t)\cd\E[\len(W'_t)]\\
&\le \sum_{t\in V^*} b^+(t)\cd\E[\len(W'_t)] \\
&= \sum_{t\in V^*} b^+(t)\cd\E[\len(W_t) - \cyc(W_t)] \\
&\le \sum_{t\in V^*} b^+(t)\cd\E[\len(W_t)] - \sum_{t\in V^*} b^+(t)\cd\E[\cyc(W_t)] \\
&\stackrel{\mathclap{\text{Clm.\,}\ref{clm:len}}}\le \ \ \ \1{\overrightarrow C\orf} - \sum_{t\in V^*} b^+(t)\cd\E[\cyc(W_t)]\\
&\le(1+\e)\opt- \sum_{t\in V^*} b^+(t)\cd\E[\cyc(W_t)],
\end{align*}

and rearranging proves the claim.

Let us return to proving bound-esssp. We actually show that for any set of infinite sequences $\{e^u_1,e^u_2,\lds:u\in V^*\}$ satisfying event $E$ (that is, $e^u_1=(u,v^u)$ for all $u\in V^*$), we have

\begin{gather} \sum_{t\in V^*} b^+(t) \cd( \len(W_t)+ 2\cyc(W_t)) \ge  \sum_{t\in V^*} b^+(t) \cd d_{T_C}(u,r_C) + \opt'. \eqnl{toshow} \end{gather}

Assuming toshow, taking expectations and then applying cycle gives

\begin{align*}
\sum_{t\in V^*} b^+(t)\cd\E[\len(W_t)\mid E] + 2\e\cd\opt &\ge\sum_{t\in V^*} b^+(t) \cd\E[ \len(W_t)\mid E]+2\sum_{t\in V^*} b^+(t)\cd\E[\cyc(W_t)\mid E] \\&=\sum_{t\in V^*} b^+(t) \cd(\E[ \len(W_t)\mid E]+2 \E[\cyc(W_t)\mid E]) \\&\stackrel{\eqn{toshow}}\ge\E[  b^+(t) \cd d_{T_C}(u,r_C)\mid E ] + \opt' \eqnl{toshow} ,
\end{align*}

as desired.

For the remainder of the proof, we will show toshow given any set of arbitrary infinite sequences $\{e^u_1,e^u_2,\lds:u\in V^*\}$ satisfying $e^u_1=(u,v^u)$ for all $u\in V^*$. In particular, now that we have fixed these infinite sequences, all randomness goes away, so there are no more probabilistic arguments for the remainder of the proof.

For each $t$, we can view the random walk $W_t$ as follows: for each vertex $u\in V^*$, the first time the walk reaches $u$, it must travel along arc $(u,v^u)$ in $\orA$, and any time after that, it can choose an arbitrary arc in $\Out(u)$.

Let $C$ be a connected component of $A$ in <ref> containing a vertex $u$. If the walk $W$ contains $u$, then it contains every arc on the (unique, possibly empty) path from $u$ to the (unique) cycle in $C$ (defined as the path from $u$ to the closest vertex on that cycle).
Consider the first time the walk visits vertex $u$. Then, the walk must traverse the arc $(u,v^u)=e^u_1$, which is the first arc along the path from $u$ to the cycle in $C$. We can then repeat the argument with $u$ replaced by $v^u$, considering the first time the walk visits vertex $v^u$. Continuing this argument until we arrive at a vertex on the cycle proves the claim.

Let $C$ be a connected component of $A$ in <ref> containing a vertex $u$. Suppose a walk $W$ contains an arc $(u,v)$ with $v\ne v^u$. Then, the cycles output by the greedy cycle-finding algorithm contains  (1) every arc along the (unique, possibly empty) path from $u$ to the (unique) cycle in $C$, and (2) every arc in the (unique) cycle in $C$ in the direction given by $\orA$.
For this proof only, imagine that the walk visits one vertex per unit of time, so we say that the walk reaches a vertex $v$ at time $i$ if $v$ is the $i$'th vertex of the walk.

We first prove  statement (2). Consider the first time $i$ that the walk reaches any vertex in $C$, which must occur since vertex $u$ in $C$ is reached eventually. Then, right after time $i$, the walk will travel along $\orA$ towards the unique cycle in $C$, and then travel along $C$ in the direction given by $\orA$. The greedy cycle-finding algorithm then removes that cycle, proving statement (2).

We now prove  statement (1). If $u$ is inside the cycle of $C$, then the path is empty and there is nothing to prove. Otherwise, let $(u',v')$ be an arbitrary arc along this (nonempty) path. We first show that $(u',v')$ is traveled at least once in the walk. For this proof only, for two vertices $u,v$ in $C$ (possibly $u=v$), let $P(u,v)$ be the (possibly empty) path in $\orA$ from $u$ to $v$ (inclusive), which will always exist and be unique when we use it. Consider the first time $i$ that the walk reaches any vertex $v$ in $P(u,u')$ (possibly $u$ or $u'$). Since the walk visits vertex $u$ at least once, this `first time $i$' must occur. Then, right after time $i$, the walk must travel along $P(v,u')$, and then along arc $(u',v')$. Let the walk reach vertex $u'$ at time $i'$ (so it reaches $v'$ at time $i'+1$).

[above] at (-5,0) $u$;
[above] at (-4,0) $x$;
[above] at (-2,0) $v$;
[above] at (-1,0) $y$;
[above] at (1,0) $u'$;
[above] at (2,0) $v'$;

[below] at (-4,0) $j$;
[below] at (-2,0) $i$;
[below] at (-1,0) $j'$;
[below] at (1,0) $i'$;
[below] at (2,0) $i'+1$;

every node = [scale=.4,fill,circle]

(v1) at (-6,0) ;
(v2) at (-5,0) ;
(v3) at (-4,0) ;
(v4) at (-3,0) ;
(v5) at (-2,0) ;
(v6) at (-1,0) ;
(v7) at (0,0) ;
(v8) at (1,0) ;
(v9) at (3,0) ;
(v15) at (2,0) ;
[->,line width=1.5]  (v3) edge (v4);
[->,line width=1.5]  (v1) edge (v2);
[->,line width=1.5]  (v2) edge (v3);
[->,line width=1.5]  (v4) edge (v5);
[->,line width=1.5]  (v5) edge (v6);
[->,line width=1.5]  (v6) edge (v7);
[->,line width=1.5]  (v7) edge (v8);
(v10) at (3.5,1.732/2) ;
(v11) at (4.5,1.732/2) ;
(v12) at (5,0) ;
(v13) at (4.5,-1.732/2) ;
(v14) at (3.5,-1.732/2) ;
[->,line width=1.5] (v9) edge (v10);
[->,line width=1.5] (v10) edge (v11);
[->,line width=1.5] (v11) edge (v12);
[->,line width=1.5] (v12) edge (v13);
[->,line width=1.5] (v13) edge (v14);
[->,line width=1.5] (v14) edge (v9);
[->,line width=1.5] (v8) edge (v15);
[->,line width=1.5] (v15) edge (v9);
[->,line width=2](4.0002,-1.5201) – (3.9323,-1.7793);
[->,line width=2](2.7784,-3.0134) – (2.5562,-2.9517);
[->,line width=2](0.6372,-1.9582) – (0.4521,-1.9767);
[->,line width=2](-2.1458,-1.6435) – (-2.2939,-1.5201);
[->,line width=2](-1.4053,-1.1252) – (-1.4176,-0.9277);
[dashed,line width=2] plot[smooth, tension=.7] coordinates (-2,-4) (-1.5383,-2.9104) (-2.7706,-1.6285) (v5);

[red,dashed,line width=2] plot[smooth, tension=.7] coordinates (v15) (4,-1) (3,-3) (1,-2) (-1.0017,-2.0856) (-1.429,-0.5154) (v6);

[green,dotted,line width=2] plot[smooth, tension=.7] coordinates (v15) (4,-1) (3,-3) (1,-2) (-1.4091,-2.0657) (v3);
[dashed,line width=2](v5) – (v6);
[red,dashed,line width=2](v6) – (v15);
[green,dotted,line width=2](v6) – (v15);
[green,dotted,line width=2](v3) – (v6);
[->,line width=2](-1.8619,-2.5321) – (-2.0285,-2.4148);
[->,line width=2](-2.5746,-0.8815) – (-2.4389,-0.6716);
(v16) at (-4,1) ;
(v17) at (-1,1) ;
at (0,1) ;
[->,line width=1.5](v16) – (v4);
[->,line width=1.5](v17) – (v7) ;
[->,line width=1.5](0,1) – (v7);

The two cases of statement (1) from charge. The curved paths that do not align with the horizontal edges are arbitrary paths in other parts of the graph. The red dashed line marks the cycle for the first case, and the green dotted line marks the cycle for the second case.

We now show that this first traversal of arc $(u',v')$ at time $i'$ is indeed added to a cycle by the greedy algorithm. Define $v$ as before, and consider the next time $j$ the walk reaches any vertex $x$ in $P(u,v)$.  Then, right after time $j$, the walk must travel along $P(x,v)$. Since the walk contains an arc $(u,v)$ with $v\ne v^u$, vertex $u$ is reached at least twice, so this `next time $j$' must occur (we need at least twice in case $v=u$). By time $j$, one of two things can happen (see Figure <ref>):
The walk returns to some vertex $y$ in $P(v,u')$ before time $j$ (but after time $i'+1$). Let time $j'\in(i'+1,j)$ be the first such return, and let $y$ be the vertex returned to. Before time $j'$, all vertices in $P(v,u')$ were visited exactly once, so either all arcs in $P(v,v')$ were added to the same cycle before time $j$, or none of them were added to any cycle before time $j$. In the former case, the path $P(v,v')$ includes arc $(u',v')$, so we are done. In the latter case, we obtain the cycle consisting of the path $P(y,v')$, followed by the (remaining) arcs in the walk from time $i'+1$ to time $j'$. The greedy algorithm then adds this cycle, which contains arc $(u',v')$.
The walk does not return to any vertex in $P(v,u')$ after time $i'+1$ and before time $j$. By the same argument as the case above, either all arcs in $P(v,v')$ were added to the same cycle before time $j$, or none were added to any cycle before time $j$. Again, in the former case, we are done, so suppose the latter. Right after time $j$, the walk travels along $P(x,v)$, and no vertex on $P(x,v)$ except possibly $v$ was visited before time $j$. Therefore, the next time the walk encloses a cycle (after time $j$) is when it travels along $P(x,v)$ and reaches $v$. At this point, all arcs in $P(x,v')$ (including arc $(u',v')$) are added into the cycle that begins and ends at $v$, so we are done.
Therefore, in both cases, we are done.

For each vertex $t\in V^*$, let $C$ be the component in $A$ containing $t$. We have

\[ \len(W_t) + 2\cyc(W_t) \ge d_{T_C}(t,r_C) + d_{G'}(s,r_C) .\]

Define a subwalk of $W$ to be a contiguous subsequence of the walk when it is viewed as a sequence of vertices.
We partition the walk $W$ into subwalks as follows. Start with the first vertex $t$ of the walk, and let $C$ be the component of $A$ containing $t$. Consider the last vertex $v$ of the walk also inside $C$. If $v=s$, then we are done; otherwise, break of the subwalk from the beginning of the walk to the (last occurrence of) vertex $v$ in the walk, and recursively apply the procedure on the remaining vertices of the walk.

Let the subwalks be $W_1,W_2,\lds,W_k$ in that order, and for $i\in[k]$, let $u_i$ and $v_i$ be the first and last vertex of $W_i$, and let $C_i$ be the component of $A$ containing both $u_i$ and $v_i$. By construction, all components $C_i$ are distinct. For each $i\in[k-1]$, the arc $(v_i,u_{i+1})$ in $\orf$ is responsible for adding an arc $(v_{C_i},v_{C_{i+1}})$ in addedge of weight $w(v_i,u_{i+1})+d_{T_{C_i}}(v_i,r_{C_i})+d_{T_{C_{i+1}}}(u_{i+1},r_{C_{i+1}})+c(C_i)+c(C_{i+1})$; let this arc be $(v'_i,u'_{i+1})$.
Consider the path from $r_C$ to $s'$ in $G'$ consisting of the edges $(v'_i,u'_{i+1})$ for $i\in[k-1]$. It suffices to show that this path has length at most $\len(W_t)+2\cyc(W_t)-d_{T_C}(t,r_C)$; the distance $d_{G'}(s,r_C)$ can only be smaller. In other words, we want to show that

\begin{align} \sum_{i=1}^{k-1} & \lp w(v_i,u_{i+1})+d_{T_{C_i}}(v_i,r_{C_i})+d_{T_{C_{i+1}}}(u_{i+1},r_{C_{i+1}})+c(C_i)+c(C_{i+1})\rp \nonumber\\
&\le \len(W_t)+2\cyc(W_t)-d_{T_C}(t,r_C).\eqnl{bound-dist}\end{align}

For each $i\in[k-1]$, the distance $d_{T_{C_i}}(v_i,r_{C_i})$ equals the length of the (possibly empty) path $P_i$ in $C_i$ from $v_i$ to the (closest vertex on the unique) cycle in $C_i$. Since $u_{i+1}$ is not in $C_i$, we have $u_{i+1} \ne v_1^{u_{i+1}}$, so by charge, every
arc in $P_i$ is added to some cycle by the greedy cycle-finding algorithm. Moreover, by charge, every edge in the (unique) cycle in $C_i$ is also added to some cycle. All such arcs mentioned are distinct, so we obtain

\[ \sum_{i=1}^{k-1} \lp d_{T_{C_i}}(v_i,r_{C_i}) +c(C_i)\rp \le \cyc(W_t) .\]

For the distances $d_{T_{C_{i+1}}}(u_{i+1},r_{C_{i+1}})$ for $i\in[k-1]$, as well as the distance $d_{T_{C_{1}}}(u_{1},r_{C_{1}})=d_{T_C}(t,r_C)$, we charge them to the walk $W_t$ directly. For each $i\in[k]$, since the walk contains vertex $u_{i}$ in $C_{i}$, by charge2, it contains all arcs on the path from $u_{i}$ to the cycle in $C_{i}$, whose weights sum to exactly  $d_{T_{C_{i}}}(u_{i},r_{C_{i}})$. Finally, we also charge the edge weights $w(v_i,u_{i+1})$ to the walk $W_t$, since the walk contains them by construction, and they are edge-disjoint from each other and all arcs in any $C_i$. Thus,

\begin{align*}
\sum_{i=1}^{k-1}&\lp w(v_i,u_{i+1})+d_{T_{C_i}}(v_i,r_{C_i})+d_{T_{C_{i+1}}}(u_{i+1},r_{C_{i+1}})+c(C_i)+c(C_{i+1})\rp \\&\le 2\sum_{i=1}^{k-1} \lp d_{T_{C_i}}(v_i,r_{C_i}) +c(C_i)\rp +\sum_{i=1}^{k-1}\lp w(v_i,u_{i+1})+d_{T_{C_{i+1}}}(u_{i+1},r_{C_{i+1}})\rp
\\&\le 2\sum_{i=1}^{k-1} \lp d_{T_{C_i}}(v_i,r_{C_i}) +c(C_i)\rp + \sum_{i=1}^{k-1}w(v_i,u_{i+1})+ \sum_{i=1}^{k}d_{T_{C_{i}}}(u_{i},r_{C_{i}})-d_{T_C}(t,r_C)
\\&\le 2\cyc(W_t) + \len(W_t)-d_{T_C}(t,r_C),
\end{align*}

proving bound-dist.
We now resume the proof of bound-esssp. Multiplying the inequality by $ b^+(t)$ for each $t$ and summing over all $t$ gives

\begin{gather} \sum_{t\in V^*} b^+(t)\cd  \len(W_t) + 2\cyc(W_t) \ge \sum_{t\in V^*} b^+(t)\cd (d_{T_C}(t,r_C) + d_{G'}(s,r_C) ) .\eqnl{sum-over-t}\end{gather}

Consider routing, for each component $C$ of $A$ and vertex $t$ in $C$, $ b^+(t)$ amount of flow along the shortest path from $s'$ to $v_C$ in $G'$. By construction of the demand vector $b'$, this is a transshipment flow that satisfies demands $b'$. Therefore, the optimum transshipment cost $\opt'$ can only be smaller (in fact, it is equal), and we obtain

\[ \opt' \le \sum_{t\in V^*} b^+(t)\cd d_{G'}(s,r_C) .\]

Together with sum-over-t, this concludes toshow, and hence bound-esssp.

Over the randomness of <ref> (in particular, the random choices on sample-edge),

\[ \E\lb \sum_{t\in V^*} b^+(t) \cd d_{T_C}(u,r_C) + \opt'  \rb \le \1{\overrightarrow C\orf} +2\e\cd\opt.\]

We apply bound-esssp by taking the expectation of bound-esssp over the randomness on sample-edge, which effectively removes the conditioning by $E$, and obtain

\[ \sum_{t\in V^*} b^+(t)\cd\E[\len(W_t)] + 2\e\cd\opt \ge \E[ b^+(t) \cd d_{T_C}(u,r_C) +\opt'] .\]

This, along with $\sum_{t\in V^*} b^+(t)\cd\E[\len(W_t)] \le \1{\overrightarrow C\orf} $ from len, finishes the proof.

Define $T'$ and $T$ as in <ref>. For each component $C$ of $A$ and each vertex $v$ in $C$, we have $d_T(s,v) \le d_{T'}(s',v_C)+d_{T_C}(t,r_C)$.

Follows easily by construction (lines <ref> to <ref>), so proof is omitted.
Over the entire randomness of <ref> (including the recursion at recurse), we have

\[ \E\lb\sum_{t\in V} b^+(t)\cd d_T(s,t)\rb \le \al(1+3\e)\opt .\]

By vstar, we have $b^+(t)=0$ for all $t\in V\sm V^*$, so it suffices to prove

\[ \E\lb\sum_{t\in \textcolor{blue}{V^*}} b^+(t)\cd d_T(s,t)\rb \le \al(1+3\e)\opt .\]

By recursion, we have the guarantee

\[ \E\lb \sum_{C:v_C\ne s'} b'_{v_C} \cd d_{T'}(s',v_C)\rb\le \al \opt .\]

For each vertex $t$, let $C_t$ be the component of $A$ containing $t$. We have

\begin{align*}
\E\lb \sum_{t\in V^*} b^+(t) \cd d_T(s,v) \rb &\stackrel{\textup{Clm.\,}\ref{clm:T-as-good}}\le \E\lb \sum_{t\in V^*} \lp b^+(t)\cd d_{T'}(s',v_{C_t}) + d_{T_{C_t}}(t,r_{C_t}) \rp \rb
\\& = \E\lb \sum_{t\in V^*}  b^+(t)\cd d_{T'}(s',v_{C_t}) \rb + \E\lb \sum_{t\in V^*} b^+(t)\cd d_{T_{C_t}}(t,r_{C_t})\rb
\\&= \E\lb \sum_{C:v_C\ne s'} b'_{v_C} \cd d_{T'}(s',v_C)\rb+ \E\lb \sum_{t\in V^*} b^+(t)\cd d_{T_{C_t}}(t,r_{C_t})\rb
\\&\le \al\E[\opt'] +  \E\lb \sum_{t\in V^*} b^+(t)\cd d_{T_{C_t}}(t,r_{C_t})\rb
\\&\le \al\lp \E[ \opt'] +  \E\lb \sum_{t\in V^*} b^+(t)\cd d_{T_{C_t}}(t,r_{C_t})\rb  \rp
\\&\stackrel{\textup{Cor.\,}\ref{cor:bound-by-f}}\le \al\lp \1{\overrightarrow C\orf}+2\e\cd\opt\rp
\\&\le \al((1+\e)\opt + 2\e\cd\opt)
\\&=\al(1+3\e)\opt,
\end{align*}

where the last inequality uses that $\orf$ is a $(1+\e)$-approximate transshipment solution.

§.§ Parallelizing the Expected SSSP Algorithm

For each component $C$, select an arbitrary vertex $u_C$ in the (unique) cycle of $C$, and let $U\s V$ be the selected vertices.
Let $z:U\to\R_{\ge0}$ be a function  satisfying $\diam_{G}(C)\le z(u_C)$ for all components $C$. Define the graph $\ol{G'}=(U,\ol{E'})$ as follows: for each pair of distinct components $C,C'$, and for each pair $u\in C,u'\in C'$ of vertices, add an edge $(u_C,u_{C'})$ to $\ol{E'}$ of weight

\[ w(u,u')+d_{T_C}(u,r_C)+d_{T_{C'}}(u',r_{C'})+c(C)+c(C')  .\]

Collapse parallel edges of $\ol{G'}$ by only keeping the parallel edge with the smallest weight.

Let $C>0$ be any constant, and suppose we are given an $\el_1$-embedding $\{x_v\in \R^d:v\in V\}$ of $G$ with distortion $C\log^Cn$ for some $d\le C\logn$. Then, there exists a constant $C'>0$ and an algorithm that computes, in $\tO(m)$ work and $\pl(n)$ time, an $\el_1$-embedding for $\ol{G'}$ with distortion $C'\log^{C'}n$ into at most $C'\logn$ dimensions.

The graph $\ol{G'}$ is actually a complete graph, so we cannot compute it efficiently if $|V'|$ is large.
Let $G$ and $\ol{G'}$ be defined as in embed-G. Let $C>0$ be any constant, and suppose we are given an $\el_1$-embedding $\{x_v\in \R^d:v\in V\}$ of $G$ with distortion $C\log^Cn$ for some $d\le C\logn$. There exists a constant $C''>0$ and an algorithm that computes, in $\tO(m)$ work and $\pl(n)$ time, a graph $\tilde G'=(U,\tilde E')$ such that
For each pair of distinct components $C,C'$ and each edge $(u,u')\in E$ with $u\in C$ and $u'\in C'$, the edge $(u,u')$ exists in $\tilde E'$ and has weight

\[ \min\{w(u,u')+d_{T_C}(u,r_C)+d_{T_{C'}}(u',r_{C'}), \norm{x_u-x_{u'}}_1\}+z(u)+z(u') ;\]

Any $\el_1$-embedding for $G$ of distortion $D$ is an $\el_1$-embedding for $\tilde G'$ of distortion at most $(C''\log^{C''} n)D$.

In this section, we parallelize the algorithm <ref> by removing its sequential recursive calls which would, if left unchecked, blow up the parallel running time of the algorithm. This is because every time <ref> calls itself, it requires a transshipment flow of a new recursive graph, which in turn requires an $\el_1$-embedding of it.

Our solution is to avoid computing an $\el_1$-embedding (from scratch) at each step of the recursion. With an $\el_1$-embedding at hand for a given recursive graph, we can compute the transshipment flow without any recursion by invoking l1. Naively, one might hope that a subset of the original vectors of the $\el_1$-embedding automatically produces an $\el_1$-embedding for the recursive graph instance. This is not true in general, but we can force it to happen at a cost: we add a set of virtual edges to the recursive graph instance (which may change its metric) that come from a spanner of the $\el_1$-metric on a subset of the original vectors. These edges may not exist in the original graph $G$, so the shortest path tree $T$ of that instance may include edges that do not correspond to edges in the original graph. Unraveling the recursion, the final tree $T$ may also contain virtual edges not originally in $G$. However, we ensure that these virtual edges do not change the metric of the original graph $G$. Hence, while the tree $T$ is not a spanning SSSP tree, it still fulfills its purpose when it is called in the algorithm <ref> of sample-tree. (If a spanning SSSP tree is explicitly required for the final output of the original graph instance, then <ref> can be called in <ref> once on the initial recursion loop, and <ref> called on every recursive instance of <ref> afterwards.)

Let $G=(V,E)$ be a connected graph with $n$ vertices and $m$ edges with aspect ratio $\poly(n)$, let $\e>0$ be a parameter.
Given graph $G$, a source $s\in V$, and an $\el_1$-embedding of it into $O(\logn)$ dimensions with distortion $\pl(n)$, we can compute, in
$\tO(m)$ work and $\pl(n)$ time, a set $E^+$ of virtual edges supported on $V$ and a tree $T\s E\cup E^+$ such that
For all edges $(u,v)\in E^+$, $w(u,v) \ge d_G(u,V)$, i.e., the edges $E^+$ do not change the metric of $G$
$T$ is a $(1+\e)$-approximate expected $s$-SSSP tree on $G\cup E^+$

We now present the recursive algorithm that proves esssp-rec. Let the original graph be $G_0$ and the current recursive instance be $G$, and let $n$ and $m$ always indicate the number of vertices and edges of the original graph $G_0$. We highlight in blue all modifications of <ref> that we make.

esssp-rec<ref>($G=(V,E),\BLUE{\{y_v\in\R^{k}:v\in V\}},s,b,(1+3\e)\al$)
Global variables: $G_0=(V_0,E_0)$ is the original input graph; $\{x_v\in\R^{O(\logn)}:v\in V\}$ is an initial $\el_1$-embedding of $G_0$ with distortion $D=\pl(n)$ given as input

Assumption: $k=O(\log^2n)$ and $\{y_v\}$ satisfies $\f1{8kD}d_G(u,v)\le\1{y_u-y_v} \le (D+6)\cd d_G(u,v)$ for all $u,v\in V$; demand vector $b$ satisfies $b_s>0$ and $b_t\le0$ for all $t\in V\sm s$
[1]
$\{8kD\cd y_v\}$ is an $\el_1$-embedding of $G$ with distortion $8kD(D+6)=\pl(n)$. Apply dimension reduction to obtain an $\el_1$-embedding of $G$ into $O(\logn)$ dimensions instead of $O(\log^2n$), with a slightly worse but still $\pl(n)$ distortion (see proof of embed-seq). Using it and l1, compute a $(1+\e$)-approximate transshipment $f$ on $G$ with demand vector $b$
Initialize the digraph $\orA\gets\emptyset$
Every vertex $u\in V\sm s$ with $\In(u)\ne\emptyset$ independently samples a random neighbor $v\in\Out(u)$ with probability $\orf(u,v)/\FOut(u)$ and adds arc $(u,v)$ to $\orA$ sample2
Add a self-loop $(s,s)$ of zero weight to $\orA$
Let $A$ be the undirected version of $\orA$
Initialize $G'\gets(\emptyset,\emptyset)$ as an empty undirected graph Graph to be recursed on, with $\le n/2$ vertices
Initialize $b'$ as an empty vector Demands to be recursed on
each connected component $C$ of $A$
$c(C)\gets$ total weight of edges in the (unique) cycle in $C$ (possibly the self-loop $(s,s)$)
Let $T_C$ be the graph $C$ with its (unique) cycle contracted into a single vertex $r_C$ $T_C$ is a tree
Let $v_C\in V$ be an arbitrary vertex on the cycle in $C$
Add the vertex $v_C$ to $G'$, and set demand $b'_{v_C}\gets\sum_{v\in V(C)}b_v$
each edge $(u,u')$ in $E$
Let $C$ and $C'$ be the connected components of $A$ containing $u$ and $u'$, respectively
$C\ne C'$
Add an edge between $v_C$ and $v_{C'}$ with weight $w(u,u')+d_{T_C}(u,r_C)+d_{T_{C'}}(u',r_{C'})+c(C)+c(C')$ addedge2
Note that $s=v_{C_s}$, where $C_s$ is the component of $A$ containing $s$
Collapse parallel edges of $G'$ by only keeping the parallel edge with the smallest weight G'
Call l1 on the original $\el_1$-embedding vectors $\{x_v:v\in V'\}$, returning a set of vectors $\{y'_v\in\R^{O(\log^2n)}:v\in V'\}$ that satisfy yv
Call Eplus on $\{y'_v:v\in V'\}$, returning a set $E^+$ of edges supported on $V'$ that satisfy both conditions of Eplus Eplus
Recursively call $\ref{esssp-rec}(\textcolor{blue}{G'\cup E^+,\{y'_v:v\in V'\},s},b',\al)$, obtaining an $\al$-approximate expected SSSP tree $T'$ of $G'\cup E^+$ recurse2
Initialize $T\gets\emptyset$ The expected SSSP tree
each edge $(v,v')$ in $T'\,\BLUE{\cap \,E}$start-T2
Let $(u,u')\in E$ be the edge responsible for adding edge $(v,v')$ to $G'$
Add edge $(u,u')$ to $T$

each edge $(v,v')$ in $T'\sm E$
Let $(u,u')\in E$ be the edge responsible for adding edge $(v,v')$ to $G'$
Let $C$ and $C'$ be the connected components of $A$ containing $u$ and $u'$, respectively
Add edge $(v,v')$ to $T$ with weight $w(v,v')-c(C)-c(C')$ These edges are not in the original edge set $E_0$ undo

each connected component $C$ of $A$
Remove an arbitrary edge from the (unique) cycle inside $C$, and add the resulting tree to $T$end-T2

One notable difference is that we always enforce the recursive vertex set $V'$ to be a subset of the current vertex set $V$. This allows us to compare the metric of the new graph $G'$ to the current graph $G$ in a more direct way.

Each edge $(v_C,v_{C'})$ added on addedge2 has weight at least $d_G(v_C,v_{C'})$.
Let $(u,u')\in E$ be the edge responsible for adding the edge $(v_C,v_{C'})$. We construct a path in $G$ from $v_C$ to $v_{C'}$ whose distance is at most $w(u,u')+d_{T_C}(u,r_C)+d_{T_{C'}}(u',r_{C'})+c(C)+c(C')$. By construction of component $C$, there is a path inside $C$ from $v_C$ to $u$ of length at most $c(C)+d_{T_C}(u,r_C)$. Similarly, there is a path inside $C'$ from $u'$ to $v_{C'}$ of length at most $c(C')+d_{T_{C'}}(u',r_{C'})$. Adding the edge $(u,u')$ completes the path from $v_C$ to $v_{C'}$.

Our first claim is that distances cannot shrink:
For any two vertices $u,v\in V$, $d_{G'}(u,v) \ge d_{G}(u,v)$.
It suffices to show that $w_{G'\cup E^+}(v_C,v_{C'})\ge d_G(v_C,v_{C'})$ for all edges $(v_C,v_{C'})\in E'$.

For each edge $(v_C,v_{C'})\in E'$, there is some edge $(u,u')\in E$ responsible for the addition of this edge on addedge2. The edge $(v_C,v_{C'})$ has weight $w(u,u')+d_{T_C}(u,r_C)+d_{T_{C'}}(u',r_{C'})+c(C)+c(C')$, where $C$ and $C'$ are the connected components of $A$ containing $u$ and $u'$, respectively. By definition, $u=v_C$ and $u'=v_{C'}$, where $v_C$ and $v_{C'}$ are arbitrary vertices on the cycle in $C$ and $C'$, respectively. By the structure of the component $C$, there is a path from $v_C$ to $u$ in $C$ of length at most $c(C)+d_{T_C}(u,r_C)$. Similarly, there is a path from $v_{C'}$ to $u'$ in $C'$ of length at most $c(C')+d_{T_{C'}}(u',r_{C'})$. Together with the edge $(u,u')$, this gives a path from $v_C$ to $v_{C'}$ of length at most

\[ c(C)+d_{T_C}(u,r_C) + w(u,u') + c(C')+d_{T_{C'}}(u',r_{C'}) = w_{G'}(v_C,v_{C'}) ,\]

as promised.

For any two vertices $u,v\in V$, $d_{G}(u,v)\ge d_{G_0}(u,v)$.
We induct along the recursive structure of the algorithm <ref>. Consider a recursive instance $G$; we need to show that for the next recursive call on $G'\cup E^+$, we still have $d_{G'\cup E^+}(u,v)\ge d_{G_0}(u,v)$ for all $v\in V$. It suffices to show that $w(v_C,v_{C'})\ge d_{G_0}(v_C,v_{C'})$ for all edges $(v_C,v_{C'})\in E'\cup E^+$. For $(u,v)\in E'$, by stretch, $d_{G'}(u,v)\ge d_G(u,v)$, which is at least $d_{G_0}(u,v)$ by induction. Since the edges $E^+$ do not change the metric, we have $w(v_C,v_{C'})\ge d_{G_0}(v_C,v_{C'})$ for all $(v_C,v_{C'})\in E^+$.

\[ d_G(v_C,v_{C'})-c(C)-c(C') \le d_{G'}(v_C,v_{C'}) \le d_G(v_C,v_{C'})+c(C)+c(C') .\]

Let $(u,u')\in E$ with $u\in C$ and $u'\in C'$ be responsible for the addition of edge $(v_C,v_{C'})$ into $E'$. Then,

After updating the $y(\cd)$ values in y

\[ y(v_C)+y(v_{C'}) \le w_{G'}(v_C,v_{C'}) .\]

We apply induction on the recursive structure of <ref>.
Let $(u,u')\in E$ with $u\in C$ and $u'\in C'$ be responsible for the addition of edge $(v_C,v_{C'})$ into $E'$. Let $y'(v_C)$ and $y'(v_{C'})$ be the $y(\cd)$ values after y on the previous iteration. Since  By induction, we have

\[ y'(u) + y'(u') \le  .\]
By induction on the edge $(u,u')\in E$ added in the previous recursion level,

\[  .\]

\begin{align*}
c(C) + c(C') \le c(C) + d_{T_C}(u,r_C) + w(u,u') + d_{T_{C'}}(u',r_{C'}) + c(C') = w
\end{align*}

Given the vectors $\{x_v\}$, we can compute, in $\tO(m)$ work and $\pl(n)$ time, a set of vectors $\{y_v\in\R^{O(\log^2n)}:v\in V'\}$ such that w.h.p., for all vertices $v_C,v_{C'}\in V'$,

\begin{align}
\1{x_{v_C}-x_{v_{C'}}} + 2(c(C)+c(C')) \le \1{y_{v_C}-y_{v_{C'}}}\le \1{x_{v_C}-x_{v_{C'}}} + 6(c(C)+c(C')) . \eqnl{yv}
\end{align}

We introduce $O(\log^2n)$ new coordinates, indexed by $(i,j)\in\Z\times[s]$. For a given component $C$ of $A$ at this instance, initialize $y_{v_C}=x_{v_C}$ without the new coordinates. Let $i\in\Z$ be the integer $i$ such that $c(C) \in [2^i,2^{i+1})$, which can take one of $O(\logn)$ values in $\Z$. For each $j\in[s]$, let the coordinate at index $(i,j)$ take value $\pm5\cd2^i/s$, each with probability $1/2$. This concludes the construction of $y_{v_C}$.

Fix vertices $v_C,v_{C'}\in V'$. Let $i,i'$ be the integers such that $c(C)\in[2^i,2^{i+1})$ and $c(C')\in[2^{i'},2^{i'+1})$. If $i\ne i'$, then by construction, the $\el_1$ distance incurred by the additional $O(\log^2n)$ coordinates is exactly $5\cd2^i+5\cd2^{i'}$. Moreover, by the input guarantee of $\{x_v:v\in V\}$,

\[ d_{G_0}(v_C,v_{C'})\le\1{x_{v_C}-x_{v_{C'}}}\le D\cd d_G(v_C,v_{C'}).\]

\begin{align}
\1{x_{v_C}-x_{v_{C'}}}+2\cd( c(C)+c(C')) &\le \1{x_{v_C}-x_{v_{C'}}}+ 2\cd2^{i+1}+2\cd2^{i'+1} \nonumber
\\&\le \1{x_{v_C}-x_{v_{C'}}}+ 5\cd2^i+5\cd2^{i'} \nonumber
\\&= \1{y_{v_C}-y_{v_{C'}}} \eqnl{dGv}
\\&\le \1{x_{v_C}-x_{v_{C'}}}+ 6\cd2^i+6\cd2^{i'} \nonumber
\\&\le \1{x_{v_C}-x_{v_{C'}}}+ 6\cd( c(C)+c(C')), \nonumber
\end{align}

as promised. Now suppose that $i=i'$. Then, for each of the $s$ coordinates $(i,j)$, there is a $1/2$ probability of contributing $0$ to $\1{y_{v_C}-y_{v_{C'}}}$, and a $1/2$ probability of contributing $6\cd2^i/s$. Since $s=O(\logn)$, by a simple Chernoff bound, the probability that the total contribution of these $s$ coordinates is in $[4\cd2^i/s,6\cd2^i/s]$ is at least $1-1/\poly(n)$. A similar bound to dGv proves the claim.

Given vectors $\{y_v\in\R^{O(\log^2n)}\}$ satisfying yv, we can compute, in $\tO(|E|)$ work and $\pl(n)$ time, a set $E^+$ of edges supported on $V'\s V$ such that
For all edges $(v_C,v_{C'})\in E^+$, $w_{E^+}(v_C,v_{C'}) \ge d_{G_0}(v_C,v_{C'})+2(c(C)+c(C'))$,

For all vertices $u,v\in V'$,

\[ \f1{8kD}\cd d_{G'\cup E^+}(u,v) \le \1{y_u-y_v} \le (D+6) \cd d_{G'\cup E^+}(u,v) .\]

Let $H$ be an $(8kD)$-spanner of the (complete) $\el_1$-metric induced by the vectors $\{y_v:v\in V'\}$. That is, for all $u,v\in V'$,

\[ \1{y_u-y_v} \le d_{H}(u,v) \le 8kD\cd\1{y_u-y_v} .\]

We show later how to compute it efficiently, but for now, assume we have computed such a graph $H$. We set the edges $E^+$ as simply the edges of $H$ (with the same weights).

Every edge $(v_C,v_{C'})\in E^+$ satisfies

\[ w_{E^+}(v_C,v_{C'}) \ge d_{H}(v_C,v_{C'}) \ge \1{y_{v_C}-y_{v_{C'}}} \stackrel{\eqn{dGv}}\ge \1{x_{v_C}-x_{v_{C'}}}+2(c(C)+c(C')) ,\]

and $\1{x_{v_C}-x_{v_{C'}}}\ge d_{G_0}(v_C,v_{C'})$ since $\{x_v\}$ is an $\el_1$-embedding for $G_0$, fulfilling condition (1).
For each pair of vertices $u,v\in V'$,

\[ d_{G'\cup E^+}(u,v)\le d_{H}(u,v) \le 8kD\cd\1{y_u-y_v} ,\]

fulfilling the lower bound in condition (2).

For the upper bound in condition (2), it suffices to show that, for all edges $(v_C,v_{C'})\in E'\cup E^+$,

\[ \1{y_u-y_v} \le (D+6)\cd w_{G'\cup E^+}(u,v) .\]

If $(v_C,v_{C'})\in E^+$, then

\[ \1{y_{v_C}-y_{v_{C'}}} \le d_H(v_C,v_{C'}) \le w_H(v_C,v_{C'}) = w_{G'\cup E^+}(v_C,v_{C'}) .\]

Otherwise, if $(v_C,v_{C'})\in E'$, then for the edge $(u,u')\in E$ with $u\in C$ and $u'\in C'$ responsible for this edge,

\begin{align*}
\1{y_{v_C}-y_{v_{C'}}} &\stackrel{\eqn{dGv}}\le\1{x_{v_C}-x_{v_{C'}}}+6(c(C)+c(C'))
\\&\le D\cd d_{G_0}(v_C,v_{C'}) + 6 w_{G'}(v_C,v_{C'})
\\&\stackrel{\eqn{only-inc}}\le D\cd d_{G}(v_C,v_{C'})+6 w_{G'}(v_C,v_{C'})
\\&\stackrel{\text{Clm.}\ref{clm:each-edge}}\le  D\cd w_{G'}(v_C,v_{C'}) +6 w_{G'}(v_C,v_{C'}),
\end{align*}

assuming the following inequality holds:

\begin{gather}
d_G(u,v)\ge d_{G_0}(u,v) \qquad \forall u,v\in V.  \eqnl{only-inc}
\end{gather}

To prove only-inc, we assume by induction (on the recursive structure of <ref>) that $d_G(u,v)\ge d_{G_0}(u,v)$ for all $u,v\in V$. By each-edge, the edges $(u,v)$ added to $G'$ on addedge2 have weight at least $d_G(u,v)\ge d_{G_0}(u,v)$. Moreover, since condition (1) of the lemma is satisfied, we have $w(u,v)\ge d_{G_0}(u,v)$ for all edges $(u,v)\in E^+$ as well. It follows that $d_{G_0}(u,v)\le d_{G'\cup E^+}(u,v)$ for all $u,v\in V'$, fulfilling the inequality as well as completing the induction.
This concludes the upper bound of condition (2), as well as the proof of Eplus modulo the construction of the spanner $H$.

Finally, we show how to compute the spanner $H$ of the $\el_1$-metric induced by the vectors $\{y_v\in\R^k:v\in V\}$. We use a randomly shifted grid approach similar to the one in Algorithm <ref>. Assume without loss of generality (by scaling and rounding) that all coordinates are positive integers with magnitude at most $M=\poly(n)$. We repeat the following process $O(\logn)$ times, computing a graph $H_j$ on trial $j$. For each $W$ a power of two in the range $[1,8kM]$, choose independent, uniformly random real numbers $r_1,\lds,r_k\in[0,W)$, and declare equivalence classes on the vertices where two vertices $u,v\in V$ are in the same class if $\lf (y_u)_i+r_i\rf_W=\lf(y_v)_i+r_i\rf_W$ for all coordinates $i\in[k]$. For each equivalence class $U\s V$, select an arbitrary vertex $u\in U$ as its representative, and for all $v\in U\sm\{u\}$, add an edge $(u,v)$ to $H_j$ of weight $\1{y_u-y_v}$. This concludes the construction of graph $H_j$, which has $O(|V|\log|V|)$ edges, since each value of $W$ adds at most $|V|$ edges. The spanner $H$ is the union of all graphs $H_j$ and has size $O(|V|\log|V|\logn)$.

Since all added edges $(u,v)$ have weight $\1{y_u-y_v}\ge d_G(u,v)$, distances in the final spanner $H$ are at least the distances in $G$. To show that distances in $H$ are not stretched too far, we show that for any vertices $u,v\in V$, with constant probability, each graph $H_j$ satisfies $d_{H_j}(u,v)\le 8kD\cd d_G(u,v)$. Then, since there are $\Th(\logn)$ graphs $H_j$, the probability that we do not have $d_H(u,v)\le d_{H_j}(u,v)\le 8kD\cd d_G(u,v)$ for any $j$ is $1/\poly(n)$, as promised.

Let $W$ be the smallest power of two greater than or equal to $2\1{y_u-y_v}$. Note that $\1{y_u-y_v} \le 2kM$, so such a $W$ always exists. It is not hard to show that, for each coordinate $i\in[k]$, the probability that $\lf (y_u)_i+r_i\rf_W=\lf(y_v)_i+r_i\rf_W$ is exactly $1-|(y_u - y_v)_i| / W \ge 1/2$. Therefore, the probability that $\lf (y_u)_i+r_i\rf_W=\lf(y_v)_i+r_i\rf_W$ for all $i$ is

\begin{align*}
\Prod_{i=1}^k\lp1-\f{|(y_u-y_v)_i|}W\rp \ge \Prod_{i=1}^k \exp\lp-2\f{|(y_u-y_v)_i|}W\rp &= \exp\lp -2\sum_{i=1}^k\f{|(y_u-y_v)_i|}W \rp \\&= \exp\lp-2\f{\1{y_u-y_v}}W\rp \ge \exp(-1) ,
\end{align*}

which is a constant. Therefore, with at least constant probability, $u$ and $v$ belong to the same equivalence class for $W$. In this case, since all vertices in this equivalence class have their vectors in a cube of side length $W$, we either added the edge $(u,v)$ of weight $\1{y_u-y_v}\le D\cd d_G(u,v)$, or we selected some vertex $v'$ and added the edges $(u,v')$ and $(v,v')$ of total weight at most

\[ \1{y_u-y_{v'}}+\1{y_v-y_{v'}} \le 2kW \le 2k \cd 4\1{y_u-y_v} \le 2k\cd 4\cd D\cd d_G(u,v) .\]

Thus, $H$ is a $8kD$-spanner w.h.p.

We now argue that, for the input graph $G_0$, source $s\in V_0$, demand vector $b_0$, and an $\el_1$-embedding $\{x_v\in\R^{O(\logn)}:v\in V_0\}$ of $G_0$ with distortion $D$, $\ref{esssp-rec}(G_0,\{x_v\},s,b_0,(1+3\e)^{\log_2n})$ returns a $(1+3\e)^{\log_2n}$-approximate expected $s$-SSSP tree. We will follow the arguments from esssp almost line-by-line; the only changes we will highlight in blue. Define $V^*,b^+,\overrightarrow C,\orf$ on the input graph $G=(V,E)$ and demands $b$ identically as in esssp. As before, define $\opt=\opt_G(b)$.

[Restatement of T-as-good]T-as-good2
Define $T'$ and $T$ as in <ref>. For each component $C$ of $A$ and each vertex $v$ in $C$, we have $d_T(s,v) \le d_{T'}(s',v_C)+d_{T_C}(t,r_C)$.
Follows easily by construction (lines <ref> to <ref>), so proof is omitted. Observe that the extra terms ${}-c(C)-c(C')$ in undo are necessary here.
[Restatement of bound-by-f]bound-by-f2
Over the randomness of <ref> (in particular, the random choices on sample2),

\[ \E\lb \sum_{t\in V^*} b^+(t) \cd d_{T_C}(u,r_C) + \opt_{G'\cup E^+}(b')  \rb \le \1{\overrightarrow C\orf} +2\e\cd\opt.\]

The optimum can only decrease with the addition of edges $E^+$ to $G'$, so we have

\begin{gather} \BLUE{\opt_{G'\cup E^+}(b') \le \opt_{G'}(b') .\eqnl{cupE}}\end{gather}

[Restatement of final-approx]final-approx2
Over the entire randomness of <ref> (including the recursion at recurse2), we have

\[ \E\lb\sum_{t\in V} b^+(t)\cd d_T(s,t)\rb \le \al(1+3\e)\opt .\]

We follow the proof of final-approx.
By vstar, we have $b^+(t)=0$ for all $t\in V\sm V^*$, so it suffices to prove

\[ \E\lb\sum_{t\in \textcolor{blue}{V^*}} b^+(t)\cd d_T(s,t)\rb \le \al(1+3\e)\opt .\]

By recursion, we have the guarantee

\[ \E\lb \sum_{C:v_C\ne s'} b'_{v_C} \cd d_{T'}(s',v_C)\rb\le \al \opt .\]

For each vertex $t$, let $C_t$ be the component of $A$ containing $t$. We have

\begin{align*}
\E\lb \sum_{t\in V^*} b^+(t) \cd d_T(s,v) \rb &\stackrel{\BLUE{\textup{Clm.\,}\ref{clm:T-as-good2}}}\le \E\lb \sum_{t\in V^*} \lp b^+(t)\cd d_{T'}(s',v_{C_t}) + d_{T_{C_t}}(t,r_{C_t}) \rp \rb
\\& = \E\lb \sum_{t\in V^*}  b^+(t)\cd d_{T'}(s',v_{C_t}) \rb + \E\lb \sum_{t\in V^*} b^+(t)\cd d_{T_{C_t}}(t,r_{C_t})\rb
\\&= \E\lb \sum_{C:v_C\ne s'} b'_{v_C} \cd d_{T'}(s',v_C)\rb+ \E\lb \sum_{t\in V^*} b^+(t)\cd d_{T_{C_t}}(t,r_{C_t})\rb
\\&\le \al\E[\opt_{G'\cup E^+}(b')] +  \E\lb \sum_{t\in V^*} b^+(t)\cd d_{T_{C_t}}(t,r_{C_t})\rb
\\& \textcolor{blue}{ \stackrel{\eqn{cupE}}\le \al\E[\opt_{G'}(b')] +  \E\lb \sum_{t\in V^*} b^+(t)\cd d_{T_{C_t}}(t,r_{C_t})\rb }
\\&\le \al\lp \E[ \opt_{G'}(b')] +  \E\lb \sum_{t\in V^*} b^+(t)\cd d_{T_{C_t}}(t,r_{C_t})\rb  \rp
\\&\stackrel{\BLUE{\textup{Cor.\,}\ref{cor:bound-by-f2}}}\le \al\lp \1{\overrightarrow C\orf}+2\e\cd\opt\rp
\\&\le \al((1+\e)\opt + 2\e\cd\opt)
\\&=\al(1+3\e)\opt,
\end{align*}

where the last inequality uses that $\orf$ is a $(1+\e)$-approximate transshipment solution.

Thus, by unraveling the recursion and repeatedly applying final-approx2, the algorithm <ref> computes a tree $T$ for $G_0$, possibly with virtual edges not in $G_0$, such that

\[ \E\lb\sum_{t\in V} b^+(t)\cd d_T(s,t)\rb \le (1+3\e)^{\log_2n}\opt .\]

It remains to show that $T$ is a “valid” approximate expected SSSP tree in the following sense: the virtual edges added to $T$ do not change the metric on $G_0$. This property is sufficient when the expected SSSP algorithm is used in <ref>.

For each vertex $v\in V_0$, consider the recursive instances with $v\in V$; let $C_i(v)$ be the components containing $v$ on previous levels of recursion, with $C_i$ as the value at recursion level $i$. We will need the following quick claim:

Consider a recursion level $i$ with input graph $G=(V,E)$.
For all vertices $v\in V$, the lengths $c(C_j(v))$ of the cycles satisfy $c(C_{j+1}(v)) \ge 2 c(C_j(v))$ for all $j<i$.
If $v=s$, then it holds because $c(C_j(v))=0$ for all $j$, so assume that $v\ne s$.
For a fixed recursion level $j$, by construction, every edge adjacent to $v$ has weight at least $c(C_i(v))$ in the graph $G'$ at that level. The cycle $C_{i+1}(v)$ must contain at least two such edges, so its total length is at least $2c(C_i(v))$.

For each virtual edge $(u,v)$ in $T$, there exists some recursion level $i$ and some edge $(u,v)\in E^+$ at that level of weight

\[ w_{E^+}(u,v) =  w_T(u,v) + \sum_{j=0}^i (c(C_j(u))+c(C_j(v))).\]

By double, the sequence $c(C_0(u)),c(C_1(u)),\lds,c(C_i(u))=c(C)$ has each term at least double the previous, which means that two times the last term is at least the sum of all terms:

\[ 2c(C)=2c(C_j(u))\ge  \sum_{j=0}^ic(C_j(u)) .\]

\[ 2c(C')=2c(C_j(v))\ge\sum_{j=0}^ic(C_j(v)) .\]

By condition (1) of Eplus,

\[ w_{E^+}(u,v) \ge d_{G_0}(u,v)+2(c(C)+c(C')) .\]

Combining these inequalities gives

\[ w_T(u,v)= w_{E^+}(u,v) - \sum_{j=0}^i (c(C_j(u))+c(C_j(v))) \ge w_{E^+}(u,v)-2(c(C)+c(C')) \ge d_{G_0}(u,v) ,\]

as claimed.

§ SAMPLING A PRIMAL TREE

In this section, we prove sample-tree. by reducing the problems of computing a $(1+\e)$-approximate SSSP tree and potential to the approximate transshipment problem, and then using the expected SSSP tree subroutine <ref> of <Ref>. Most of these ideas originate from [5], and we adapt their ideas and present them here for completeness. In particular, we  do not claim any novelty in this section.

We now briefly describe our algorithm for sample-tree. First, we run the expected SSSP algorithm <ref> with demands $\sum_{v\ne s}(\mathbbm1_v-\mathbbm1_s)$, obtaining distances that are near-optimal in expectation in the two different ways. Of course, what we need is that all distances are near-optimal. This is where the potential $\phi$ is useful: using it, we can approximately tell which vertices have near-optimal distances. Then, among the vertices $V'\s V\sm s$ whose distances are not near-optimal, we then compute another transshipment instance with demands $\sum_{v\in V'}(\mathbbm1_v-\mathbbm1_s)$ and repeat the process. As long as the set of remaining vertices $V'$ drops by a constant factor each round in expectation, we only require $O(\logn)$ rounds w.h.p.

To construct the potential, our strategy is simple: we simply take the coordinate-wise maximum of all potentials $\phi$ found over the iterations (assuming $\phi(s)=0$ always). For each vertex $v\in V\sm s$, since at least one iteration computes a near-optimal distance for $v$, the corresponding potential is also near-optimal.

Constructing the specific SSSP tree requires a little more care. We now describe our algorithm in pseudocode below.

sssp<ref>($G=(V,E),\be\in(0,1],\{x_v\in\R^{O(\logn)}:v\in V\}$)
Assumption: $\{x_v\in\R^{O(\logn)}:v\in V\}$ is an $\el_1$-embedding of $G$ with distortion $\pl(n)$
[1]
Initialize $V'\gets V\sm s$ $V'$ is the set of vertices whose distances still need to be computed
Initialize $d^*:V\sm s\to\R\cup\infty$ as $d^*(v)=\infty$ everywhere $d^*$ tracks the best distance found for each vertex $v$
Initialize $p^*:V\sm s\to V\cup\{\bot\}$ as $p^*(v)=\bot$ everywhere $p^*$ is the “parent” function, used to construct the final SSSP tree
Initialize $\phi^*:V\sm s\to\R$ as $\phi^*(v)=0$ everywhere $\phi^*$ tracks the best potential found for each vertex $v$
$V'\ne\emptyset$ sssp-loop
With the $\el_1$-embedding $\{x_v:v\in V\}$, call l1 on demands $\sum_v(\mathbbm1_v-\mathbbm1_s)$ to obtain $(1+\e/10)$-approximate flow-potential pair $(f,\phi)$, where $f$ is an acyclic flow and $\phi(s)=0$
Set demands $b\gets \sum_{v\in V'}(\mathbbm1_v-\mathbbm1_s)$ for this iteration
With the $\el_1$-embedding $\{x_v:v\in V\}$, call <ref>$(G,\{x_v:v\in V\},s,b,\Th(\f\e\logn))$ to obtain a SSSP tree $T$ with $\E \lb \sum_{v\in V'} d_T(s,v)\rb \le (1+\f\e{10})\opt $Satisfies the recursion in esssp-rec

Compute distances $d_T(s,v)$ for all $v\in V'$
each vertex $v\in V'$ in parallel
Let $p(v)$ be the second-to-last vertex on the path from $s$ to $v$ in $T$
Update $d^*(v)\gets d_T(s,v)$dT
Update $p^*(v)\gets p(v)$p*
Update $\phi^*(v)\gets\max\{\phi^*(v),\phi(v)\}$
$d_T(s,v) \le (1+\e)\phi_v$ dT-small
Remove $v$ from $V'$
Initialize $T^*\gets\emptyset$ $T^*$ is the final SSSP tree that we compute
each vertex $v\in V\sm s$
Add edge $(v,p^*(v))$ to $T^*$
SSSP tree $T^*$ and potential $\phi^*$ (augmented with $\phi^*(s):=0$)

If <ref> finishes, then the potential $\phi^*$ that it returns is a $(1+\e)$-approximate $s$-SSSP potential, and the returned $T^*$ is a $(1+\e)$-approximate SSSP tree.
<ref> essentially takes the coordinate-wise maximum over all potentials $\phi$ that Algorithm $\m A$ computes over the iterations. For each vertex $v\in V\sm s$, since it was removed from $V'$ at some point, some potential $\phi$ computed satisfies $(1+\e)\phi_v\ge d_T(s,v)\ge d(s,v)$ (dT-small), so the final potential $\phi^*$ also satisfies $(1+\e)\phi^*_v\ge d(s,v)$. Since each potential $\phi$ satisfies $|\phi(u)-\phi(v)|\le w(u,v)$ or each edge $(u,v)$, by <Ref>, so does the coordinate-wise maximum $\phi^*$. Therefore, $\phi^*$ is an SSSP potential.

Next, we show that the graph $T^*$ returned is indeed a tree. Observe the following invariant: for each vertex $v\in V$, whenever $p^*(v)\ne\bot$, we have $d^*(p^*(v))<d^*(v)$. This is because whenever $d^*(v)$ is updated to $d_T(s,v)$ on dT, we must have $d_T(s,p^*(v))<d_T(s,v)$ for that tree $T$, so $d^*(p^*(v))$ would be updated as well if it was still at least $d_T(s,v)$. Therefore, the edges $(v,p^*(v))$ at the end of the while loop must also satisfy $d^*(p^*(v))<d^*(v)$, so the edges are acyclic. Since there are $n-1$ edges total, $T^*$ is a tree. Finally, to show that $T^*$ is a $(1+\e$)-approximate SSSP tree, we show that for each vertex $v\in V$, $d_{T^*}(s,v)\le d^*(v)$. To see that this is sufficient, observe that since every vertex $v\in V\sm s$ was removed from $V'$, we have $d_T(s,v)\le(1+\e)\phi_v\le(1+\e)d(s,v)$ at some point (dT-small), so on this iteration, $d^*(v)$ would be updated to at most $(1+\e)d(s,v)$.

We prove by induction on the ordering of $d^*(v)$ (from smallest to largest) that $d_{T^*}(s,v)\le d^*(v)$. If $p^*(v)=s$, then since $d^*(v)$ and $p^*(v)$ are updated at the same time (lines <ref> and <ref>), the value $d^*(s)=d_T(s,v)=w(s,v)$ cannot be changed after $p^*(v)$ was set to $s$. Therefore, $d_{T^*}(s,v)=d^*(v)$. Otherwise, suppose that $p^*(v)=u\ne s$. Let $T$ be the tree computed on the iteration when $p^*(v)$ was updated to its final value. We have

\[ d_{T^*}(s,v) = d_{T^*}(s,u)+w(u,v) \stackrel{\text{(ind.)}}\le d^*(u)+w(u,v) \le d_T(s,u)+w(u,v) ,\]

where the (ind.) stands for applying the inductive statement on vertex $u$. This completes the induction and the claim.

For the remainder of this section, we show that the while loop runs for only $O(\logn)$ iterations w.h.p. Consider the following potential function $\sum_{v\in V'}b_vd(s,v)$; we will show that it drops by a constant factor in expectation on each iteration of the  loop. Since the graph $G$ has polynomial aspect ratio, the potential function can only decrease by a constant factor $O(\logn)$ times, so the lemma below suffices to finish sample-tree.
On each iteration of the  loop (sssp-loop), the quantity $\sum_{v\in V'}d(s,v)$ drops by a constant factor in expectation.
Define $\ol d(v):=\E[d_T(s,v)]$ over the randomness of <ref> on this iteration, which satisfies $\sum_{v\in V'}\ol d(v)\le(1+\e/10)\sum_{v\in V'}d(s,v)$ since $T$ is an $(1+\e/10)$-approximate expected SSSP tree with demands $\sum_{v\in V'}(\mathbbm1_v-\mathbbm1_s)$.

Since $(f,\phi)$ is a $(1+\e/10)$-approximate flow-potential pair, we have $\1{f}\le(1+\e/10)\sum_{v\in V}b_v\phi_v$. We have, for small enough $\e$,

\begin{align*}
\sum_{v\in V'}\ol d(v)\le\lp1+\f\e{10}\rp\sum_{v\in V'}d(s,v)&\le\lp1+\f\e{10}\rp\opt\bigg(\sum_{v\in V'}(\mathbbm1_v-\mathbbm1_s)\bigg) \\&\le\lp1+\f\e{10}\rp\1{f} \\&\le \lp1+\f\e{10}\rp^2\sum_{v\in V}b_v\phi_v\le\lp1+\f\e4\rp\sum_{v\in V}b_v\phi_v =\lp1+\f\e4\rp\sum_{v\in V'}\phi_v ,% \\&\le\lp1+\f\e4\rp\sum_{v\in V'}b_vd(s,v),
\end{align*}

which implies that

\[ \sum_{v\in V'} (\ol d(v)-\phi_v) \le \f\e4\sum_{v\in V'} \phi_v . \]

Observe that for all $v\in V'$, $\ol d(v)\ge d(s,v)\ge\phi_v-\phi_s=\phi_v$, so  $\ol d(v)-\phi_v\ge0$. Let $V'_{\text{good}}\s V'$ be the vertices $v\in V'$ with

\[ \ol d(v)-\phi_v \le \f\e2\phi_v .\]

By a Markov's inequality-like argument, we have

\begin{gather} \sum_{v\in V'_{\text{good}}} \phi_v \ge \f12\sum_{v\in V'} \phi_v ;\eqnl{Vgood}\end{gather}

otherwise, we would have

\[ \sum_{v\in V'} (d(v)-\phi_v) \ge \sum_{v\in V'\sm V'_{\text{good}}} (d(v)-\phi_v) \ge\f\e2\sum_{v\in V'\sm V'_{\text{good}}}  \phi_v > \f\e4\sum_{v\in V'} \phi_v, \]
a contradiction.

For each $v\in V'_{\text{good}}$, by Markov's inequality on the nonnegative random variable $d_T(s,v)-\phi_v$ (which has expectation $\ol d(v)-\phi_v\le\f\e2\phi_v$), with probability at least $1/2$, we have

\[ d_T(s,v)-\phi_v\le\e\,\phi_v \iff d_T(s,v) \le (1+\e)\phi_v ,\]

so vertex $v$ is removed from $V'$ with probability at least $1/2$. In other words, the contribution of $v$ to the expected decrease of $\sum_{u\in V'} d(s,u)$ is at least $\f12  \phi_v$. Since

\[ d(s,v)\le d_T(s,v)\le(1+\e)\phi_v \implies \phi_v\ge(1+\e)\inv d(s,v) ,\]
this expected decrease is at least $\f1{2(1+\e)} \phi_v$. Summing over all $v\in V'_{\text{good}}$, the expected decrease of $\sum_{u\in V'} d(s,u)$ is at least

\[ \sum_{v\in V'_{\text{good}}}\f1{2(1+\e)} d(s,v) \stackrel{\eqn{Vgood}}\ge \f1{4(1+\e)}\sum_{v\in V'} d(s,v) ,\]

which is a constant factor.

§ OMITTED PROOFS

§.§ Proof of aspect-ratio

Suppose that the demand vector $b$ satisfies $b_v\in\{0,1,2,\lds,n^C\}$ for all $v\in V$, for some constant $C$.

First, compute a minimum spanning tree $T$ of the graph $G=(V,E)$,[This can be computed work-efficiently in Parallel, e.g., with Boruvka's algorithm.] and compute the optimal transshipment cost where the input graph is $T$ instead, which is easily done efficiently since $T$ is a tree. Since $T$ is a minimum spanning tree, it is easy to see that for any vertices $u,v\in V$, we have $d_G(u,v)\le d_T(u,v)\le (n-1) \cd d_G(u,v)$, i.e., the stretch of $T$ is at most $(n-1)$. Define $Z:=\opt_T(b)$ as the optimal cost on $T$; it follows that

\begin{gather} \opt_G(b) \le Z\le (n-1)\,\opt_G(b) \eqnl{optT}.\end{gather}

To construct $\wG$, we start with $G$ and remove all edges of weight more than $Z$ from $G$, and then add $Z/n^{C+5}$ weight to each remaining edge in the graph. Clearly, $\wG$ has aspect ratio $\poly(n)$ and satisfies $\opt_G(b)\le\opt_{\wG}(b)$. It remains to show that

\begin{gather}\opt_{\wG}(b)\le\left(1+\f1{n^2}\right)\,\opt_G(b).\eqnl{to-show-wG}\end{gather}

The transshipment problem can be formulated as an uncapacitated minimum cost flow problem. It is well-known that if the demands of a minimum cost flow problem are integral, then there exists an optimal flow that is integral. Let $f$ be this integral flow for demands $b$. Then, $f$ cannot carry any flow along any edge with weight more than $Z$, since if it did, then it must carry at least $1$ flow along that edge, bringing its total cost to more than $Z$, contradicting the fact that $\opt_G(b)\le\opt_T(b)=Z$. It follows that removing edges with weight more than $Z$ does not affect the optimal transshipment cost.

Since $|b_v|\le n^C$ for all $v\in V$, it is also well-known that the optimal flow $f$ satisfies $|f_e|\le n^C$ for all $e\in E$. Consider the same flow $f$ on $\wG$ instead of $G$; since each edge has its weight increased by $Z/n^{C+4}$, the total increase in cost of the flow $f$ on $\wG$ is

\[ \sum_{e\in E}|f_e| \cd \f Z{n^{C+5}} \le \bn n2 \cd n^C \cd \f Z{n^{C+5}} \le \f Z{n^3} \stackrel{\eqn{optT}}\le \f{\opt_G(b)}{n^2} .\]

The cost of the optimal flow on $\wG$ can only be lower, which proves to-show-wG.

§.§ Proof of embed
[1]
Let $N\gets O(\logn)$, $T\gets\lc\logn\rc$, $\e\gets1/\logn$
independent iteration $i=1,2,\lds,N$
$t=1,2,\lds,T$ for-t
Sample each vertex in $G$ independently with probability $1/2^t$; let $S$ be the sampled set sample
Compute $(1+\e)$-approximate $S$-SSSP potential $\phi_{i,t}(u)$ of $G$ through algorithm $\m A$
Extend $\phi_{i,t}$ so that $\phi_{i,t}(v)=\phi_{i,t}(s)$ for all $v\in S$, so that $\phi_{i,t}(v)$ is now defined for all $v\in V$
For each $v\in V$, output the vector $x(v):=\langle \f1{NT}\phi_{i,t}(v) \rangle_{i\in[N],t\in[T]} \in \R^{[N]\times[T]}$ as the $\el_1$-embedding of $v$

Fix two vertices $u,v$ throughout the proof, and define $d:=d(u,v)$; we need to show that w.h.p.,

\[ \norm{x(u)-x(v)}_1 = \f1{NT}\sum_{i\in[N],t\in[T]} \left| \phi_{i,t}(u) - \phi_{i,t}(v) \right| \in \lb \f{d}{O(\log^3n)} ,\ d \rb .\]

The upper bound is easy: by definition of approximate $s$-SSSP potential, we have $|\phi_{i,t}(u)-\phi_{i,t}(v)|\le d$ for all $i,t$, so taking the average over all $i,t$ gives $\f1{NT}\sum_{i,t} \left| \phi_{i,t}(u) - \phi_{i,t}(v) \right|\le  d $. To finish embed, it remains to prove the lower bound, whose proof occupies the rest of this section.

There is a value of $t\in[T]$ such that with probability $\Om(1)$,

\[ |\phi_{i,t}(u) - \phi_{i,t}(v)| \ge \Om(\e d) .\]

For each positive $r$, define $B(u,r):=\{w\in V:d(w,u)\le r\}$ as the vertices within distance $r$ from $u$. Similarly, define $B(v,r)$ as the vertices within distance $r$ from $v$.

There exists a value $r\in[d/6,d/3]$ and a (universal) constant $C>1$ such that

\[ |B(u,(1+2\e)r)| \le C|B(v,r)| \quad\text{or}\quad |B(v,(1+2\e)r)| \le C|B(u,r)| .\]

First, we show that such a value $r$ must exist. If not, then we have the chain of inequalities

\[  |B(v,\f d6)| < \f1C|B(u,(1+2\e)\f d6)| < \f1{C^2}|B(v,(1+2\e)^2\f d6)|< \f1{C^3}|B(u,(1+2\e)^3\f d6)| < \cds < \f1{C^L}|B(u,(1+2\e)^L\f d6)|\]

for $L=\lf\log_{(1+2\e)}2\rf=\Th(1/\e)=\Th(\logn)$ (we assume w.l.o.g. that the last expression has $u$ and not $v$). For large enough $C$, this means that

\[ 1 \le |B(u,\f d6)| \le \f1{C^{\Th(\logn)}}|B(u ,(1+2\e)^L\f d6)| < \f1n |B(u ,(1+2\e)^L\f d6)| \implies |B(u ,(1+2\e)^L\f d6)|>n ,\]

which is impossible. Therefore, such a value $r$ exists.

Take the value $r$ guaranteed by <Ref>, and assume w.l.o.g. that $|B(u,(1+2\e)r)| \le C|B(v,r)|$. Pick $t\in[T]$ satisfying $2^{t-1}\le|B(v,r)|\le2^{t}$, which also means that $|B(u,(1+2\e)r)|\le O(2^t)$. Suppose we sample each vertex in $V$ with probability $1/2^t$ (sample). With probability $\Om(1)$, we sample at least one vertex in $B(v,r)$, and with probability $\Om(1)$, we sample zero vertices in $B(u,(1+2\e)r)$. Moreover, since $r + (1+2\e)r < 3r \le 3 \cd d/3=d$, the two sets $B(u,(1+2\e)r)$ and $B(v,r)$ are disjoint, so the two events are independent. Thus, with probability $\Om(1)$, we have both $S\cap B(v,r)\ne\emptyset$ and $S\cap B(u,(1+2\e)r)=\emptyset$, which implies that $d(S,v)\le r$ and $d(S,u)\ge(1+2\e)r$.

Fix an iteration $i\in[N]$, and let us condition on the previous event. Since $\phi_{i,t}$ is a $(1+\e)$-approximate $S$-SSSP potential of $G$, we have $\phi_{i,t}(v)-\phi_{i,t}(s)\le d(S,v)\le r$ by property (1) of SSSP-dual and $\phi_{i,t}(u)-\phi_{i,t}(s)\ge\f1{1+\e}d(S,u)\ge\f1{1+\e}(1+2\e)r=(1+\Om(\e))r$ by dual-upper. Thus, $|\phi_{i,t}(u)-\phi_{i,t}(v)|\ge\Om(\e)\cd r \ge \Om(\e)\cd d/6= \Om(\e d)$.

Since there are $N=O(\logn)$ trials, w.h.p., one of the iterations $i\in[N]$ will satisfy $|\phi_{i,t}(u)-\phi_{i,t}(v)|\ge\Om(\e d)$ for the value of $t$ guaranteed by exists-t. Thus, w.h.p., we have

\[\norm{x(u)-x(v)}_1 =\f1{NT}\sum_{i,t} \left| \phi_{i,t}(u) - \phi_{i,t}(v) \right| \ge \f1{NT} \Om(\e d) =\f{d}{O(\log^3n)}  ,\]

concluding exists-t.

§.§ Proof of tree-SSSP
It suffices to compute (exact) $S$-SSSP distances on $T$, after which we simply define $\phi(v)$ as the distance to $v$ for each vertex $v$.

Define a centroid of the tree $T$ as a vertex $v\in V$ such that every component of $T-v$ has size at most $|V|/2$. We can compute a centroid $r$ as follows: root the tree $T$ arbitrarily, and for each vertex $v$, compute the size of the subtree rooted at $v$; then, let the centroid be a vertex whose subtree has size at least $n/2$, but whose children each have subtrees of size less than $n/2$. Next, compute the distance $d_T(r,S)$ from $r$ to the closest vertex in $S$, which can be accomplished by computing SSSP on the tree with $r$ as the source. Now root the tree $T$ at $r$, and for each child vertex $v$ with subtree $T_v$, construct the following recursive instance: the tree is $T_v$ together with the edge $(v,r)$ of weight $d_T(r,S)+w(v,r)$, and the set $S$ is $(V(T_v) \cap S)\cup \{r\}$. Solve the recursive instances, and for each vertex $u\in V\sm r$, the distance $d(u)$ is the computed distance in the (unique) recursive instance $T_v$ such that $u\in T_v$.

It is clear that the above algorithm is correct and can be implemented in $\tO(m)$ work and $\pl(n)$ time.

§.§ Proof of ol-d

Define a flow path $P$ as a sequence of vertices $(s=v_0,v_1,\lds,v_\el)$ such that  $\bar f(v_{i-1},v_i)>0$ for all $i\in[\el]$ (equivalently, $v_i\in\Out(v_{i-1})$). We say that $v\in P$ if $v=v_i$ for some $i\in[0,\el]$,  and define $P(v_i)$ to be the (sub-)path $(s=v_0,v_1,\lds,v_i)$. Also, we say that $(u,v)\in P$ if $(u,v)=(v_{i-1},v_i)$ for some $i\in[\el]$. Define $\End(P):=v_\el$ as the last vertex on the path, and let $(P,v)$ denote the flow path $P$ with vertex $v$ added to the end of the sequence (provided that $v\in\Out(\End(P))$). For a flow path $P$, define $w(P):=\sum_{i=1}^\el w(u,v)$ as the weight of the path, and we assign a value $c(P)>0$ as its capacity.
We construct a set $\m P$ of flow paths satisfying the following:
For all $u,v\in V$ with $\bar f(u,v)>0$, we have

\[ \sum_{P\in\m P:\,(u,v)\in P} c(P) = \bar f(u,v) .\]

By summing over all such $u,v\in V$, this implies that
\[ \sum_{P\in\m P}c(P)w(P) = \1{f}.\]

There are no paths $P\in\m P$ with $\End(P)=s$, and for all $v\in V\sm s$, we have

\[ \sum_{P\in\m P:\,\End(P)=v}c(P)\,w(P(v))=\f{b_v}{\FIn(v)}\sum_{P\in\m P:\,v\in P}c(P)\,w(P(v)) .\]

For all $v\in V$, we have

\[ \sum_{P\in\m P:\,v\in P}c(P)\,w(P(v)) = \FIn(v)\,\ol d(v) .\]

By summing over all $v\in V\sm s$, this implies that

\[ \sum_{P\in\m P}c(P)w(P)=\sum_{v\notin s}b_v\ol d(v) .\]

Combining properties (2) and (3), we obtain

\[\sum_{P\in\m P:\,\End(P)=v}c(P)\,w(P(v)) = b_v\ol d(v) ,\]

and summing over all $v\in V\sm s$ and applying property (1), we get the desired

\[ \1{f}=\sum_{P\in\m P}c(P)\,w(P(v))=\sum_{v\ne s} b_v\ol d(v) .\]

Therefore, it suffices to find the desired set $\m P$ of flow paths.

To construct  $\m P$, fix an arbitrary topological ordering of the vertices $s=v_1,v_2,\lds,v_n$. We will imagine the set $\m P$ as a liquid flow that travels through the graph $G$, where for each flow path $P$ along which some nonzero volume of liquid travels, we add the path $P$ to $\m P$ with capacity $c(P)$ equal to this volume.

First, initialize $|b_s|$ liquid at vertex $s$. Then, for iteration $i=1,2,\lds,n$ in that order, take the liquid currently at  $v_i$, “mix” them together, and for each $u\in\Out(v_i)$, send $\bar f(v_i,u)$ volume of the mixed liquid to vertex $u$. The rest of the liquid stays at $u$. A simple induction on $i$ shows that exactly $\FIn(u)$ liquid resides at $v_i$ before iteration $i$, and $\FIn(u)-\FOut(u)=b_{v_i}$ liquid remains at $v_i$ after the iteration. Note that by construction, the set of paths $\m P$ corresponding to this liquid flow satisfy properties (1) and (2). To prove property (3), we induct on $i=1,2,\lds,n$. Fix a vertex $v=v_i$; for each vertex $u\in\In(v)$, since we mix the liquid at $u$ before sending it along to $v$, every path $P\ni u$ has exactly $\f{\ol f(u,v)}{\FIn(v)}c(P)$ volume of its corresponding liquid sent along $v$. Therefore, we have the first equality in the chain of equalities below:

\begin{align*}
\sum_{P\ni v}c(P)w(P(v)) &= \sum_{u\in\In(v)}\sum_{P\ni u}\f{\bar f(u,v)}{\FIn(u)}c(P) w(P(v))
\\&= \sum_{u\in\In(v)}\sum_{P\ni u}\f{\bar f(u,v)}{\FIn(u)}c(P)(w(P(u))+w(u,v))
\\&= \sum_{u\in\In(v)}\f{\bar f(u,v)}{\FIn(u)}\sum_{P\ni u}c(P)(w(P(u))+w(u,v))
\\&=  \sum_{u\in\In(v)}\f{\bar f(u,v)}{\FIn(u)}\lp\sum_{P\ni u}c(P)w(P(u))+\sum_{P\ni u}w(u,v)\rp
\\&=  \sum_{u\in\In(v)}\f{\bar f(u,v)}{\FIn(u)}\lp\sum_{P\ni u}c(P)w(P(u))+\FIn(u)\cd w(u,v)\rp
\\&\mathclap{\stackrel{\text{(ind.)}}=}  \sum_{u\in\In(v)}\f{\bar f(u,v)}{\FIn(u)}\lp \FIn(u)\,\ol d(u)+\FIn(u)\cd w(u,v)\rp
\\&=  \sum_{u\in\In(v)}{\bar f(u,v)}\lp \ol d(u)+ w(u,v)\rp
\\& \stackrel{\eqn{ol-d}}=\FIn(v)\,\ol d(v),
\end{align*}

where (ind.) stands for applying the inductive statement on vertex $u$.

For $i=2,3,\lds,n$ in that order, modify the set $\m P$ as follows. For each $P\in\m P$ with $\End(P)=v_i$, and for each $u\in\Out(v_i)$, add $(P,u)$ to $\m P$ with capacity $\f{\bar f(v,u)}{\sum_{u'\in\In(v)}\bar f(u',v)}$; afterwards, decrease the capacity of each such $P$ by $\f{\sum_{u\in\Out(v)}\bar f(v,u)}{\sum_{u'\in\In(v)}\bar f(u',v)}$. If the path $P$ now has capacity $0$, then remove it from $\m P$. (We will later show that the capacity can never go negative.)

Throughout the process, we show the following invariants: before each iteration $i\in[2,n]$, we have

\[ \sum_{P\in\m P:\,\End(P)=v_i} c(P) = \sum_{u'\in\In(v)}\bar f(u',v), \]

and after each iteration $i\in[2,n]$, we have

\[ \sum_{P\in\m P:\,\End(P)=v_i} c(P) = \sum_{u'\in\In(v)}\bar f(u',v) - \sum_{u\in\Out(v)}\bar f(v,u) =b_v ;\]

note that $\max\{0,b_v\}=b_v$ for all $v\ne s$.

We prove these invariants by induction on $i\in[2,n]$. For each $i\in[2,n]$, define $\m P_i$ as the set $\m P$ right before iteration $i$.
Before each iteration $i\in[2,n]$, all paths $P\in\m P$ with $\End(P)=v_i$ were either added on some iteration $j<i$ with $v_i\in\Out(v_j)$, or initialized at the beginning. For each $j<i$ satisfying $v_i\in\Out(v_j)$, by induction, the total capacity of flow paths $(P,u)$ for $P\in\m P_j$ is

\[ \sum_{P\in\m P_j:\,\End(P)=v_j} \f{\bar f(v_j,u)}{\sum_{u'\in\In(v)}\bar f(u',v_j)} = \sum_{P\in\m P_j:\,\End(P)=v_j} \f{\bar f(v_j,u)}{\sum_{P\in\m P_j:\,\End(P)=v_j}c(P)} = \bar f(v_j,u). \]

Therefore, . After iteration $i$, the capacity of each path $P\in\m P_i$ is decreased by

We start off with a $2$-approximate transshipment flow that is acyclic. Ignore any non-source vertices with zero incoming flow. (These also have zero outgoing flow, so they're irrelevant.) Let $V'$ be the remaining vertices. For each vertex $v\in V'\setminus s$, sample one edge $(u,v)$ with probability proportional to $f_{uv}$ among all incoming arcs $(u,v)$.

The expected ? is BLAH.
Consider partitioning the flow into paths as follows: start with a topological ordering of the vertices (so $s$ is first). Initially, $s$ has $|b_s|$ amount of the (empty) path $(s)$. Next, go through the topological order; for each vertex $v\in V'\setminus s$, move $f_{uv}$ amount of flow