Maximum Spanning k-Tree: A Case Study

The Maximum Spanning Backbone k-Tree (BkT) problem, for k 2, is to find a maximum weight spanning k-tree from the input edge-weighted graph with a designated Hamiltonian path to be desired in the output spanning graph. Originally motivated by research in bio-molecular 3D structure prediction, BkT turns out a typical problem in a new class of languages definable beyond Monadic Second Order logic. We show that, unlike the Maximum Spanning k-Tree problem that is NP-hard for even k = 2, the BkT problem is solvable in time O(nk+1), for every fixed k 2. While there is evidence of difficulty to improve the polynomial degree k + 1 to any number lower, we show that there are O(n3)-time algorithms to approximate the BkT problem to the ratio k(kNon UBCUnreviewedAuthor affiliation: University of GeorgiaFacult