Hardness of approximation and integer programming frameworks for searching for caterpillar trees
Michael J. Dinneen, Masoud Khosravani · ResearchSpace (University of Auckland) · 2011
We consider the problems of nding a caterpillar tree in a graph. We rst prove that, unless P=NP, there is no approximation algorithms for nding 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/ε , for 0 < ε < 1. Finally, we show that our formulation is equivalent to a semide nite programming formulation, which introduces another approach for solving the problem.