## Abstract

For k≥ 1, the k- commodity flow problem is, we are given k pairs of vertices in a graph G, and we ask whether there exist k flows in the graph, where. •the ith flow is between the ith pair of vertices, and has total value one; and•for each edge e, the sum of absolute values of the flows along e is at most one. We prove that for all k there exists n(k) such that if G is connected, and contraction-minimal such that the k-commodity flow problem is infeasible (that is, minimal in the sense that contracting any edge makes the problem feasible) then |V(G)|+|E(G)|≤ n(k). For integers k, p≥ 1, the (k, p)- commodity flow problem is as above, with the extra requirement that the flow value of each flow along each edge is a multiple of 1/p. We prove that if p> 1, and G is connected, and contraction-minimal such that the (k, p)-commodity flow problem is infeasible, then |V(G)|+|E(G)|≤ n(k), with the same n(k) as before, independent of p. In contrast, when p= 1 there are arbitrarily large contraction-minimal instances, even when k = 2. We give some other corollaries of the same approach, including. •a proof that for all k≥0 there exists p>0 such that every feasible k-commodity flow problem has a solution in which all flow values are multiples of 1/p, and•a very simple polynomial-time algorithm to solve the (k, p) multicommodity flow problem when p>1.

Original language | English (US) |
---|---|

Pages (from-to) | 136-179 |

Number of pages | 44 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 110 |

DOIs | |

State | Published - Jan 1 2015 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

## Keywords

- Multicommodity flows
- Polynomial-time
- Tree-decomposition