To refer to this page use:

`http://arks.princeton.edu/ark:/88435/pr1968d`

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 vertical bar V(G)vertical bar + vertical bar E(G)vertical bar <= 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 vertical bar V(G)vertical bar + vertical bar E(G)vertical bar <= 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. (C) 2014 Elsevier Inc. All rights reserved. |

Publication Date: | Jan-2015 |

Electronic Publication Date: | 23-Aug-2014 |

Citation: | Seymour, Paul. (2015). Criticality for multicommodity flows. JOURNAL OF COMBINATORIAL THEORY SERIES B, 110 (136 - 179. doi:10.1016/j.jctb.2014.08.001 |

DOI: | doi:10.1016/j.jctb.2014.08.001 |

ISSN: | 0095-8956 |

EISSN: | 1096-0902 |

Pages: | 136 - 179 |

Type of Material: | Journal Article |

Journal/Proceeding Title: | JOURNAL OF COMBINATORIAL THEORY SERIES B |

Version: | Author's manuscript |

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.