Improved Tree Sparsifiers in Near-Linear Time

We now elaborate on the tools and techniques that allow us to obtain Theorem 1.1. First, we develop a way to work directly with cuts rather than flows.

Our work builds on the tree flow-sparsifier constructions of [24] and [12], combined with an expander decomposition result by [2].

A crucial component in [24] was a variant of the cut-matching game, introduced by Khandekar, Rao, and Vazirani [14]. The cut-matching game [14] provides an $O({\log }^{2}n)$-approximate sparsest cut in near-linear time. By running a “non-stop” version of this game, [24] obtained balanced $O({\log }^{2}n)$-approximate sparse cuts, or alternatively, constructed clusters whose inter-cluster edges (not including boundary edges) are flow-linked.

A stronger cut strategy was developed by [20], achieving an $O(\log n)$-approximation for the sparsest cut problem. The expansion produced by this cut strategy follows from Cheeger’s inequality [8] and therefore, at least intuitively, is unsuitable for flow routing purposes. This stands in contrast to the cut player of [14], whose expansion follows from embedding a uniform demand matrix (all $1$’s) into the expanding set.

Agassy, Dorfman, and Kaplan [1] were able to translate [20]’s improved cut strategy into a “balanced cut or expander” procedure of approximation $O(\log n)$, resulting in a near-linear time expander decomposition algorithm which improved on the prior expander decomposition algorithm by Saranurak and Wang [26] that uses [14]’s cut strategy. In [2], Agassy, Dorfman and Kaplan show how to extend their results to the case of generalized conductance. By generalized conductance, they refer to conductance with respect to a vertex measure. Formally, given a vertex measure $\mu :V\to {ℝ}_{\ge 0}$, and a set $S\subseteq V$, the expansion of a cut $(S,\overline{S})$ with respect to $\mu$ is defined as ${\mathrm{\Phi }}_G^{\mu }(S,\overline{S}):=\frac{\mathrm{cap}(S,\overline{S})}{\min (\mu (S),\mu (\overline{S}))}$, where $\mu (U)$, for $U\subseteq V$, is defined as $\mu (U):={\sum }_{v\in U}\mu (v)$. We use the result by [2] in a black-box manner as explained in Section 2.5. We note that for the purpose of obtaining our $O({\log }^{3}n\log \log n)$ quality tree flow-sparsifier, one could alternatively rely on [26], together with our refinement phase. However, achieving the improved $O({\log }^{2}n\log \log n)$ quality tree cut-sparsifier crucially relies on the spectral cut player underlying [2].

Typically, as in this work, hierarchical decompositions are computed top-down by recursively splitting clusters starting from the root $V$. Li, Rao, and Wang [17] take the opposite, bottom-up approach, constructing a congestion approximator of quality $O({\log }^{10}n)$. Their main tool is a weak expander decomposition: they build a sequence of partitions $P_1,P_2,\mathrm{\dots },P_L$ of $V$, where each partition corresponds to a weak expander decomposition, and $P_1$ is the partition into singleton clusters and $P_L=\{V\}$. The collection of cuts from these partitions does not form a laminar family. Instead, the congestion-approximator’s set of cuts consists of all intersections of sub-clusters drawn from different levels. A technical challenge is that expander-decomposition routines typically invoke approximate max-flow algorithms that themselves rely on the top-down congestion-approximator of [24]. The construction of [17] avoids this potential circularity by maintaining “pseudo”-congestion-approximators derived from the partial hierarchy $P_1,\mathrm{\dots },P_i$ and using them within the max-flow subroutines required for the weak expander decomposition.

We note that the “balanced cut or expander” primitive of [2], which we use extensively, internally computes fair-cuts (approximate maximum flows) via the algorithm of [16]. This algorithm requires a congestion–approximator for the underlying graph $G$. By instantiating the congestion–approximator required by the fair-cut routine [16] with the construction of [17], our tree cut–sparsifiers can be implemented without invoking the congestion–approximator of [24]. This means that one can also think of our work (in particular, Section 4) as a simplification of the construction of [24] (which does not depend on it).

