The metric bridge partition problem: Partitioning of a metric space into two subspaces linked by an edge in any optimal realization (Q1015445)

Let \(G=(V,E,w)\) be a graph with vertex and edge sets \(V\) and \(E\), respectively, and \(w:E\rightarrow {\mathbb{R}}^+\) a function which assigns a positive weight to each edge of \(G.\) Then \(G\) is called a realization of a finite metric space \((M,d),\) with \(M=\{1,\ldots,n\}\) if and only if \(\{1,\ldots,n\}\subseteq V\) and \(d(i,j)\) is equal to the length of the shortest chain linking \(i\) and \(j\) in \(G,\) whenever \(i,j\in \{1,\ldots,n\}\). A realization \(G\) of \((M,d)\) is said optimal if the sum of its weights is minimal among all the realizations of \((M,d)\). The Metric Bridge Partition Problem is to determine if the elements of a finite metric space \((M,d)\) can be partitioned into two nonempty subsets \(K\) and \(L\) such that all optimal realizations of \((M,d)\) contain a bridge linking \(K\) with \(L\). The authors prove that this problem is polynomially solvable. They also describe an algorithm that constructs an optimal realization of \((M,d)\) from optimal realizations of \((K,d_{| K})\) and \((L,d_{| L})\).