Version & licenses
Creative Commons License
  1. {`frametitle "Notes on the multicommodity flow problem"}
  2. {`windowtitle "Notes on the multicommodity flow problem"}
  3. {`menu "guyslain"}
  4. {`author "Guyslain"}
  5. {`date "Last modification: Dec 2013"}

  6. - {internal "introduction" Introduction}
  7. -- {internal "lp-path" Linear program: formulation using paths}
  8. -- {internal "lp-edge" Linear Program: formulation on edges}
  9. -- {internal "cuts" Cuts}
  10. - {internal "scflow" Single-commodity flow}
  11. - {internal "twocflow" Two-commodity flows}
  12. - {internal "bistable" Bistable graphs}
  13. -- {internal "locking" $H$ is a clique and the locking theorem}
  14. -- {internal "polymatroids" Where the polymatroids come into play}
  15. - {internal "congestion" Congestion and distortion}
  16. - {internal "spgraphs" Cut-sufficiency in series-parallel graphs}
  17. {*
  18. -- {internal "k2m" Special case: $K_{2,m}$}
  19. -- {internal "spproperties" Properties of series-parallel graphs}
  20. -- {internal "compliant" Special case: compliant instances}
  21. -- {internal "spg-general" General case: odd-spindle free instances}
  22. *}
  23. - {internal "metrics" Metrics and potentials}

  24. {section 2 {`anchor "introduction"} Introduction} An instance of the
  25. {sc MultiCommodity flow} problem (or {sc Multiflow} problem) is
  26. composed of an undirected graph $G = (V,E)$ with capacities $c: E \to
  27. \mathbb{N}$, a set of {emph terminals} $T \subseteq V$, and a function
  28. $\mu: \binom{T}{2} \to \mathbb{R}_+$. We denote $H$ the graph with
  29. vertex set $T$, and edges $st$ for every pair $s,t \in T$ of terminals
  30. with $\mu_(s,t) > 0$.

  31. A {emph $T$-path} is any path whose endpoints are distinct elements of
  32. $T$. For two vertices $s$ and $t$, an $(s,t)$-path is a path whose
  33. endpoints are $s$ and $t$. Denote by $\mathcal{P}_{G,T}$ the set of
  34. all $T$-paths of $(G,T)$ (we will omit the indices when there is no
  35. ambiguity). A $c$-packing of $T$-paths is a mapping $f: \mathcal{P}
  36. \to \mathbb{R}_+$, such that, for any edge $e \in E$, the sum of
  37. $f(P)$ where $P$ ranges over all $T$-paths containing $e$ is at most
  38. $c_e$. The value of a $T$-path $P$ with extremities $s,t \in T$ is
  39. $\mu(p) := \mu(s,t)$. We extend this definition to packings of
  40. $T$-paths by saying that the value of a packing $f$ is
  41. $\left\|f\right\|_\mu := \sum_{P\in\mathcal{P}} f_P \mu(P) = f \cdot
  42. \mu$.

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

  44. {section 3 {`anchor "lp-path"} Linear Program: formulation using paths}

  45. We can rewrite the definition directly as a linear program:

  46. $$
  47. \begin{array}{ll}
  48. \max ||f||_\mu \quad\textrm{subject to} & \\
  49. \qquad \sum_{P \in \mathcal{P}, e \in P} f_P \leq c_e & (\forall e \in E)\\
  50. \qquad f \geq 0 &
  51. \end{array}
  52. $$

  53. From this we can derive the dual program with variables $y \in \mathbb{R}_+^{E}$:

  54. $$
  55. \begin{array}{ll}
  56. \min \sum_{e \in E} c_e y_e \quad\textrm{subject to} & \\
  57. \qquad \sum_{e \in P} y_e \geq \mu_P & (\forall P \in \mathcal{P})\\
  58. \qquad y \geq 0
  59. \end{array}
  60. $$

  61. 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 ({emph 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 $\mu_{s,t}$ for the chosen lengths.

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

  63. $$
  64. \begin{array}{ll}
  65. \min c \cdot d \quad\textrm{subject to} & \\
  66. \qquad d(s,t) \geq \mu(s,t) & (\forall s,t \in T)\\
  67. \qquad d~\text{metric on}~V &
  68. \end{array}
  69. $$

  70. 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 = uv \in P} d(u,v)$ at least $\mu_P$. Thus, $P$ consumes at least $f_P d(P)$ of the length of $G$, and contributes exactly $f_P \mu_P$ to the primal objective. From this we get:
  71. $$ \sum_{P \in \mathcal{P}} f_P \mu_P \leq \sum_{P \in \mathcal{P}} f_P d(P) \leq d(G)$$
  72. 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.

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

  74. {theorem {`anchor "dist_cond"} {`caption {Onaga-Kakusho {ref "onaga1971fcm"}}} {
  75. The maximum value of a multicommodity flow for $(G,T,c,\mu)$ is equal to the minimum length $d(G)$ over all distance $d$ such that $d(s,t) \geq \mu(s,t)$ for all terminals $s,t \in T$.
  76. }}

  77. 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)$:
  78. - every active $T$-path $P$ ({emph i.e.} with $f_P > 0$) has length $d(P) = \mu_P$,
  79. - every active edge $e = uv$ ({emph i.e.} with $d(u,v) > 0$) is saturated: $\sum_{P \in \mathcal{P}, e \in P} f_P = c_e$.

  80. {section 3 {`anchor "lp-edge"} Linear Program: formulation on edges}

  81. 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.

  82. Let $E(H)$ be $\{h_1 = s_1t_1,\ldots, h_n = s_nt_n\}$. The variables are $f \in \mathbb{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).
  83. $$
  84. \begin{array}{ll}
  85. \max \sum_{i=1}^n \mu(s_i,t_i) f_{h_i,i}\quad\textrm{subject to} & \\
  86. \qquad \sum_{e \in \delta^+_{G+H}(v)} f_{e,i} - \sum_{e \in \delta^-_{G+H}(v)} f_{e,i} = 0 & (\forall v \in V, i \in [1,h]) \\
  87. \qquad f_{h_i,j} = 0 & (\forall i \neq j)\\
  88. \qquad \sum_{i \in [1,h]} |f_{e,i}| \leq c_e & (\forall e \in E, i \in [1,h])
  89. \end{array}
  90. $$

  91. 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.

  92. 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.

  93. 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 \mathbb{R}^{E(G)}$ in any graph $G$ is called a {emph circulation} if it satisfies this constraint, precisely $\sum_{e \in \delta^+_G(v)} f_e = \sum_{e \in \delta^-_G(v)}$ for all vertex $v \in V(G)$. Here, $\delta^+_G(v)$ and $\delta^-_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 \mathbb{R}$, we define the excess of $g$ at $v$ by:
  94. $$\textrm{excess}(g,v) := \sum_{e \in \delta^-(v)} g_e - \sum_{e \in \delta^+(v)} g_e$$
  95. 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.

  96. 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.

  97. 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 {emph commodity edges} $s_it_i$. Then orient each cycle such that $s_it_i$ is always forward. For a given cycle $C$, let $\chi_C \in \{-1,0,1\}^{E(G+H)}$ be the function defined by $\chi_C(e) = 1$ if $e$ is forward in $C$, $\chi_C(e) = -1$ if $e$ is backward in $C$, and $\chi_C(e) = 0$ otherwise. It is obvious that for any cycle $\chi_C$ is a circulation, and any linear combination of circulations is a circulation. Hence, $\sum_{P~(s_i,t_i)\text{-path}} f_P \chi_{C(P)}$ defines a circulation $(f_{e,i})_e \in \mathbb{R}^{E(G+H)}$. Repeating this over every commodity gives the equivalent solution to the edge formulation.

  98. 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:

  99. {theorem {`anchor "conf-dec"} {`caption {Fulkerson, comformal decomposition of circulation}} {
  100. Let $f$ be a circulation on a graph $G$, then there is a set of at most $|E(G)|$ cycles $C_1,\ldots,C_k$ such that $f$ is a conic combination of $\chi_{C_1},\ldots,\chi_{C_k}$, and no edge is used backward in one cycle and forward in another one.
  101. }}

  102. 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.

  103. 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 ({emph i.e.} {sc Maximum Flow}) always admits an integral optimal solution. We will show an alternative proof below.

  104. {section 3 {`anchor "cuts"} Cuts}

  105. We recall that a {emph cut} $\delta(X)$ is the subset of edges $uv \in E$ with exactly one endpoint in $X$ (formally $|\{u,v\} \cap X| = 1$). The capacity $c(\delta(X))$ of a cut is $\sum_{e \in \delta(X)} c_e$. We say that a cut $\delta(X)$ {emph separates} $a$ from $b$ if $|X \cap \{a,b\}| = 1$. An {emph $(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 $\lambda(A,B)$ the minimum capacity of an $(A,B)$-cut, $\lambda(S) = \lambda(S,T \setminus S)$ (where $T$ is the set of terminals), and $\delta[A,B]$ the set of edges with one endpoint in $A \setminus B$ and the other in $B \setminus A$.

  106. 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 $st$ cannot contribute to the objective more than $c \mu(s,t)$, where $c$ is the capacity of a (minimum) $(s,t)$-cut.

  107. We will use the following general inequalities on cuts. For any sets $A,B \subseteq V$,
  108. $$c(\delta(A)) + c(\delta(B)) = c(\delta(A \cup B)) + c(\delta(C \cap B) + 2 c(\delta[A,B])$$

  109. As the capacities are always non-negative, it implies the submodularity inequation for cuts:
  110. $$c(\delta(A)) + c(\delta(B)) \geq c(\delta(A \cup B)) + c(\delta(C \cap B))$$

  111. Another similar relation is (actually they are equivalent using that $\delta(A) = \delta(\overline{A})$):
  112. $$c(\delta(A) + c(\delta(B)) = c(\delta(A \setminus B)) + c(\delta(B \setminus A) + 2c(\delta[A \cap B, \overline{A \cup B}])$$

  113. Given an instance $G,H,c,D$, we will denote $\sigma(U)$ the surplus of a cut defined by $U$:
  114. $$ \sigma(U) = c(\delta_G(U)) - D(\delta_H(U)) $$

  115. A cut $\delta(U)$ is {emph tight} if its surplus $\sigma(U) =
  116. 0$. $\sigma$ has remarkable equalities similar to those of cuts (from
  117. which they derive easily). We will also use the notation $\sigma[U,W]
  118. = c(\delta[U,W]) - D(\delta[U,W])$.

  119. We say that a cut $\delta(X)$ is {emph central} in $G$ if both $G[X]$ and $G[V \setminus X]$ are connected.

  120. {section 2 {`anchor "scflow"} Single-commodity flows}

  121. We start with the simplest case where $T = \{s,t\}$, that is $H$ has only one edge. By scaling, we may assume that $\mu(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 {link 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.

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

  123. {theorem {`anchor "mfmc"} {`caption {Ford-Fulkerson {ref "ford1956maximal"}, Max-Flow-Min-Cut}} {
  124. The maximum value of an $(s,t)$-flow in $G,c$ is equal to the minimum capacity of an $(s,t)$-cut.
  125. }}

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

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

  129. Consider any edge $e = uv$ in $\delta(R_\alpha)$, wlog $u \in R_\alpha$. 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 $\delta(R_\alpha)$ only at $e$, otherwise its length would be strictly more than $1$. By summing over all the edges of $R_\alpha$, and because every active path intersects $\delta(R_\alpha)$, we get $c(\delta(R_\alpha)) = ||f||$.
  130. }}

  131. 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).

  132. 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 $\mu$ is not uniform.

  133. 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 \mathbb{N}^R$ such that there is an integral $(R,S)$-flow with exactly $m(r)$ paths with endpoint $r$, for any $r \in R$.

  134. {corollary {
  135. Let $\{R, S\}$ be a partition of $T$, and $m \in \mathbb{R}^R$. Then there is an $(R,S)$-flow with $m(r)$ $(r,S)$-paths, for any $r \in R$, if and only if $\lambda(R',S) \geq m(R')$ for any $R' \subseteq R$.
  136. }}

  137. {proof {
  138. The necessity is obvious. Let $m \in \mathbb{R}^R$ be such that there is no flow as required. Define $G'$ by adding to $G$ a vertex $r$ with edges $rt$ of capacity $m(t)$ for every $t \in R$, and a vertex $s$ with edges $ts$ 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'}(\delta(X)) < m(R)$. Consider $X = X' \cap V(G)$, then $m(X \cap R) = m(R) - c_{G'}(\delta[s,R \setminus X']) > c_{G'}(\delta[X' - r, V(G') \setminus X]) = c_G(\delta(X))$ (and thus $m(R') > \lambda(R',S)$), because $c_{G'}(\delta(X')) = c_{G'}(\delta[r,R \setminus X] + c_{G'}(\delta[X' - r, V(G') - X'])$.
  139. }}

  140. {section 2 {`anchor "twocflow"} Two-commodity flows}

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

  142. {theorem {`anchor "rw"} {`caption {Hu {ref "hu1963multi"}, Rothschild-Whinston {ref "rothschild1966ftc"}}} {
  143. When $H = \{s_1t_1, s_2t_2\}$, $\mu(s_1,t_1) = \mu_1 \leq \mu_2 = \mu(s_2,t_2)$, we have:
  144. $$ \max_f \left\|f\right\|_\mu = \mu_1 \min_{X}~c(\delta(X)) + (\mu_2 - \mu_1) \min_{Y}~c(\delta(y))$$
  145. 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.
  146. }}

  147. {proof {
  148. 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_1t_1$, and $r_2$ units for $s_2t_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 \setminus 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(\delta(X)) + c(\delta(Y)) \geq \max\{c(\delta(Y \setminus X)), c(\delta(Y \cup X))\}$, hence $c(\delta(X)) \geq r_1$.

  149. 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(ss1) = r_1$, $c(ss_2) = r_2$, $c(t_1t) = r_1$ and $c(t_2t) = r_2$. Let $g':E(G_1) \to \mathbb{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$.
  150. - if $X$ separates the two pairs $s_1t_1$ and $s_2t_2$, then by definition of $r_1$, $X$ has capacity at least $r_1 + r_2$.
  151. - if $X$ separates only $s_1$ from $t_1$, then $\delta(X)$ contains either $ss_2$ or $t_2t$, of capacity $r_2$, and $\delta(X')$ separates $s_1$ from $t_1$, hence $c_1(\delta(X')) = r_2 + c(\delta(X)) \geq r_1 + r_2$.
  152. - symmetrically if $X$ separates only $s_2$ from $t_2$, $c(\delta(X)) \geq r_1 + r_2$.
  153. - if $X$ separates none of the two pairs, $X$ contains one of $\{ss_1,t_1t\}$ and one of $\{ss_2,t_2t\}$, hence $c(\delta(X)) \geq r_1 + r_2$.

  154. 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:
  155. - $\textrm{excess}(g,t_1) = -\textrm{excess}(g,s_1) = r_1$,
  156. - $\textrm{excess}(g,t_2) = -\textrm{excess}(g,s_2) = r_2$,
  157. - $\textrm{excess}(h,t_1) = -\textrm{excess}(h,s_1) = r_1$,
  158. - $\textrm{excess}(h,s_2) = -\textrm{excess}(h,t_2) = -r_2$,
  159. - and $\textrm{excess}(g,v) = \textrm{excess}(h,v) = 0$ for any $v \in V \setminus T$.

  160. Now, consider $f_1 = \frac{g + h}{2}$ and $f_2 = \frac{g - h}{2}$. We get immediately:
  161. - $\textrm{excess}(f_1,t_1) = -\textrm{excess}(f_1,s_1) = r_1$,
  162. - $\textrm{excess}(f_2,t_2) = -\textrm{excess}(f_2,s_2) = r_2$,
  163. - all the other excesses are $0$.

  164. 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$:
  165. $$\left|f_1(e)\right| + \left|f_2(e)\right| = \frac{1}{2}\left(\left|g(e) + h(e)\right| + \left|g(e) - h(e)\right| \right) \leq c_e$$
  166. 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 $\left|g(e)\right| \leq \left|h(e)\right|$, symmetrically otherwise), and $\left|h(e)\right| \leq c_e$.
  167. }}

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

  169. {section 2 {`anchor "bistable"} Bistable graphs}

  170. Most of this section relies on an article of Frank, Karzanov and Sebő {ref "frank1997integer"}, and the PhD thesis of Mouna Sadli {ref "sadli"}. We follow the former to prove a theorem by Karzanov and Lomonosov {ref "karzanov1978systems"}.

  171. {section 3 {`anchor "locking"} $H$ is a clique and the locking theorem}

  172. 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 $\lambda(t)$ the minimum capacity of a $(t,T - t)$-cut.

  173. {theorem {`caption {Cherkasky {ref "cherkassky1977solution"}, Lovász {ref "lovasz1976some"}}} {
  174. If $\mu(s,t) = 1$ for every pair $s,t \in \binom{T}{2}$, then $\max_f \left\|f\right\|_\mu = \frac{1}{2} \sum_{t \in T} \lambda(t)$.
  175. }}

  176. We will prove a generalization of this theorem, but before that we need some definitions. We say that a family of paths {emph locks} a subset of terminals $A \subseteq T$ if it contains $\lambda(A,T-A)$ $(A,T-A)$-paths. A family of subsets of $T$ is {emph 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 \setminus B$, $B \setminus A$ and $\overline{A \cup B}$ is empty. An instance of {sc Multiflow} is inner-Eulerian if $c(\delta(v))$ is even for all non-terminal vertex $v \in V \setminus T$.

  177. {theorem {`caption {Karnazov, Lomonosov}} {`anchor "kl3crossfree"} {
  178. Let $G,c,T$ be an inner-Eulerian instance and $\mathcal{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 $\mathcal{L}$.
  179. }}

  180. Before giving the proof of this theorem, let's see why it implies the Cherkasky-Lovász theorem. Take the family $\mathcal{L} = \left(\{t\}\right)_{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 $\lambda(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} \lambda(t)$, as predicted by the Cherkasky-Lovász theorem.

  181. {proof {
  182. The proof relies on the splitting-off technique: a splitting-off operation consists in taking two incident edges $uv$, $vw$, and replacing them by the edge $uw$. We only want to do it when it preserves the minimum cuts of the graph (the {emph tight} cuts). If we manage to apply splitting-off iteratively until the graph becomes {emph trivial}, without altering the $\lambda(S)$ values for $S \in \mathcal{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 {emph unfolding} the splitting-off in a natural way.

  183. Consider an edge $tu \in E$, with $t \in T$ and $u \notin T$. We want to show that there always is an edge $uv$ such that we can split $tu$, $uv$. We say that a set $X$ of vertices is {emph tight} if $X \cap T \in \mathcal{L}$ and $c(\delta(X)) = \lambda(X \cap T)$.

  184. 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(\delta(X,Y)) = 0$. Indeed, $(X \cup Y) \cap T = Y \cap T \in \mathcal{L}$ and $(X \cap Y) \cap T = X \cap T \in \mathcal{L}$, proving the first condition. It also implies that:
  185. $$\lambda(X \cap T) + \lambda(Y \cap T) = c(\delta(X)) + c(\delta(Y)) = c(\delta(X \cap Y)) + c(\delta(X \cup Y)) + 2 c(\delta[X,Y]) \geq \lambda(X \cap T) + \lambda(Y \cap T) + 2 c(\delta[X,Y])$$
  186. As $c$ is non-negative, we get that $c(\delta[X,Y]) = 0$, $\lambda(X \cap T) = c(\delta(X \cap Y))$ and $\lambda(Y \cap T) = c(\delta(X \cup Y))$, proving the claim.

  187. 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 $\mathcal{L}$, and hence are not pairwise crossing.
  188. - 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$.
  189. - if $T \subseteq X \cup Y$, then $\overline{X}$ is tight and $\overline{X} \cap T \subseteq Y \cap T$, hence by the first claim $c(\delta[\overline{X},Y]) = 0$, contradicting the existence of the edge $tu$.

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

  191. The two last claims prove the existence of an edge $uv$ that is not covered by any tight set. Moreover, if for some $X \subseteq V$, $X \cap T \in \mathcal{L}$ and $\lambda(X \cap T) < c(\delta(X))$, then $\lambda(X \cap T) \leq c(\delta(X)) - 2$ because the instance is Eulerian. Thus, splitting off $su$, $uv$ does not change the values of the $\lambda(S)$ for any $S \in \mathcal{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.
  192. }}

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

  194. {section 3 {`anchor "polymatroids"} Where the polymatroids come into play}

  195. A graph $H$ is {emph bistable} if there are two partitions such that $st \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 $\mu: \binom{T}{2} \to \{0,1\}$. An $H$-path is a path whose endpoints $s$, $t$ are endpoints of an edge of $H$, {emph i.e.} $\mu(s,t) = 1$.

  196. An admissible subpartition of $V$ is a subpartition $X_1,\ldots,X_k$ with $T \subseteq \bigcup_{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,\ldots,X_k$ is defined by $\sum_{i=1}^k \frac{c(\delta(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:

  197. {theorem {`caption {Karzanov, Lomonosov}} {`anchor "kl"} {
  198. 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.
  199. }}

  200. 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.

  201. A {emph polymatroid} is a polyhedron $P(r) := \{x \in \mathbb{R}_+^S~|~\forall A \subseteq S, x(A) \leq r(A)\}$, where $S$ is a finite set and $r: 2^S \to \mathbb{R}_+$ is a {emph polymatroidal function}:
  202. - $r(\emptyset) = 0$,
  203. - $r(A) \leq r(B)$ for all $A \subseteq B \subseteq S$ (monotonicity),
  204. - $r(A) + r(B) \geq r(A \cup B) + r(A \cap B)$ for all $A, B \subseteq S$ (submodularity).
  205. $r$ is the rank function of $P$.

  206. Edmonds introduced the concept of polymatroids and several great properties they have. Among them:
  207. - the polymatroidal function is uniquely determined by the polymatroid,
  208. - a polymatroid is integral iff its polymatroidal function is integral-valued,
  209. - 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 \setminus X)$. If $a$ and $b$ are integral, the maximum $x$ can be chosen integral.
  210. - given an (integral) polymatroid $P$ on $S$ with rank function $r$, any (integral) vector $p$ of $P$ is dominated by a vector in the {emph base polyhedron} $B(P) := P \cap \{x \in \mathbb{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)$.

  211. 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 \mathbb{R}_+^A$ for which there is an $(A,T \setminus A)$-flow with exactly $m(a)$ $(a,T \setminus A)$-paths for each $a \in A$ are described by the equations $m(A') \leq \lambda(A', T \setminus A)$. As the function $r: 2^A \to \mathbb{N}$ with $r(A') = \lambda(A',\overline{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$,
  212. $$ r(X) + r(Y) = c(\delta(X')) + c(\delta(Y')) \geq c(\delta(X' \cup Y')) + c(\delta(X' \cap Y') \geq r(X \cup Y) + r(X \cap Y)$$
  213. where $X'$ and $Y'$ are respectively a minimum capacity $(X,T-X)$-cut and a minimum capacity $(Y,T-Y)$-cut.

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

  215. {theorem {`caption {Frank, Karzanov, Sebő {ref "frank1997integer"}}} {`anchor "thpartitionpath"} {
  216. Let $m$ be an integer vector of $P(\mathcal{X})$, with $m(T) = r_{\mathcal{X}}(T)$. Then there is an integer packing of $\mathcal{X}$-paths such that every $t \in T$ is the endpoint of exactly $m(t)$ paths.
  217. }}

  218. {proof {
  219. For a part $X \in \mathcal{X}$, define a minimum capacity $(X,T-X)$-cut minimal $\delta(S_X)$ such that $S_X$ is minimal by inclusion. Let $X, Y \in \mathcal{X}$. We claim that $S_X$ and $S_Y$ are disjoint. Indeed,
  220. $$\lambda(X,T \setminus X) + \lambda(Y,T \setminus Y) = c(\delta(S_X)) + c(\delta(S_Y)) \geq c(\delta(S_X \setminus S_Y)) + c(\delta(S_X \setminus S_Y)) \geq \lambda(X,T \setminus X) + \lambda(Y,T \setminus Y)$$
  221. thus $c(\delta(S_X \setminus S_Y)) = c(\delta(S_X))$ and by minimality $S_X \cap S_Y = \emptyset$.

  222. Let $G'$ be the graph obtained by contracting each $S_X$ into a single vertex $v_X$, for $X \in \mathcal{X}$. Define $T'$ to be the set of contracted vertices, $T' := \{v_X, X \in \mathcal{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 $\lambda(X,T \setminus X)$ paths.

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

  224. }}

  225. If $H$ is induced by a partition, this means that the polymatroid associated to that partition describes the incidence vectors $m \in \mathbb{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 {ref "frank1997integer"}, but unfortunately this approach fails. The reason is that there is no equivalent of Theorem {ref "thpartitionpath"} 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:

  226. {figure af://guyslain/images/maths/bistable-counterexample.png {`tooltip "Commodities are dashed, terminals are in black"} A counterexample to the polymatroid intersection approach for Karzanov-Lomonosov bistable theorem.}

  227. $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 $\{\{v1\}, \{v_2\}, \{v_3, v_6, v_4\}\}$).

  228. The proof in {ref "frank1997integer"} 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 {ref "kl"} for Eulerian $G$, for inner Eulerian one would add a new terminal adjacent to odd vertices, and apply the Eulerian case.

  229. {proof {`caption {of Theorem {ref "kl"}, only for $G$ Eulerian }} {
  230. let $\mathcal{A}$ and $\mathcal{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:
  231. - a family of $m'(T)/2$ $H$-paths,
  232. - an admissible subpartition of value $m'(T)/2$.

  233. 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:
  234. $$m_a + m_b - m \geq m'$$
  235. For any vector $q \in \mathbb{N}^T$, let $G_q$ be the graph obtained by adding for each terminal $t$, a new vertex $t'$, an edge $tt'$ 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 $\lambda_{G_q}(U)$ the maximum number of $(U,T \setminus U)$ paths in $G_q$ for any $U \subset T$.

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

  237. Then we count the number of $\mathcal{A}$-paths in $\mathcal{F}$ ({emph ie} connecting distinct parts of $\mathcal{A}$). $m \geq m_a \in P_a$ (Theorem {ref "thpartitionpath"}), by definition of $P_a$ there is a packing of $\mathcal{A}$ paths locking $\mathcal{A}$ with incidence vector $m_a$. For any $S \in \mathcal{A}$, because $\lambda_{G_m}(S) \geq \lambda_{G_{m_a}}(S) = m_a(S)$, there are at least $m_a(S)$ paths in $\mathcal{F}$ with exactly one extremity in $S$. Therefore there are at least $m_a(T)/2$ $\mathcal{A}$-paths in $\mathcal{F}$. Similarly there are at least $m_b(T)/2$ $\mathcal{B}$-paths in $\mathcal{F}$.

  238. Now we count the number $h$ of $H$-paths, recall that $\left|\mathcal{F}\right| \leq m(T)/2$. We remove from that the paths that are neither $A$-paths nor $B$-paths.
  239. $$
  240. \begin{align*}
  241. h &\geq \left|\mathcal{F}\right| - \left(\left|\mathcal{F}\right| - m_a(T)/2 \right) - \left(\left|\mathcal{F}\right| - m_a(T)/2\right)\\
  242. &\geq m_a(T)/2 + m_b(T)/2 - \left|\mathcal{F}\right|\\
  243. &\geq (m_a(T) + m_b(T) - m(T))/2\\
  244. &\geq m'(T)/2
  245. \end{align*}
  246. $$
  247. This concludes the first part of the proof.

  248. 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$.

  249. For a stable set $S \in \mathcal{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 $\mathcal{A}$, and $m'(A) = a(A)$). Similarly define $Y_S$ for any stable set $S \in \mathcal{B}$, $d(Y_S) = b(B \cap S) = m'(B \cap S)$. We consider $\mathcal{K} := \{X_S~:~S \in \mathcal{A}, S \cap A \neq \emptyset\} \cup \{Y_S~:~S \in \mathcal{B}, S \cap B \neq \emptyset\}$, and prove that it is a subpartition of value $m'(T)/2$

  250. The main step is to prove that $\mathcal{K}$ is a subpartition.

  251. We claim that for $X_S \in \mathcal{K}$, $S \in \mathcal{A}$, $X_S \cap T \subseteq A$. Indeed,
  252. $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.

  253. Next we claim that for $Y_S \in \mathcal{K}$, $S \in \mathcal{B}$, $Y_S \cap T \subseteq B$. Again,
  254. $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
  255. $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 \mathcal{A}$ and $S \in \mathcal{B}$):
  256. $$
  257. \begin{align*}
  258. m'(A \cap X_R) + m'(B \cap Y_S) = m'(A \cap R) + m'(B \cap S) &= d(X_R) + d(Y_S)\\
  259. &\geq d(X_R \setminus Y_S) + d(Y_S \setminus X_R) \\
  260. &\geq a((X_R \setminus Y_S) \cap A) + b((Y_S \setminus X_R) \cap B) \\
  261. &\geq m'((X_R \setminus Y_S) \cap A) + m'((Y_S \setminus X_R) \cap B) \\
  262. &= m'(X_R \cap A) + m'(Y_S \cap B)
  263. \end{align*}
  264. $$
  265. Hence $d(Y_S \setminus X_R) = b((Y_S \setminus X_R) \cap B) = m'((Y_S \setminus X_R) \cap B)$. Then if $t \in Y_S \cap A$, and $t \in X_R$, $Y_S \setminus X_R$ contradicts the minimality of $Y_S$, proving the claim.

  266. Therefore $\mathcal{K}$ is a subpartition: indeed, take $L, K \in \mathcal{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 \setminus L) + d(L \setminus K)$, contradicting the minimality of $K$ or $L$.

  267. Finally, $\mathcal{K}$ is clearly admissible, and has value
  268. $$\frac{1}{2} \left(\sum_{R \in \mathcal{A}} d(X_R) + \sum_{S \in \mathcal{B}} d(Y_S)\right)
  269. = \frac{1}{2} \left(\sum_{R \in \mathcal{A}} a(A \cap R)+\sum_{S \in \mathcal{B}} b(B \cap S)\right)
  270. = \frac{m'(T)}{2}
  271. $$
  272. concluding the proof.

  273. }}

  274. In the same article {ref "frank1997integer"}, Frank, Karzanov and Sebő introduced the {sc 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 {emph 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:

  275. {theorem {`caption {Frank, Karzano, Sebő {ref "frank1997integer"}}} {`anchor "thtwocov"} {
  276. Let $(G,H,m)$ be an instance of the {sc 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$:
  277. $$ m(S) - m(X \cap T \setminus S) \leq d(X)$$
  278. }}

  279. {proof {
  280. The necessity is clear: the demands from $S \cap X$ can only be routed to terminals in $X \setminus S$, or outside $X$. We prove the sufficiency.

  281. Let $\mathcal{L}$ be the family of maximal stable sets of $H$. We prove that $\mathcal{L}$ is 3-cross-free, in order to apply Theorem {ref "kl3crossfree"}. 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.

  282. Recall that $\lambda_{G_m}(S)$ is the maximum number of $(S,T \setminus 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$, $\lambda_{G_m}(S) = \min d(X) + m(S \setminus X) + m((T \cap X) \setminus S)$ for $X \subset V$. For $X$ reaching this minimum, we have $m(S) \geq \lambda_{G_m}(S) = d(X) + m(S \setminus X) + m((X \cap T) \setminus S) \geq m(S\cap X) - m(X \cap T \setminus (S \setminus X)) + m(S-X) + m((X \cap T) \setminus S) \geq m(S)$.

  283. Finally, apply Theorem {ref "kl3crossfree"} to $G_m, \mathcal{L}$ to get a family $\mathcal{F}$ of paths. Any terminal $t$ is in the stable set $\{t\}$, so $\lambda_{G_m}(\{t\}) = m(t)$, hence $\mathcal{F}$ contains $m(t)$ paths with extremity $t$. $if s,t \in T$ are non-adjacent in $H$, then there is a stable set $S$ containing both $s$ and $t$, again $\lambda_{G_m}(S) = m(S)$ hence no path in $\mathcal{F}$ joins $s$ and $t$. Therefore $\mathcal{F}$ is a solution to the {sc Node Demand Problem} $(G,H,m)$.

  284. }}

  285. {section 2 {`anchor "congestion"} Congestion and Distortion}

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

  294. The decision version can be solved by linear programming, as long as
  295. we don't need an integral solution. It also admits a characterization
  296. similar to Theorem {ref "dist_cond"}:

  297. {theorem {`caption {Onaga-Kakusho {ref "onaga1971fcm"}}} {`anchor "dist_cond_dec"} {
  298. Given $G,H,c,D$, exactly one of these two propositions is true:
  299. - there is a solution $f$ to the {sc Multicommodity Flow} instance $G,H,c,D$,
  300. - there is a length function $l: E(G) \to \mathcal{R}_+$ with $\sum_{st \in H} D_{st}\text{dist}_l(s,t) > \sum_{e \in E} c_e l(e)$.
  301. }}

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

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

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

  324. {figure af://guyslain/images/maths/multiflow-cut-condition.png {`width 800} The cut condition is not sufficient, where demands are the dashed edges, capacites are 1 everywhere}

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

  331. As the cut condition is not sufficient, we can reinforce it in the
  332. following way: ask for each cut $X$ to have $\sum_{st \in H \cap
  333. \delta(X)} D_{st} \geq \alpha c(\delta(X))$, with $\alpha \geq 1$. For
  334. $\alpha = 1$, this is simply the cut condition. This parameter
  335. $\alpha$ is called the {emph congestion}, and one natural problem is
  336. to minimize it: given an instance $(G,H,c,D)$ satisfying the cut
  337. condition, find the minimum $\alpha$ such that $G,H,\alpha c,D$ is
  338. (fractionally) feasible. Leighton and Rao {ref
  339. "leighton1988approximate"} showed that a congestion of
  340. $O(\log n)$ is always sufficient. This result was latter improved in a
  341. series of papers, until Aumann and Rabani {ref "aumann1998log"} gave a
  342. proof that $O(\log~\left|E(H)\right|)$ is sufficient. An equivalent
  343. setting is to ask, in an instance that satisfies the cut condition, for a
  344. multiflow that simultaneously routes $1/\alpha$ unit of demand of each
  345. commodity, this is the {sc Maximal Throughput} problem. As a
  346. consequence, the minimum congestion can be computed using the dual
  347. (Theorem {ref "dist_cond_dec"}):

  348. $$\frac{1}{\alpha} = \min_{d} \frac{c \cdot d}{\sum_{st \in H} D_{st} d(s,t)} $$
  349. where $d$ ranges over all metrics on $V$ with $d(s,t) \geq 1$ for all $st \in H$.

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

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

  372. {lemma {
  373. A metric $d$ on $V$ is an $l_1$-metric if and only if there
  374. is $\lambda: 2^V \to \mathbb{R}_+$ such that $d(u,v) = \sum_{S \subset
  375. V~:~|\{u,v\} \cap S| = 1} \lambda(S)$
  376. }}

  377. {proof { Suppose $d$ is an $l_1$ metric, with embedding
  378. $x_1,\ldots,x_n$ in $\mathbb{R}^p$. We define
  379. $$\lambda(S) := \sum_{q=1}^p \max \left(0, \min_{i \in S} x_{iq} - \max_{j \notin S} x_{jq}\right)$$
  380. Then $\sum_{S: i \in S, j \notin S} \lambda(S) = \sum_{q=1}^p \sum_{S:
  381. i \in S, j \notin S} \max \left(0, \min_{i' \in S} x_{i'q} - \max_{j'
  382. \notin S} x_{j'q}\right)$. For any $q$, we may assume that $x_{1q} \leq
  383. x_{2q} \leq \ldots x_{nq}$, then
  384. $\sum_{S: i \in S, j \notin S} \max \left(0, \min_{i' \in S} x_{i'q} - \max_{j' \notin S} x_{j'q}\right)
  385. = \sum_{k = j}^{i-1} x_{(k+1)q} - x{kq} = \max \left(0, x_{iq} - x_{jq}\right)$. Hence,
  386. $\sum_{S: i \in S, j \notin S} \lambda(S) = d(x_i,x_j)$.

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

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

  392. {theorem {
  393. Consider a metric $d$ for $G,H,c,D$ minimizing $\frac{c
  394. \cdot d}{\sum_{st \in H} D_{st} d(s,t)}$. Let $\lambda$ be a cut
  395. packing for $d$ with distortion $\beta$. Then there is a cut $S$ with
  396. $\lambda(S) \neq 0$ that has sparsity at most $\beta/\alpha$
  397. }}

  398. {proof {
  399. $$
  400. \frac{1}{\alpha}
  401. = \frac{\sum_{e \in E(G)} c_e d_e}{\sum_{st \in H} D_{st} d(s,t)}
  402. \geq \frac{\sum_{e \in E(H)} c_e \sum_{S: e \in \delta(S)} \lambda(S)}{\sum_{st \in H} D_{st} \beta \sum_{S: st \in \delta(S)} \lambda(S)}
  403. \geq (1/\beta) \frac{c(\delta(S))}{\sum_{st \in H \cap \delta(S)} D_{st}}
  404. $$
  405. for some cut $S$, where the last inequality comes from $\frac{\sum \lambda_i a_i}{\sum \lambda_i b_i} \geq \min \frac{a_i}{b_i}$ for any $b \geq 0$, $\lambda > 0$ and $a$.
  406. }}

  407. {*
  408. The remaining part of this section is devoted to proving a stronger
  409. relationship between congestion and distortion. We fix a graph $G$ and
  410. a demand graph $H$. Then the maximum congestion needed for any $c,D$
  411. is equal to the maximum distortion needed to embed any shortest-path
  412. metric on $G$ into $l_1$.
  413. *}

  414. The following theorem is the {emph congestion-distortion equivalence} theorem.

  415. {theorem {`caption {Linial, London, Rabinovich {ref "linial94"}}} {
  416. 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$.
  417. }}

  418. We follow the proof given by Chakrabarti, Fleischer and Weibel in {ref "chakrabarti2012cut"}.

  419. {proof {
  420. We fix a pair $G,H$. We denote by $\mathcal{P}_f$ the set of possible flow paths for commodity $f \in E(H)$, and by $\mathcal{P}$ their union $\bigcup_{f \in E(H)} \mathcal{P}_f$.

  421. Firstly, we express the congestion $\gamma(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:

  422. $$
  423. \begin{array}{ll}
  424. \gamma(c,d) = \min \alpha \quad\textrm{subject to} & \\
  425. \qquad \sum_{P \in \mathcal{P}_f} x_P \geq d_f & (\forall f \in E(H))\\
  426. \qquad \sum_{P \in \mathcal{P} : e \in P} x_P \leq \alpha c_e & (\forall e \in E(G))\\
  427. \qquad x_P \geq 0 & (\forall P \in \mathcal{P})\\
  428. \end{array}
  429. $$

  430. By duality we have:

  431. $$
  432. \begin{array}{ll}
  433. \gamma(c,d) = \max \sum_{f \in E(H)} \mu_f d_f \quad\textrm{subject to} & \\
  434. \qquad \mu_f \leq \sum_{e \in P} y_e & (\forall P \in \mathcal{P}_f, f \in E(H)) \\
  435. \qquad \sum_{e \in E(G)} c_e y_e = 1 & \\
  436. \qquad \mu, y \geq 0 &
  437. \end{array}
  438. $$

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

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

  441. $$
  442. \begin{array}{ll}
  443. \gamma = \max \gamma(c,d) \quad\textrm{subject to} & \\
  444. \qquad \sum_{e \in \delta_G(S)} c_e \geq \sum_{f \in \delta_H(S)} d_f & (\forall S \subsetneq V(G)) \\
  445. \qquad c, d \geq 0 &
  446. \end{array}
  447. $$

  448. We can develop the objective function using the dual linear program for $\gamma(c,d)$, this gives the non-linear program with variables $c$, $d$, $y$, $\mu$:

  449. $$
  450. \begin{array}{ll}
  451. \gamma = \max \sum_{f \in E(H)} \mu_f d_f \quad\textrm{subject to} & \\
  452. \qquad \mu_f \leq \sum_{e \in P} y_e & (\forall P \in \mathcal{P}_f, f \in E(H)) \\
  453. \qquad \sum_{e \in E(G)} c_e y_e = 1 & \\
  454. \qquad \sum_{e \in \delta_G(S)} c_e \geq \sum_{f \in \delta_H(S)} d_f & (\forall S \subsetneq V(G)) \\
  455. \qquad \mu_f, d_f \geq 0 & (\forall f \in E(H))\\
  456. \qquad c_e, y_e \geq 0 & (\forall e \in E(G))
  457. \end{array}
  458. $$

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

  460. $$
  461. \begin{array}{ll}
  462. w(y,\mu) = \max \sum_{f \in E(H)} \mu_f l_f \quad\textrm{subject to} & \\
  463. \qquad \sum_{e \in E(G)} y_e c_e = 1 & \\
  464. \qquad \sum_{e \in \delta_G(S)} c_e \geq \sum_{f \in \delta_H(S)} d_f & (\forall S \subsetneq V(G)) \\
  465. \qquad \mu_f, d_f \geq 0 & (\forall f \in E(H))\\
  466. \qquad c_e, y_e \geq 0 & (\forall e \in E(G))
  467. \end{array}
  468. $$

  469. And by adding the metric inequality constraints we get:
  470. $$
  471. \gamma = \begin{array}{ll}
  472. \max w(y,\mu) \quad\textrm{subject to} & \\
  473. \qquad \mu_f \leq \sum_{e \in P} y_e & (\forall e \in P_f, f \in E(H)) \\
  474. \qquad \mu, y \geq 0 &
  475. \end{array}
  476. $$

  477. Now we take the dual of the program defining $w(y,\mu)$:
  478. $$
  479. \begin{array}{ll}
  480. w(y,\mu) = \min \zeta \\
  481. \qquad \sum_{S \subsetneq V : e \in \delta_G(S)} z_S \leq y_e \zeta & (\forall e \in E(G)) \\
  482. \qquad \sum_{S \subsetneq V : f \in \delta_H(S)} z_S \geq \mu_f & (\forall f \in E(H)) \\
  483. \qquad z \geq 0 &
  484. \end{array}
  485. $$

  486. Now this is just minimizing the distortion given $\mu, y$ respecting the metric inequalities. As when maximising $\gamma$, $\mu$ is the shortest path metric induced by $y$, we get another expression of $\gamma$ 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 $\gamma$ gave us the maximum congestion over any $c,d$ satisfying the cut condition, hence the congestion-distortion equivalence.

  487. }}

  488. {section 2 {`anchor "spgraphs"} Cut-sufficiency in series-parallel graphs}

  489. {link af://callcc/Guyslain/Works/draft here.}

  490. {section 2 {`anchor "metrics"} Metrics and Potentials}

  491. Recall the dual of the {sc Maximum MultiCommodity Flow} problem, in its metric form:

  492. $$
  493. \begin{array}{ll}
  494. \min c \cdot d \quad\textrm{subject to} & \\
  495. \qquad d(s,t) \geq \mu(s,t) & (\forall s,t \in T)\\
  496. \qquad d~\text{metric on}~V &
  497. \end{array}
  498. $$

  499. 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 $\mu(s,t)$ from each other.

  500. 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 {emph potential}. A potential is a mapping $p: V \to \mathbb{R}$ with the property that for any edge $uv$, $\left|p_v - p_u\right| \leq l(uv)$. Notice that the constraints only uses differences between the potential at two vertices, so a potential is defined up to some constant.

  501. 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,\ldots,u_k=v$, then by a simple summation we get:
  502. $$ p_u - p_v = (p_{u_0} - p_{u_1}) + (p_{u_1} - p_{u_2}) + \ldots (p_{u_{k-1}} - p_{u_k}) \leq l(u_0u_1) + l(u_1u_2) + \ldots + l(u_{k-1}u_k) \leq l(P)$$
  503. hence the difference of potential is a lower bound on the distance between two vertices.

  504. 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.

  505. Applied to our dual problem, we can write a new formulation. It uses one potential $\rho_t: V \to \mathbb{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} |\rho_s(u) - \rho_s(v)|$. For simplicity, we keep this part hidden and just denote by $||\rho(u) - \rho(v)||_\infty$ this maximum.

  506. $$
  507. \begin{array}{ll}
  508. \min \sum_{uv \in E} c_{uv} ||\rho(u) - \rho(v)||_\infty \quad \text{subject to} & \\
  509. \qquad \rho_t(t) = 0 & (\forall t \in T) \\
  510. \qquad \rho_t(s) \geq \mu(s,t) & \left(\forall (s,t) \in \binom{T}{2}\right)\\
  511. \qquad \rho_t \in \mathbb{R}_+^V & (\forall t \in T)
  512. \end{array}
  513. $$

  514. It is worth noting that this program is also the dual of the edge formulation of the {sc 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 {ref "conf-dec"}.

  515. 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 {emph extension} of $\mu$ if $m(s,t) \geq \mu(s,t)$ for all pairs $(s,t) \in \binom{T}{2}$. We say that an extension $m$ of $\mu$ is {emph 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.

  516. The {emph universal tight extension} $(\mathcal{X},d)$ of a metric space $(T,\mu)$ is defined by:
  517. $$\mathcal{X} := \{ f:T \to \mathbb{R}~:~ \forall s,t \in T^2, f(s)+f(t) \geq \mu(s,t) \}$$
  518. $$d(f,g) := \sup_{t \in T} |f(t) - g(t)| $$

  519. Given $t \in T$, we associate $e_t \in \mathcal{X}$ defined by $e_t(s) = \mu(s,t)$.

  520. {lemma {`caption {Dress}} {
  521. Any tight extension $m$ on $V$ of $(T,\mu)$ is isometrically embeddable in $(\mathcal{X},d)$.
  522. }}

  523. {proof {
  524. We use the embedding given by $\rho_v : t \in T \to m(v,t)$. We must check that for any $x,y \in V$, $f(\rho_x,\rho_y) = m(x,y)$.

  525. 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:
  526. $$|\rho_x(t) - \rho_y(t)| = |m(x,t) - m(y,t)| = |m(x,y) + m(y,t) - m(y,t)| = m(x,y)$$
  527. and $|\rho_x(t') - \rho_y(t')| = |m(x,t') - m(y,t')| \leq m(x,y)$ by the triangular inequality, for any $t' \in T - t$. Thus, $d(\rho_x,\rho_y) = m(x,y)$.
  528. }}

  529. 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 $\mu(s,t)$, than $s$ and $t$ would at distance less than $\mu(s,t)$ from each other. This leads to one more formulation of the dual:

  530. $$
  531. \begin{array}{ll}
  532. \min c \cdot d \quad\textrm{subject to} & \\
  533. \qquad \rho_v \in \mathcal{X} & (\forall v \in V) \\
  534. \qquad \rho_t(t) = 0 & (\forall t \in T)
  535. \end{array}
  536. $$

  537. The next lemma shows that we can restrict our interest to the minimal elements of the universal tight extension. Let $T_\mu$ be the {emph tight span} of $\mu$, defined by:
  538. $$ T_\mu := \{ \rho \in \mathbb{R}^T~:~ \rho(s) = \sup_{t \in T} \mu(s,t) - \rho(t) \}$$

  539. {lemma {`caption {Dress}} {
  540. There is a map $p: \mathcal{X} \to T_\mu$ such that:
  541. - $d(p(f),p(g)) \leq d(f,g)$ for all $f, g \in \mathcal{X}$,
  542. - $p(f) \leq f$ for all $f \in \mathcal{X}$.
  543. }}

  544. {proof {
  545. Let $f \in \mathcal{X}$. Define $\delta_f(t) := \max_{s \in T} \mu(s,t) - f(s) \geq 0$. Notice that $\delta_f = f$ when $f \in T_\mu$, but $\delta_f$ is not necessarily in $\mathcal{X}$. We abusively extend the definition of $d$ to any map $T \to \mathbb{R}$.

  546. Then for any $g \in \mathcal{X}$ and $t \in T$, we have
  547. $$\begin{align}
  548. \delta_f(t) &= \sup_{s \in T} \mu(s,t) - g(s) + g(s) - f(s)\\
  549. &\leq \sup_{s \in T} (\mu(s,t) - g(s)) + \sup_{s \in T} (g(s) - f(s))\\
  550. &= \delta_g(t) + d(f,g)
  551. \end{align}
  552. $$
  553. Hence $\delta_f(t) - \delta_g(t) \leq d(f,g)$ for all $t \in T$, that is $d(\delta_f(t),\delta_g(t)) \leq d(f,g)$.

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

  556. This implies the following strenghtening:

  557. $$
  558. \begin{array}{ll}
  559. \min c \cdot d \quad\textrm{subject to} & \\
  560. \qquad \rho_v \in T_\mu & (\forall v \in V) \\
  561. \qquad \rho_t(t) = 0 & (\forall t \in T)
  562. \end{array}
  563. $$

  564. The first application of this formulation is that we can characterize the fractionality of the dual problem by the dimension of $T_\mu$. The {emph fractionality} of $\mu$ is the minimum $k \in \mathbb{N}$ such that any instance $G$ of the $\mu$-{sc Multicommodity Flow} problem admits an optimal $\frac{1}{k}$-integral solution. The {emph dual fractionality} is the minimum $k \in \mathbb{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.

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

  566. {theorem {`caption {Karzanov, Hirai}} {
  567. The fractionality of the dual of the {sc Multicommodity Flow} problem for a given $\mu$ is:
  568. - 1, 2 or 4 if $\dim T_\mu = 2$,
  569. - $\infty$ if $\dim T_\mu \geq 3$.
  570. }}

  571. More to come soon!

  572. {publi {:

  573. @article{aumann1998log,
  574. title = "An $O(\log k)$ Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm",
  575. author = "Yonatan Aumann",
  576. author = "Yuval Rabani",
  577. journal = "SIAM Journal on Computing",
  578. volume = 27,
  579. number = 1,
  580. pages = 291--301,
  581. year = 1998,
  582. publisher = "Citeseer"
  583. }

  584. @inproceedings{chakrabarti2012cut,
  585. title = "When the cut condition is enough: a complete characterization for multiflow problems in series-parallel networks",
  586. author = "Amit Chakrabarti",
  587. author = "Lisa Fleischer",
  588. author = "Christophe Weibel",
  589. booktitle = "Proceedings of the 44th symposium on Theory of Computing",
  590. pages = 19--26,
  591. year = 2012
  592. }

  593. @article{chekuri2012sp,
  594. title = "Flow-cut gaps for integer and fractional multiflows",
  595. author = "Chandra Chekuri",
  596. author = "F. Bruce Shepherd",
  597. author = "Christophe Weibel",
  598. journal = "Journal of Combinatorial Theory, Series B",
  599. year = 2012,
  600. publisher = "Elsevier"
  601. }

  602. @article{cherkassky1977solution,
  603. title = "A solution of a problem on multicommodity flows in a network",
  604. author = "Boris V. Cherkassky",
  605. journal = "Ekonomika i matematicheskie metody",
  606. volume = 13,
  607. number = 1,
  608. pages = 143--151,
  609. year = 1977
  610. }

  611. @article{ford1956maximal,
  612. title= "Maximal flow through a network",
  613. author= "Lester R. Ford",
  614. author = "Delbert R. Fulkerson",
  615. journal= "Canadian Journal of Mathematics",
  616. volume= 8,
  617. number= 3,
  618. pages= 399--404,
  619. year= 1956
  620. }

  621. @article{frank1997integer,
  622. title = "On integer multiflow maximization",
  623. author = "András Frank",
  624. author = "Alexander V. Karzanov",
  625. author = "András Sebő",
  626. journal= "SIAM Journal on Discrete Mathematics",
  627. volume = 10,
  628. number = 1,
  629. pages = 158--170,
  630. year = 1997
  631. }

  632. @article{hirai2009tight,
  633. title = "Tight spans of distances and the dual fractionality of undirected multiflow problems",
  634. author = "Hiroshi Hirai",
  635. journal = "Journal of Combinatorial Theory, Series B",
  636. volume = 99,
  637. number = 6,
  638. pages = 843--868,
  639. year = 2009,
  640. publisher = "Elsevier"
  641. }

  642. @article{hirai2009folder,
  643. title = "Folder complexes and multiflow combinatorial dualities",
  644. author = "Hiroshi Hirai",
  645. journal = "SIAM J. Discret. Math. (to appear)",
  646. year = 2009
  647. }

  648. @inproceedings{hirai2010maximum,
  649. title = "The maximum multiflow problems with bounded fractionality",
  650. author = "Hiroshi Hirai",
  651. booktitle = "Proceedings of the 42nd ACM symposium on Theory of computing",
  652. pages = 115--120,
  653. year = 2010
  654. }

  655. @article{hu1963multi,
  656. title = "Multi-commodity network flows",
  657. author = "T. C. Hu",
  658. journal = "Operations Research",
  659. pages = 344--360,
  660. year = 1963,
  661. publisher = "JSTOR"
  662. }
  663. @article{karzanov2004minimum,
  664. title = "Minimum 0-extensions of graph metrics",
  665. author = "Alexander V. Karzanov",
  666. journal = "European Journal of Combinatorics",
  667. volume = 19,
  668. number = 1,
  669. pages = 71--101,
  670. year = 2004,
  671. publisher = "Elsevier Science"
  672. }

  673. @article{karzanov1978systems,
  674. title = "Systems of flows in undirected networks",
  675. author = "Alexander V. Karzanov",
  676. author = "Michael V. Lomonosov",
  677. journal = "Mathematical Programming",
  678. publisher = "Institute for System Studies, Moscow",
  679. pages = 59--66,
  680. year = 1978
  681. }

  682. @inproceedings{leighton1988approximate,
  683. title = "An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms",
  684. author = "Frank T. Leighton",
  685. author = "Satish Rao",
  686. booktitle = "29th Annual Symposium on Foundations of Computer Science (FoCS)",
  687. pages = 422--431,
  688. year = 1988
  689. }

  690. @article{linial94,
  691. author = "N. Linial",
  692. author = "E. London",
  693. author = "Y. Rabinovich",
  694. title = "The geometry of graphs and some of its algorithmic applications",
  695. journal = "Combinatorica",
  696. number = 15,
  697. pages = 577--591,
  698. year = 1994
  699. }

  700. @article{lovasz1976some,
  701. title = "On some connectivity properties of Eulerian graphs",
  702. author = "László Lovász",
  703. journal = "Acta Mathematica Hungarica",
  704. volume = 28,
  705. number = 1,
  706. pages = 129--138,
  707. year = 1976,
  708. publisher = "Akadémiai Kiadó and Springer Science"
  709. }

  710. @article{onaga1971fcm,
  711. title= "On feasibility conditions of multicommodity flows in networks",
  712. author= "Kenji Onaga",
  713. author= "O. Kakusho",
  714. journal= "IEEE Transactions on Circuit Theory",
  715. volume= 18,
  716. number= 4,
  717. pages= 425--429,
  718. year= 1971
  719. }

  720. @article{rothschild1966ftc,
  721. title= "Feasibility of two commodity network flows",
  722. author= "Bruce Rothschild",
  723. author= "Andrew Whinston",
  724. journal= "Operations Research",
  725. pages= 1121--1129,
  726. year= 1966,
  727. publisher= "Operations Research Society of America"
  728. }

  729. @phdthesis{sadli,
  730. author = "Mouna Sadli",
  731. title = "Généralisation de matroïdes et chemins disjoints",
  732. institution = "Université Joseph Fourier, Grenoble 1",
  733. year = 2000
  734. }

  735. :}
  736. }