A polynomial algorithm for the minimum quartet inconsistency problem with O(n) quartet errors

摘要

We show that for the Minimum Quartet Inconsistency problem, if the number of quartet errors is O(n), where n is the number of taxa under consideration, then it can be solved in polynomial time. This improves the previously-best algorithmic result saying that if the number of quartet errors is at most (n-3)/2 then the problem can be solved in polynomial time.