Hypercube embedding of generalized bipartite metrics Original Research Article

A metric d is h-embeddable if it can be isometrically embedded in some hypercube. Equivalently, d is h-embeddable if d can be written as a nonnegative integer combination of cut metrics. The problem of testing h-embeddability is NP-complete (Chvátal, 1980). A good characterization of h-embeddability permitting a polynomial-time algorithm was given for several classes of metrics, in particular, for metrics on n ⩽ 5 points (Deza, 1961), for path metrics of graphs (Djokovic, 1973), for metrics with values in {1, 2} (Assouad and Deza, 1980), for metrics on n ⩾ 9 points with values in {1, 2, 3} (Avis, 1990). We consider here generalized bipartite metrics, i.e., the metrics d for which d(i, j) = 2 for all distinct i,jϵ S or i,jϵT for some bipartition (S, T) of the points. We characterize h-embeddable generalized bipartite metrics and derive a polynomial recognition algorithm.