Traffic-Oblivious Multi-Commodity Flow Network Design

We present the MMCFS problem, which has both a natural formulation and practical applicability. After discussing related problems from literature in Section 2, we give some structural results in Section 3: We show how the MMCFS problem, even though it is traffic-oblivious in nature, can be reformulated to consider a specific single “hardest” traffic matrix. We also establish how an MCFcan be routed in an optimal MMCFS solution, and how the ratio between the values of a feasible MMCFS solution and an optimal one relates to their average edge capacities. In Section 4, we prove that MMCFS is NP-hard already with unit edge capacities. Additionally, we show that it is NP-hard (and a closely related problem cannot be approximated within a sublogarithmic factor) already on directed acyclic graphs (DAGs). Our most important contribution is given in Section 5, where we present a $\max (1/\alpha ,2)$-approximation algorithm for MMCFS: after modelling MMCFS as an ILP, we can deduce a surprisingly simple LP-rounding scheme, whose complexity is solely shifted to the correctness proof. Moreover, we show that our analysis of this algorithm is tight.

Let $C≔\lceil \frac{2\beta }{1-\beta }\rceil$ be a (high) edge capacity value and $k>\sqrt{\frac{C}{\alpha }}$ a number of vertices. Construct $G=(V,E)$ (visualized in Figure 1) as follows: Create two vertex sets $X$ and $Y$ with $k$ vertices each, as well as two distinct vertices $z_1,z_2$, and let $V≔X\cup Y\cup \{z_1,z_2\}$. Moreover, let $E_{XY}≔X\times Y$, $E^{\prime }≔(X\times \{z_1\})\cup \{z_1{z}_2\}\cup (\{z_2\}\times Y)$, and $E≔E_{XY}\cup E^{\prime }$. Edge capacities and the traffic matrix are chosen as follows:

Every non-zero demand $T(u,v)$ can be routed in $(G,\text{cap})$ using the respective edge $uv\in E_{XY}$.

The only optimal MCPS-solution of $(G,\text{cap},\beta )$ is $E^{\prime }$: For every vertex pair $(u,v)\in E^{\prime }$, the only $u$-$v$-path in $G$ is the one consisting of the edge $uv$ – so the edges $E^{\prime }$ must be in the solution. $E^{\prime }$ also establishes a maximum flow of sufficient value for the remaining vertex pairs. In particular, for every vertex pair $(u,v)\in X\times Y$, there exists a maximum $u$-$v$-flow of value $C$ in $E^{\prime }$, which is at least $\beta$ times the value $(C+1)$ of a maximum $u$-$v$-flow in $E$:

However, the scaled matrix $\alpha \cdot T$ is not routable in $E^{\prime }$: $|X|\cdot |Y|=k^2>\frac{C}{\alpha }$ many demands of value $\alpha$ would have to be routed over the single edge $z_1{z}_2$, exceeding its capacity $C$. $◀$

Lastly, we want to highlight similarities of MMCFS to the well-established NP-hard Minimum Equivalent Digraph (MED) problem [2, 37, 21, 27], where, given a digraph $G$, one asks for the edge-wise minimum subgraph of $G$ that preserves the reachability relation of $G$. In Section 4, we show that MED is a special case of MMCFS. Further, we observe:

In any simple DAG $G$, the MEDis unique and consists of exactly those edges $st$ for which there is no $s$-$t$-path in $G-st$ [2]. A feasible MMCFS solution must also contain these edges $st$ in order to allow for a non-zero amount of flow from $s$ to $t$. $◀$ However, in general digraphs, a feasible MMCFS solution may not always contain the MED, see Figure 2. Note that MED is not only polynomial-time solvable on DAGs, but there are also several polynomial approximation algorithms for general graphs [29, 45] with the currently best approximation ratio being 1.5 [11, 42].

${𝕋}_E$ is routable in $E$ by definition. If every traffic matrix routable in $E$ is also routable in $A$ when scaled down by $\alpha$, then so is $\alpha \cdot {𝕋}_E$. For the other direction, consider any arbitrary traffic matrix $T$ routable in $E$. Let $\{f_{s,t}^T\mid (s,t)\in V^2\}$ be the MCFthat routes $T$ in $E$ with the vector ${𝐟}^T≔{\sum }_{(s,t)\in V^2}{f}_{s,t}^T$ specifying the total flow over each edge. Using this MCF, we can construct a new traffic matrix $T^{\prime }$:

