Measuring tree dissimilarity and studying the shape of trees are important tasks in phylogenetics. One of the most studied shape properties is the notion of tree imbalance, which can be quantified by different indicators, such as the Colless index. Here, we study the generalization of the Colless index to mobiles, i.e., full binary trees in which each leaf has been assigned a positive integer weight. In particular, we focus on the problem BALANCED MOBILES, which given as input n weights and a full binary tree on n leaves, asks to find an assignment of the weights to the leaves that minimizes the Colless index, i.e., the sum of the imbalances of the internal nodes (computed as the difference between the total weight of the left and right subtrees of the node considered). We prove that this problem is strongly -hard, answering an open question given at IWOCA 2016.

Hardness of Balanced Mobiles

Rizzi, Romeo;
2023-01-01

Abstract

Measuring tree dissimilarity and studying the shape of trees are important tasks in phylogenetics. One of the most studied shape properties is the notion of tree imbalance, which can be quantified by different indicators, such as the Colless index. Here, we study the generalization of the Colless index to mobiles, i.e., full binary trees in which each leaf has been assigned a positive integer weight. In particular, we focus on the problem BALANCED MOBILES, which given as input n weights and a full binary tree on n leaves, asks to find an assignment of the weights to the leaves that minimizes the Colless index, i.e., the sum of the imbalances of the internal nodes (computed as the difference between the total weight of the left and right subtrees of the node considered). We prove that this problem is strongly -hard, answering an open question given at IWOCA 2016.
2023
978-3-031-34346-9
Phylogenetic trees, Colless Index, BALANCED MOBILES, Strong NP-hardness
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/1117632
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact