Approximating the spanning star forest problem and its application to genomic sequence alignment

Abstract

This paper studies the algorithmic issues of the spanning star forest problem. We prove the following results: (1) There is a polynomial-time approximation scheme for planar graphs; (2) there is a polynomial-time 3/5-approximation algorithm for graphs; (3) it is NP-hard to approximate the problem within ratio 259/260 + ε{lunate} graphs; (4) there is a linear-time algorithm to compute the maximum star forest of a weighted tree; (5) there is a polynomial-time 1/2-approximation algorithm for weighted graphs. We also show how to apply this spanning star forest model to aligning multiple genomic sequences over a tandem duplication region. © 2008 Society for Industrial and Applied Mathematics.