Minimum 0-extensions of graph metrics (Q1378296)

Given are a connected graph \(H= (T, U)\), a set of nodes \(V\supseteq T\), a nonnegative function \(c\) defined on unordered pairs of elements of \(V\). The minimum 0-extension problem means to minimize the inner product \(c\cdot m\) over all metrics \(m\) on \(V\) such that (i) \(m\) coincides with the distance function of \(H\) within \(T\), (ii) each \(v\in V\) is at zero distance from some \(s\in T\), i.e. \(m(v, s)= 0\). The minimum 0-extension problem is equivalent to the minimum cut problem that has wide applications in different branches of engineering mainly concerning flow problems. Relaxation of the minimum 0-extension problem concerns dropping (ii) and solving the reminder by linear programming. We say that a graph \(H\) is minimizable if solutions of the minimum 0-extension and its relaxation coincide. Therefore specifying what graph is minimizable enables us to say for what graph there exists a polynomial time algorithm solving the minimum cut problem. The author gives a proof 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 ciruit. The presented research is in accordance with the current standard of studying strong NP-hardness of different problems. The goal is to know cases for which polynomial time algorithms can be applied for solving a particular NP-hard problem. The main weakness of these studies is the very individual treatment of each NP-hard problem and the lack of a common methodology for studying a class of such problems.