Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts

We formalize the notions of length-constrained expanders in directed graphs and in undirected vertex-capacitated graphs. Then, we show the existence of length-constrained expander decomposition in directed graphs (Theorem 10) and in undirected vertex-capacitated graphs (Theorem 11). Along the way, we also show that the definition of length-constrained expanders based on cuts is almost equivalent to the characterization based on multi-commodity flow (Theorems 9 and 12). This can be viewed as a version of the approximate multicommodity maxflow mincut theorem [34] but for length-constrained expansion in directed and vertex-capacitated graphs. While this part does not require technical novelty, it is an important foundation for our paper and, we believe, for future work using this concept.

Our main technical contribution (Theorem 14) is to show that, for any undirected vertex-capacitated graph and any $ϵ>0$, there exists a $2^{O(\frac{1}{ϵ})}$-step flow shortcut $E^{\prime }$ of size $|E^{\prime }|=O(n^{1+O(ϵ)}\mathrm{polylog}(n))$ with length slack $O(1/{ϵ}^3)$ and congestion slack $n^{O(ϵ)}$. This generalizes the flow shortcut of [20] in undirected edge-capacitated graphs.

Our trade-off between size, length slack, and congestion slack matches the one of [20]. However, our step-bound is $2^{O(\frac{1}{ϵ})}$ instead of $O(1/{ϵ}^2)$. This is due to technical barriers unique to vertex-capacitated graphs, which also requires us to use very different analysis. We leave as a very interesting open problem if it is possible to obtain $\text{poly}(1/ϵ)$ steps.

We note that obtaining similar LC-flow shortcuts on directed graphs is currently out of reach because it would give the breakthrough on reachability shortcuts. Given a graph $G=(V,E)$, an edge set $E^{\prime }$ is a $t$-step reachability shortcut of $G$ if, for every pair of vertices $u,v\in V$, $u$ can reach $v$ in $G$ if and only if $u$ can reach $v$ in $G\cup E^{\prime }$ using at most $t$ steps. Observe that an LC-flow shortcut in a directed graph is strictly stronger than a reachability shortcut. It is a major open problem whether there exists a $n^{o(1)}$-step reachability shortcut of size $n^{1+o(1)}$.⁴⁴4When endpoints of $E^{\prime }$ must be in $V$, [26, 28, 6] already showed that there is no $\mathrm{\Omega }(n^{1/4})$-step reachability shortcut of size $O(n)$. The lower bounds extend to the shortcut of size $n^{1+ϵ}$ with a worse step bound.

Before explaining the obstacle, we first show how to shortcut an LC-vertex expander as a warm-up. Suppose that a node-weighting $A$ is $(h,s)$-length $\varphi$-vertex expanding in $G$. Say, $A:={\mathrm{𝟙}}_V$ (i.e., $A(v)=1$ for all $v\in V$).

Suppose further that $G$ has diameter at most $h$. In this case, our shortcut is simply a star $S$ connecting each original vertex $v$ to a Steiner vertex $r_S$ with an $(hs)$-length $A(v)$-capacity edge. We can shortcut any feasible flow in $G$ with $2$ steps. An illustrative example is shown in Figure 1. The length slack is $O(s)$ since an $h$-length original feasible flow is mapped forward to a $(2hs)$-length feasible flow in the star. The congestion slack is $O(\log n/\varphi )$ because any feasible flow in the star induces an $h$-length $A$-respecting demand. Since $A$ is $(h,s)$-length $\varphi$-expanding in $G$, we route such demand in $G$ with congestion $O(\log n/\varphi )$ and without length increasing.

In general, the diameter can be large. Thus, we can construct a sparse neighborhood cover to decompose the graph into clusters with diameter $h$, such that (1) for each vertex $v$, there is a cluster containing all vertices within distance $h/s$ from $v$, and (2) each vertex is inside $n^{O(1/s)}$ clusters. Then, we can construct a shortcut by adding an $(hs)$-edge-length star on each cluster. By a similar argument, we obtain a flow shortcut graph for $(h/s)$-length original flows with length slack $O(s^2)$, congestion slack $O(n^{O(1/s)}\log n/\varphi )$ and step $2$.

