Pinning on Tight Cuts: Improved Algorithm and Bounds for Unsplittable Multicommodity Flows in Outerplanar Graphs

In this work, we significantly improve the state-of-the-art capacity-violation bounds for the existence of an unsplittable flow in outerplanar graphs.

Let ${\alpha }_O>0$ be the smallest value such that every feasible instance with an outerplanar supply graph $G$ admits an unsplittable flow that exceeds the edge capacities by at most an additive amount of ${\alpha }_O{d}_{\max }$. Similarly, let ${\alpha }_{RL}$ denote the smallest associated value for ring-loading instances.

Prior work showed that $1.01\le {\alpha }_{RL}\le 1.5$ [22], which was ultimately improved to ${\alpha }_{RL}\le 1.3$ [7], and the lower bound ${\alpha }_{RL}\ge 1.1$ [26]. Since every cycle is an outerplanar graph, we have ${\alpha }_O\ge {\alpha }_{RL}$, and prior to our work, it was not known that the parameters ${\alpha }_O$ and ${\alpha }_{RL}$ are necessarily different.

Our first main result establishes that ${\alpha }_O\le 2$, improving on the bound of Alemán Espinosa and Kumar [2], who showed that ${\alpha }_O\le 2{\alpha }_{RL}+1\in [3.2,3.6]$. Our proof uses a more robust divide-and-conquer framework that treats the parameters of the instance more globally. We hope this approach to be useful for obtaining similar congestion bounds in other settings where the cut condition is sufficient, or approximately sufficient, for feasibility.

We complement this result by showing that ${\alpha }_O\ge \frac{4}{3}$.

Recall that previously, the only lower bound known on ${\alpha }_O$ was that ${\alpha }_O\ge {\alpha }_{RL}\ge 1.1$. Our improved lower bound in Theorem 2, together with the fact that ${\alpha }_{RL}\le 1.3$ [7], shows that the $\alpha$-parameters for ring-loading and outerplanar graphs are different, and concretely shows that outerplanar graphs are more difficult settings than ring-loading instances for multicommodity unsplittable flows.

Very recently, Alemán Espinosa, Kumar, Poremba, and Shepherd [3] showed that in the fully planar setting, defined by instances in which $G+H$ is planar, any feasible flow can be converted into an unsplittable flow that violates the edge capacities by at most $2d_{\max }$. They also showed that the additive congestion has to be at least $1.5d_{\max }$ in this setting. The authors in [3] also showed that when $G$ is series-parallel (i.e., $G$ does not contain a $K_4$ minor), any feasible flow can be converted into an unsplittable flow such that the flow on any edge is at most twice its capacity plus $7.2d_{\max }$.

The directed single-source setting has been extensively studied; see, e.g., [25, 17, 18, 28, 27], including work on minimum-cost variants. Recently, Majthoub Almoghrabi, Skutella, and Warode [16] studied a multicommodity setting in a special class of directed series-parallel graphs and showed that any fractional flow can be converted into an unsplittable flow of no larger cost, such that the flow values on each arc differ by at most $d_{\max }$.³³3We note that, as mentioned in [16] (see footnote on page 429 in [16]), that their results do not extend to the undirected (outerplanar) setting we consider here, nor the other way around.

Interestingly, and perhaps not surprisingly, all of these settings have the common feature that one can identify a simple structural property, called the cut-condition that is sufficient, or nearly-sufficient, to guarantee the existence of a feasible flow. This condition requires that, for every cut, the total demand separated by the cut is at most the total capacity of the supply edges crossing it. The cut-condition is always necessary for feasibility of a multicommodity flow instance (see, e.g., [21]), but it is not always sufficient, even for small graphs such as $G=K_{2,3}$ [19]. It is well known that the cut-condition is sufficient for the following instances:

1. (i)

   (Single-source setting) $G$ is arbitrary and $H$ is a star [9].

2. (ii)

   (Okamura-Seymour setting) $G$ is planar and $E(H)$ is incident to one face of $G$ [19].

3. (iii)

   (Outerplanar setting) $G$ is outerplanar and $H$ is arbitrary (special case of (ii)).

4. (iv)

   (Fully planar setting) $G+H=(V,E(G)\cup E(H))$ is planar [23].