We use $\log$ to denote the base-2 logarithm. Throughout the paper, we assume all graphs are undirected. Given an undirected graph $G=(V,E)$ and a set $S\subseteq V$, we denote by ${\mathrm{deg}}_G(v)$ the degree of $v$ (for a weighted graph, this is the sum of the weights of the edges adjacent to $v$). The volume of a set $S$ is defined as ${\mathrm{𝐯𝐨𝐥}}_G(S):={\sum }_{v\in S}{\mathrm{deg}}_G(v)$. Given a vertex measure $\mu :V\to {ℝ}_{\ge 0}$, and a set $U\subseteq V$, we denote the total weight of $U$ as $\mu (U):={\sum }_{v\in U}\mu (v)$. We write ${\mu }_U:={\mathrm{𝟙}}_U$ for the indicator measure of $U$. For disjoint sets $A,B\subseteq V$, we denote by $E_G(A,B)$ the set of edges connecting $A$ and $B$. We denote by ${\mathrm{cap}}_G(A,B)$ the number of edges in $E_G(A,B)$, or the sum of their weights if the graph is weighted. We sometimes omit the subscript when the graph is clear from the context. Denote $\overline{A}=V\setminus A$.

For $A\subseteq V$, the all-to-all demand on $A$ is denoted $Q_A$ and defined by $Q_A(u,v)=1/|A|$ for $u,v\in A$, and $0$ otherwise. For a routing $f$ of $Q$ in a capacitated graph $G$, let ${\mathrm{cong}}_G(f)={\max }_{e\in E}f(e)/c(e)$, where $f(e)$ is the total flow through $e$. Let ${\mathrm{cong}}_G(Q)={\min }_f{\mathrm{cong}}_G(f)$, over routings of $Q$.

Note that $G$ $\alpha$-respecting a demand matrix $Q$ does not necessarily imply that $Q$ can be routed with congestion $1/\alpha$ in $G$. Due to the flow–cut gap [15], an additional $O(\log n)$ factor may be required.

We prove the following theorem:

However, first, to gradually develop our techniques, we prove a weaker and simpler version of the theorem, in which we look for a tree cut-sparsifier of quality $O({\log }^{3}n)$:

The following claim follows from the flow-cut gap theorem [15, 4], together with the fact that the flow-cut gap in a tree is $1$ [19].

Hence, as a corollary of Theorem 2.4, we get:

The flow-cut gap for planar graphs is $O(\sqrt{\log n})$ [25]. Therefore, for planar graphs, our construction achieves a tree flow-sparsifier (and congestion-approximator) of quality $O({\log }^{2.5}n\log \log n)$.

For simplicity, we present our algorithms in the setting where $G$ is unweighted, but our constructions can be adapted to the case of polynomially bounded weights.

Our construction follows a recursive partitioning algorithm which takes as input a cluster $S\subseteq V$ and partitions it to sub-clusters $S_1,\mathrm{\dots },S_t$. Applying this algorithm recursively gives a laminar decomposition of the set $V$, which naturally corresponds to a hierarchical tree $T$ (see Remark 2.6). The root of $T$ corresponds to the set $V$ while the leaves correspond to individual vertices $v\in V$. The weight of an edge $(S,P_T(S))$ in $T$, between the node corresponding to the cluster $S$ and its parent $P_T(S)$ is ${\mathrm{cap}}_G(S,V\setminus S)$.