So far, when we build an LC-flow shortcut for an LC-expander, the vertex-capacitated setting presents no difficulties compared to the edge-capacitated setting, because the above simple approach works in both settings. However, the differences between the two settings arise when generalizing this approach to general graphs via expander hierarchies.

The key idea of [20] is to exploit a hierarchy of boundary-linked LC-expander decomposition, defined as follows. Let $G$ be an edge-unit-capacity graph. Initialize the node-weight $A_0={\mathrm{deg}}_G$. For each level $0\le i\le d$, compute a cut $C_{i+1}\subseteq E$ of size $|C_{i+1}|\approx \varphi |A_i|$ such that $A_i+{\mathrm{deg}}_{C_{i+1}}$ is $(h,s)$-length $\varphi$-expanding in $G-C_{i+1}$ where ${\mathrm{deg}}_{C_{i+1}}(v)$ counts the number of $C_{i+1}$-edges incident to $v$.⁶⁶6In the actual construction, $C_{i+1}$ assigns fractional values to edges and is called a moving cut, defined in Section 3. Here, we assume $C_{i+1}$ is a classic edge cut for simplicity. The cut $C_{i+1}$ is called the boundary-linked LC-expander decomposition for $A_i$ because it gives a stronger expansion guarantee of $A_i+{\mathrm{deg}}_{C_{i+1}}$ instead of just $A_i$. Then, we set $A_{i+1}:={\mathrm{deg}}_{C_{i+1}}$ and continue to the next level $i+1$. By setting $\varphi =1/(n^{O(1/s)}{n}^{\epsilon })$, we have that $d=O(1/\epsilon )$ and $A_{d+1}=0$.

From the above construction, we conclude that, for each $i$, $A_i+A_{i+1}$ is $(h,s)$-length $\varphi$-expanding in $G-C_{i+1}$. Therefore, as we have seen in the warm-up, we can add stars on the support of $A_i+A_{i+1}$ so that any flows routing $h$-length $(A_i+A_{i+1})$-respecting demands in $G-C_{i+1}$ can be shortcut.

Now consider a feasible $h$-length flow in $G$. The boundary-linkedness suggests a natural bottom-up shortcut scheme. For each flow path $P$, we can think of routing $P$’s head packet and tail packet (initially at $P$’s left and right endpoints, denoted by $u_0$ and $v_0$) to the same place via shortcuts. Take the head packet as an example. Start with $u_0\in \mathrm{supp}(A_0)=V$. At each level $0\le i\le d-1$, let $u_{i+1}$ be the left endpoint of the first $P\cap C_{i+1}$-edge behind $u_i$. By definition, $u_{i+1}\in \mathrm{supp}(A_{i+1})$ and $P$’s subpath between $u_i$ and $u_{i+1}$ is disjoint from $C_{i+1}$, so we can use star graphs at level $i$ to route the head packet from $u_i$ to $u_{i+1}$ within $2$ steps. In sum, each of the head and tail packets is routed from the bottom up until they reach $u_d,v_d\in \mathrm{supp}(A_d)$, and the top-level star graphs can route them together. The total number of steps is $O(d)=O(1/ϵ)$⁷⁷7We note that the step bound in [20] is $O(1/{ϵ}^2)$ because they used powers of expander graphs instead of star graphs to avoid creating vertices outside $G$, which brought another $O(1/ϵ)$ factor..

The overall strategy of the above approach is to shortcut flow paths from a vertex of $A_i$ to an endpoint of edges in $C_{i+1}$. This was possible since the boundary-linked expander decomposition guarantees that $A_i+{\mathrm{deg}}_{C_{i+1}}$ is expanding.