Alemán Espinosa and Kumar [2] posed as an open problem whether every feasible Okamura–Seymour instance admits an unsplittable flow with additive congestion $O(d_{\max })$. Alemán Espinosa, Kumar, Poremba, and Shepherd [3] posed a more general question. Given a (supply graph, demand graph) pair $(G,H)$, the flow-cut gap of $(G,H)$ is the smallest value $\beta \ge 1$ such that, for all choices of capacities and demands, if every cut has capacity at least $\beta$ times the total demand it separates, then a feasible flow exists. For example, $\beta =1$ for the classes of instances (i)–(iv), it is known that $\beta =2$ for instances in which $G$ is series-parallel and $H$ is arbitrary [5, 14]. For instances in which $G$ is planar it is only known that $\beta \in [2,O(\sqrt{\log n})]$ [20, 14]. In contrast, for general graphs the flow-cut gap is known to be $\beta =\mathrm{\Theta }(\log k)$, where $k$ is the number of source-sink pairs [15, 4]. Alemán Espinosa, Kumar, Poremba, and Shepherd [3] posed the natural question of whether a flow-cut gap of $\beta$ for a class of instances implies the existence of an unsplittable flow that can be routed with capacities $O(\beta )u+O(d_{\max })$, or even $f(\beta )u+O(d_{\max })$ for some $f:{ℝ}_{\ge 0}\to {ℝ}_{\ge 0}$.

The sufficiency of the cut-condition for the outerplanar setting is used crucially in [2] and also in this work. Its approximate sufficiency for series-parallel graphs is used in [3], where the framework in [2] is carefully adapted to handle this setting. We build on the ideas in [2] and develop a more robust divide-and-conquer framework that treats the instance parameters more globally. We hope that this approach can be extended beyond the outerplanar setting, for example, to the significantly more intricate Okamura–Seymour setting $(ii)$, which is perhaps the most natural (intermediate) generalization.

Pinning a demand edge $h=(s,t)\in E(H)$ is a standard technique in (unsplittable) multicommodity flow problems. It subdivides $h$ into a sequence $(s,v_1),(v_1,v_2),\mathrm{\dots },(v_{\mathrm{\ell }},t)$ of demand edges, each with the same demand value, with the goal of transforming the instance into a more structured one. However, pinning can destroy feasibility: the resulting instance may not even admit a fractional flow. The algorithms of Dinitz et al. [8], Alemán Espinosa and Kumar [2], Majthoub Almoghrabi et al. [16], and Alemán Espinosa et al. [3] (for series-parallel graphs), perform pinnings in a controlled way so that an unsplittable flow exists, while incurring only an $O(d_{\max })$ additive capacity violation.

We first provide a high-level overview of the algorithm in [2] for outerplanar instances, which proceeds in two phases. In the first phase, it performs pinnings until every demand edge becomes parallel to a supply edge. They show that the cut-condition, and hence feasibility, can be preserved throughout this phase by increasing capacities by at most $2{\alpha }_{RL}{d}_{\max }$, where ${\alpha }_{RL}\le 1.3$ [7] is the ring-loading parameter. In the second phase, they compute an unsplittable flow greedily, exceeding capacities by an additional amount of $d_{\max }$. We say that an ear of $G$ is a path whose internal vertices have degree two, ignoring parallel edges. In each iteration of the first phase, their algorithm selects an ear $P=v_1,\mathrm{\dots },v_{\mathrm{\ell }}$ (with $\{v_1,v_{\mathrm{\ell }}\}\in E(G)$), and considers the set $H_P\subseteq E(H)$ of demand edges with at least one endpoint in $P$. Each demand $(v_i,w)\in H_P$ is then pinned along a subpath of $P$. The key observation in [2] is that all demands in $H_P$ can be pinned via a reduction to ring-loading, which preserves the cut-condition in the resulting instance, at the expense of increasing capacities on $E(P)+\{v_1,v_{\mathrm{\ell }}\}$ by an additive amount of ${\alpha }_{RL}{d}_{\max }$. After the pinnings along $P$ are made, a feasible flow is computed, and then each demand $(s,t)\in E(H)\cap E(G)$ and its corresponding $s$-$t$ flow are removed from the first phase. After this removal, $P$ can be treated as an edge that is parallel to $\{v_1,v_{\mathrm{\ell }}\}$ for the remaining demands $E(H)\setminus H_P$. A similar ring-loading reduction approach was implemented by Alemán Espinosa et al. [3] in order to contract the ears of series-parallel graphs, where the goal of the first phase is to pin the demands so that the resulting instance becomes fully planar (i.e., $G+H$ is planar).

The main drawback of this procedure is that we can not remove the ear $P$ after an iteration because the demands in $E(H)\setminus H_P$ may still require the residual capacity of $P$. This is not an issue in the outerplanar setting, but it becomes critical in, for example, an Okamura-Seymour instance $(G,u,H,d)$. For example, suppose that both endpoints of every demand edge lie on the unbounded face of $G$. Not being able to remove $P$ implies that one cannot pin the demands by using the inner nodes of $G$. If one makes such a pinning, then the resulting instance is no longer an Okamura-Seymour instance. Therefore, one can not get access to these inner nodes by relying on such a ring-loading reduction.

