In graph theory, a graph is a pairwise compatibility graph (PCG) if there exists a weighted 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 .
The subclasses of PCG include graphs of at most seven vertices, cycles, forests, complete graphs, interval graphs and ladder graphs. However, there is a graph with eight vertices that is known not to be a PCG.
Relationship to phylogenetics 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.
Complexity The computational complexity of deciding whether an arbitrary graph is a PCG is NP-complete. Additionally, 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.
The task of finding nodes in a tree whose path distances lie 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.
References