On the approximability of the Fixed-Tree Balanced Minimum Evolution Problem

Frohn, Martin
(2021) , 5 pages

Files

CORE_DP_2021-20.pdf
  • Open Access
  • Adobe PDF
  • 394.58 KB
Download

Details

Authors
  • Frohn, MartinUCLouvain
    Author
Abstract
The Fixed-Tree BMEP (FT-BMEP) is a special case of the Balanced Minimum Evolution Problem (BMEP) that consists of finding the assignment of a set of n taxa to the n leaves of a given unrooted binary tree so as to minimize the BMEP objective function. Deciding the computational complexity of the FT-BMEP has been an open problem for almost a decade. Here, we show that a few modifications to Fiorini and Joret’s proof of the NP-hardness of the BMEP suffice to prove the general NP-hardness of the FT-BMEP as well as its strong inapproximability.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Frohn, M. (2021). On the approximability of the Fixed-Tree Balanced Minimum Evolution Problem (LIDAM Discussion Paper CORE 2021/20). https://hdl.handle.net/2078.5/108480