2026-08-27T21:19:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27529 2026-08-27T06:04:07Z ddc:004 open_access

Constructing Incompatibility Graphs of Pairs of Trees in Optimal Output-Sensitive Time Lafond, Manuel Phylogenetics graph theory output-sensitive algorithms clusters splits incompatibility We present an output-sensitive algorithm for constructing incompatibility graphs between pairs of rooted or unrooted phylogenetic trees, in which edges represent incompatible clusters or splits. Incompatibility graphs capture conflicting evolutionary signals and play an important role in applications such as phylogenetic network reconstruction, supertree inference, and BHV distance computation. Existing approaches typically require O(n³/w) time using bitset operations, where n is the number of taxa and w is the machine word size. We introduce a new algorithm based on lowest common ancestor mappings that constructs the incompatibility graph of two rooted trees in optimal O(n+d) time, where d is the number of incompatibility edges. The method is extended to unrooted trees and trees with different leaf sets while preserving the same complexity, while also being relatively simple to implement. Experimental results on random and simulated phylogenetic trees show substantial practical speedups over existing implementations, particularly on sparse incompatibility graphs, which commonly arise in large datasets. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Manuel Lafond 2026 Is Part Of LIPIcs, Volume 390, 26th International Conference on Algorithms for Bioinformatics (WABI 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2026.25 urn:nbn:de:0030-drops-275292 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2026.25 eng https://creativecommons.org/licenses/by/4.0/legalcode