A graph class
In graph theory, a graph formula_1 is a pairwise compatibility graph (PCG) if there exists a tree formula_2 and two non-negative real numbers formula_3 such that each node formula_4 of formula_1 has a one-to-one mapping with a leaf node formula_6 of formula_2 such that two nodes formula_4 and formula_9 are adjacent in formula_1 if and only if the distance between formula_6 and formula_12 are in the interval formula_13.
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 formula_3 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 formula_1 and a selection of non-edge relations formula_16 a PCG containing formula_1 as a subgraph and with none of the edges in formula_16 is known to be NP-hard.
The task of finding nodes in a tree whose paths distance lies between formula_19 and formula_20 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.
 ;templatestyles src="Reflist/styles.css" / ;