Finding well-balanced pairs of edge-disjoint trees in edge-weighted graphs

The well-known number partition problem is NP-hard even in the following version: Given a set SS of nn non-negative integers; partition SS into two sets XX and YY such that |X|=|Y||X|=|Y| and the sum of the elements in XX is as close as possible to the sum of the elements in YY (or equivalently, minimize the maximum of the two sums). In this paper we study the following generalization of the partition problem: given an edge-weighted graph GG containing two edge-disjoint spanning trees. Find a pair of edge-disjoint spanning trees such that the maximum weight of these two trees is as small as possible. In the case when GG is precisely the union of two trees this problem may be seen as a generalization of the partition problem in which we have added a graph structure to the numbers (through the edges) and the extra restriction that only the sets XX and YY which correspond to trees in GG are valid partitions. We first show how to obtain a 2-approximation via an algorithm for weighted matroid partition. Then we describe a simple heuristic which when applied to the 2-approximation above will result in a solution whose value is no more than 32 times the value of an optimal solution. We also show that the approach above may sometimes exclude all the optimal solutions. Both the partition problem and its generalization to the problem above on edge-disjoint spanning trees are special cases of the problem of finding, in a weighted matroid with two disjoint bases, a pair of disjoint bases which minimize the maximum of their weights. In the last part of the paper we give some results on this problem for transversal matroids which turn out to be analogous to those for graphs.