Our main technical contribution is to consider a tight cut $(S_1,S_2:=V(G)\setminus S_1)$, that is, a cut whose capacity equals the demand it separates, instead of an ear of $G$. We then solve a smaller instance that allows us not only to pin the demands in ${\delta }_H(S_1)$ on the cut, but also to fix their unsplittable routing on ${\delta }_G(S_1)$. This yields another smaller instance, which we solve recursively.

More concretely, tightness of the cut $(S_1,S_2)$ implies that all demands in $H[S_i]$ are routed within $G[S_i]$. We construct a cut instance ${ℐ}^{\prime }$ by picking $i\in \{1,2\}$, deleting all demands in $H[S_i]$ and all inner (not outer) edges of $G$ within $S_i$, and updating the capacities of the outer edges in $S_i$ to guarantee feasibility of the cut instance.

We solve the cut instance recursively, i.e., we find an unsplittable flow $y^{\prime }$ for ${ℐ}^{\prime }$ which violates edge capacities in ${ℐ}^{\prime }$ by at most $2d_{\max }$. Actually, for the outer edges (edges on the boundary of the outer face) we will even get a stronger bound of $\frac{3}{2}\cdot d_{\max }$. The flow $y^{\prime }$ already determines our unsplittable flow for $ℐ$ on all edges except for $G[S_i]$.

To extend this partial unsplittable flow to all of $G$ we construct a split instance by only considering $G[S_i]$ as supply graph and adding a demand edge between any vertices $s,t\in S$ that are connected within $S_i$ in the unsplittable flow for some demand in $y^{\prime }$. We also add the demands in $H[S_i]$ which were not considered in the cut instance at all. We show that since $y^{\prime }$ does not exceed capacities too much, this split instance becomes feasible after increasing the capacities of the edges $E^{\ast }\subseteq E(G[S_i])$ which are incident to ${\delta }_G(S_i)$, by $\frac{3}{2}\cdot d_{\max }$. This edge set contains at most one edge per block of $G[S_i]$.

We again use recursion to solve the split instance, which yields an unsplittable flow $\widehat{y}$ that can “fill the gaps” for $y^{\prime }$. Our final unsplittable flow $y$ will be equal to $\widehat{y}$ on $G[S_i]$ and to $y^{\prime }$ outside $G[S_i]$. For the edges $E^{\ast }$ we will guarantee an even stronger bound of $\frac{1}{2}\cdot d_{\max }$ on the capacity violation of $\widehat{y}$, which will yield the capacity bounds needed for $y$.

The only case where our recursion step fails is if the tight cut ${\delta }_G(S_i)$ already contains all inner edges of $G$, because then the cut instance will not be smaller than the original instance. In this case, we consider a face $F$ which is incident to at most one inner edge $\{v,w\}$ in $G$. W.l.o.g. both $v$ and $w$ have degree $3$ in $G$, and we can find two cuts of size $2$ among the edges incident to $v$ and $w$. We will show that for one of these cuts we can perform the same procedure as above to reduce our instance to two smaller instances.

An instance $(G,u,H,d)$ of multicommodity flow is given by an undirected graph $G=(V,E(G))$ with edge capacities $u:E(G)\to {ℝ}_{\ge 0}$, and a graph $H=(V,E(H))$ with demand values $d:E(H)\to {ℝ}_{\ge 0}$. $G$ and $H$ may have parallel edges but no loops. We refer to $G$ and $E(G)$ as the supply graph and supply edges, respectively. We refer to $H$ and $E(H)$ as the demand graph and demand edges, respectively.

For a demand edge $h=\{s,t\}\in E(H)$, we use ${𝒫}_h$ to denote the set of all (simple) $st$-paths in $G$. A flow for $h$, or $h$-flow, is an assignment $x_h:{𝒫}_h\to {ℝ}_{\ge 0}$ of non-negative real numbers to paths in ${𝒫}_h$ such that ${\sum }_{P\in {𝒫}_h}{x}_h(P)=d(h)$. A collection of flows $x={(x_h)}_{h\in E(H)}$ constitutes a multicommodity flow for the instance. For simplicity, we often refer to multicommodity flows simply as flows. For a supply edge $e\in E(G)$ and a demand edge $h\in E(H)$, we use $x_h(e):={\sum }_{P:e\in P}{x}_h(P)$ to denote the total $h$-flow going through $e$. We use $x(e):={\sum }_{h\in E(H)}{x}_h(e)$ to denote the total flow going through $e$. A flow $x$ is feasible if it satisfies the edge-capacity constraints, that is, if $x(e)\le u(e)$ for all $e\in E(G)$.

