Pairwise Compatibility Graph
In graph theory, a graph [math]\displaystyle{ G }[/math] is a Pairwise Compatibility Graph (PCG) if there exists a tree [math]\displaystyle{ T }[/math] and two non-negative real numbers [math]\displaystyle{ d_{min} \lt d_{max} }[/math] such that each node [math]\displaystyle{ u' }[/math] of [math]\displaystyle{ G }[/math] has a one-to-one mapping with a leaf node [math]\displaystyle{ u }[/math] of [math]\displaystyle{ T }[/math] such that two nodes [math]\displaystyle{ u' }[/math] and [math]\displaystyle{ v' }[/math] are adjacent in [math]\displaystyle{ G }[/math] if and only if the distance between [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] are in the interval [math]\displaystyle{ [d_{min}, d_{max}] }[/math].[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 [math]\displaystyle{ d_{min} \lt d_{max} }[/math] 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 [math]\displaystyle{ G }[/math] and a selection of non-edge relations [math]\displaystyle{ S }[/math] a PCG containing [math]\displaystyle{ G }[/math] as a subgraph and with none of the edges in [math]\displaystyle{ S }[/math] is known to be NP-hard.[2]
The task of finding nodes in a tree whose paths distance lies between [math]\displaystyle{ d_{min} }[/math] and [math]\displaystyle{ d_{max} }[/math] 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
- ↑ 1.0 1.1 1.2 1.3 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. https://www.tandfonline.com/doi/full/10.1016/j.akcej.2019.12.011. Retrieved December 30, 2021.
This article incorporates text available under the CC BY 4.0 license.
- ↑ 2.0 2.1 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. http://dx.doi.org/10.1016/j.tcs.2015.01.011.
- ↑ 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, http://dx.doi.org/10.1007/978-3-540-39763-2_14, retrieved 2022-02-13
 |
