Graph (b) that is pairwise compatibility graphs of the trees (a) and (c)
Graphs that are not pairwise compatibility graphs
In graph theory, a graph is a pairwise compatibility graph (PCG) if there exists a tree and two non-negative real numbers such that each node of has a one-to-one mapping with a leaf node of such that two nodes and are adjacent in if and only if the distance between and are in the interval .[1]
Pairwise compatibility graphs were first introduced by Paul Kearney, J. Ian Munro and Derek Phillips in the context of phylogeny reconstruction. When sampling from a phylogenetic tree, the task of finding nodes whose path distance lies between given lengths is equivalent to finding a clique in the associated PCG.[3]
The computational complexity of recognizing a graph as a PCG is unknown as of 2020.[1] However, the related problem of finding for a graph and a selection of non-edge relations a PCG containing as a subgraph and with none of the edges in is known to be NP-hard.[2]
The task of finding nodes in a tree whose paths distance lies between and is known to be solvable in polynomial time. Therefore, if the tree could be recovered from a PCG in polynomial time, then the clique problem on PCGs would be polynomial too. As of 2020, neither of these complexities is known.[1]