Observe that $T^{\prime }\le {𝕋}_E$ when using component-wise comparison. Thus, since $\alpha \cdot {𝕋}_E$ is routable in $A$, so is $\alpha \cdot T^{\prime }$. But if $\alpha \cdot T^{\prime }$ is routable in $A$ using the flows $\{f_{u,v}^{\alpha \cdot T^{\prime }}\mid (u,v)\in V^2\}$, then $\alpha \cdot T$ is also routable in $A$ using the flows $\{f_{s,t}^{\alpha \cdot T}\mid (s,t)\in V^2\}$ constructed as follows: for each commodity $st\in E$ and each edge $uv\in E$, calculate the fraction of flow routed over $uv$ that is used by $f_{s,t}^T$, and route this fraction over the path chosen by $f_{u,v}^{\alpha \cdot T^{\prime }}$. In short,

$◀$

We note that a related but slightly different concept to Theorem 3 has been implicitly used previously in [35] (on undirected graphs). From this point onwards, we may refer to edges as commodities since ${𝕋}_E$ specifies a non-zero demand precisely for the edges in $E$. Moreover, given a flow $f_{\tilde{e}}$ for a commodity $\tilde{e}\in E$, we call $f_{\tilde{e}}(\tilde{e})$ the direct flow for $\tilde{e}$. We observe that in an optimal MMCFS solution $A$, for every commodity $\tilde{e}\in A$, the demand ${𝕋}_E(\tilde{e})$ can always be fully satisfied by a direct flow $f_{\tilde{e}}(\tilde{e})$:

Among all MCFsthat witness the routability of $T$ in $A$, let ${ℱ}^{\prime }=\{f_{s,t}^{\prime }\mid (s,t)\in V^2\}$ be one with a maximum sum of direct flow values ${\sum }_{\tilde{e}\in E}{f}_{\tilde{e}}^{\prime }(\tilde{e})$.

We give a proof by contradiction: Assume that there exists an edge $e^{\prime }=uv\in A$ such that (if no such edge exists, $ℱ={ℱ}^{\prime }$ and we are done). There must exist at least one alternative $u$-$v$-path $P$ that routes at least some of the remaining demand $T(e^{\prime })-f_{e^{\prime }}^{\prime }(e^{\prime })$. Further, the edge $e^{\prime }$ has residual capacity $\text{cap}(e^{\prime })-{\sum }_{(s,t)\in V^2:}{f}_{s,t}^{\prime }(e^{\prime })=0$ as otherwise we could increase $f_{e^{\prime }}(e^{\prime })$ (and decrease flow along $P$ accordingly), which would contradict the selection of ${ℱ}^{\prime }$. Thus, there exists an edge $e^{\prime \prime }\in E$, $e^{\prime \prime }\ne e^{\prime }$, with $f_{e^{\prime \prime }}(e^{\prime })>0$. But then, we can exchange a non-zero amount $\epsilon >0$ of flow of commodity $e^{\prime }$ routed over $P$ with an equally small amount of flow of commodity $e^{\prime \prime }$ routed over $e^{\prime }$. This increases $f_{e^{\prime }}^{\prime }(e^{\prime })$ without decreasing any other direct flow value – again a contradiction to the selection of ${ℱ}^{\prime }$. $◀$

Further, for any edge set $A$, we can compare its total edge capacity ${\sum }_{e\in A}\text{cap}(e)$ to the total flow needed to satisfy the demands ${𝕋}_E$. This not only gives us a necessary condition for an edge set $A$ to be a feasible MMCFS solution, but, upon closer analysis, also allows us to relate its quality as a solution to its mean capacity $\overline{{\text{cap}}_A}≔\frac{1}{|A|}\cdot {\sum }_{e\in A}\text{cap}(e)$. The following results apply both in the case of simple and non-simple graphs, but we can give better guarantees in the former case.