Consider first the task of certifying that such a tree $T$ is a flow-sparsifier. We can do this by showing that the congestion of routing a demand matrix $Q$ in $T$ is comparable to the congestion of routing $Q$ in $G$. Note that by choosing the capacities of the tree edges as we did, the inequality ${\mathrm{cong}}_T(Q)\le {\mathrm{cong}}_G(Q)$ is immediate: we route the demand matrix $Q$ in $T$ trivially along the unique path between each pair of vertices. If the flow problem can be routed in $G$ with congestion $c$, then by Fact 2.3 it must be that, for every sub-cluster $S\in V_T$, the cut $(S,V\setminus S)$ $\frac{1}{c}$-respects $Q$: $\frac{\mathrm{cap}(S,V\setminus S)}{{\mathrm{dem}}_Q(S,V\setminus S)}\ge \frac{1}{c}$. The demand across each cut $(S,V\setminus S)$ corresponds exactly to the total amount of flow routed along the edge $(S,P_T(S))$ in the tree, so the way the edge capacities in $T$ are assigned ensures that the flow problem can be routed in the tree with congestion $c$. Therefore, when building a tree flow-sparsifier, our goal is to choose the tree such that the reverse inequality ${\mathrm{cong}}_G(Q)\le \alpha \cdot {\mathrm{cong}}_T(Q)$ also holds. This means that given demands $Q$ which can be routed in $T$ we have to show how to route $Q$ in $G$ with similar congestion. $Q$ being routable in $T$ means that only for $S\in V_T$, the cut $(S,V\setminus S)$ in $G$, respects $Q$. Therefore, the intuition is that we look to include in the tree the sub-clusters which best capture the cut structure of the graph, in the sense that any demands respected by them can be routed in $G$.

In the flow-sparsifier case, given demands $Q$ routable in $T$, [12, 7, 24] used the tree structure to describe the routing of $Q$ in the graph $G$. They did this by routing $Q$ which originates at all the vertices of $V$ (corresponding to leaves in $T$), toward the boundaries of sub-clusters $S$ as they go up along the tree.⁴⁴4This is made formal using the subdivision graph (see Definition 3.1), where the demands reside on the split nodes of the boundary edges. For the overview in this section, however, we omit these details for simplicity. That is, when a sub-cluster $S\in T$ is partitioned into $\{S_1,\mathrm{\dots },S_t\}$, they route (in $G$) the mass from the boundary edges of ${\{S_i\}}_{i=1}^t$ (where they arrived in the previous iteration) to the boundary edges of $S$. We emphasize that this routing takes place in $G$, while the structure of $T$ is used only as a “blueprint” to direct the intermediate flows. Then, source and target demands of vertex pairs that are both in $S$, are “paired up” and canceled before moving further upwards in the tree.

Turning now back to cut-sparsifiers, in order to certify that $T$ is a tree cut-sparsifier, we no longer need to route the demands $Q$ (which can be routed in $T$) in $G$, but rather only show that $G$ respects $Q$ (see Claim 3.14 which essentially says that $T$ is a tree cut-sparsifier of quality $\alpha$ if it $1/\alpha$-respects every demand $Q$ that is $1$-respected by $T$). To show that demands $Q$ are respected by $G$ we develop a technique of moving demands rather than flow. For this we define the notion of a valid demand state (see Definition 3.6).

In a demand state $P$ each node $v\in V$ has its own vector of $|V|$ commodities (one for each vertex), where for each commodity it has some amount of mass that is waiting at $v$ to be shipped out (or, if the amount is negative, waiting to be shipped into $v$). This representation is particularly convenient in the hierarchical setting: Even when we focus on a sub-cluster $S$, we maintain at each $v\in S$ information on the mass from all $|V|$ commodities including those of vertices that are not in $S$. In contrast, working directly with $|S|\times |S|$ demand matrices within a sub-cluster $S$ would be inconvenient, as the local view would lose information about demands involving vertices outside $S$. The demand state formulation, on the other hand, always retains the complete global demand structure, allowing us to reason locally within clusters while still maintaining awareness of the external interactions.

