Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
C. Thach Nguyen, Jian Xing Shen, Minmei Hou, Sheng Li, Webb Miller, Louxin Zhang · SIAM Journal on Computing · 2008
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 $\frac{3}{5}$-approximation algorithm for graphs; (3) it is NP-hard to approximate the problem within ratio $\frac{259}{260} + \epsilon$ for graphs; (4) there is a linear-time algorithm to compute the maximum star forest of a weighted tree; (5) there is a polynomial-time $\frac{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.