Let $X≔A\setminus O$, and $Y≔A\cap O$. The commodities of all $\tilde{e}\in O$ must be routed through $O$, requiring a total flow of at least $\alpha {\sum }_{e\in O}\text{cap}(e)$ and leaving a total remaining capacity in $O$ of at most $(1-\alpha ){\sum }_{e\in O}\text{cap}(e)$. Every commodity ${\tilde{e}}^{\prime }\in X$ has to be routed within this remaining capacity since $O$ is feasible. This requires a total flow of at least $\theta \alpha {\sum }_{e\in X}\text{cap}(e)$; the $\theta$ is due to the fact that without parallel edges each such commodity ${\tilde{e}}^{\prime }$ must be routed over at least two other edges in $O$ since ${\tilde{e}}^{\prime }\notin O$. We thus have

By adding $\theta \alpha {\sum }_{e\in Y}\text{cap}(e)\le \theta \alpha {\sum }_{e\in O}\text{cap}(e)$ to this inequality, we obtain

Alternatively, we can rewrite inequality (1) as $\theta \alpha \cdot |X|\cdot \overline{{\text{cap}}_X}\le (1-\alpha )\cdot |O|\cdot \overline{{\text{cap}}_O}$ and obtain

$◀$

This ratio is met, e.g., on a bundle of parallel edges with $\mathrm{\ell }≔(\frac{1}{\alpha }-1)\cdot k$ capacity-1 edges and one capacity-$k$ edge (for any given $\alpha \in {\mathbb{Q}}_{(0,1)}$ and an arbitrary $k\in \mathbb{Q}$ s.t. $\mathrm{\ell }\in \mathbb{N}$).

An optimal solution $A\subseteq E$ for an MMCFS instance $(G,\text{cap},\alpha )$ with unit edge capacities is an edge set of minimum cardinality such that the demands $\alpha \cdot {𝕋}_E(s,t)=\alpha \cdot \text{cap}(st)\le \frac{1}{|E|}$ for each edge $st\in E$ are routable in $A$. This is equivalent to ensuring that there exists an $s$-$t$-path in $A$ for every edge $st\in E$ since the (unit) capacity of an edge can never be surpassed by the $|E|$ many flows of size at most $\frac{1}{|E|}$ each. $◀$

Moreover, we can show that MMCFS is NP-hard already on DAGsusing a reduction from the NP-hard decision variant of Set Cover [27], where one asks: given a universe $U$, a family of sets $𝒮={\{S_i\subseteq U\}}_{1\le i\le k}$ with $k\in 𝒪(\text{poly}(|U|))$, and a parameter $\phi$, is there a subfamily $𝒞\subseteq 𝒮$ of cardinality $|𝒞|\le \phi$ such that ${\bigcup }_{S\in 𝒞}S=U$? The reduction is similar to that given in [15] to prove the NP-hardness of the Minimum Capacity-Preserving Subgraph problem.

Given a Set Cover instance $(U,𝒮,\phi )$ and a fixed retention ratio $\alpha \in (0,1)$, we construct an instance $I=(G=(V,E),\text{cap},\alpha ,\psi )$ for the decision variant of MMCFS: $I$ is a yes-instance if and only if there exists a feasible MMCFS solution $E^{\prime }\subseteq E$ for $(G,\text{cap},\alpha )$ with cardinality $|E^{\prime }|\le \psi$. We construct $I$ as follows (see Figure 3 for a visualization):

As $G$ is a DAG, its MEDis unique [2] and must be part of any feasible MMCFS solution, see Section 2. This MEDis formed by the edges $e\in E_1$; a flow of $\alpha$ must be routed over each of them in order to satisfy the demands ${𝕋}_E(e)=\alpha \cdot \text{cap}(e)$. The remaining capacity for each edge $e\in E_1$ is $1-\alpha$.

