be a graph with nonnegative integer capacities c(e) of the edges , and let μ be a metric that establishes distances on the pairs of elements of a subset . In the minimum 0-extension problem (*), one is asked for finding a (semi)metric m on V such that m coincides with μ within T, each is at zero distance from some , and the value is as small as possible. This is the classical minimum (undirected) cut problem when and , and the minimum (2, r)-metric problem when μ is the path metric of the complete bipartite graph . It is known that the latter problem can be solved in strongly polynomial time by use of the ellipsoid method.
We develop a polynomial time algorithm for the minimum (2, r)-metric problem, using only ``purely combinatorial'' means. The algorithm simultaneously solves a certain associated integer multiflow problem. We then apply this algorithm to solve (*) for a wider class of metrics μ, present other results and raise open questions.
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received: June 11, 1998
Rights and permissions
About this article
Cite this article
Karzanov, A. A Combinatorial Algorithm for the Minimum (2, r)-Metric Problem and Some Generalizations. Combinatorica 18, 549–568 (1998). https://doi.org/10.1007/s004930050040
Issue Date:
DOI: https://doi.org/10.1007/s004930050040