Notes on the multicommodity flow problem

Introduction
Single-commodity flow
Two-commodity flows
Bistable graphs
- $H$ is a clique and the locking theorem
- Where the polymatroids come into play
Congestion and distortion
Cut-sufficiency in series-parallel graphs
Metrics and potentials

Introduction

An instance of the MultiCommodity flow problem (or Multiflow problem) is composed of an undirected graph $G = (V, E)$ with capacities $c : E \to N$ , a set of terminals $T \subseteq V$ , and a function $μ : (\binom{T}{2}) \to R_{+}$ . We denote $H$ the graph with vertex set $T$ , and edges $s t$ for every pair $s, t \in T$ of terminals with $μ_{(} s, t) > 0$ .

A $T$ -path is any path whose endpoints are distinct elements of $T$ . For two vertices $s$ and $t$ , an $(s, t)$ -path is a path whose endpoints are $s$ and $t$ . Denote by $P_{G, T}$ the set of all $T$ -paths of $(G, T)$ (we will omit the indices when there is no ambiguity). A $c$ -packing of $T$ -paths is a mapping $f : P \to R_{+}$ , such that, for any edge $e \in E$ , the sum of $f (P)$ where $P$ ranges over all $T$ -paths containing $e$ is at most $c_{e}$ . The value of a $T$ -path $P$ with extremities $s, t \in T$ is $μ (p) := μ (s, t)$ . We extend this definition to packings of $T$ -paths by saying that the value of a packing $f$ is ${‖ f ‖}_{μ} := \sum_{P \in P} f_{P} μ (P) = f \cdot μ$ .

The goal of the MultiCommodity Flow problem is to find a $c$ -packing $f$ of $T$ -paths of maximum value.

Linear Program: formulation using paths

We can rewrite the definition directly as a linear program:

$\begin{array}{ll} max | | f | |_{μ} subject to \\ \sum_{P \in P, e \in P} f_{P} \leq c_{e} & (\forall e \in E) \\ f \geq 0 \end{array}$

From this we can derive the dual program with variables $y \in R_{+}^{E}$ :

$\begin{array}{ll} min \sum_{e \in E} c_{e} y_{e} subject to \\ \sum_{e \in P} y_{e} \geq μ_{P} & (\forall P \in P) \\ y \geq 0 \end{array}$

The interpretation of this dual program leads directly to a problem about distances. Actually there is a very deep connection between multicommodity flows and distance embeddings as we shall see later. For now, we interprete $y$ as giving a length to every edge of the graph. The main constraints say that the distance (i.e. the length of a shortest path, which is the minimal length over all paths) between two terminals $s$ and $t$ must be at least $μ_{s, t}$ for the chosen lengths.

We rewrite the dual, replacing $y$ by its metric closure $d \in R_{+}^{V \times V}$ . We denote $c \cdot d := \sum_{e = u v \in E} c_{e} d (u, v)$ .

$\begin{array}{ll} min c \cdot d subject to \\ d (s, t) \geq μ (s, t) & (\forall s, t \in T) \\ d metric on V \end{array}$

There is a very intuitive interpretation of the weak duality for the multicommodity flow problem. The capacity of an edge can be interpreted as having multiple copies of that edge, each with unitary capacity. With this in mind, the objective value of the dual program is the sum $d (G) := c \cdot d$ of the lengths of all the edges of $G$ . Consider a $T$ -path $P$ , with endpoints $s$ and $t$ , $P$ must have a total length $d (P) := \sum_{e = u v \in P} d (u, v)$ at least $μ_{P}$ . Thus, $P$ consumes at least $f_{P} d (P)$ of the length of $G$ , and contributes exactly $f_{P} μ_{P}$ to the primal objective. From this we get:

$\sum_{P \in P} f_{P} μ_{P} \leq \sum_{P \in P} f_{P} d (P) \leq d (G)$

In words, the multiflow cannot use more length than available, and each path contributes at most its own length to the objective, hence the length $d (G)$ of $G$ gives an upper bound on the value of any feasible flow.

Using the strong duality theorem, we get the so-called Japanese theorem:

Theorem 1: (Onaga -Kakusho [16]) The maximum value of a multicommodity flow for $(G, T, c, μ)$ is equal to the minimum length $d (G)$ over all distance $d$ such that $d (s, t) \geq μ (s, t)$ for all terminals $s, t \in T$ .

As a corollary of the strong duality, it is of interest to look at what complementary slackness tells us about a pair of optimal solution $(f, d)$ :

every active $T$ -path $P$ (i.e. with $f_{P} > 0$ ) has length $d (P) = μ_{P}$ ,
every active edge $e = u v$ (i.e. with $d (u, v) > 0$ ) is saturated: $\sum_{P \in P, e \in P} f_{P} = c_{e}$ .

Linear Program: formulation on edges

We can give a completely different formulation of the flow problem, where the notion of path is forgotten. This gives a linear program with very interesting properties for the single-commodity case. For this, we only record how much of each commodity is actually flowing through any edge. As a side effect, this formulation is compact.

Let $E (H)$ be ${h_{1} = s_{1} t_{1}, \dots, h_{n} = s_{n} t_{n}}$ . The variables are $f \in R_{+}^{(E \cup E (H)) \times [1, n]}$ . Also, to keep track of the direction on which a commodity is flowing, we give an arbitrary orientation to $G$ . If $f_{e, i}$ is positive, it means that the commodity is flowing forward along that arc, if it is negative it is flowing backward (note that this is necessary only because we are looking at undirected graphs, in directed graphs the commodities can flow in only one direction, forward by definition).

$\begin{array}{ll} max \sum_{i = 1}^{n} μ (s_{i}, t_{i}) f_{h_{i}, i} subject to \\ \sum_{e \in δ_{G + H}^{+} (v)} f_{e, i} - \sum_{e \in δ_{G + H}^{-} (v)} f_{e, i} = 0 & (\forall v \in V, i \in [1, h]) \\ f_{h_{i}, j} = 0 & (\forall i \neq j) \\ \sum_{i \in [1, h]} | f_{e, i} | \leq c_{e} & (\forall e \in E, i \in [1, h]) \end{array}$

Let's explain these constraints in reverse order. The last one is the capacity constraint: an edge cannot support more flow than its capacity. Because we can have negative values for commodities routed backward, we need to take the absolute values of the variables. We let the reader find how to encode these constraints linearly.

The second constraint concerns the edges of $H$ : the idea is that the flow routed through $h_{i}$ corresponds to the number of paths that can be packed between $s_{i}$ and $t_{i}$ , and this also explains the objective value. The second constraint ensures that these additional edges cannot be used to route a different commodity.

The first constraint is known as the conservation law: the quantity of a commodity entering a vertex is equal to the quantity of that same commodity leaving that same vertex. A vector $f \in R^{E (G)}$ in any graph $G$ is called a circulation if it satisfies this constraint, precisely $\sum_{e \in δ_{G}^{+} (v)} f_{e} = \sum_{e \in δ_{G}^{-} (v)}$ for all vertex $v \in V (G)$ . Here, $δ_{G}^{+} (v)$ and $δ_{G}^{-} (v)$ stand respectively for the set of outgoing and incoming arcs of vertex $v$ . It also suggests the definition of the excess of an edge function at a vertex: for any $g : E \to R$ , we define the excess of $g$ at $v$ by:

$excess (g, v) := \sum_{e \in δ^{-} (v)} g_{e} - \sum_{e \in δ^{+} (v)} g_{e}$

that is, the quantity of flow entering minus that leaving the vertex $v$ . A circulation is thus a function for which the excess is zero at every vertex.

Hence, this linear program expresses the existence of one circulation for each commodity, the circulation for commodity $h_{i}$ being defined on $G + h_{i}$ , and these circulations can be routed concurrently with respect to the capacities.

To get a solution encoded on edges from a packing of paths is relatively easy: First, close each path $P$ into a cycle $C (P)$ by adding one of the commodity edges $s_{i} t_{i}$ . Then orient each cycle such that $s_{i} t_{i}$ is always forward. For a given cycle $C$ , let $χ_{C} \in {- 1, 0, 1}^{E (G + H)}$ be the function defined by $χ_{C} (e) = 1$ if $e$ is forward in $C$ , $χ_{C} (e) = - 1$ if $e$ is backward in $C$ , and $χ_{C} (e) = 0$ otherwise. It is obvious that for any cycle $χ_{C}$ is a circulation, and any linear combination of circulations is a circulation. Hence, $\sum_{P (s_{i}, t_{i}) -path} f_{P} χ_{C (P)}$ defines a circulation $(f_{e, i})_{e} \in R^{E (G + H)}$ . Repeating this over every commodity gives the equivalent solution to the edge formulation.

Reciproqually, a circulation can be decomposed into a set of cycles. The number of cycles using a given edge $h$ will be the amount of flow through that edge:

Theorem 2: (Fulkerson , comformal decomposition of circulation) Let $f$ be a circulation on a graph $G$ , then there is a set of at most $| E (G) |$ cycles $C_{1}, \dots, C_{k}$ such that $f$ is a conic combination of $χ_{C_{1}}, \dots, χ_{C_{k}}$ , and no edge is used backward in one cycle and forward in another one.