We use the structure of $T$ to direct the movement of demands. This corresponds to updating the demand state. Specifically, as we climb up the sparsifier $T$, we move the demands of the demand state from internal edges to the boundary edges of sub-clusters $S\in V_T$. However, unlike in the flow-sparsifier setting, these movements do not necessarily correspond to an actual multi-commodity flow that is routable in the graph. In fact, we do not “pay” for the congestion of these routings, as in the flow-sparsifier analysis, but rather according to how much the graph respects them (see Definition 2.2). This charging scheme is detailed in Sections 3.4 and 5.

As mentioned in Section 2.3, a key property of tree flow-sparsifier $T$ is that for every cluster $S\in V_T$, we can move the demands currently in the inter-cluster edges $F$ between sub-clusters $\{S_1,\mathrm{\dots },S_t\}$ of $S$, to the boundary edges $B=E(S,V\setminus S)$ of $S$ while incurring small congestion. An ideal scenario is when the algorithm guarantees that $F\cup B$ is flow-linked inside $G[S]$, meaning that one can route an all-to-all multi-commodity flow $Q_{F\cup B}$ between the edges of $F\cup B$ with low congestion. In this scenario, we can transfer the demands from the inter-cluster edges $F$ to the boundary $B$ in a two-step process:

• $\mathrm{■}$

  Spread the demands of $F\cup B$ uniformly by routing them according to $Q_{F\cup B}$.

• $\mathrm{■}$

  Route the demands of $F$ to $B$ according to the flow paths of the sub-matrix $Q_{F\cup B}(F,B)$.

Note that the uniform spreading in the first step ensures that demands whose source and target are in $S$ are routed to the same uniform distribution over $F\cup B$ and are therefore canceled. Moreover, after the second step every boundary edge carries an equal share of the total demand. Because $S\in V_T$, the cut $E(S,V\setminus S)$ must respect $Q$, so the amount of mass that has to leave the cluster $S$ is at most $E(S,V\setminus S)$. Therefore, the mentioned cancellation guarantees that the load (total demand per edge) is at most $1$ on each boundary edge.

However, as discussed in [7, 12, 23, 24], there may be sub-clusters $S\subseteq V$, for which we cannot find a partition ${\{S_i\}}_{i=1}^t$ such that $F\cup B$ is flow-linked in $G[S]$. A simple counter-example is that it might be the case that $B$ itself is not flow-linked in $G[S]$, or maybe even disconnected there. In this case, no partition of $G[S]$ will work. We use the name bottleneck cut to refer to a cut which certifies that the boundary edges are not flow-linked. This name was introduced by [23], though their bottleneck cuts had to satisfy a slightly different requirement. A similar (yet not equivalent) notion appeared earlier in [7, 12]. The algorithms of [7, 12, 23] had to make sure that the clusters have no bottleneck cuts. They achieved this by cutting clusters that have bottleneck cuts. We call this step the refinement phase [23]. Previous work implements the refinement phase in different ways, either by ensuring a “precondition” on the sub-clusters they recur into [7], or encountering these cuts and handling them “on the fly” [12, 23]. In either case dealing with these cuts slowed down these early algorithms substantially.

Since ensuring that there is no bottleneck cut in each sub-cluster before recurring into it may be expensive (in terms of running time), [24] settled for something slightly weaker: They first ignore the boundary edges of $S$ and find a partition of $S$ into $\{S_1,\mathrm{\dots },S_t\}$ such that the inter-cluster edges $F$ are flow-linked. Then they find an approximate min-cut $Y$ for the (single commodity) flow problem which routes flow from $F$ to $B$. By adding to $T$ a new sub-cluster whose boundary is $Y$, [24] are able to bound the amount of mass that has to cross the cut $Y$, since now the demand matrix $Q$ is respected by $Y$ in $G$.

