Recognizing Leaf Powers and Pairwise Compatibility Graphs is NP-Complete
Abstract
Leaf powers and pairwise compatibility graphs were introduced over twenty years ago as simplified graph models for phylogenetic trees. Despite significant research, several properties of these graph classes poorly understood. In this paper, we establish that the recognition problem for both classes is NP-complete. We extend this hardness result to a broader hierarchy of graph classes, including pairwise compatibility graphs and their generalizations, multi-interval pairwise compatibility graphs.
Fields of Study & Subjects
Genomics and Phylogenetic Studies
Genome Rearrangement Algorithms
Advanced Graph Theory Research
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 6166–6183
- Publication date
- 1 January 2026
- Language
- EN