Integral packing of trees and branchings (Q1907770)

We apply the results of our previous publications to propose an \(O(n^2 mp)\) algorithm for the problem of integral packing of spanning trees, where \(n\) and \(m\) respectively are the number of vertices and edges in the graph \(G\) and \(p\) is the time complexity of the maximum flow problem on \(G\). The algorithm constructs a basis solution, so that the optimal solution contains a minimum number of spanning trees of nonzero cardinalities. In other words, the number of nonzero components forming the optimal packing does not exceed \(n\). The proposed algorithm is easily modified for the solution of problems of minimum integral covering of a graph by spanning trees. (\dots) The spanning tree packing problem is transformed into a similar problem for digraphs, specifically, the problem of packing branchings into a given digraph with a distinguished root. A good characterization of this problem is provided by the Edmonds theorem: The maximum cardinality of branchings packed into a digraph is equal to the cardinality of the minimum cut separating the root from any of the vertices. The first strictly polynomial algorithm for the solution of this problem was proposed in [\textit{P. A. Pevzner}, Combinatorial methods in flow problems, Work Collect. 3, Moskva 1979, 113-127 (1979; Zbl 0494.90024)]. However, it has the same shortcomings as the previous algorithms for the undirected case.