In the vertex-capacitated graph, however, the cut $C_{i+1}\subseteq V$ is now a vertex set. To follow the same strategy, we have two natural options. We shortcut flow from a vertex of $A_i$ to either (1) a vertex in $C_{i+1}$, or (2) a neighbor of $C_{i+1}$.

In the first case, the strategy requires that $A_i+C_{i+1}$ is expanding in $G-C_{i+1}$. This is trivially impossible because $C_{i+1}$ is not even in the graph $G-C_{i+1}$. In the second case, let $N(C_{i+1})$ denote the neighbors of $C_{i+1}$ that are not in $C_{i+1}$. The strategy requires $A_i+N(C_{i+1})$ is expanding in $G-C_{i+1}$. However, possibly $N(C_{i+1})$ is very big and has size $|N(C_{i+1})|=\mathrm{\Omega }(n|C_{i+1}|)$. It is unlikely that expander decomposition exists to guarantee the expansion of such a large node-weighting. Even if it exists, we would set $A_{i+1}=N(C_{i+1})$ and, hence, we cannot guarantee $|A_{i+1}|\ll |A_i|$. So the number of levels of the hierarchy is unbounded.

In either option, this overall strategy fails in the vertex-capacitated graphs. At a very high level, this is because edges have two endpoints while vertices may have an unbounded number of neighbors.

We construct a similar hierarchy of LC-vertex expander decomposition without boundary-linkedness as follows. Let $G=(V,E)$ be a vertex-unit-capacity graph. Initialize node-weighting $A_0={\mathrm{𝟙}}_V$. At each level $0\le i\le d$, computes a cut $C_{i+1}\subseteq V$ such that $A_i$ is $(h,s)$-length $\varphi$-vertex-expanding in $G-C_{i+1}$, and set $A_{i+1}:={\mathrm{𝟙}}_{C_{i+1}}$. In particular, the top level $d$ has $C_{d+1}=\mathrm{\varnothing }$. The LC-vertex-expander decomposition guarantees $|C_{i+1}|\approx \varphi |A_i|$, so the number $d$ of levels is $O(1/ϵ)$ by choosing proper $\varphi$.

Next, we construct the shortcut as follows. For each $i$, by the expansion of $A_i$, we can add stars on the support of $A_i$ into our shortcut so that any flows routing $h$-length $A_i$-respecting demands in $G-C_{i+1}$ can be shortcut. To analyze the shortcut quality, we will no longer try to route from $A_i$ to $A_{i+1}$ as in the edge-capacitated setting, because we no longer have boundary-linkedness guarantee.

Our analysis is instead top-down. At each level $i$, we shortcut the current flow path as much as possible, and then the prefix and suffix that have not yet been shortcut will be deferred to lower levels as subproblems. To be more concrete, say our initial goal is to shortcut a flow path $P$ in a feasible $h$-length original flow. At each level $0\le i\le d$, assume we will receive a subpath $P^{\prime }$ of $P$ with length at most $h$ in $G-C_{i+1}$ (note that $P$ is a valid input to the top level $d$ because $C_{d+1}$ is empty). We will shortcut $P^{\prime }$ using star graphs at levels up to $i$ as follows (see Figure 2 for an illustration when $i=1$).

Let $x_i$ and $y_i$ be the first and last $P^{\prime }$-vertices in $\mathrm{supp}(A_i)$ respectively. We can easily shortcut the subpath $P^{\prime }[x_i,y_i]$ (i.e. the subpath from $x_i$ to $y_i$) within $2$ steps using the star graphs at level $i$.

Let $x_i^{\prime }$ be the $P^{\prime }$-vertex right before $x_i$ and let $y_i^{\prime }$ be the $P^{\prime }$-vertex right after $y_i$. We regard shortcutting the prefix $P^{\prime }[u,x_i^{\prime }]$ and the suffix $P^{\prime }[y_i^{\prime },v]$ as two subproblems at level $i-1$, where $u,v$ are endpoints of $P^{\prime }$. Note that both $P^{\prime }[u,x_i^{\prime }]$ and $P^{\prime }[y_i^{\prime },v]$ has length at most $h$ in $G-C_i$ because they are disjoint from $C_i$ by definition.