Adding $Y$ as a boundary of a sub-cluster in $T$ is enough to show how to move the demands to the boundary edges $B$, such that the load on each boundary edge is multiplied by $1+\mathrm{\tau }$ units ($\mathrm{\tau }$ is a parameter ). However, the distribution of demands on the boundary edges is not uniform. Hence, demands whose source and target are in the sub-cluster do not cancel-out. Consequently, the load accumulates when going up along the tree, multiplied by a factor of at most $1+\mathrm{\tau }$ in each iteration. Choosing $\mathrm{\tau }=\frac{1}{\log n}$, such that the load is multiplied by a factor of $(1+\frac{1}{\log n})$ along the $O(\log n)$ levels of the tree, ensures that the load is constant. This method, however, incurs a degradation of $O(\frac{1}{\mathrm{\tau }})$ per level in the quality of the tree flow-sparsifier, leading to an overall loss of $O(\frac{\log n}{\mathrm{\tau }})=O({\log }^{2}n)$.⁵⁵5Choosing $\mathrm{\tau }=\frac{1}{\log n}$ is optimal, up to a multiplicative constant. Let $k=\mathrm{\Theta }(\log n)$ be the depth of the tree. We omit the proof of the following claim: For any sequence of ${\mathrm{\tau }}_1,\mathrm{\dots },{\mathrm{\tau }}_k\le 1$, it holds that ${\sum }_{i=1}^k\frac{1}{{\mathrm{\tau }}_i}{\prod }_{j=i+1}^k(1+{\mathrm{\tau }}_j)=\mathrm{\Omega }(k^2)$. The additional $O({\log }^{2}n)$ factor in their quality comes from the usage of [14]’s cut-matching game for flow (so in total the quality is $O({\log }^{4}n)$).

In our first step below (Section 2.5) we deal with bottleneck cuts similarly to [24], but using primitives from the expander decomposition algorithm in [2], which are the cut-analogue of [14]’s cut-matching game. This allows us to get Theorem 2.5. Afterwards, in Section 2.6 we describe a better way to deal with bottleneck cuts, by implementing a version of the refinement phase in near-linear time. This allows us to improve the quality of the resulting tree cut-sparsifier and get Theorem 2.4.

We now adapt [24] to the cut-sparsifier setting. As outlined in Section 2.3, our goal here is not to route the demand matrix $Q$ within $G$, but rather to ensure that $G$ respects $Q$. In this formulation, the analogue of a set $F$ of inter-cluster edges (within a cluster $S$) being flow-linked in [24] is that $G[S]$ respects the all-to-all demand matrix between edges of $F$, or equivalently that $F$ expands in $G[S]$ (see Definition 3.2 below). Therefore, our first goal is to obtain, efficiently, such a set $F$. For this step we ignore the boundary edges of $S$ (which may be separated by bottleneck cuts). We use the following algorithmic tool:

Following the naming of [12, 23], we call the partitioning algorithm from Section 2.5 the merge phase. Given a cluster $S$, it returns sub-clusters ${\{S_i\}}_{i=1}^t$ such that the inter-cluster edges $F$ expand, and such that we can route from $F$ to the boundary $B=E(S,V\setminus S)$. It does not, however, make $F$ and $B$ expand together. Thus the demand placed on $B$ may be non-uniform, so source and target demands need not cancel as they move up the hierarchy. This causes the extra $O(\log n)$ loss in Theorem 2.5.

To prove Theorem 2.4, Section 5 inserts a near-linear-time refinement phase after each merge step. Given a cluster $S$, the refinement phase partitions it into sub-clusters $\{S_1,\mathrm{\dots },S_t\}$ such that each sub-cluster respects the all-to-all flow problem on its boundary edges, and such that the inter-cluster edges of the refinement partition can be routed to the boundary of $S$. This is a variant of the precondition of [7] and the requirement of [12, 23]. The algorithm again uses [2]: on the current sub-cluster, it either certifies expansion of the boundary edges, or finds a balanced sparse cut with respect to the boundary measure, together with a routing from the cut edges to the boundary of one side. Unlike the merge phase, refinement does not guarantee a constant factor shrinkage, and may even return the trivial partition $\{S\}$.