The proof is left as an exercise. The condition that no edge is used both forward and backward ensures that each edge is present as many times in the cycle decomposition as in the circulation. The importance of the theorem is thus to prove that the formulation on edges is indeed equivalent (in some sense) to the formulation on paths.

Let's conclude this part by mentioning a direct and fundamental application of the edge formulation of single-commodity flows, that is multiflows with only one commodity. Then the linear program asks for only one circulation. and it can be seen that the corresponding system of inequations is totally unimodular. Indeed, the matrix of conservation law for a circulation is the matrix of incidence between arcs and vertices. A submatrix corresponds to a subgraph. If this subgraph contains a cycle, the corresponding columns are not linearly independant and the submatrix has determinant $0$ . Otherwise, it is a forest. Then by developping the determinant by a leaf and applying induction, the determinant is $1$ or $- 1$ , hence the matrix is totally unimodular. This implies that the circulation polyhedron is integral, hence the single-commodity flow problem (i.e. Maximum Flow) always admits an integral optimal solution. We will show an alternative proof below.

Cuts

We recall that a cut $δ (X)$ is the subset of edges $u v \in E$ with exactly one endpoint in $X$ (formally $| {u, v} \cap X | = 1$ ). The capacity $c (δ (X))$ of a cut is $\sum_{e \in δ (X)} c_{e}$ . We say that a cut $δ (X)$ separates $a$ from $b$ if $| X \cap {a, b} | = 1$ . An $(a, b)$ -cut is a cut separating $a \in V$ from $b \in V$ , more generally an $(A, B)$ -cut for two vertex sets $A$ and $B$ is a cut separating every pair $a, b \in A \times B$ . We denote $λ (A, B)$ the minimum capacity of an $(A, B)$ -cut, $λ (S) = λ (S, T ∖ S)$ (where $T$ is the set of terminals), and $δ [A, B]$ the set of edges with one endpoint in $A ∖ B$ and the other in $B ∖ A$ .

Cuts sometimes provide a simple way to prove the optimality of a multiflow, and actually we are very interested in characterizing the instances for which cuts are sufficient to this purpose. The reason is that the capacity of an $(S, T)$ -cut is an upper bound on the number of paths with one extremity in $S$ and the other in $T$ . For instance, a commodity $s t$ cannot contribute to the objective more than $c μ (s, t)$ , where $c$ is the capacity of a (minimum) $(s, t)$ -cut.

We will use the following general inequalities on cuts. For any sets $A, B \subseteq V$ ,

