Pairwise compatibility graph

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 $G$ is a pairwise compatibility graph (PCG) if there exists a tree $T$ and two non-negative real numbers $d_{min}<d_{max}$ such that each node $u'$ of $G$ has a one-to-one mapping with a leaf node $u$ of $T$ such that two nodes $u'$ and $v'$ are adjacent in $G$ if and only if the distance between $u$ and $v$ are in the interval $[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_{min}<d_{max}$ is equivalent to finding a clique in the associated PCG.

Complexity

The computational complexity of recognizing a graph as a PCG is unknown as of 2020. However, the related problem of finding for a graph $G$ and a selection of non-edge relations $S$ a PCG containing $G$ as a subgraph and with none of the edges in $S$ is known to be NP-hard.

The task of finding nodes in a tree whose paths distance lies between $d_{min}$ and $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.