Recognizing Leaf Powers and Pairwise Compatibility Graphs is NP-Complete
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909864136015872 |
|---|---|
| author | la Tour, Max Dupré Lafond, Manuel Ndiaye, Ndiamé |
| author_facet | la Tour, Max Dupré Lafond, Manuel Ndiaye, Ndiamé |
| contents | 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 remain 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_19763 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Recognizing Leaf Powers and Pairwise Compatibility Graphs is NP-Complete la Tour, Max Dupré Lafond, Manuel Ndiaye, Ndiamé Combinatorics Discrete Mathematics 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 remain 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. |
| title | Recognizing Leaf Powers and Pairwise Compatibility Graphs is NP-Complete |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2510.19763 |