
University of Bonn > Department of Computer Science > Chair V  
CSReports 2008  Copyright 2008 University of Bonn, Department of Computer Science, Abt. V  
85299 18.12.2008 
Approximability of Selected Phylogenetic Tree Problems
Mathias Hauptmann and Marlis Lamp [Download PostScript] [Download PDF] We study the approximability of the reconstruction problem of phylogenetic trees with respect to three different cost measures and give the first explicit lower bounds, under standard complexitytheoretic assumptions. For the Steiner Tree Problem in Phylogeny (STPP) and the Generalized Tree Alignment (GTA) problem, we show that unless P = NP, no polynomialtime algorithm can approximate these problems with an approximation ratio below 359/358. For the Ancestral Maximum Likelihood (AML) problem we give a lower bound of 1577/1576. Furthermore we construct a polynomialtime approximation scheme (A_{ε})_{ε>0} for the AML problem, such that for each ε > 0, A_{ε} is a polynomial time approximation algorithm with ratio (1 + ε) ⋅ (1 + ln(3)/2). This result is based on the Steiner tree algorithm of Robins and Zelikovsky [RZ00] and on a new exact algorithm for AML instances of constant size. This improves upon recent results by Alon et al. [ACPR08] who gave a 1.78approximation algorithm for the AML problem. 

Last Change:
11/05/14 at 10:39:58
Deutsch 
University of Bonn > Department of Computer Science > Chair V 