Let H = (T, U ) be a connected graph, V β T a set, and c a non-negative function on the unordered pairs of elements of V . In the minimum 0-extension problem ( * ), one is asked to minimize the inner product c β’ m over all metrics m on V such that (i) m coincides with the distance function of H within T ; and (ii) each v β V is at zero distance from some s β T , i.e. m(v, s) = 0.
This problem is known to be NP-hard if H = K 3 (as being equivalent to the minimum 3-terminal cut problem), while it is polynomially solvable if H = K 2 (the minimum cut problem) or H = K 2,r (the minimum (2, r )-metric problem). We study problem ( * ) for all fixed H . More precisely, we consider the linear programming relaxation ( * * ) of ( * ) that is obtained by dropping condition (ii) above, and call H minimizable if the minima in ( * ) and ( * * ) coincide for all V and c. Note that for such an H problem ( * ) is solvable in strongly polynomial time.
Our main theorem asserts that H is minimizable if and only if H is bipartite, has no isometric circuit with six or more nodes, and is orientable in the sense that H can be oriented so that nonadjacent edges of any 4-circuit are oppositely directed along this circuit. The proof is based on a combinatorial and topological study of tight and extreme extensions of graph metrics.
Based on the idea of the proof of the NP-hardness for the minimum 3-terminal cut problem in [4], we then show that the minimum 0-extension problem is strongly NP-hard for many non-minimizable graphs H . Other results are also presented.