Pairwise compatibility graph

Comment: Hi! Based on the Google Scholar link, the good news is I think this topic meets notability. However, it needs to be expanded and incorporate many of the more well-cited references listed at this link. Currently, it's just a definition and one fact, which IS helpful but needs significant improvement and someone would need to commit to bringing the article to Start class. Caleb Stanford (talk) 03:27, 30 December 2021 (UTC)

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}]$ .^[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

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

Complexity

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 $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.^[2]

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.

References

^ ^a ^b ^c 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. Retrieved December 30, 2021. This article incorporates text available under the CC BY 4.0 license.
^ ^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.
^ Kearney, Paul; Munro, J. Ian; Phillips, Derek (2003), "Efficient Generation of Uniform Samples from Phylogenetic Trees", Lecture Notes in Computer Science, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 177–189, ISBN 978-3-540-20076-5, retrieved 2022-02-13

[:0-1] 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. Retrieved December 30, 2021. This article incorporates text available under the CC BY 4.0 license.

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

[3] Kearney, Paul; Munro, J. Ian; Phillips, Derek (2003), "Efficient Generation of Uniform Samples from Phylogenetic Trees", Lecture Notes in Computer Science, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 177–189, ISBN 978-3-540-20076-5, retrieved 2022-02-13

[1]

[2]

[3]