Hardness of Approximation and Integer Programming Frameworks for Searching for Caterpillar Trees

Dinneen, M. J. and Khosravani, M.

We consider the problems of finding a caterpillar tree in a graph. We first prove that, unless P=NP, there is no approximation algorithms for finding a minimum spanning caterpillar in a graph within a factor of f(n); where f(n) is any polynomial time computable function of n, the order of the graph. Then we present a quadratic integer programming formulation for the problem that can be a base for a branch and cut algorithm. We also show that by using Gomory cuts iteratively, one can obtain a solution for the problem that is close to the optimal value by a factor of 1/ε,for0<ε<1. Finally, we show that our formulation is equivalent to a semidefinite programming formulation, which introduces another approach for solving the problem.

Cite as: Dinneen, M. J. and Khosravani, M. (2011). Hardness of Approximation and Integer Programming Frameworks for Searching for Caterpillar Trees. In Proc. Computing: The Australasian Theory Symposium (CATS 2011) Perth, Australia. CRPIT, 119. Alex Potanin and Taso Viglas Eds., ACS. 145-150

(from crpit.com) (local if available)