So consider a single set $S\in 𝒮$ and the corresponding two-path $\{v_S{z}_S,z_{S}t\}\in E_1$, whose remaining capacity can thus accommodate either arbitrarily many item commodities ${\tilde{e}}_U\in E_U$ (each one with the sufficiently small demand ${𝕋}_E({\tilde{e}}_U)=\alpha \cdot \epsilon$) or a single set commodity ${\tilde{e}}_{𝒮}\in E_{𝒮}$ (with the demand $\alpha \cdot {𝕋}_E({\tilde{e}}_{𝒮})=\alpha \cdot \frac{1-\alpha }{\alpha }=1-\alpha$). In the former case, we can remove at least two corresponding item edges $v_{u}t$, $v_u^{\prime }t$ with $u\in S$, which is more than the single corresponding set edge $v_{S}t$ we can remove in the latter case. Thus, for each item commodity $v_{u}t\in E_U$, an optimal MMCFS solution must contain one of the corresponding set edges $\{v_{S}t\mid S\ni u\}\subseteq E_{𝒮}$; the item commodity can then be routed over the path from $v_u$ over $v_S$ to $t$.

Given a Set Cover solution $𝒞$ with $|𝒞|\le \phi$, we can construct an MMCFS solution $E^{\prime }=E_1\cup \{v_{S}t\in E_{𝒮}\mid S\in 𝒞\}$ with cardinality $|E^{\prime }|=|E_1|+|𝒞|\le |E_1|+\phi =\psi$. Since every item is covered by the sets in $𝒞$, the constructed MMCFS solution includes at least one corresponding set edge for each item, ensuring its feasibility. Conversely, since a feasible MMCFS solution $E^{\prime }$ with $|E^{\prime }|\le \psi$ has at least one corresponding set edge for each item $u\in U$, the Set Cover solution $𝒞=\{S\mid v_{S}t\in E_{𝒮}\cap E^{\prime }\}$ also contains at least one covering set for each item. Moreover, $|𝒞|=|E^{\prime }|-|E_1|\le \psi -|E_1|=\phi$. $◀$

Considering the optimization variants of Set Cover and MMCFS (and thus ignoring the additional input values $\phi$ and $\psi$), the reduction above also implies the inapproximability of the number of edges in an optimal MMCFS solution beyond the edges required for an MED: Consider an instance $I=(G=(V,E),\text{cap},\alpha )$ for the optimization variant of MMCFS that is produced by the reduction above, and an arbitrary feasible solution $A\subseteq E$ for this instance. Let $\mu (I,A)≔|A|-\text{med}(G)$ where $\text{med}(G)$ denotes the number of edges in an MEDof $G$. Then, $A$ can be transformed into a feasible solution for the original Set Cover instance with objective value $\mu (I,A)$ in linear time. Further, let $\mu (I)$ be the minimum $\mu (I,A^{\prime })$ over all feasible solutions $A^{\prime }$ for $I$, and recall that the size $|E|$ of the MMCFS instance $I$ is linear in the size $N\in 𝒪(\text{poly}(U))$ of the Set Cover instance: if it was possible to approximate $\mu (I)$ within a factor in $o(\log |E|)=o(\log |U|)$, one could also approximate Set Cover within $o(\log |U|)$, which is NP-hard [17, 33]. This implies that any approximation algorithm for MMCFS (such as the one we present in Section 5) must leverage the existence of a comparatively high number of MED-edges in order to achieve its approximation ratio.

Let $H≔\{e\in E\mid x_e^{\ast }=1\}$ be the $h$ many edges that are saturated by the fractional multi-commodity flow, and $L≔\{e\in E\mid x_e^{\ast }\in (0,\alpha )\}$ with $\mathrm{\ell }≔|L|$ the edges that are only used to a fraction less than $\alpha$; in short, edges with high and low corresponding $x^{\ast }$-values. We show that an optimal fractional solution $x^{\ast }$ with $\mathrm{\ell }>h$ would allow us to construct a vector $p\in {\mathbb{Q}}^{|E|}$ such that both $(x^{\ast }+p)$ and $(x^{\ast }-p)$ are still feasible solutions for the LP relaxation – thus, $x^{\ast }$ would not be basic.

