Searching for Optimal Caterpillars in General and Bounded Treewidth Graphs

Abstract

In this thesis we are interested in optimization problems on caterpillar trees. A caterpillar is a tree with this property that if one removes its leaves only a path is left. The majority of this thesis is devoted to studying the Minimum Spanning Caterpillar Problem (MSCP). An instance of the MSCP is a graph with dual costs over its edges. In the MSCP our goal is to find a caterpillar tree that spans the input graph with the smallest overall cost. The cost of the caterpillar is the sum of the cost of its edges, where each edge takes one of two costs based on its role as a leaf edge or an internal one. We first show that the problem of finding a spanning caterpillar in a graph is NP-complete. As another result on the hardness of the MSCP, we show that there is no f (n)-approximation algorithm for the MSCP unless P = NP. Here f (n) is any polynomial-time computable function of n, the number of nodes of a graph. Then we introduce a quadratic integer programming formulation for the MSCP. By using the Gomory cutting method iteratively, we show that one can find a near optimal solution. We then show that our integer programming formulation can be transformed to a semi-definite programming problem. A parametrized algorithm that finds an optimal solution for the MSCP in bounded treewidth graphs is given in Chapter 4. Our algorithm is fast and practical for outer-planar, series parallel, Halin graphs and other graphs with small treewidth.