A combinatorial algorithm for the minimum \((2,r)\)-metric problem and some generalizations (Q1297737)

A graph \(G(V,E)\) is given with nonnegative integer capacities \(c(e)\) on the edges \(e\in E\) and with a metric \(\mu\) establishing distances between pairs of vertices of \(T\subseteq V\). This metric should be extended to a (semi-)metric \(m\) on \(V\) so that \(m=\mu\) within \(T\), each \(x\in V\) is at zero distance from some \(t\in T\), and \(\sum_{e\in E} c(e)m(e)\) be as small as possible. This is the classical undirected cut problem for \(T=\{s,t\}\). Another special case is if \(\mu\) is the path metric (minimum number of edges in a path connecting the vertices) in the complete bipartite graph \(K_{2,r}\). This latter problem is polynomial but previous solutions used the ellipsoid method. The author gives a ``purely combinatorial'' method for this and for a certain associated integer multiflow problem.