For every edge $e=st\in L$, let $P_e$ denote an arbitrary alternative $s$-$t$-path not using the edge $e$ and $f_e(e^{\prime })>0$ for all edges $e^{\prime }\in P_e$. Such a path must exist since at most flow is routed over $e$, so an alternative $s$-$t$-path is necessary to satisfy the demand $\alpha \cdot {𝕋}_E(s,t)=\alpha \cdot \text{cap}(e)$. Further, the total cost of routing a unit of flow over $P_e$ must be lower than or equal to the cost of routing it over $e$ itself, i.e., ${\sum }_{e^{\prime }\in P_e}\frac{1}{\text{cap}(e^{\prime })}\le \frac{1}{\text{cap}(e)}$, by the optimality of $x^{\ast }$. Based on the alternative paths, we construct a matrix $M\in {\{0,1\}}^{\mathrm{\ell }\times h}$ indexed by pairs $(e,e^{\prime \prime })\in L\times H$, with $M(e,e^{\prime \prime })≔1\text{if}{e}^{\prime \prime }\in P_e,\text{and}0\text{otherwise}$. Since $\mathrm{\ell }>h$, the $\mathrm{\ell }$ rows of $M$ must be linearly dependent, i.e., there exists a vector of coefficients $q\in {\mathbb{Q}}^{\mathrm{\ell }}$ with $q\ne \mathrm{𝟎}$, such that $q^{\top }\cdot M=\mathrm{𝟎}$ (and consequently, $-q^{\top }\cdot M=\mathrm{𝟎}$).

We can obtain two new feasible solutions by modifying the MCFcorresponding to the optimal basic solution $x^{\ast }$ as follows: for each edge $e\in L$, and using a small positive value $\epsilon \in \mathbb{Q}$, we send $\epsilon \cdot q(e)$ less flow over $e$ itself and $\epsilon \cdot q(e)$ more flow over the alternative path $P_e$ – or vice versa. Put formally, we argue that for a small enough $\epsilon >0$, the following vector $p\in {\mathbb{Q}}^{|E|}$ yields two feasible solutions $(x^{\ast }+p)$ and $(x^{\ast }-p)$ for the LP relaxation:

Clearly, the two solutions satisfy all demands and flow preservation constraints (1.b). Consider the capacity constraints (1.c): By construction of $q$, the flow difference on saturated edges is 0. For all non-saturated edges $e^{\prime }$ it holds: if we modified the flow routed over $e^{\prime }$, this flow was already non-zero before our modification, and $\epsilon$ can be chosen sufficiently small such that the flow will neither turn negative nor surpass $\text{cap}(e^{\prime })$.

It remains to show that $p\ne \mathrm{𝟎}$ given that $q\ne \mathrm{𝟎}$. So, among the edges $e\in L$ with $q(e)\ne 0$, choose one with maximum cost $\frac{1}{\text{cap}(e)}$ and denote it by $e_{\max }$. We show that $p(e_{\max })\ne 0$.

If $e_{\max }$ were contained in any of the alternative paths $P_e$ with $e\in L$ and $q(e)\ne 0$, we would arrive at a contradiction even without using $p$: Recall that ${\sum }_{e^{\prime }\in P_e}\frac{1}{\text{cap}(e^{\prime })}\le \frac{1}{\text{cap}(e)}$. So we must have $|P_e|=1$, i.e., $e$ and $e_{\max }$ are parallel edges with $\text{cap}(e)=\text{cap}(e_{\max })$. Since $e,e_{\max }\in L$ and thus $x_e^{\ast },x_{e_{\max }}^{\ast }\in (0,\alpha )$, we could simply obtain two new solutions by shifting some small $\epsilon >0$ of flow from one to another, or vice versa, contradicting that $x^{\ast }$ is basic.

Hence, $e_{\max }$ is only contained in alternative paths $P_e$ with $e\in L$ s.t. $q(e)=0$, and

$◀$

The proof implicitly gives an intuitive explanation for the distribution of LP values:

Assume that, for some edge $e=st$ with $x_e^{\ast }\in (0,\alpha )$, there is a $P_e$ that does not contain an edge $e^{\prime \prime }$ with $x_{e^{\prime \prime }}^{\ast }=1$. Then, we can follow the proof of Section 5, choosing $P_e$ as the alternative $s$-$t$-path for $e$. As a result, the matrix $M$ constructed in the proof contains a row of zeroes, allowing us to route $\epsilon$ more flow over $e$ and $\epsilon$ less flow over $P_e$, or vice versa. Thus, $x^{\ast }$ cannot be basic, a contradiction. $◀$

