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. 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, for path metrics of graphs, for metrics with values in {1,2}, for metrics on n≥9 points with values in {1,2,3}. The authors 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. They characterize h-embeddable generalized bipartite metrics and derive a polynomial recognition algorithm.
