Finding Well-Balanced Pairs of Edge-Disjoint Trees in Edge-Weighted Graphs

Jørgen Bang-Jensen, Daniel Goncalves, Inge Li Gørtz

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    The well-known number partition problem is NP-hard even in the following version: Given a set S of n non-negative integers; partition S into two sets X and Y such that vertical bar X vertical bar = vertical bar Y vertical bar and the sum of the elements in X is as close as possible to the sum of the elements in Y (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 G 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 G 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 X and Y which correspond to trees in G 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 3/2 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.
    Original languageEnglish
    JournalDiscrete Optimization
    Volume4
    Issue number3-4
    Pages (from-to)334-348
    ISSN1572-5286
    DOIs
    Publication statusPublished - 2007

    Cite this