2005-14: Inapproximability Results for the Lateral Gene Transfer Problem

DIMACS TR: 2005-14

Inapproximability Results for the Lateral Gene Transfer Problem

Authors: Bhaskar Dasgupta, Sergio Ferrarini, Uthra Gopalakrishnan and Nisha Raj Paryani

ABSTRACT
In this paper we establish some inapproximability results for the \textsc{Lateral Transfer Problem}. This optimization problem, which was defined by Hallet and Lagergren, is that of finding the most parsimonious lateral gene transfer scenario for a given pair of gene and species trees. We will prove that the Lateral Transfer Problem is MAX SNP-hard; thus Polynomial Time Approximation Scheme is not possible for it unless P = NP.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-14.ps.gz

DIMACS Home Page