After the recursion, we obtain shortcuts for both $P^{\prime }[u,x_i^{\prime }]$ and $P^{\prime }[y_i^{\prime },v]$. The shortcut for $P^{\prime }$ is given by concatenating shortcuts for $P^{\prime }[u,x_i^{\prime }],P^{\prime }[x_i,y_i]$ and $P^{\prime }[y_i^{\prime },v]$ using two original edges $(x_i^{\prime },x_i)$ and $(y_i,y_i^{\prime })$.

It is not hard to see the final step bound is $2^{O(d)}=2^{O(1/ϵ)}$ since the recursion has $d$ levels and each level has two branches. We note that the actual argument is more complicated because the cuts $C_i$ are actually moving cuts which have fractional cut values, and there is no clear partition of $P^{\prime }$ into $3$ parts.

When $4s^2\cdot {\sum }_{j^{\prime }}{C}_{i,j^{\prime }}(P)\le 3$, we simply add $P$ to $F_{i-1}$. We have

where the inequality is by $\mathrm{leng}(P,G)\le h_j$, $h_{\mathrm{diam},j}=4s{h}_j$ and $C_{i,j}(P)\le 3/(4s^2)$. Therefore, in this case, the flow path added to $F_{i-1}$ satisfies the invariant.

Now suppose $4s^2\cdot {\sum }_{j^{\prime }}{C}_{i,j^{\prime }}(P)>3$. Let $u$ and $v$ be $P$’s endpoints. We say $u$ is the left side and $v$ the right side. For each $0\le k\le |P|$, we refer to $w_k$ as the $P$-vertex with $k$ steps away from $u$. In particular, $w_0=u$ and $w_{|P|}=v$.

We now define two functions $x:V(P)\to ℝ$ denoting the budgets of $P$-vertices from the left and the right respectively: for each vertex $w_k\in V(P)$,

In particular,

Let $k_L$ be the minimum index such that ${\sum }_{0\le k\le k_L}{x}_P(w_k)\ge 1$, and symmetrically let $k_R$ be the maximum index such that ${\sum }_{k_R\le k\le |P|}{x}_P(w_k)\ge 1$. To avoid clutter, we let $L=\{w_0,\mathrm{\dots },w_{k_L}\}$ and $R=\{w_{k_R},\mathrm{\dots },w_{|P|}\}$. The following Claim 19 says that $L$ and $R$ have at most one common vertex.

By the definition of $k_L$ and $k_R$, we have

However, ${\sum }_{0\le k\le |P|}{x}_P(w_k)\ge 4s^2{\sum }_{j^{\prime }}{C}_{i,j^{\prime }}(P)>3$. This means there exists a vertex $w_k$ with , which implies $k_L\le k_R$ $\mathrm{⊲}$

We assign each vertex $w\in L\cup R$ a load $x_P^{\prime }(w)\le x_P(w)$, satisfying that ${\sum }_{w\in L}{x}_P^{\prime }(w)=1$ and ${\sum }_{w\in R}{x}_P^{\prime }(w)=1$. We consider the following three-phase strategy to route $F_i(P)$ flow units from $u$ to $v$. Phase 1: the vertex $u$ sends $F_i(P)$ flow units and each $w\in L$ receives $F_i(P)x_P^{\prime }(w)$ units. Phase 2: Each vertex $w\in L$ sends $F_i(P)x_P^{\prime }(w)$ units and each vertex $w\in R$ receives $F_i(P)x_P^{\prime }(w)$ units. Phase 3: Each vertex $w\in R$ sends exactly $F_i(P)x_P^{\prime }(w)$ units, and the vertex $v$ receives $F_i(P)$ units.

