Polyhedra related to undirected multicommodity flows (Q1119951)

The author associates with the two undirected graphs \(G=(VG,EG)\) and \(H=(VH,EH)\) (\(VH\subset VG)\) an unbounded polyhedron \(P(H,G)\), refered as a dual flow polyhedron. For the graph \(H\) is defined an integer index \(\nu\) (H) as the least positive integer \(k\) such that each dual problem (in the linear programming sense) to a maximum undirected multicommodity flow problem with the ``commodity graph'' \(H\) has an optimal solution that is \(1/k\)-integral \((\nu (H)=\infty\) is such \(k\) does not exist). This numerical characteristic \(\nu(H)\) of the graph \(H\) is also expressed in the terms of the dual flow polyhedron \(P(G,H)\), as the least positive integer \(k\) such that each vertex of \(P(G,H)\) is \(1/k\)-integral for any \(G\) with \(VH\subset VG\). In the paper, one shows that \(\nu(H)\) can be only 1, 2, 4 or \(\infty\). Some properties regarding extreme rays of certain cones related to the dual flow polyhedron are also obtained.