Pairwise Compatibility Graphs (PCG) are graphs introduced in relation to the biological problem of reconstructing phylogenetic trees. Without demanding to be exhaustive, in this note we take a quick look at what is known in the literature for these graphs.
The evolutionary history of a set of organisms is usually represented by a tree-like structure called phylogenetic tree, where the leaves are the known species and the internal nodes are the possible ancestors that might have led, through evolution, to this set of species. Edges are evolutionary relationships between species, while the edge weights represent evolutionary distances among species (evolutionary times).
The phylogenetic tree reconstruction problem consists in nding a fully labeled phylogenetic tree that 'best' explains the evolution of given species, where 'best' means that it optimizes a speci c target function.
Tree reconstruction problem is proved to be NP-hard under many criteria
of optimality, so the performance of the heuristics for this problem is
usually experimentally evaluated by comparing the output trees with
the partial trees that are unanimously recognized as sure by biologists.
But real data consist of a huge number of species, and it is unfeasible to
compare trees with such a number of leaves, so it is common to exploit
sample techniques. The idea is to nd e cient ways to sample subsets
of species from a large set in order to test the heuristics on the smaller
sub-trees induced by the sample. The constraints on the sample attempt
to ensure that the behavior of the heuristics will not be biased by the fact
it is applied on the sample instead of on the whole tree. Since very close
or very distant taxa can create problems for phylogenetic reconstruction
heuristics [
In g. 1.a graph G = P CG(T; 4; 5) is depicted, where T is shown in g. 1.b.
The sample problem in terms of graph theory is hence strictly related with the PCG recognition problem, asking whether a given graph is PCG, for some tree T and values dmin and dmax. While it is trivial to construct graph G starting from T; dmin; dmax, the inverse problem is di cult and it has been conjectured that this problem is NP-hard, so the aim of the researchers has been to prove or disprove the conjecture; to this aim, some graph classes have been proved to be inside and outside PCGs, moreover some steps towards characterization of PCGs have been done (conditions, techniques, properties, : : :).
In the following we will present a brief overview of some results on PCGs. u u u u c.
u u
u u u u u u u u u u u u u u u u u u
u u
It was conjectured [
Some classes of graphs are pairwise compatibility; among them there
are interval graphs [
Moreover some classes of graphs are not pairwise compatibility, such as
some bipartite graphs [
Since all graphs with 7 vertices are PCGs, it is natural to wonder whether
some interesting classes of graphs remain PCGs or not when they have
n 8 nodes. The n node wheels Wn behave in an unexpected way:
wheel with 7 nodes, W7, is clearly PCG (see Fig. 3.a for a witness tree
[
The following results are not restricted to special classes of graphs and
are mainly based on the de nition of tri-coloring:
De nition 2. [
We say that triple (T; dmin; dmax) induces C.
In g. 1.c a tri-coloring for the graph of g. 1.a is depicted.
A tri-coloring C (even only partial) of a graph G is forbidden if no triple (T; dmin; dmax) inducing C exists.
It holds that: { Any induced subgraph H of a given PCG G inherits the tri-coloring
C of G and so is PCG, too (easy to prove). { If a graph contains as induced subgraph a not PCG, then it is not
PCG, too (easy to prove by contradiction).
{ If a tri-coloring C of a graph G is forbidden for a PCG subgraph of
G, then it is forbidden also for G. Consequently, G is not PCG if and
only if each tri-coloring of a graph G induces a forbidden tri-coloring
in at least an induced PCG subgraph of G [
In Fig. 4 an interesting picture shows how PCGs contain many well
known classes of graphs. Here there are the de nitions of all the named
subclasses:
{ C: cycles;
{ LP G: Leaf Power Graphs, i.e. PCGs in which dmin is always equal
to 0: G = P CG(T; 0; dmax) = LP G(T; dmax) [
It holds that the complement of every graph in LPG is in mLPG and,
conversely, the complement of every graph in mLPG is in LPG [
PCG '
$ '
LPG
SM &
T & $
SA mLPG %
C %
To conclude this brief presentation on PCGs, we make some
considerations on di erent classes of trees that can be witness trees of a PCG.
Caterpillars and stars are very simple and natural tree structures so, since
PCGs may have di erent witness trees, they have often been exploited to
prove that some graph classes are in PCG. Nevertheless there are graphs
that are PCGs, but not PCGs of caterpillars nor of stars. Consequently, it
appears very natural to characterize PCGs that have as witness tree one
of these two tree structures. For what concerns caterpillars, the complete
characterization of PCGs of caterpillars is at moment an interesting open
problem since the literature contains results only on caterpillars with all
weights equal 1. Namely,it is known that graph classes P CG(T; 0; dmax)
and unit interval graphs are equivalent when T is a caterpillar with all
weights equal 1 [
It is worth to be noticed that there exists an algorithm requiring O(n6)
time for testing if a given n node graph is PCG of a star or not [
AAA AAA
AAA S1
S2 u S1 u u u u
u (b)
K u u u u S2 u u u u 2 2 3 4