OR Seminar - Roberto Ronco
29-01-2026 / CORE C035
Roberto Ronco
National Research Council of Italy
will give a presentation on:
Characterizing Path-Length Matrices of Unrooted Binary Trees
Abstract:
The Path-Length Matrix (PLM) of an Unrooted Binary Tree (UBT) is a symmetric integer matrix of order n ≥ 3 that uniquely encodes a tree with n leaves and internal vertices of degree 3. PLMs have applications in clustering and in computational biology, among others. One notable example is the Balanced Minimum Evolution Problem (BMEP), a NP-hard problem that is central in phylogeny estimation. In this talk, we extend the results in [1, 2] on necessary and sufficient conditions for a matrix to encode the PLM of a UBT with n leaves [3]. In particular, we show a reduced set of conditions for n ≤ 11 that, interestingly, does not include the so-called Buneman’s four-point conditions [4]. 1. Catanzaro, D., Labb´e, M., Pesenti, R., and Salazar-Gonz´ales, J. J., The balanced minimum evolution problem, INFORMS Journal on Computing 24(2), 276–294 (2012). 2. Catanzaro, D., Pesenti, R., Sapucaia, A., and Wolsey, L. A., Optimizing over path-length matrices of unrooted binary trees, Mathematical Programming A (2025). 3. Catanzaro, D., Pesenti, R., and Ronco, R., Characterizing path-length matrices of unrooted binary trees (LIDAM Discussion Paper CORE 2024/28), UCLouvain, LIDAM/CORE (2024). 4. Buneman, P., A note on the metric properties of trees, Journal of combinatorial theory 17(B), 48–50 (1974)
