Graphs, and more generally matroids, where the simplest possible necessary condition, the 'Cut Condition', is also sufficient for multiflow feasibility, have been characterized by Seymour. In this work we exhibit the 'next' necessary conditions - there are three of them - and characterize the subclass of matroids where these are also sufficient for multiflow feasibility, or for the existence of integer multiflows in the Eulerian case. Surprisingly, this subclass turns out to properly contain every matroid for which, together with all its minors, the metric packing problem - the 'polar' of the multiflow problem - has an integer solution for bipartite data (and a half integer solution in general). We also provide the excluded minor characterization of the corresponding subclass.
Integer multiflows and metric packings beyond the cut condition
Discrete Mathematics, 28 August 2001, Volume 239, N°1
Type:
Journal
Date:
2001-08-28
Department:
Sécurité numérique
Eurecom Ref:
752
Copyright:
© Elsevier. Personal use of this material is permitted. The definitive version of this paper was published in Discrete Mathematics, 28 August 2001, Volume 239, N°1 and is available at : http://dx.doi.org/10.1016/S0012-365X(00)00372-1
PERMALINK : https://www.eurecom.fr/publication/752