We now analyze the following LP-rounding algorithm: compute a basic optimal solution $x^{\ast }$ for the relaxation of ILP (1) in polynomial time, and return the edge set $\{e\in E\mid x_e^{\ast }>0\}$. Based on Section 5, one could use naïve techniques to prove approximation guarantees of $(2+\frac{1}{\alpha })$ or $\frac{2}{\alpha }$ for this algorithm. However, we provide the stronger bound of $\max (1/\alpha ,2)$ based on the following intuition: the algorithm either “misses” the optimal solution mainly due to edges with $x_e^{\ast }\in (0,\alpha )$ and we can obtain a 2-approximation via Section 5, or due to edges with $x_e^{\ast }\in [\alpha ,1)$ and we can round up the variables for a $\frac{1}{\alpha }$-approximation.

The solution $A$ is clearly feasible. Let $z≔|A|$ be the number of edges $e$ such that $x_e^{\ast }>0$. Furthermore, let $\mathrm{\Delta }=|\{e\in E\mid x_e^{\ast }\in [\alpha ,1)\}|$ be the number of these $z$ edges whose $x^{\ast }$-variable is set to a value in the interval $[\alpha ,1)$. We know that the remaining $(z-\mathrm{\Delta })$ edges have a $x^{\ast }$-variable either set to $1$ or a value lower than $\alpha$. In particular, by Section 5, there exist at least as many edges $e^{\prime }$ with $x_{e^{\prime }}^{\ast }=1$ as there are edges $e^{\prime \prime }$ with $x_{e^{\prime \prime }}^{\ast }\in (0,\alpha )$. Thus, $|\{e\in E\mid x_e^{\ast }=1\}|\ge \frac{z-\mathrm{\Delta }}{2}$. Hence, the optimal fractional solution $x^{\ast }$ has objective value

Using the minimum fractional objective value $z^{\ast }$ as a lower bound for the minimum integral objective value $z_{\mathrm{𝑖𝑛𝑡}}^{\ast }$, we can then give an upper bound for the approximation ratio:

To obtain an upper bound on this ratio, we examine when its denominator is at its minimum. For $\alpha \ge \frac{1}{2}$, the term $(\alpha -\frac{1}{2})\cdot \frac{\mathrm{\Delta }}{z}$ is always non-negative and reaches its lowest value 0 when $\mathrm{\Delta }=0$, giving us the upper bound $2\ge r$ in this case. In contrast, for , the term $(\alpha -\frac{1}{2})\cdot \frac{\mathrm{\Delta }}{z}$ is negative, and the minimum of the denominator is reached when $\mathrm{\Delta }=z$, leading to the upper bound $\frac{1}{\alpha }\ge r$ in this second case. $◀$

It is surprisingly hard to find instances (in particular, ones without parallel edges) where the worst-case approximation ratio given by Theorem 14 is actually met. However, we show that such instances exist for the most relevant $\alpha \in (0,1)$, and hence our analysis is tight:

Consider a complete bidirected graph $G=(V,E)$ on $q+1$ vertices, and let $H\subset G$ denote an arbitrarily chosen directed Hamiltonian cycle in $G$ (an example for $q=4$ is visualized in Figure 4). For all edges $st\in E$, let $\eta (st)$ denote the number of edges of the unique $s$-$t$-path in $H$ and set the capacity $\text{cap}(st)≔\frac{1}{\eta (st)}$. $E(H)$ is a feasible integral solution for the MMCFS instance $(G,\text{cap},\alpha )$ since the demands $\alpha \cdot {𝕋}_E$ are routable in it: A single edge $e\in H$ is able to satisfy its own demand $\alpha \cdot \text{cap}(e)=\frac{1}{q}\cdot 1$. Adding to this, for every $i\in \{2,\mathrm{\dots },q\}$, there are $i$ edges $uv\in E\setminus E(H)$ with $\eta (uv)=i$ whose unique $u$-$v$-path in $H$ contains $e$. The edge $e$ can accommodate all of these commodities $uv$ because each of them has a demand of $\alpha \cdot \text{cap}(uv)=\frac{1}{q}\cdot \frac{1}{i}$, summing up to a total flow of ${\sum }_{i=1}^{q}i\cdot \frac{1}{i}\cdot \frac{1}{q}=1\le \frac{1}{\text{cap}(e)}$. Lastly, $E(H)$ is not only feasible but optimal since we need at least $|E(H)|$ many edges to preserve the reachability relation of $G$ in $H$.

