Jump to content

Pairwise compatibility graph

From Wikipedia, the free encyclopedia
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 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.[1] However, there is a graph with eight vertices that is known not to be a PCG.[2]

Relationship to phylogenetics

[edit]

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.[3]

Complexity

[edit]

The computational complexity of recognizing a graph as a PCG is unknown as of 2020.[1] 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.[2]

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.[1]

References

[edit]
  1. ^ a b c d Rahman, Md Saidur; Ahmed, Shareef (2020). "A survey on pairwise compatibility graphs". AKCE International Journal of Graphs and Combinatorics. 17 (3): 788–795. doi:10.1016/j.akcej.2019.12.011. S2CID 225708614.  This article incorporates text available under the CC BY 4.0 license.
  2. ^ a b Durocher, Stephane; Mondal, Debajyoti; Rahman, Md. Saidur (2015). "On graphs that are not PCGs". Theoretical Computer Science. 571: 78–87. doi:10.1016/j.tcs.2015.01.011. ISSN 0304-3975. S2CID 17290164.
  3. ^ Kearney, Paul; Munro, J. Ian; Phillips, Derek (2003), Efficient Generation of Uniform Samples from Phylogenetic Trees, Lecture Notes in Computer Science, vol. 2812, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 177–189, doi:10.1007/978-3-540-39763-2_14, ISBN 978-3-540-20076-5, retrieved 2022-02-13