Hardness of Linear Variants of the Balanced Minimum Evolution Problem

Abstract

A cubic tree is a tree with leaves in which every internal vertex has degree exactly 3. Any such tree can be encoded by a Path‐Length Matrix (PLM), that is, an integer matrix whose th entry gives the number of edges in the unique path between leaves and in . The convex hull of all PLMs associated with cubic trees on leaves defines the PLM‐polytope . In this article, we prove that optimizing a linear function over the PLM‐polytope is strongly ‐hard. This result is motivated by the balanced minimum evolution problem, a highly nonlinear ‐hard network design problem arising in computational biology, whose underlying combinatorial structure is captured by the PLM‐polytope.