Pairwise compatibility graph explained
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] 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.[2]
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 recognizing a graph as a PCG is unknown as of 2020. 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.
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.
Notes and References
- Rahman . Md Saidur . Ahmed . Shareef . A survey on pairwise compatibility graphs . AKCE International Journal of Graphs and Combinatorics . 2020 . 17 . 3 . 788–795 . 10.1016/j.akcej.2019.12.011 . 225708614 . free .
- Durocher. Stephane. Mondal. Debajyoti. Rahman. Md. Saidur. 2015. On graphs that are not PCGs. Theoretical Computer Science. 571. 78–87. 10.1016/j.tcs.2015.01.011. 17290164 . 0304-3975. free.
