Abstract:
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.
