A Polynomial-Time Algorithm for Near-perfect Phylogeny

摘要

We define a parameterized version of the steiner tree problem in phylogeny where the parameter measures the amount by which a phylogeny differs from" perfection". This problem is shown to be solvable in polynomial time for any fixed value of the parameter.