Approximating the spanning star forest problem and its applications to genomic sequence alignment
C. Thach Nguyen, Jian Shen, Minmei Hou, Sheng Li, Webb Miller, Louxin Zhang · 2007
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-approximation algorithm for graphs; (3) it is NP-hard to approxi-5 mate the problem within ratio 259 + ɛ for graphs; (4) there is a linear-time algorithm to compute the 260 maximum star forest of a weighted tree; (5) there is a polynomial-time 1-approximation algorithm 2 for weighted graphs. We also show how to apply this spanning star forest model to aligning multiple genomic sequences over a tandem duplication region. Key words. Dominating set, spanning star forest, approximation algorithm, genomic sequence alignment AMS subject classifications. 68Q17, 68Q25, 68R10, 68W25 1. Introduction. A