The resulting hierarchy alternates between merge steps, which shrink clusters, and refinement steps, which make boundary demand uniform. After refinement, since each resulting sub-cluster $S_i$ is a node of $T$ and $Q$ is $1$-respected by $T$, the total demand leaving $S_i$ is at most $|E(S_i,V\setminus S_i)|$. Redistributing this demand uniformly over the boundary therefore leaves load of at most $1$ per boundary edge. Hence each merge step starts with constant boundary load, rather than with load accumulated from lower levels. Thus, we may set $\mathrm{\tau }=1$ in the merge phase, reducing its total contribution from $O({\log }^{3}n)$ to $O({\log }^{2}n)$. The refinement contribution is bounded, by adapting the analysis of [12, 23], by $O({\log }^{2}n\log \log n)$ over all sub-clusters. This proves Theorem 2.4. By Claim 2.7, the same tree is also a flow-sparsifier of quality $O({\log }^{3}n\log \log n)$, giving Theorem 2.8.

When $\mu ={\mathrm{𝟙}}_X$ is an indicator measure, $A$ $\alpha$-expands with respect to ${\mathrm{𝟙}}_X$ iff $A\cap X$ $\alpha$-expands in $G$. This is the cut-analogue of $A$ being $\alpha$-flow-linked when each $v\in A$ injects $\mu (v)$ units of flow [24].

The next remark bridges the two viewpoints introduced in Definitions 2.2 and 3.2: the notion of a set $A$ that $\alpha$-expands with respect to a measure $\mu$, and the notion of a graph $G$ that $\alpha$-respects a corresponding demand matrix defined by $\mu$.

The following is a recent result of [2], which generalizes [1]. They show that in near-linear time we can get a balanced sparse cut, or certify that a large part of the graph is an expander, with respect to a general vertex measure.⁶⁶6Theorem 3.4 requires that $\mu (v)$ will be in $[\frac{1}{\mathrm{poly}(n)},\mathrm{poly}(n)]\cup \{0\}$, which will hold for our usages.

When we describe the solution to a multi-commodity flow problem, it is useful to talk about intermediate stages of the flow. Analogously, to show that a graph respects a demand matrix, we use intermediate demand states: vertices hold positive or negative mass of each commodity, which is moved according to demand matrices and may cancel when opposite signs of the same commodity meet. These movements incur congestion for flows, or charge in our cut-sparsifier analysis.

As explained below in Remark 3.8, demand states generalize demand matrices. Unlike demand matrices (see Definition 2.1), where each vertex serves as the source of its own commodity and source-sink pairs are explicitly encoded in the matrix, in a demand state the commodities are independent of the vertices, and multiple vertices may act as sources of the same commodity (similarly, the same vertex may act as a source of multiple commodities).

Intuitively, we think of a demand state as the current state of mass residing at the vertices of the graph, where positive and negative demands “await” to be canceled-out, while a multi-commodity flow problem and its demand matrix describe an explicit movement of mass between pairs of vertices.

Throughout the paper we manipulate many demand states that are not themselves valid. Such demand states typically arise by restricting a valid demand state to a subgraph (or cluster), that is, by retaining only the demand vectors associated with vertices in the cluster. Although these restricted demand states may violate the validity condition, this poses no issue: they should be viewed as a partial or intermediate collection of demand vectors.

The following fact, which we use extensively, is a direct consequence of Definitions 3.7 and 3.9:

Suppose we have a demand state $P$. Given a demand matrix $Q$ (recall Definition 2.1), we can “move” the demand vectors in $P$ according to the requirements of $Q$. Each vertex $u\in V$ will send $Q(u,v)$ units in total to $v\in V$, and we split the demands evenly according to the distribution of commodities in the demand vector $P(u)$. In other words, $\frac{P(u,k)}{{\Vert P(u)\Vert }_1}\cdot Q(u,v)$ units of commodity $k\in 𝒦$ will be shipped to $v$. If this corresponds to shipping units of commodity $k$ from $v$ to $u$. This results in a demand state $P^{\uparrow Q}$, called the updated demand state:

