The cut cone, L 1 embeddability, complexity, and multicommodity flows

A finite metric (or more properly semimetric) on n points is a nonnegative vector d = (d ij ) 1 ⩽ i < j ⩽ n that satisfies the triangle inequality d ij ⩽ d ik + d jk . The L 1 (or Manhattan ) distance ‖ x − y ‖ 1 between two vectors x = (x i ) and y = (y i ) in R m is given by ‖ x − y ‖ 1 = ∑ 1⩽ i ⩽ m | x i − y i |. A metric d is L 1 ‐embeddable if there exist vectors z 1 , z 2 ,…, z n in R m for some m , such that d ij = ‖ z i − z j ‖ 1 for 1 ⩽ i < j ⩽ n . A cut metric is a metric with all distances zero or one and corresponds to the incidence vector of a cut in the complete graph on n vertices. The cut cone H n is the convex cone formed by taking all nonnegative combinations of cut metrics. It is easily shown that a metric is L 1 ‐embeddable if and only if it is contained in the cut cone. In this expository paper, we provide a unified setting for describing a number of results related to L 1 ‐embeddability and the cut cone. We collect and describe results on the facial structure of the cut cone and the complexity of testing the L 1 ‐embeddability of a metric. One of the main sections of the paper describes the role of L 1 ‐embeddability in the feasibility problem for multi‐commodity flows. The Ford and Fulkerson theorem for the existence of a single commodity flow can be restated as an inequality that must be valid for all cut metrics . A more general result, known as the Japanese theorem, gives a condition for the existence of a multicommodity flow. This theorem gives an inequality that must be satisfied by all metrics . For multicommodity flows involving a small number of terminals, it is known that the condition of the Japanese theorem can be replaced with one of the Ford–Fulkerson type. We review these results and show that the existence of such Ford–Fulkerson‐type conditions for flows with few terminals depends critically on the fact that certain metrics are L 1 ‐embeddable.