The algorithm from Theorem 14 would potentially choose all edges of $G$, i.e., $|E|=(|V|-1)\cdot |V|=q\cdot |E(H)|=\frac{1}{\alpha }\cdot |E(H)|$ many: As the cost $\frac{1}{\text{cap}(uv)}=\eta (uv)$ of an edge $uv\in E\setminus E(H)$ is equal to the total cost of its unique $u$-$v$-path in $H$, all $u$-$v$-paths are equal in cost. Thus, one optimal solution for the relaxation of ILP (1) simply routes all commodities $\tilde{e}\in E$ completely over their own edges $\tilde{e}$ and chooses $x_{\tilde{e}}^{\ast }=\alpha$. This solution is also basic: Let $f$ denote the flow variables of this solution. If it were not basic, there would exist two other optimal solutions with flow variables $f^{\prime },f^{\prime \prime }$ respectively, such that for some $\tilde{e},e\in E$, . However, if $e=\tilde{e}$, $f$ already routes the full demand of commodity $\tilde{e}$ over $e$ and we cannot increase $f_{\tilde{e}}(e)$ without introducing a flow cycle, which would raise the objective value and thus be suboptimal. In contrast, if $e\ne \tilde{e}$, $f_{\tilde{e}}(e)$ is already $0$ and cannot be decreased. $◀$

We construct a family of MMCFS instances (visualized in Figure 5), each one consisting of a simple graph $G=(V,E)$ with edge capacities cap and the given retention ratio $\alpha$, that meets the approximation ratio of 2 asymptotically with increasing size. Intuitively, the edge set of each instance contains two subsets that have a size quadratic in the number of vertices and two subsets of linear size; our algorithm chooses both quadratic-size subsets even though one could be replaced by a linear-size subset.

Let $V$ be comprised of five disjoint vertex sets $X$, $Y$, $Z$, $U$, $W$ with $k\in \mathbb{N}$ vertices each (respectively named with the corresponding lowercase letter and indexed by $i\in \{1,\mathrm{\dots },k\}$) and a distinct vertex $v$. Further, let $\epsilon \le \frac{1-\alpha }{k\cdot \alpha }$ and $B\ge \frac{k\cdot \epsilon }{1-\alpha }$ be sufficiently low and high positive values, respectively. Then, $E≔E_v\cup E_{XZ}\cup E_1\cup E_B$ with

$G$ is a DAG, thus its MEDis unique [2] and must be part of any feasible solution for the MMCFS instance $(G,\text{cap},\alpha )$, see Section 2. The MEDof $G$ consists of the edges $E_1\cup E_B$ and in particular can satisfy all demands $\alpha \cdot {𝕋}_E(e)=\alpha \cdot \text{cap}(e)$ with $e\in E_1\cup E_B$. The “remaining” capacity of $1-\alpha$ for each of the edges in $E_1$ (and $(1-\alpha )\cdot B$ for edges in $E_B$) is also sufficient to satisfy the demands $\alpha \cdot {𝕋}_E(e_v)$ of the commodities $e_v\in E_v$, and to almost satisfy the demands $\alpha \cdot {𝕋}_E(e_{XZ})=1-\alpha +\epsilon$ for the commodities $e_{XZ}\in E_{XZ}$: it only leaves a demand of $\epsilon$ for every such $e_{XZ}$. Thus, there exists a feasible solution $E_1\cup E_B\cup E_v$ for $(G,\text{cap},\alpha )$ that contains all of the $k^2+5k$ edges from $E_1\cup E_B$ and additionally, to satisfy the remaining demands (of size $\epsilon$ each), the $2k$ edges from $E_v$. This feasible solution gives an upper bound on the objective value $z_{\mathrm{𝑖𝑛𝑡}}^{\ast }$ of the optimal integral solution: $z_{\mathrm{𝑖𝑛𝑡}}^{\ast }\le k^2+7k$.