We make frequent use of the following fact. It states that because we only move the mass around, no mass of any commodity is created or destroyed. This means that the total mass of each commodity is the same in $P$ and $P^{\uparrow Q}$, so it is zero in $P-P^{\uparrow Q}$. Therefore, $P-P^{\uparrow Q}$ is a valid demand state. The full proof is given in the full version of the paper.

The next lemma presents two basic types of demand-state updates that will be used extensively throughout the analysis. The first corresponds to uniformly redistributing mass within a set, and the second to pushing all mass out of a set. Both updates arise frequently when we manipulate demand states.

In this subsection we describe the general framework for moving demands in $G$ according to a given hierarchical tree. The tree is used only as a blueprint: the movement of demands takes place in the graph $G$, while the laminar structure of the tree determines the order in which demand is moved from lower-level clusters to higher-level clusters. We also introduce a useful invariant for analyzing such bottom-up demand-movement processes. This invariant will be used throughout the paper to control the load (total demand) placed on split nodes.

The following claim is our main tool to show that $T$ is a tree cut-sparsifier.

We prefer to work with demand states instead of demand matrices. To this end, we use the following Corollary:

Let $T$ be a hierarchical tree of $G$ (see Remark 2.6), and let $P$ be a valid demand state that is $1$-respected by $T$, and a cut $(U,W)$ of $G$. We will compare ${\mathrm{dem}}_P(U,W)$ with the demand created by the bottom-up demand-state process in the subdivision graph.

Let $G^{\prime }=(V^{\prime },E^{\prime })$ be the subdivision graph of $G$ (Recall Definition 3.1). The cut $(U,W)$ in $G$ induces the cut $(U^{\prime },W^{\prime })$ in $G^{\prime }$, where $U^{\prime }:=U\cup \{x_e\mid e\cap U\ne \mathrm{\varnothing }\}$ and $W^{\prime }:=V^{\prime }\setminus U^{\prime }$. Each edge of $G$ crossing $(U,W)$ contributes exactly one edge crossing $(U^{\prime },W^{\prime })$ in $G^{\prime }$, and no other edge contributes. Thus ${\mathrm{cap}}_{G^{\prime }}(U^{\prime },W^{\prime })={\mathrm{cap}}_G(U,W)$.

We first split $P$ to a set of demand states ${\{P_{{\{v\}}^{\prime }}\}}_{v\in V}$, where for each vertex $v\in V$, $P_{{\{v\}}^{\prime }}$ is supported on ${\{v\}}^{\prime }$. For each $v\in V$, we construct $P_{{\{v\}}^{\prime }}$ by first placing the demand of $v$ at the vertex $v$ itself, namely $P_{{\{v\}}^{\prime }}(v)=P(v)$, while setting $P_{{\{v\}}^{\prime }}(x_e)=0$ for every split node $x_e$ adjacent to $v$. We then evenly distribute this demand among the split nodes corresponding to edges incident to $v$: for every such edge $e$, we set $P_{{\{v\}}^{\prime }}(x_e)=\frac{1}{{\mathrm{deg}}_G(v)}P(v)$, and set $P_{{\{v\}}^{\prime }}(v)=0$. Observe that ${\Vert P(v)\Vert }_1={\mathrm{dem}}_P(\{v\},V\setminus \{v\})\le {\mathrm{cap}}_G(\{v\},V\setminus \{v\})={\mathrm{deg}}_G(v)$, where the inequality is due to the fact that $\{v\}$ is a cluster in $T$ and that $P$ is $1$-respected by $T$. In particular, each split node $x_e$ has a total load of at most $1$: ${\Vert P_{{\{v\}}^{\prime }}(x_e)\Vert }_1=\frac{1}{\mathrm{deg}(v)}{\Vert P(v)\Vert }_1\le 1$. Each non-split vertex of $V$ has load of $0$.