$c (δ (A)) + c (δ (B)) = c (δ (A \cup B)) + c (δ (C \cap B) + 2 c (δ [A, B])$

As the capacities are always non-negative, it implies the submodularity inequation for cuts:

$c (δ (A)) + c (δ (B)) \geq c (δ (A \cup B)) + c (δ (C \cap B))$

Another similar relation is (actually they are equivalent using that $δ (A) = δ (\overset{―}{A})$ ):

$c (δ (A) + c (δ (B)) = c (δ (A ∖ B)) + c (δ (B ∖ A) + 2 c (δ [A \cap B, \overset{―}{A \cup B}])$

Given an instance $G, H, c, D$ , we will denote $σ (U)$ the surplus of a cut defined by $U$ :

$σ (U) = c (δ_{G} (U)) - D (δ_{H} (U))$

A cut $δ (U)$ is tight if its surplus $σ (U) = 0$ . $σ$ has remarkable equalities similar to those of cuts (from which they derive easily). We will also use the notation $σ [U, W] = c (δ [U, W]) - D (δ [U, W])$ .

We say that a cut $δ (X)$ is central in $G$ if both $G [X]$ and $G [V ∖ X]$ are connected.

Single-commodity flows

We start with the simplest case where $T = {s, t}$ , that is $H$ has only one edge. By scaling, we may assume that $μ (s, t) = 1$ . Then the problem is equivalent to the maximum flow problem. We won't discuss here about the algorithmic aspects of the question, for which there already is an extensive litterature (I would like to recommand Pr. Tom McCormick's lecture notes, which partly inspired the presentation of the present note, but I don't know if they are available anywhere). We only prove the famous Max-Flow-Min-Cut theorem (in its undirected version) using only the previous considerations, and look at some of the consequences.

An $(s, t)$ -flow is a multicommodity flow with $T = {s, t}$ (hence it is actually a single-commodity flow). An $(R, S)$ -flow, $R \cap S = \emptyset$ , is a multicommodity flow where $μ (r, s) = 1$ if $r \in R$ , $s \in S$ , and $μ (r, s) = 0$ otherwise.

Theorem 3: (Ford -Fulkerson [5], Max-Flow-Min-Cut) The maximum value of an $(s, t)$ -flow in $G, c$ is equal to the minimum capacity of an $(s, t)$ -cut.

Proof: One direction is obvious: the capacity of an $(s, t)$ -cut $δ (X)$ limits the value of a flow. This is also an application of the Japanase theorem, by taking $d (u, v) = 1$ if $δ (X)$ separates $u$ from $v$ , and $d (u, v) = 0$ otherwise.

Let $f$ be a maximum $(s, t)$ -flow of value $‖ f ‖$ , and $d$ a minimum metric for the dual problem. By definition $d (s, t) = 1$ . Consider any value $0 \leq α < 1$ , and define $R_{α}$ the set of vertices at distance at most $α$ from $s$ . Then, we claim that $c (δ (R_{α})) = ‖ f ‖$ . We already argued why $c (δ (R_{α})) \geq ‖ f ‖$ . But the next paragraph proves directly the equation.

Consider any edge $e = u v$ in $δ (R_{α})$ , wlog $u \in R_{α}$ . Then $d (s, v) \leq d (s, u) + d (u, v)$ implies that $d (u, v) > 0$ . By complementary slackness, $e$ is saturated by $f$ . Also by complementary slackness, any active path containing $e$ crosses $δ (R_{α})$ only at $e$ , otherwise its length would be strictly more than $1$ . By summing over all the edges of $R_{α}$ , and because every active path intersects $δ (R_{α})$ , we get $c (δ (R_{α})) = | | f | |$ .

It is an almost direct consequence that there always is an integral maximum flow, provided that the capacities are integral (think that if an edge is not saturated, we can decrease its capacity by one unit without changing the value of a minimum cut, then by iterating we will get a graph with integer capacities where all the edges are saturated).

This result can also be extended to the case when $H$ is a star, by the usual trick of adding a super-source adjacent to all the leaves of $H$ (with unlimited capacities), and taking a maximum flow from the center of $H$ to the super-source. With more work, a maximum flow can be found even when $μ$ is not uniform.

More generally, using one super-source and one super-sink, we get that the maximum $(R, S)$ -flow is equal to the minimum capacity of a cut separating all the pairs $r, s \in R \times S$ (but this time it works only for the uniform case). We can be more precise. Suppose that we want to find an $(R, S)$ -flow. We can characterize the vectors $m \in N^{R}$ such that there is an integral $(R, S)$ -flow with exactly $m (r)$ paths with endpoint $r$ , for any $r \in R$ .

Corollary 4: Let ${R, S}$ be a partition of $T$ , and $m \in R^{R}$ . Then there is an $(R, S)$ -flow with $m (r)$ $(r, S)$ -paths, for any $r \in R$ , if and only if $λ (R^{'}, S) \geq m (R^{'})$ for any $R^{'} \subseteq R$ .

Proof: The necessity is obvious. Let $m \in R^{R}$ be such that there is no flow as required. Define $G^{'}$ by adding to $G$ a vertex $r$ with edges $r t$ of capacity $m (t)$ for every $t \in R$ , and a vertex $s$ with edges $t s$ of unlimited capacity for any $t \in S$ . This instance does not have an $(s, t)$ -flow of value $m (R)$ . Hence, by the Max-Flow-Min-Cut theorem, there is a cut $X^{'}$ with $c_{G^{'}} (δ (X)) < m (R)$ . Consider $X = X^{'} \cap V (G)$ , then $m (X \cap R) = m (R) - c_{G^{'}} (δ [s, R ∖ X^{'}]) > c_{G^{'}} (δ [X^{'} - r, V (G^{'}) ∖ X]) = c_{G} (δ (X))$ (and thus $m (R^{'}) > λ (R^{'}, S)$ ), because $c_{G^{'}} (δ (X^{'})) = c_{G^{'}} (δ [r, R ∖ X] + c_{G^{'}} (δ [X^{'} - r, V (G^{'}) - X^{'}])$ .

Two-commodity flows

In this section we consider the case when $H$ has only two edges. Once again we can characterize the maximum multiflow with cuts.

Theorem 5: (Hu [10], Rothschild-Whinston [17]) When $H = {s_{1} t_{1}, s_{2} t_{2}}$ , $μ (s_{1}, t_{1}) = μ_{1} \leq μ_{2} = μ (s_{2}, t_{2})$ , we have:

$max_{f} {‖ f ‖}_{μ} = μ_{1} min_{X} c (δ (X)) + (μ_{2} - μ_{1}) min_{Y} c (δ (y))$

where $X$ ranges over all the cuts separating both $s_{1}$ from $t_{1}$ and $s_{2}$ from $t_{2}$ , and $Y$ ranges over all the $(s_{2}, t_{2})$ -cuts.

Proof: Let $r_{2}$ be the minimum capacity of an $(s_{2}, t_{2})$ -cuts, and define $r_{1}$ such that $r_{1} + r_{2}$ is the minimum capacity of a cut separating $s_{1}$ from $t_{1}$ and $s_{2}$ from $t_{2}$ . It is sufficient (and actually necessary) to find a multiflow that routes $r_{1}$ units for $s_{1} t_{1}$ , and $r_{2}$ units for $s_{2} t_{2}$ . Note that the capacity of any $(s_{1}, t_{1})$ -cut is at least $r_{1}$ . Indeed, given such a cut $X$ , if $X$ separates $s_{2}$ from $t_{2}$ , it has capacity at least $r_{1} + r_{2} \geq r_{1}$ . Else, we may assume that $X \cap {s_{2}, t_{2}} = \emptyset$ . Let $Y$ be a minimum cut separating $s_{2}$ from $t_{2}$ . Then, one of $Y ∖ X$ and $Y \cup X$ separates $s_{1}$ from $t_{1}$ and $s_{2}$ from $t_{2}$ , and thus has capacity at least $r_{1} + r_{2}$ . But $c (δ (X)) + c (δ (Y)) \geq max {c (δ (Y ∖ X)), c (δ (Y \cup X))}$ , hence $c (δ (X)) \geq r_{1}$ .

For this proof, we use the formulation of flows on edges (and thus we orient every edge arbitrarily). Firstly, define the graph $G_{1}$ obtained from $G, c$ by adding two new vertices, a super-source $s$ and a super-sink $t$ , with arcs and capacities $c (s s 1) = r_{1}$ , $c (s s_{2}) = r_{2}$ , $c (t_{1} t) = r_{1}$ and $c (t_{2} t) = r_{2}$ . Let $g^{'} : E (G_{1}) \to N_{+}$ be an $(s, t)$ -flow on $G_{1}$ of value $r_{1} + r_{2}$ . We prove that $g^{'}$ exists. Indeed, consider a cut $X^{'}$ containing $s$ but not $t$ , and define $X := X^{'} - s$ .

if $X$ separates the two pairs $s_{1} t_{1}$ and $s_{2} t_{2}$ , then by definition of $r_{1}$ , $X$ has capacity at least $r_{1} + r_{2}$ .
if $X$ separates only $s_{1}$ from $t_{1}$ , then $δ (X)$ contains either $s s_{2}$ or $t_{2} t$ , of capacity $r_{2}$ , and $δ (X^{'})$ separates $s_{1}$ from $t_{1}$ , hence $c_{1} (δ (X^{'})) = r_{2} + c (δ (X)) \geq r_{1} + r_{2}$ .
symmetrically if $X$ separates only $s_{2}$ from $t_{2}$ , $c (δ (X)) \geq r_{1} + r_{2}$ .
if $X$ separates none of the two pairs, $X$ contains one of ${s s_{1}, t_{1} t}$ and one of ${s s_{2}, t_{2} t}$ , hence $c (δ (X)) \geq r_{1} + r_{2}$ .

By the Max-Flow-Min-Cut theorem, $g^{'}$ exists. Let $g$ be the restriction of $g^{'}$ to $E (G)$ . Similarly, we define a flow $h$ of value $r_{1} + r_{2}$ from $s_{1}$ and $t_{2}$ to $s_{2}$ and $t_{1}$ . We have:

$excess (g, t_{1}) = - excess (g, s_{1}) = r_{1}$ ,
$excess (g, t_{2}) = - excess (g, s_{2}) = r_{2}$ ,
$excess (h, t_{1}) = - excess (h, s_{1}) = r_{1}$ ,
$excess (h, s_{2}) = - excess (h, t_{2}) = - r_{2}$ ,
and $excess (g, v) = excess (h, v) = 0$ for any $v \in V ∖ T$ .

Now, consider $f_{1} = \frac{g + h}{2}$ and $f_{2} = \frac{g - h}{2}$ . We get immediately:

$excess (f_{1}, t_{1}) = - excess (f_{1}, s_{1}) = r_{1}$ ,
$excess (f_{2}, t_{2}) = - excess (f_{2}, s_{2}) = r_{2}$ ,
all the other excesses are $0$ .

which mean that $f_{1}, f_{2}$ is a candidate solution. We only have to check that they respect the capacities. For every edge $e$ :

$| f_{1} (e) | + | f_{2} (e) | = \frac{1}{2} (| g (e) + h (e) | + | g (e) - h (e) |) \leq c_{e}$

where the last inequality follows from the fact that the central term is half the sum of the distances from $g (e)$ to $h (e)$ and $- h (e)$ (if $| g (e) | \leq | h (e) |$ , symmetrically otherwise), and $| h (e) | \leq c_{e}$ .

The proof shows that there even is a half-integral optimal packing of paths.

Bistable graphs

Most of this section relies on an article of Frank, Karzanov and Sebő [6], and the PhD thesis of Mouna Sadli [18]. We follow the former to prove a theorem by Karzanov and Lomonosov [12].

$H$ is a clique and the locking theorem

Another important case where there always are half-integral solutions is when $H$ contains all the pairs of terminals. Given a set $T$ of terminal and a terminal $t$ , we denote $λ (t)$ the minimum capacity of a $(t, T - t)$ -cut.

Theorem 6: (Cherkasky [4], Lovász [15]) If $μ (s, t) = 1$ for every pair $s, t \in (\binom{T}{2})$ , then $max_{f} {‖ f ‖}_{μ} = \frac{1}{2} \sum_{t \in T} λ (t)$ .

We will prove a generalization of this theorem, but before that we need some definitions. We say that a family of paths locks a subset of terminals $A \subseteq T$ if it contains $λ (A, T - A)$ $(A, T - A)$ -paths. A family of subsets of $T$ is 3-cross-free if it has no three pairwise crossing members (two sets $A$ and $B$ are crossing if none of $A \cap B$ , $A ∖ B$ , $B ∖ A$ and $\overset{―}{A \cup B}$ is empty. An instance of Multiflow is inner-Eulerian if $c (δ (v))$ is even for all non-terminal vertex $v \in V ∖ T$ .

Theorem 7: (Karnazov , Lomonosov) Let $G, c, T$ be an inner-Eulerian instance and $L \subset 2^{T}$ a 3-cross-free family of subsets of terminals. Then there is a family of disjoint $T$ -paths locking all the members of $L$ .

Before giving the proof of this theorem, let's see why it implies the Cherkasky-Lovász theorem. Take the family $L = {({t})}_{t \in T}$ , which is obviously 3-cross-free. By the locking theorem there is a family of path locking ${t}$ , for every terminal $t \in T$ . Hence every terminal $t$ is the endpoint of exactly $λ (t)$ paths in this family. Counting that each path has two endpoints, we get that the number of paths is precisely $\frac{1}{2} \sum_{t \in T} λ (t)$ , as predicted by the Cherkasky-Lovász theorem.

Proof: The proof relies on the splitting-off technique: a splitting-off operation consists in taking two incident edges $u v$ , $v w$ , and replacing them by the edge $u w$ . We only want to do it when it preserves the minimum cuts of the graph (the tight cuts). If we manage to apply splitting-off iteratively until the graph becomes trivial, without altering the $λ (S)$ values for $S \in L$ , then we are done: indeed, if we can find a packing of paths in the trivial graph, then we can extend it to the original graph by unfolding the splitting-off in a natural way.

Consider an edge $t u \in E$ , with $t \in T$ and $u \notin T$ . We want to show that there always is an edge $u v$ such that we can split $t u$ , $u v$ . We say that a set $X$ of vertices is tight if $X \cap T \in L$ and $c (δ (X)) = λ (X \cap T)$ .

Firstly, we claim that if $X$ and $Y$ are two tight sets, and $X \cap T \subseteq Y \cap T$ , then $X \cap Y$ and $X \cup Y$ are also tight, and $c (δ (X, Y)) = 0$ . Indeed, $(X \cup Y) \cap T = Y \cap T \in L$ and $(X \cap Y) \cap T = X \cap T \in L$ , proving the first condition. It also implies that:

$λ (X \cap T) + λ (Y \cap T) = c (δ (X)) + c (δ (Y)) = c (δ (X \cap Y)) + c (δ (X \cup Y)) + 2 c (δ [X, Y]) \geq λ (X \cap T) + λ (Y \cap T) + 2 c (δ [X, Y])$

As $c$ is non-negative, we get that $c (δ [X, Y]) = 0$ , $λ (X \cap T) = c (δ (X \cap Y))$ and $λ (Y \cap T) = c (δ (X \cup Y))$ , proving the claim.

Secondly, we claim that there are no three distinct maximal tight sets containing $t$ but not $u$ . Consider three maximal tight sets $X$ , $Y$ and $Z$ containing $t$ and not $u$ . Then, $X \cap T$ , $Y \cap T$ and $Z \cap T$ , are elements of $L$ , and hence are not pairwise crossing.

if $X \cap T \subseteq Y \cap T$ (up to renaming), then by the first claim $X \cup Y$ is tight, and by maximality $X = X \cup Y = Y$ .
if $T \subseteq X \cup Y$ , then $\overset{―}{X}$ is tight and $\overset{―}{X} \cap T \subseteq Y \cap T$ , hence by the first claim $c (δ [\overset{―}{X}, Y]) = 0$ , contradicting the existence of the edge $t u$ .

Thirdly, we claim that there are no two tight sets $X$ and $Y$ containing $t$ and not $u$ , with $δ (u) \subseteq δ (X) \cup δ (Y)$ . Otherwise, one of the two sets, say $X$ , would have $c (δ (u) \cap δ (X)) > \frac{1}{2} c (δ (u))$ (the inequality being strict as each set separates $t$ from $u$ ), but then $c (δ (X - u)) < c (δ (X))$ , contradicting the fact that $X$ is tight.

The two last claims prove the existence of an edge $u v$ that is not covered by any tight set. Moreover, if for some $X \subseteq V$ , $X \cap T \in L$ and $λ (X \cap T) < c (δ (X))$ , then $λ (X \cap T) \leq c (δ (X)) - 2$ because the instance is Eulerian. Thus, splitting off $s u$ , $u v$ does not change the values of the $λ (S)$ for any $S \in L$ . By iteratively splitting off the graph until no terminal is adjacent to a non-terminal vertex (and removing the non-relevant parts of the graph), we reduced the instance to the case where all the vertices are terminals. But in that case, the theorem is trivial as taking all the possible paths of length $1$ gives a solution.

If the instance is not inner-Eulerian, it still gives a half-integrality result.

Where the polymatroids come into play

A graph $H$ is bistable if there are two partitions such that $s t \in (\binom{T}{2})$ is an edge of $H$ iff $s$ and $t$ appears on distinct parts in both partitions. Equivalently, we can separate the maximal independant sets of $H$ into two subpartitions of its vertex set. In this section, we assume that $μ : (\binom{T}{2}) \to {0, 1}$ . An $H$ -path is a path whose endpoints $s$ , $t$ are endpoints of an edge of $H$ , i.e. $μ (s, t) = 1$ .

An admissible subpartition of $V$ is a subpartition $X_{1}, \dots, X_{k}$ with $T \subseteq ⋃_{i = 1}^{k} X_{i}$ and $X_{i} \cap T$ is independant in $H$ for all $i \in [1, k]$ . The value of an admissible subpartition $X_{1}, \dots, X_{k}$ is defined by $\sum_{i = 1}^{k} \frac{c (δ (X_{i}))}{2}$ . The value of an admissible subpartition is obviously an upper bound of the value of a maximum multiflow for $G, H$ : any $H$ -path must have its endpoints in distinct parts of the subpartition (as each part is an independant set in $H$ ). What is more surprising is that this is a good characterization of maximum multiflows when $H$ is bistable:

Theorem 8: (Karzanov , Lomonosov) If $G, T$ is inner-Eulerian and $H$ is bistable, then the cardinality of a maximum packing of $H$ -admissible $T$ -paths is equal to the minimum value of an admissible subpartition.

Note how this implies both Cherkasky-Lovász theorem and Rothschild-Whinston theorem (in the uniform case). Both $K_{n}$ and $K_{2} + K_{2}$ are bistable (the intersection graphs of maximal independant sets are respectively $S_{n}$ and $C_{4}$ ), and the values of subpartitions give almost immediately the characterizations given above.

A polymatroid is a polyhedron $P (r) := {x \in R_{+}^{S} | \forall A \subseteq S, x (A) \leq r (A)}$ , where $S$ is a finite set and $r : 2^{S} \to R_{+}$ is a polymatroidal function:

$r (\emptyset) = 0$ ,
$r (A) \leq r (B)$ for all $A \subseteq B \subseteq S$ (monotonicity),
$r (A) + r (B) \geq r (A \cup B) + r (A \cap B)$ for all $A, B \subseteq S$ (submodularity). $r$ is the rank function of $P$ .

Edmonds introduced the concept of polymatroids and several great properties they have. Among them:

the polymatroidal function is uniquely determined by the polymatroid,
a polymatroid is integral iff its polymatroidal function is integral-valued,
if $r_{1}$ and $r_{2}$ are two polymatroidal functions on $S$ , then $max {x (S) | x \in P (r_{1}) \cap P (r_{2})} = min_{X \subseteq S} r_{1} (X) + r_{2} (V ∖ X)$ . If $a$ and $b$ are integral, the maximum $x$ can be chosen integral.
given an (integral) polymatroid $P$ on $S$ with rank function $r$ , any (integral) vector $p$ of $P$ is dominated by a vector in the base polyhedron $B (P) := P \cap {x \in R_{+}^{S} : x (S) \leq r (S)}$ of $P$ , that is there is $p^{'} \in P$ with $p^{'} \geq p$ and $p^{'} (S) = r (S)$ .

We have seen an example of polymatroidal function sooner when we studied the single-commodity case. We say that for a vertex set $A \subset V$ , the vectors $m \in R_{+}^{A}$ for which there is an $(A, T ∖ A)$ -flow with exactly $m (a)$ $(a, T ∖ A)$ -paths for each $a \in A$ are described by the equations $m (A^{'}) \leq λ (A^{'}, T ∖ A)$ . As the function $r : 2^{A} \to N$ with $r (A^{'}) = λ (A^{'}, \overset{―}{A})$ turns out to be polymatroidal, the set of feasible vectors $m$ is a polymatroid, let's call it $P (A)$ . As the monotonicity is obvious, we just check the submodularity. For any two sets $X, Y \subseteq A$ ,

$r (X) + r (Y) = c (δ (X^{'})) + c (δ (Y^{'})) \geq c (δ (X^{'} \cup Y^{'})) + c (δ (X^{'} \cap Y^{'}) \geq r (X \cup Y) + r (X \cap Y)$

where $X^{'}$ and $Y^{'}$ are respectively a minimum capacity $(X, T - X)$ -cut and a minimum capacity $(Y, T - Y)$ -cut.

It is easy to check that the direct sum of two polymatroids is a polymatroid, so given a subpartition $X = X_{1}, \dots, X_{k}$ of $T$ , $P (X) := P (X_{1}) ⊎ \dots ⊎ P (X_{k})$ is a polymatroid, denote by $r_{X}$ its polymatroidal function. An $X$ -path is a path whose endpoints are in distinct parts of $X$ . The next lemma explains how the polymatroid defined by a partition relates to the multicommodity flow problem.

Theorem 9: (Frank , Karzanov, Sebő [6]) Let $m$ be an integer vector of $P (X)$ , with $m (T) = r_{X} (T)$ . Then there is an integer packing of $X$ -paths such that every $t \in T$ is the endpoint of exactly $m (t)$ paths.

Proof: For a part $X \in X$ , define a minimum capacity $(X, T - X)$ -cut minimal $δ (S_{X})$ such that $S_{X}$ is minimal by inclusion. Let $X, Y \in X$ . We claim that $S_{X}$ and $S_{Y}$ are disjoint. Indeed,

$λ (X, T ∖ X) + λ (Y, T ∖ Y) = c (δ (S_{X})) + c (δ (S_{Y})) \geq c (δ (S_{X} ∖ S_{Y})) + c (δ (S_{X} ∖ S_{Y})) \geq λ (X, T ∖ X) + λ (Y, T ∖ Y)$

thus $c (δ (S_{X} ∖ S_{Y})) = c (δ (S_{X}))$ and by minimality $S_{X} \cap S_{Y} = \emptyset$ .

Let $G^{'}$ be the graph obtained by contracting each $S_{X}$ into a single vertex $v_{X}$ , for $X \in X$ . Define $T^{'}$ to be the set of contracted vertices, $T^{'} := {v_{X}, X \in X}$ . Then, by Cherkasky-Lovász applied to $G^{'}, T^{'}$ , we get a family of edge-disjoint $T^{'}$ -paths such that $v_{X}$ is the endpoint of $λ (X, T ∖ X)$ paths.

On the other hand, because $m$ is in $P (X)$ (a direct sum of polymatroids) and $m (T) = r_{X} (T)$ , we have $m (X) = λ (X, T ∖ X) = c (δ (S_{X}))$ . Hence there is a set of edge-disjoint $(X, T ∖ X)$ -paths saturating $δ (S_{X})$ . Combining these paths, for each $X \in X$ , with the paths found in $G^{'}, T^{'}$ gives the desired family of $X$ -paths.

If $H$ is induced by a partition, this means that the polymatroid associated to that partition describes the incidence vectors $m \in N$ of integral families of paths. One of Edmonds' result is that the intersection of two integral polymatroids is integral. It suggests that we might be able to solve the case when $H$ is bistable, that is induced by two partitions, by just applying the polymatroid intersection theorem. This was the original intention of the authors of [6], but unfortunately this approach fails. The reason is that there is no equivalent of Theorem 9 for bistable demand: given an integral $m$ in the intersection of the two polymatroids, it is not always possible to build a set of valid paths with incidence vector $m$ . The following picture gives a counterexample:

A counterexample to the polymatroid intersection approach for Karzanov-Lomonosov bistable theorem.

$H$ is indeed bistable, the two partitions into stable sets are ${v_{1}, v_{4}}, {v_{2}, v_{3}}$ , and ${v_{3}, v_{4}}, {v_{1}}, {v_{2}}$ . The vertices of the intersection of the two polymatroids are $(2, 2, 2, 0)$ and $(2, 2, 0, 2)$ , but none of these solutions is realisable, the optimal solution to the maximum multiflow problem has incidence vector $(2, 2, 1, 1)$ (as can be checked using the subpartition ${{v 1}, {v_{2}}, {v_{3}, v_{6}, v_{4}}}$ ).

The proof in [6] uses an incidence vector $m$ that is bigger than an incidence vector from the intersection of the matroid, and hence also infeasible for $H$ but still feasible by a family of $T$ -paths. From this it finds a family of $H$ -paths of the expected size, using the locking theorem. We only prove Theorem 8 for Eulerian $G$ , for inner Eulerian one would add a new terminal adjacent to odd vertices, and apply the Eulerian case.

Proof: (of Theorem 8, only for $G$ Eulerian) let $A$ and $B$ be the two partitions defining $H$ , and $P_{a}$ and $P_{b}$ the two associated polymatroids, $a$ and $b$ their rank functions. Let $m^{'}$ be a maximum vector of $P_{a} \cap P_{b}$ . We want to find two things:

a family of $m^{'} (T) / 2$ $H$ -paths,
an admissible subpartition of value $m^{'} (T) / 2$ .

Recall that vectors of polymatroids are dominated by basis: there are a base $m_{a}$ in $P_{a}$ and a base $m_{b}$ in $P_{b}$ with $m^{'} \leq m_{a}$ and $m^{'} \leq m_{b}$ . Because $P_{a}$ and $P_{b}$ are even polymatroids (by definition of their ranks) we may assume that $m_{a}$ and $m_{b}$ are even. Let $m$ be defined by $m (t) := max {m_{a} (t), m_{b} (t)}$ , for all $t \in T$ . $m$ is even, and we clearly have:

$m_{a} + m_{b} - m \geq m^{'}$

For any vector $q \in N^{T}$ , let $G_{q}$ be the graph obtained by adding for each terminal $t$ , a new vertex $t^{'}$ , an edge $t t^{'}$ with capacity $q$ , and making all edges incident to $t$ in $G$ incident to $t^{'}$ in $G_{q}$ (this encodes in the hardware that $q$ upper-bounds the number of paths at each terminal). We denote $λ_{G_{q}} (U)$ the maximum number of $(U, T ∖ U)$ paths in $G_{q}$ for any $U \subset T$ .

We apply Theorem 7 to $G_{m}$ , with $L$ the family of stable sets in $A$ and $B$ . $L$ is obviously a 3-cross-free family. Let $F$ be the locking family in $G_{m}$ , we abuse notations and consider $F$ to be paths in $G$ (by the trivial injection).

Then we count the number of $A$ -paths in $F$ (ie connecting distinct parts of $A$ ). $m \geq m_{a} \in P_{a}$ (Theorem 9), by definition of $P_{a}$ there is a packing of $A$ paths locking $A$ with incidence vector $m_{a}$ . For any $S \in A$ , because $λ_{G_{m}} (S) \geq λ_{G_{m_{a}}} (S) = m_{a} (S)$ , there are at least $m_{a} (S)$ paths in $F$ with exactly one extremity in $S$ . Therefore there are at least $m_{a} (T) / 2$ $A$ -paths in $F$ . Similarly there are at least $m_{b} (T) / 2$ $B$ -paths in $F$ .

Now we count the number $h$ of $H$ -paths, recall that $| F | \leq m (T) / 2$ . We remove from that the paths that are neither $A$ -paths nor $B$ -paths.

$\begin{aligned} h & \geq | F | - (| F | - m_{a} (T) / 2) - (| F | - m_{a} (T) / 2) \\ \geq m_{a} (T) / 2 + m_{b} (T) / 2 - | F | \\ \geq (m_{a} (T) + m_{b} (T) - m (T)) / 2 \\ \geq m^{'} (T) / 2 \end{aligned}$

This concludes the first part of the proof.

To find an admissible subpartition, we use the matroid intersection theorem on $m^{'}$ , there exists a partition $A, B$ of $T$ with $m^{'} (A) = a (A)$ and $m^{'} (B) = b (B)$ . Choose $A$ maximal. Then, for any $t \in B$ , $a (A + T) > a (A)$ . Indeed, if $a (A + t) = a (A)$ , then $a (A) = m^{'} (A) \leq m^{'} (A + t) \leq a (A + t) = a (A)$ , from which $m^{'} (t) = 0$ , but then $b (B) = m^{'} (B) = m^{'} (B - t) \leq b (B - t) \leq b (B)$ , contradicting the maximality of $A$ .

For a stable set $S \in A$ intersecting $A$ , define $X_{S} \subset V$ to be a minimal set with $A \cap S \subset X_{S} \cap T \subset S$ and $d (X_{S}) = a (A \cap S) = m^{'} (A \cap S)$ (the last inequality follows from the fact that $P_{a}$ is a direct sum of polymatroids over $A$ , and $m^{'} (A) = a (A)$ ). Similarly define $Y_{S}$ for any stable set $S \in B$ , $d (Y_{S}) = b (B \cap S) = m^{'} (B \cap S)$ . We consider $K := {X_{S} : S \in A, S \cap A \neq \emptyset} \cup {Y_{S} : S \in B, S \cap B \neq \emptyset}$ , and prove that it is a subpartition of value $m^{'} (T) / 2$

The main step is to prove that $K$ is a subpartition.

We claim that for $X_{S} \in K$ , $S \in A$ , $X_{S} \cap T \subseteq A$ . Indeed, $m^{'} (A \cap S) = a (A \cap S) = d (X_{S}) \geq a (X_{S} \cap S) \geq m^{'} (X_{S} \cap S) \geq m^{'} (A \cap S)$ (first inequality: definition of $a$ ; second inequality: definition of $m^{'}$ ; third inequality: monotonicity of $m^{'}$ ), therefore $a (A \cap S) = a (X_{S} \cap S)$ . Then, if $t \in X_{S} \cap B$ , $a (A + t) = a (A)$ , contradiction.

Next we claim that for $Y_{S} \in K$ , $S \in B$ , $Y_{S} \cap T \subseteq B$ . Again, $m^{'} (B \cap S) = b (B \cap S) = d (Y_{S}) \geq b (Y_{S} \cap S) \geq m^{'} (Y_{S} \cap S) \geq m^{'} (B \cap S)$ , thus $m^{'} (Y_{S} \cap S) = m^{'} (B \cap S)$ , so for any $t \in A \cap Y_{S}$ , $m^{'} (t) = 0$ . We use this in the last equation of (for $R \in A$ and $S \in B$ ):

$\begin{aligned} m^{'} (A \cap X_{R}) + m^{'} (B \cap Y_{S}) = m^{'} (A \cap R) + m^{'} (B \cap S) & = d (X_{R}) + d (Y_{S}) \\ \geq d (X_{R} ∖ Y_{S}) + d (Y_{S} ∖ X_{R}) \\ \geq a ((X_{R} ∖ Y_{S}) \cap A) + b ((Y_{S} ∖ X_{R}) \cap B) \\ \geq m^{'} ((X_{R} ∖ Y_{S}) \cap A) + m^{'} ((Y_{S} ∖ X_{R}) \cap B) \\ = m^{'} (X_{R} \cap A) + m^{'} (Y_{S} \cap B) \end{aligned}$

Hence $d (Y_{S} ∖ X_{R}) = b ((Y_{S} ∖ X_{R}) \cap B) = m^{'} ((Y_{S} ∖ X_{R}) \cap B)$ . Then if $t \in Y_{S} \cap A$ , and $t \in X_{R}$ , $Y_{S} ∖ X_{R}$ contradicts the minimality of $Y_{S}$ , proving the claim.

Therefore $K$ is a subpartition: indeed, take $L, K \in K$ , and suppose $K \cap L \neq \emptyset$ . By the previous claim, $L \cap K \cap T = \emptyset$ . Then $d (K) + d (L) \geq d (K ∖ L) + d (L ∖ K)$ , contradicting the minimality of $K$ or $L$ .

Finally, $K$ is clearly admissible, and has value

$\frac{1}{2} (\sum_{R \in A} d (X_{R}) + \sum_{S \in B} d (Y_{S})) = \frac{1}{2} (\sum_{R \in A} a (A \cap R) + \sum_{S \in B} b (B \cap S)) = \frac{m^{'} (T)}{2}$

concluding the proof.

In the same article [6], Frank, Karzanov and Sebő introduced the Node Demand Problem. Motivated by the fact that a maximal vector $m$ in the intersection of the polymatroids $P_{a}$ and $P_{b}$ is not always feasible, this problem asks, given $G, H, m$ , whether $m$ is the incidence vector of a family of edge-disjoint $H$ -paths in $G$ . A demand graph $H$ is two-covered if every terminal is in at most two maximal stable sets of $H$ . This generalizes the notion of bistable graphs (consider a $C_{5}$ ). They proved that an approriate version of the directed cut is sufficient when $H$ is two-covered:

Theorem 10: (Frank , Karzano, Sebő [6]) Let $(G, H, m)$ be an instance of the Node Demand Problem with $H$ two-covered. Then $m$ is feasible iff the following cut condition holds for every $X \subseteq V$ and every $S \subseteq X \cap T$ stable set of $H$ :

$m (S) - m (X \cap T ∖ S) \leq d (X)$

Proof: The necessity is clear: the demands from $S \cap X$ can only be routed to terminals in $X ∖ S$ , or outside $X$ . We prove the sufficiency.

Let $L$ be the family of maximal stable sets of $H$ . We prove that $L$ is 3-cross-free, in order to apply Theorem 7. Take three distinct stable sets $A, B, C$ of $H$ . Because $H$ is two-covered, $A \cap B \cap C = \emptyset$ . Also $D = (A \cap B) \cup (A \cap C) \cup (B \cap C)$ is a stable set. If $D$ is non-empty, say $A \cap B \neq \emptyset$ , then because $H$ is two-covered, $D = A$ or $D = B$ , say $D = A$ , hence $B \cap C = \emptyset$ , $A, B, C$ are not pairwise crossing.

Recall that $λ_{G_{m}} (S)$ is the maximum number of $(S, T ∖ S)$ -paths having an incidence vector $m^{'} \leq m$ , $G_{m}$ being a graph obtained by pushing the terminals to new nodes of degrees given by $m$ . Then for any stable set $S$ of $H$ , by Menger theorem in $G$ , $λ_{G_{m}} (S) = min d (X) + m (S ∖ X) + m ((T \cap X) ∖ S)$ for $X \subset V$ . For $X$ reaching this minimum, we have $m (S) \geq λ_{G_{m}} (S) = d (X) + m (S ∖ X) + m ((X \cap T) ∖ S) \geq m (S \cap X) - m (X \cap T ∖ (S ∖ X)) + m (S - X) + m ((X \cap T) ∖ S) \geq m (S)$ .

Finally, apply Theorem 7 to $G_{m}, L$ to get a family $F$ of paths. Any terminal $t$ is in the stable set ${t}$ , so $λ_{G_{m}} ({t}) = m (t)$ , hence $F$ contains $m (t)$ paths with extremity $t$ . $i f s, t \in T$ are non-adjacent in $H$ , then there is a stable set $S$ containing both $s$ and $t$ , again $λ_{G_{m}} (S) = m (S)$ hence no path in $F$ joins $s$ and $t$ . Therefore $F$ is a solution to the Node Demand Problem $(G, H, m)$ .

Congestion and Distortion

In this section we move to the decision problem regarding multicommodity flows. Instead of having a function $μ$ over pairs of terminals, we are given for each pair of terminals $s, t$ the number $D_{s t}$ of paths that we desire between $s$ and $t$ . Given $G, T, c, D$ , we are asked whether there is $c$ -packing of $T$ -paths $f$ with $f (P_{s t}) \geq D_{s t}$ for all $s, t \in T$ , where $P_{s t}$ is the set of $s t$ -paths. Again, we can define a commodity graph $H = (T, {s t : D_{s t} \neq 0})$ .

The decision version can be solved by linear programming, as long as we don't need an integral solution. It also admits a characterization similar to Theorem 1:

Theorem 11: (Onaga -Kakusho [16]) Given $G, H, c, D$ , exactly one of these two propositions is true:

there is a solution $f$ to the Multicommodity Flow instance $G, H, c, D$ ,
there is a length function $l : E (G) \to R_{+}$ with $\sum_{s t \in H} D_{s t} {dist}_{l} (s, t) > \sum_{e \in E} c_{e} l (e)$ .

The interpretation is the same: if the problem does not have a solution, $G, H$ can be embedded in some metric space, where the total length of $G$ is strictly smaller than what would be the length of a solution. One easy consequence is the necessity of the cut condition: if the first proposition is true, then for any cut $X$ of $G$ , $c (δ_{G} (X)) \geq \sum_{s \in X \cap T, t \in T ∖ X} D_{s t}$ (consider the metric space ${0, 1}$ with $d (0, 1) = 1$ ). We denote $D (X) := \sum_{s \in X \cap T, t \in T ∖ X} D_{s t}$ the total demand between $T \cap X$ and $T ∖ X$ .

Here we are interested in finding when the cut condition is sufficient, or how strong it is. The main reason for looking at this problem in terms of the cut condition is that for many problems, we are interested in finding good cuts more than finding flows, in particular the sparsest cut problem is related to these questions. Other reasons are that cuts are a mathematical object that has many interesting properties, and that there are actually deep results relating the cut condition and existence of multicommodity flows.

In this setting, a natural question is: how much do we need to strengthen the cut condition to ensure the existence of a multicommodity flow? Indeed, the cut condition is seldom sufficient, as this figure shows:

The cut condition is not sufficient, where demands are the dashed edges, capacites are 1 everywhere

In the left side, the cut condition is satisfied but there is no integral solution, though there is a half-integral solution. In the right side, the cut condition is again satisfied, but there is not even a fractional multiflow. Indeed, we can check it by setting the length of any edge to be $1$ , then the total length of $G$ is $6$ , but the sum of lengths of the paths of a solution would be at least $8$ .

As the cut condition is not sufficient, we can reinforce it in the following way: ask for each cut $X$ to have $\sum_{s t \in H \cap δ (X)} D_{s t} \geq α c (δ (X))$ , with $α \geq 1$ . For $α = 1$ , this is simply the cut condition. This parameter $α$ is called the congestion, and one natural problem is to minimize it: given an instance $(G, H, c, D)$ satisfying the cut condition, find the minimum $α$ such that $G, H, α c, D$ is (fractionally) feasible. Leighton and Rao [13] showed that a congestion of $O (\log n)$ is always sufficient. This result was latter improved in a series of papers, until Aumann and Rabani [1] gave a proof that $O (\log | E (H) |)$ is sufficient. An equivalent setting is to ask, in an instance that satisfies the cut condition, for a multiflow that simultaneously routes $1 / α$ unit of demand of each commodity, this is the Maximal Throughput problem. As a consequence, the minimum congestion can be computed using the dual (Theorem 11):

$\frac{1}{α} = min_{d} \frac{c \cdot d}{\sum_{s t \in H} D_{s t} d (s, t)}$

where $d$ ranges over all metrics on $V$ with $d (s, t) \geq 1$ for all $s t \in H$ .

The congestion is strongly related to the notion of distortion in metric embeddings. Here the minimum metric is a graph metric, hence is rather arbitrary. One might wonder what happens when we restrict ourselves to some specific metrics. This question arises naturally when studying the sparsest cut problem: for an instance $(G, H, c, D)$ of the multiflow problem, find a cut $S$ minimizing $\frac{c (δ (S))}{D (S)}$ . Sparsest cuts are noticeably used in clustering problems, where the ability to find sparse cuts of good quality is often critical. They are also quite useful to solve multicommodity flows: for instance, checking the cut condition is equivalent to checking that the sparsity of any cut is at least $1$ .

How do we find a sparsest cut? The answer is: we don't, as it is an NP-hard problem. But we can find good approximations for the sparsest cut problem. Consider the following cut packing problem: Given $G = (V, E)$ , $H = (T \subseteq V, F)$ and $l$ a length function on $E$ , defining a metric $d$ on $V$ , find an $l$ -packing $y$ of cuts in $G$ minimizing $max_{f \in F : l (f) > 0} \frac{l (f)}{\sum_{S : f \in δ_{H} (S)} y_{S}}$ . Let $β$ be the optimum value for this problem, $β$ is called the distortion of $G, H, l$ . This parameter tells how much we need to stretch $l$ to get an $l_{1}$ -metric; indeed, an exact cut packing (i.e. every edge is tightly packed, $β = 1$ ) is equivalent to an $l_{1}$ embedding.

Lemma 12: A metric $d$ on $V$ is an $l_{1}$ -metric if and only if there is $λ : 2^{V} \to R_{+}$ such that $d (u, v) = \sum_{S \subset V : | {u, v} \cap S | = 1} λ (S)$

Proof: Suppose $d$ is an $l_{1}$ metric, with embedding $x_{1}, \dots, x_{n}$ in $R^{p}$ . We define

$λ (S) := \sum_{q = 1}^{p} max (0, min_{i \in S} x_{i q} - max_{j \notin S} x_{j q})$

Then $\sum_{S : i \in S, j \notin S} λ (S) = \sum_{q = 1}^{p} \sum_{S : i \in S, j \notin S} max (0, min_{i^{'} \in S} x_{i^{'} q} - max_{j^{'} \notin S} x_{j^{'} q})$ . For any $q$ , we may assume that $x_{1 q} \leq x_{2 q} \leq \dots x_{n q}$ , then $\sum_{S : i \in S, j \notin S} max (0, min_{i^{'} \in S} x_{i^{'} q} - max_{j^{'} \notin S} x_{j^{'} q}) = \sum_{k = j}^{i - 1} x_{(k + 1) q} - x k q = max (0, x_{i q} - x_{j q})$ . Hence, $\sum_{S : i \in S, j \notin S} λ (S) = d (x_{i}, x_{j})$ .

The reverse direction is even easier: for each $S$ with $λ (S) \neq 0$ , take a new dimension $k$ and set $x_{i k} = λ (S)$ if $i \in S$ , $x_{i k} = 0$ otherwise.

Now, we link the notions of congestion, distortion and sparsest cuts:

Theorem 13: Consider a metric $d$ for $G, H, c, D$ minimizing $\frac{c \cdot d}{\sum_{s t \in H} D_{s t} d (s, t)}$ . Let $λ$ be a cut packing for $d$ with distortion $β$ . Then there is a cut $S$ with $λ (S) \neq 0$ that has sparsity at most $β / α$

Proof: $\frac{1}{α} = \frac{\sum_{e \in E (G)} c_{e} d_{e}}{\sum_{s t \in H} D_{s t} d (s, t)} \geq \frac{\sum_{e \in E (H)} c_{e} \sum_{S : e \in δ (S)} λ (S)}{\sum_{s t \in H} D_{s t} β \sum_{S : s t \in δ (S)} λ (S)} \geq (1 / β) \frac{c (δ (S))}{\sum_{s t \in H \cap δ (S)} D_{s t}}$

for some cut $S$ , where the last inequality comes from $\frac{\sum λ_{i} a_{i}}{\sum λ_{i} b_{i}} \geq min \frac{a_{i}}{b_{i}}$ for any $b \geq 0$ , $λ > 0$ and $a$ .

The following theorem is the congestion-distortion equivalence theorem.

Theorem 14: (Linial , London, Rabinovich [14]) Let $G = (V, E)$ , $H = (T, F)$ be two graphs with $T \subseteq V$ . Then the maximum congestion of $G, H, c, d$ over any $c, d$ satisfying the cut condition, is equal to the maximum distortion of $G, H$ over any shortest path metric $l$ .

We follow the proof given by Chakrabarti, Fleischer and Weibel in [2].

Proof: We fix a pair $G, H$ . We denote by $P_{f}$ the set of possible flow paths for commodity $f \in E (H)$ , and by $P$ their union $⋃_{f \in E (H)} P_{f}$ .

Firstly, we express the congestion $γ (c, d)$ for $G, H, c, d$ as a linear program, consisting in minimizing by how much we violate the capacity constraints to find a flow:

$\begin{array}{ll} γ (c, d) = min α subject to \\ \sum_{P \in P_{f}} x_{P} \geq d_{f} & (\forall f \in E (H)) \\ \sum_{P \in P : e \in P} x_{P} \leq α c_{e} & (\forall e \in E (G)) \\ x_{P} \geq 0 & (\forall P \in P) \end{array}$

By duality we have:

$\begin{array}{ll} γ (c, d) = max \sum_{f \in E (H)} μ_{f} d_{f} subject to \\ μ_{f} \leq \sum_{e \in P} y_{e} & (\forall P \in P_{f}, f \in E (H)) \\ \sum_{e \in E (G)} c_{e} y_{e} = 1 \\ μ, y \geq 0 \end{array}$

At an extreme point, $μ$ is simply the shortest path metric induced by $y$ on the terminals $V (H)$ .

Now we maximise this value $γ (c, d)$ over all possible choices of $c$ and $d$ that satisfy the cut condition:

$\begin{array}{ll} γ = max γ (c, d) subject to \\ \sum_{e \in δ_{G} (S)} c_{e} \geq \sum_{f \in δ_{H} (S)} d_{f} & (\forall S ⊊ V (G)) \\ c, d \geq 0 \end{array}$

We can develop the objective function using the dual linear program for $γ (c, d)$ , this gives the non-linear program with variables $c$ , $d$ , $y$ , $μ$ :

$\begin{array}{ll} γ = max \sum_{f \in E (H)} μ_{f} d_{f} subject to \\ μ_{f} \leq \sum_{e \in P} y_{e} & (\forall P \in P_{f}, f \in E (H)) \\ \sum_{e \in E (G)} c_{e} y_{e} = 1 \\ \sum_{e \in δ_{G} (S)} c_{e} \geq \sum_{f \in δ_{H} (S)} d_{f} & (\forall S ⊊ V (G)) \\ μ_{f}, d_{f} \geq 0 & (\forall f \in E (H)) \\ c_{e}, y_{e} \geq 0 & (\forall e \in E (G)) \end{array}$

Now we refactor this program, by fixing the values of $μ$ and $y$ , assuming $μ$ satisfies the metric inequalities induced by $y$ , we get:

$\begin{array}{ll} w (y, μ) = max \sum_{f \in E (H)} μ_{f} l_{f} subject to \\ \sum_{e \in E (G)} y_{e} c_{e} = 1 \\ \sum_{e \in δ_{G} (S)} c_{e} \geq \sum_{f \in δ_{H} (S)} d_{f} & (\forall S ⊊ V (G)) \\ μ_{f}, d_{f} \geq 0 & (\forall f \in E (H)) \\ c_{e}, y_{e} \geq 0 & (\forall e \in E (G)) \end{array}$

And by adding the metric inequality constraints we get:

$γ = \begin{array}{ll} max w (y, μ) subject to \\ μ_{f} \leq \sum_{e \in P} y_{e} & (\forall e \in P_{f}, f \in E (H)) \\ μ, y \geq 0 \end{array}$

Now we take the dual of the program defining $w (y, μ)$ :

$\begin{array}{ll} w (y, μ) = min ζ \\ \sum_{S ⊊ V : e \in δ_{G} (S)} z_{S} \leq y_{e} ζ & (\forall e \in E (G)) \\ \sum_{S ⊊ V : f \in δ_{H} (S)} z_{S} \geq μ_{f} & (\forall f \in E (H)) \\ z \geq 0 \end{array}$

Now this is just minimizing the distortion given $μ, y$ respecting the metric inequalities. As when maximising $γ$ , $μ$ is the shortest path metric induced by $y$ , we get another expression of $γ$ as the maximum distortion needed to embed a shortest path metric on $V (H)$ into an $l_{1}$ -embedding (a packing of cut). The first expression of $γ$ gave us the maximum congestion over any $c, d$ satisfying the cut condition, hence the congestion-distortion equivalence.

Cut-sufficiency in series-parallel graphs

here.

Metrics and Potentials

Recall the dual of the Maximum MultiCommodity Flow problem, in its metric form:

$\begin{array}{ll} min c \cdot d subject to \\ d (s, t) \geq μ (s, t) & (\forall s, t \in T) \\ d metric on V \end{array}$

It says that we want to find a metric minimizing the total length of the graph, but still keeping the terminals sufficiently far from each other, that is, for every pair $s, t$ of terminals, $s$ and $t$ must be at distance at least $μ (s, t)$ from each other.

Let's start with some very basic considerations. Suppose that we have a graph where each edge $e$ has an associated length $l (e)$ , and we want to know the distance between two vertices $s$ and $t$ . We can get an upper bound easily by exhibiting a shortest $(s, t)$ -path. But how do we prove its optimality, that is how to get a matching lower bound? The classical answer to this problem is to exhibit a potential. A potential is a mapping $p : V \to R$ with the property that for any edge $u v$ , $| p_{v} - p_{u} | \leq l (u v)$ . Notice that the constraints only uses differences between the potential at two vertices, so a potential is defined up to some constant.

A potential gives a lower bound on $d (u, v)$ for any pair of vertices $u, v \in V$ . Indeed, consider any path $u = u_{0}, u_{1}, \dots, u_{k} = v$ , then by a simple summation we get:

$p_{u} - p_{v} = (p_{u_{0}} - p_{u_{1}}) + (p_{u_{1}} - p_{u_{2}}) + \dots (p_{u_{k - 1}} - p_{u_{k}}) \leq l (u_{0} u_{1}) + l (u_{1} u_{2}) + \dots + l (u_{k - 1} u_{k}) \leq l (P)$

hence the difference of potential is a lower bound on the distance between two vertices.

To see that is is a good characterization, we must exhibit, for two given vertices $u$ and $v$ , a potential such that $p_{u} - p_{v} = d (u, v)$ . This is done by defining $p_{w} := d (u, w)$ , as then $p_{u} = 0$ and $p_{v} = d (u, v)$ . We must just check that it is a potential: $d (u, x) - d (u, y) \leq d (x, y)$ for any $x, y \in V$ , which is the triangular inequality.

Applied to our dual problem, we can write a new formulation. It uses one potential $ρ_{t} : V \to R$ for each terminal. The only difficulty is to express the objective function: we would need one additional variable for each edge, to measure (an upper bound on) the maximum difference of any potential between its endpoint, which is the distance of that edge: $max_{s \in T} | ρ_{s} (u) - ρ_{s} (v) |$ . For simplicity, we keep this part hidden and just denote by $| | ρ (u) - ρ (v) | |_{\infty}$ this maximum.

$\begin{array}{ll} min \sum_{u v \in E} c_{u v} | | ρ (u) - ρ (v) | |_{\infty} subject to \\ ρ_{t} (t) = 0 & (\forall t \in T) \\ ρ_{t} (s) \geq μ (s, t) & (\forall (s, t) \in (\binom{T}{2})) \\ ρ_{t} \in R_{+}^{V} & (\forall t \in T) \end{array}$

It is worth noting that this program is also the dual of the edge formulation of the MultiCommodity Flow problem as introduced above (after some cleaning). Thus, to some extent, the correspondance between metrics and potentials is equivalent to the correspondance between packing of cycles and circulations formulated in Theorem 2.

There is another way to get to a dual formulated with a different kind of potential, and it will turn out to be very useful. Recall the metric formulation, and call a metric $m$ on $V \supseteq T$ an extension of $μ$ if $m (s, t) \geq μ (s, t)$ for all pairs $(s, t) \in (\binom{T}{2})$ . We say that an extension $m$ of $μ$ is tight if it is (Pareto) minimal: for every other extension $m^{'}$ there are $x, y \in V$ such that $m (x, y) < m^{'} (x, y)$ . Thus, the metric dual formulation asks for an extension minimizing $c \cdot d$ , and such an extension is clearly minimal.

The universal tight extension $(X, d)$ of a metric space $(T, μ)$ is defined by:

$X := {f : T \to R : \forall s, t \in T^{2}, f (s) + f (t) \geq μ (s, t)}$

$d (f, g) := sup_{t \in T} | f (t) - g (t) |$

Given $t \in T$ , we associate $e_{t} \in X$ defined by $e_{t} (s) = μ (s, t)$ .

Lemma 15: (Dress) Any tight extension $m$ on $V$ of $(T, μ)$ is isometrically embeddable in $(X, d)$ .

Proof: We use the embedding given by $ρ_{v} : t \in T \to m (v, t)$ . We must check that for any $x, y \in V$ , $f (ρ_{x}, ρ_{y}) = m (x, y)$ .

The fact that $m$ is tight implies that for any $x, y \in V$ , there are two terminals $s$ and $t$ such that $m (s, t) = m (s, x) + m (x, y) + m (y, t)$ (and hence $m (x, t) = m (x, y) + m (y, t)$ ). From this we deduce:

$| ρ_{x} (t) - ρ_{y} (t) | = | m (x, t) - m (y, t) | = | m (x, y) + m (y, t) - m (y, t) | = m (x, y)$

and $| ρ_{x} (t^{'}) - ρ_{y} (t^{'}) | = | m (x, t^{'}) - m (y, t^{'}) | \leq m (x, y)$ by the triangular inequality, for any $t^{'} \in T - t$ . Thus, $d (ρ_{x}, ρ_{y}) = m (x, y)$ .

The elements of the universal tight extension can be interpretated as representing the distance from some point to all the terminals. If the sum of the distance to $s$ and $t$ was less that $μ (s, t)$ , than $s$ and $t$ would at distance less than $μ (s, t)$ from each other. This leads to one more formulation of the dual:

$\begin{array}{ll} min c \cdot d subject to \\ ρ_{v} \in X & (\forall v \in V) \\ ρ_{t} (t) = 0 & (\forall t \in T) \end{array}$

The next lemma shows that we can restrict our interest to the minimal elements of the universal tight extension. Let $T_{μ}$ be the tight span of $μ$ , defined by:

$T_{μ} := {ρ \in R^{T} : ρ (s) = sup_{t \in T} μ (s, t) - ρ (t)}$

Lemma 16: (Dress) There is a map $p : X \to T_{μ}$ such that:

$d (p (f), p (g)) \leq d (f, g)$ for all $f, g \in X$ ,
$p (f) \leq f$ for all $f \in X$ .

Proof: Let $f \in X$ . Define $δ_{f} (t) := max_{s \in T} μ (s, t) - f (s) \geq 0$ . Notice that $δ_{f} = f$ when $f \in T_{μ}$ , but $δ_{f}$ is not necessarily in $X$ . We abusively extend the definition of $d$ to any map $T \to R$ .

Then for any $g \in X$ and $t \in T$ , we have

$\begin{aligned} δ_{f} (t) & = sup_{s \in T} μ (s, t) - g (s) + g (s) - f (s) \\ \leq sup_{s \in T} (μ (s, t) - g (s)) + sup_{s \in T} (g (s) - f (s)) \\ = δ_{g} (t) + d (f, g) \end{aligned}$

Hence $δ_{f} (t) - δ_{g} (t) \leq d (f, g)$ for all $t \in T$ , that is $d (δ_{f} (t), δ_{g} (t)) \leq d (f, g)$ .

Define $ψ : f \in X \to λ_{f} f + (1 - λ_{f}) δ_{f}$ , where $λ_{f}$ is maximal such that $ψ (f) \in X$ . Say that a terminal $t$ is tight for $g \in X$ if there is some $s \in T$ for which $f (s) + f (t) = μ (s, t)$ . Then $ψ (f)$ has strictly more tight terminals than $f$ if $f \notin T_{μ}$ . Hence $p := ψ^{| T |} (f)$ has only tight terminals for any $f \in X$ , that is $ψ^{| T |} (f) \in T_{μ}$ . Moreover $ψ$ is clearly a retractation, so is $ψ^{| T |}$ .

This implies the following strenghtening:

$\begin{array}{ll} min c \cdot d subject to \\ ρ_{v} \in T_{μ} & (\forall v \in V) \\ ρ_{t} (t) = 0 & (\forall t \in T) \end{array}$

The first application of this formulation is that we can characterize the fractionality of the dual problem by the dimension of $T_{μ}$ . The fractionality of $μ$ is the minimum $k \in N$ such that any instance $G$ of the $μ$ -Multicommodity Flow problem admits an optimal $\frac{1}{k}$ -integral solution. The dual fractionality is the minimum $k \in N$ such that the dual problem has an optimal $\frac{1}{k}$ -integral solution. The fractionality or dual fractionality may be $\infty$ , and the fractionality is always at least the dual fractionality.

Karzanov first proved the next theorem when $μ$ is a metric, and Hirai extended it to general $μ$ .

Theorem 17: (Karzanov , Hirai) The fractionality of the dual of the Multicommodity Flow problem for a given $μ$ is:

1 , 2 or 4 if $\dim T_{μ} = 2$ ,
$\infty$ if $\dim T_{μ} \geq 3$ .

More to come soon!

Yonatan Aumann, Yuval Rabani: An

O (\log k)

Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm.
SIAM Journal on Computing, 27, 291 -- 301.
Citeseer, (1998).

Amit Chakrabarti, Lisa Fleischer, Christophe Weibel: When the cut condition is enough: a complete characterization for multiflow problems in series-parallel networks.
In: Proceedings of the 44th symposium on Theory of Computing. , 19 -- 26.
(2012).

Chandra Chekuri, F. Bruce Shepherd, Christophe Weibel: Flow-cut gaps for integer and fractional multiflows.
Journal of Combinatorial Theory, Series B.
Elsevier, (2012).

Boris V. Cherkassky: A solution of a problem on multicommodity flows in a network.
Ekonomika i matematicheskie metody, 13, 143 -- 151.
(1977).

Lester R. Ford, Delbert R. Fulkerson: Maximal flow through a network.
Canadian Journal of Mathematics, 8, 399 -- 404.
(1956).

András Frank, Alexander V. Karzanov, András Sebő: On integer multiflow maximization.
SIAM Journal on Discrete Mathematics, 10, 158 -- 170.
(1997).

Hiroshi Hirai: Tight spans of distances and the dual fractionality of undirected multiflow problems.
Journal of Combinatorial Theory, Series B, 99, 843 -- 868.
Elsevier, (2009).

Hiroshi Hirai: Folder complexes and multiflow combinatorial dualities.
SIAM J. Discret. Math. (to appear).
(2009).

Hiroshi Hirai: The maximum multiflow problems with bounded fractionality.
In: Proceedings of the 42nd ACM symposium on Theory of computing. , 115 -- 120.
(2010).

10.

T. C. Hu: Multi-commodity network flows.
Operations Research, 344 -- 360.
JSTOR, (1963).

11.

Alexander V. Karzanov: Minimum 0-extensions of graph metrics.
European Journal of Combinatorics, 19, 71 -- 101.
Elsevier Science, (2004).

12.

Alexander V. Karzanov, Michael V. Lomonosov: Systems of flows in undirected networks.
Mathematical Programming, 59 -- 66.
Institute for System Studies, Moscow, (1978).

13.

Frank T. Leighton, Satish Rao: An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms.
In: 29th Annual Symposium on Foundations of Computer Science (FoCS). , 422 -- 431.
(1988).

14.

N. Linial, E. London, Y. Rabinovich: The geometry of graphs and some of its algorithmic applications.
Combinatorica, 577 -- 591.
(1994).

15.

László Lovász: On some connectivity properties of Eulerian graphs.
Acta Mathematica Hungarica, 28, 129 -- 138.
Akadémiai Kiadó and Springer Science, (1976).

16.

Kenji Onaga, O. Kakusho: On feasibility conditions of multicommodity flows in networks.
IEEE Transactions on Circuit Theory, 18, 425 -- 429.
(1971).

17.

Bruce Rothschild, Andrew Whinston: Feasibility of two commodity network flows.
Operations Research, 1121 -- 1129.
Operations Research Society of America, (1966).

18.

Mouna Sadli: Généralisation de matroïdes et chemins disjoints.
PhD. thesis, Université Joseph Fourier, Grenoble 1, (2000).