An $h$-flow $x_h$ is called unsplittable if exactly one of the paths in ${𝒫}_h$ is assigned a non-zero value in $x_h$. We call a flow $x={(x_h)}_{h\in E(H)}$ unsplittable if each $x_h$ is unsplittable. In this work, whenever we refer to an unsplittable flow, we also assume that it routes all demands. We use $d_{\max }:={\max }_{h\in E(H)}d(h)$ to denote the maximum demand value. To simplify notation in the upcoming proofs, we adopt the notion of $\alpha$-feasibility introduced in [2] and generalize it to the notion of $\overrightarrow{\beta }$-feasibility.⁴⁴4In [3] the authors defined $(\alpha ,\beta )$-feasibility, to indicate that a flow $x$ satisfies $x(e)\le \alpha u(e)+\beta d_{\max }$ for every $e\in E(G)$ (and some $\alpha ,\beta \in {ℝ}_{\ge 0}$). In this work, we focus only on additive violations with respect to $d_{\max }$.

We may assume w.l.o.g. that the supply graph $G$ is $2$-vertex-connected. Indeed, suppose that $G$ has a cut vertex. Let $B_1\subseteq V(G)$ denote the vertex set of a block⁵⁵5A block of $G$ is a maximal (inclusion-wise) vertex set $S\subseteq V(G)$ such that $G[S]$ is $2$-vertex-connected, where we regard $K_2$ as $2$-vertex-connected. of $G$ containing exactly one cut vertex $v\in B_1$ and define $B_2:=V(G)\setminus (B_1\setminus \{v\})$. For any demand $h=\{a,b\}\in E(H)$ with $h\subseteq B_i$ for some $i\in \{1,2\}$ we have that any $ab$-path in $G$ is contained inside $B_i$, so that demand does not interact with edges in the other component $B_{3-i}$. For a demand $h=\{a,b\}\in E(H)$ with $a\in B_1$, $b\in B_2$ we have that any $ab$-path in $G$ contains $v$. Hence, we can replace $h$ by two demands $\{a,v\}$ and $\{v,b\}$, each of value $d(h)$, obtaining an equivalent multicommodity flow instance. Repeating this transformation until no cut vertex exists reduces the problem to a collection of smaller instances, whose supply graphs are the blocks of $G$.

A graph is outerplanar if it admits a planar embedding in which all vertices lie on the unbounded face. Throughout this work, the supply graph $G$ of our instance $(G,u,H,d)$ is outerplanar, and we fix an outerplanar embedding of $G$. We sometimes also call the unbounded face the outer face, and the other faces inner faces. Similarly, we call the edges of $G$ incident with the outer face the outer edges, and the remaining edges the inner edges. We denote the sets of outer and inner edges by $E_{\text{outer}}(G)$ and $E_{\text{inner}}(G)$, respectively. Since we may assume that $G$ is $2$-vertex-connected, every face of $G$ is bounded by a cycle.

Let $(G,u,H,d)$ denote a multicommodity flow instance, and set $V:=V(G)$. For any $S\subseteq V$, the cut $(S,V\setminus S)$ is a bipartition of the vertex set. The cut-condition requires that, for every cut, the total demand crossing the cut is at most the total capacity of the supply edges crossing it i.e.,

A set $\mathrm{\varnothing }\ne S⊊V$ is called central if both of the induced graphs $G[S]$ and $G[V\setminus S]$ are connected. We say that $(S,V\setminus S)$ is a central cut if $S$ is central. The following is a well known fact (see, e.g., [21]).

Observe that in a $2$-vertex-connected outerplanar graph $G$, the central sets are precisely the vertex sets of subpaths of the outer face.

A classical result of Okamura and Seymour states that the cut-condition is sufficient whenever $G$ is planar and the endpoints of all demand edges lie on a common face of $G$.

Since every vertex of an outerplanar graph is incident to the outer face, an immediate consequence of the above theorem is that the cut-condition is sufficient for the feasibility of an instance if the supply graph $G$ is outerplanar.

For the ring-loading problem, Däubel [7] showed how to compute a $1.3$-feasible unsplittable flow in any feasible instance. For our purposes, however, it is essential to obtain a much stronger bound on the capacity violation for one special edge, while still keeping the capacity violations on all other edges small. Therefore, we make use of the algorithm of Schrijver, Seymour, and Winkler [22], which only gives a $\frac{3}{2}$-feasible unsplittable flow, but also directly implies a bound of $+\frac{1}{2}{d}_{\max }$ for the capacity violation on one edge that can be chosen arbitrarily in advance.

We also need an even stronger bound for the special case where all demands are incident to one of two specified vertices.

The proof of Theorem 6 follows by using the same algorithm and analysis as Schrijver, Seymour, and Winkler [22]. We include the details, together with the proof of Lemma 7, in the extended version of this paper.

Recall that a nonempty vertex set $S⊊V(G)$ is central if $G[S]$ and $G[V(G)\setminus S]$ are connected. A useful tool which we use in our proof is the notion of $x$-nice central sets:

We make use of two types of $x$-nice sets, which are captured in the following two lemmata: