Recognizing Leaf Powers and Pairwise Compatibility Graphs is NP-Complete.

Max Dupr la Tour, Manuel Lafond, Ndiam Ndiaye

Browse the full SODA paper archive.