Hypercube embedding of generalized bipartite metrics (Q1842652)

The authors consider a case of the general problem of a metric which is called \(h\)-embeddability. The question is ``whether for a given hypercube containing \(n\)-dimensional binary vectors and for a given metric \(d(x,y)\), there exist \(n\) vectors \(v_ 1,v_ 2,\dots, v_ n\) for which the Hamming distance between each two vectors \(v_ x\), \(v_ y\) equals \(d(x,y)\)?'' The general problem is NP-complete. However, there are known numerous general instances for which \(h\)-embeddability of a given metric can be tested in polynomial time. The main objective of the paper consists in showing that for generalized \(h\)-embeddable bipartite metrics the problem can be solved in polynomial time. Also given is a polynomial time algorithm for the recognition of the \(h\)-embeddability of a given metric. The problem is considered in a very general way giving important and practical knowledge concerning properties of metrics defined in a hypercube.