In graph theory, a graph G {\displaystyle G} is a pairwise compatibility graph (PCG) if there exists a weighted tree T {\displaystyle T} and two non-negative real numbers d m i n ≤ d m a x {\displaystyle d_{min}\leq d_{max}} such that each node u ′ {\displaystyle u'} of G {\displaystyle G} has a one-to-one mapping with a leaf node u {\displaystyle u} of T {\displaystyle T} such that two nodes u ′ {\displaystyle u'} and v ′ {\displaystyle v'} are adjacent in G {\displaystyle G} if and only if the distance between u {\displaystyle u} and v {\displaystyle v} are in the interval [ d m i n , d m a x ] {\displaystyle [d_{min},d_{max}]} . 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 d m i n ≤ d m a x {\displaystyle d_{min}\leq d_{max}} 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 G {\displaystyle G} and a selection of non-edge relations S {\displaystyle S} a PCG containing G {\displaystyle G} as a subgraph and with none of the edges in S {\displaystyle S} is known to be NP-hard. The task of finding nodes in a tree whose path distances lie between d m i n {\displaystyle d_{min}} and d m a x {\displaystyle d_{max}} 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
