Intractability of the Minimum-Flip Supertree problem and its variants

Details Intractability of the Minimum-Flip Supertree problem and its variants Intractability of the Minimum-Flip Supertree problem and its variants

2011-12-20

arxiv.org/abs/1112.4536v1

Computer Science

Computational Complexity

To be submitted

Scientific paper

Computing supertrees is a central problem in phylogenetics. The supertree method that is by far the most widely used today was introduced in 1992 and is called Matrix Representation with Parsimony analysis (MRP). Matrix Representation using Flipping (MRF)}, which was introduced in 2002, is an interesting variant of MRP: MRF is arguably more relevant that MRP and various efficient implementations of MRF have been presented. From a theoretical point of view, implementing MRF or MRP is solving NP-hard optimization problems. The aim of this paper is to study the approximability and the fixed-parameter tractability of the optimization problem corresponding to MRF, namely Minimum-Flip Supertree. We prove strongly negative results.

Affiliated with

Also associated with

No associations

Rating

Intractability of the Minimum-Flip Supertree problem and its variants does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Intractability of the Minimum-Flip Supertree problem and its variants, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Intractability of the Minimum-Flip Supertree problem and its variants will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-54371