Hardness of Linear Variants of the Balanced Minimum Evolution Problem
Networks · 2026-08-21
DOI: 10.1002/net.70069 ↗At a glance
Journal article in Networks, published online on 2026-08-21. Written by Daniele Catanzaro and 3 co-authors. 29 references. Funded by: Fonds De La Recherche Scientifique - FNRS, Fondation Louvain.
Abstract (original language)
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.
Funding
- Fonds De La Recherche Scientifique - FNRS
- Fondation Louvain
Cite
APA
Catanzaro, D., Joret, G., Pierre, B., & Pisanu, F. (2026). Hardness of Linear Variants of the Balanced Minimum Evolution Problem. Networks. https://doi.org/10.1002/net.70069
Vancouver
Catanzaro D, Joret G, Pierre B, Pisanu F. Hardness of Linear Variants of the Balanced Minimum Evolution Problem. Networks. 2026. doi:10.1002/net.70069
BibTeX
@article{Catanzaro2026,
author = {Catanzaro, Daniele and Joret, Gwenaël and Pierre, Brieuc and Pisanu, Francesco},
title = {Hardness of Linear Variants of the Balanced Minimum Evolution Problem},
journal = {Networks},
year = {2026},
doi = {10.1002/net.70069}
}
EUVIMED