Finding Totally Independent Spanning Trees with Linear Integer Programming

摘要

Two spanning trees of an undirected graph are totally independent if they are edge disjoint and if the unique paths that connect any pair of vertices in these trees are also node disjoint. Accordingly, K ≥ 2 spanning trees are totally independent if they are pairwise totally independent. The problem of finding K totally independent spanning trees (KTIST) or proving that no such trees do exist is NP-Complete. We investigate KTIST and an optimization problem which consists of finding K totally independent spanning trees with the minimum possible number of central nodes. Both problems have applications in the design of interconnection networks. We propose an integer programming formulation, valid inequalities and a Branch-and-cut algorithm to solve them. We also present an experimental evaluation of such an algorithm.