Phylogenetic Network Simplification

多标记树(或简称MUL树)是一种系统发育树，其中每个叶标签可能出现不止一次。这种树可应用于通过折叠操作构建系统发育网络[Huber&Moulton，数学生物学，2006]。我们考虑了MUL-树集剪枝的一致性问题(MULSETPC)，它以一组MUL-树为输入，询问是否存在每棵MUL-树的完美剪枝，从而产生一组相容的单标记树。已知MULSETPC是NP-完全的[Gascon，Dondi，and El-Mabrouk，Proceents of Iwoca 2021]。当MUL-树是二叉树时，每个叶标签至多使用三次，并且MUL-树的数量是无界的。我们解决了Gascon等人提出的一个公开问题。通过证明一个更强的结果，即即使只有两棵MUL树，MULSETPC也是NP完全的，每个叶标签至多使用两次，并且要么每棵MUL树是二叉树，要么每棵MUL树具有恒定的高度。此外，我们引入了MULSETPC的一个扩展，称为MULSETPComp，它用相容取代了一致性的概念，并证明了即使只有两棵MUL-树，每个叶标签最多使用三次，并且每个MUL-树具有恒定的高度，MULSETPComp也是NP完全的。最后，在每个叶标签在至少一棵MUL-树中恰好出现一次的特殊情况下，我们设计了一个多项式时间算法来计算具有固定数目的二叉MUL-树的MULSETPC实例。

A multi-labeled tree (or MUL-tree, for short) is a phylogenetic tree in which every leaf label may appear more than once. Such trees have applications to the construction of phylogenetic networks by folding operations [Huber & Moulton, Mathematical Biology, 2006]. We considered the MUL-tree Set Pruning for Consistency problem (MULSETPC), which takes as input a set of MUL-trees and asks if there exists a perfect pruning of each MUL-tree that results in a consistent set of single-labeled trees. MULSETPC was known to be NP-complete [Gascon, Dondi, and El-Mabrouk, Proceedings of IWOCA 2021] when the MUL-trees are binary, each leaf label is used at most three times, and the number of MUL-trees is unbounded. We resolved an open question posed by Gascon et al. by proving a much stronger result, namely that MULULSETPC is NP-complete even when there are only two MUL-trees, every leaf label is used at most twice, and either every MUL-tree is binary or every MUL-tree has constant height. Furthermore, we introduced an extension of MULSETPC that we call MULSETPComp, which replaces the notion of consistency with compatibility, and proved that MULSETPComp is NP-complete even when there are only two MUL-trees, every leaf label is used at most thrice, and every MUL-tree has constant height. Finally, we designed a polynomial-time algorithm for instances of MULSETPC with a constant number of binary MUL-trees, in the special case where every leaf label occurs exactly once in at least one MUL-tree.