Roughly speaking, for the first and third phases, we will add their corresponding original flows into $F_{i-1}$, meaning that they will be deferred to lower levels to get shortcut.

Regarding the first phase, recall that for each $w_k\in L$, we want to route $F_i(P)x^{\prime }(w_k)$ units from $u$ to $w_k$. To do this, we add into $F_{i-1}$ a flow path $P_k=P[w_0,w_{k-1}]$ with value $F_i(P)\cdot x^{\prime }(w_k)$. That is, we require the lower levels to give a shortcut that routes $F_i(P)\cdot x^{\prime }(w_k)$ from $u$ to $w_{k-1}$ (the $P$-vertex one step closer to $u$ than $w_k$). Then, we route $F_i(P)x^{\prime }(w_k)$ units from $w_{k-1}$ to $w_k$ using the original edge $(w_{k-1},w_k)\in E(G)$.

The third phase is handled in a similar way. For each $w_k\in R$, we route $F_i(P)x^{\prime }(w_k)$ flow units from $w_k$ to $w_{k+1}$ using the original edge $(w_{k-1},w_k)$, and then we add into $F_{i-1}$ a flow path $P_k=P[w_{k+1},v]$ with value $F_i(P)\cdot x^{\prime }(w_k)$.

To proceed to the lower level $i-1$, it remains to show that the flow paths added into $F_{i-1}$ satisfy the invariant. Consider a flow path $P_k=P[u,w_{k-1}]$ added from the first phase (where $w_k\le L$, i.e. $0\le k\le k_L$). We want to show that $\mathrm{leng}(P_k,G-C_{i,j_k})\le h_{\mathrm{cov},j_k}$, where $j_k$ is the minimum index such that $h_{j_k}\ge \mathrm{leng}(P_k,G)$. By the definition of the budget function $x$, we have , where the second inequality is by $k\le k_L$ and (from the definition of $k_L$). In particular, $C_{i,j_k}(P_k)\le 1/(4s^2)$. Because $C_{i,j_k}$ is an $(h_{\mathrm{diam},j_k}s)$-length moving cut, we have

as desired, where the first inequality uses $h_{\mathrm{diam},j_k}=4s{h}_{j_k}$. By a similar argument, we can show that each flow path added from the third phase also satisfies the invariant, so we will not explain it in detail.

The second phase is where the shortcut happens. We define an arbitrary (multi-commodity) demand ${\widehat{D}}_{i,P}$ capturing this single-commodity demand. Namely, ${\widehat{D}}_{i,P}$ satisfies that (1) $|{\widehat{D}}_{i,P}|=F_i(P)$; (2) for each $w\in L$, ${\widehat{D}}_{i,P}(w,\cdot )=F_i(P)x_P^{\prime }(w)$; and (3) for each $w\in R$, ${\widehat{D}}_{i,P}(\cdot ,w)=F_i(P)x_P^{\prime }(w)$. We will assign ${\widehat{D}}_{i,P}$ to $H_{i,j}$, meaning that we route ${\widehat{D}}_{i,P}$ using shortcut edges in $H_{i,j}$.

By the above assignment, for each $H_{i,j}$ at level $i$, its total assigned demand, denoted by ${\widehat{D}}_{i,j}$, sums over ${\widehat{D}}_{i,P}$ of all $P\in \mathrm{path}(F_i)$ s.t. $j$ is the minimum index with $h_j\ge \mathrm{leng}(P,G)$. The following Lemma 20 showing that ${\widehat{D}}_{i,j}$ can be routed with low steps, small length and congestion $1$, and we defer the proof to the full version.

It remains to show that $\mathrm{Dem}(F)$ can be routed in $G^{\prime }=G\cup {\bigcup }_{i,j}{H}_{i,j}$ with length $\mathrm{leng}(F)\cdot O(1/{ϵ}^3)$, congestion $1$ and step $2^{O(1/ϵ)}$. The proof for this can be found in the full version.