Characterizing the flow equivalent trees of a network (Q1811121)

Let \(E_1,\dots,E_p\) be a partition of the edge set \(E^c\) of a complete graph \(H = (V,E^c)\). A cover of \(E_1,\dots,E_p\) is a subset of \(E^c\) containing precisely one member of each \(E_i\), \(i=1,\dots,p\). If each cover of \(E_1,\dots,E_p\) is the edge set of a spanning tree of \(H\), then the partition \(E_1,\dots,E_p\) is called a tree-partition, and the collection of all such trees is a tree-partition collection on \(V\). Let \(G\) be a connected weighted graph with positive perturbed edge weights (that is, the weights of the subsets of edges of \(G\) are different). \textit{R. E. Gomory} and \textit{T. C. Hu} [J. Soc. Ind. Appl. Math. 9, 551-570 (1961; Zbl 0112.12405)] showed that there always exists a positively weighted tree \(T\) on the same node set as \(G\) such that the max flow value between any pair of nodes in \(G\) is the same as the one between the corresponding pair of nodes in \(T\); such a tree is called a flow equivalent tree for \(G\). In the paper under review, the author presents the ``compact'' (i.e. polynomial size) characterization of the collection of all flow equivalent trees for \(G\) in terms of tree-partition collections. Also, a polynomial algorithm that recognizes a tree-partition is presented.