=Paper=
{{Paper
|id=Vol-2243/invited1
|storemode=property
|title=None
|pdfUrl=https://ceur-ws.org/Vol-2243/invited1.pdf
|volume=Vol-2243
}}
==None==
https://ceur-ws.org/Vol-2243/invited1.pdf
Pairwise Compatibility Graphs
(Invited Talk)
Rossella Petreschi and Tiziana Calamoneri
Sapienza University of Rome
Computer Science Department.
{petreschi, calamo}@di.uniroma1.it
Abstract. 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 evo-
lutionary relationships between species, while the edge weights represent
evolutionary distances among species (evolutionary times).
The phylogenetic tree reconstruction problem consists in finding a fully la-
beled phylogenetic tree that ’best’ explains the evolution of given species,
where ’best’ means that it optimizes a specific 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 find efficient 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 [9], the following definition of Pairwise Compatibility Graphs
[12] appears natural:
Definition 1. Graph G = (V, E) is a Pairwise Compatibility Graph,
P CG(T, dmin , dmax ), if:
V = Leaves(T ) and E = {(u, v)|dmin ≤ dT (u,v) ≤ dmax } where:
– T is a positive edge-weighted tree and is called witness tree for G;
– dT (u,v) is the sum of the weights of all the edges on the (unique) path
from u to v on T ;
– dmin and dmax are two nonnegative values.
b b
u u
u 2 u
u u u u
a c 2 1 1 2 a c
u u u u u u
d a d b c d
a. b. c.
Fig. 1. a. A graph G. b. An edge-weighted tree T such that G = P CG(T, 4, 5). c. The
PCG-coloring induced on G by triple T, 4, 5.
In fig. 1.a graph G = P CG(T, 4, 5) is depicted, where T is shown in fig.
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 difficult 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 u u u u u u u u
u u u
u u u u u u
u u u
u u u u u
u u
a. b. c.
Fig. 2. a. The first graph proven not to be a PCG. b. The (not planar) graph of smallest
size proven not to be a PCG. c. The (planar) graph of smallest size proven not to be
a PCG.
It was conjectured [12] that all graphs are PCGs, but this was disproved
in 2010 showing that the graph in Fig. 2.a cannot be PCG [16].
All graphs with a number of nodes not greater than 7 are PCGs [3] and
there are examples of graphs with 8 nodes that are not PCGs (see Fig.2.b
[8] and 2.c [1]).
Some classes of graphs are pairwise compatibility; among them there
are interval graphs [2], cliques, trees,cycles, cacti, single chord cycles [16,
17], triangle-free outerplanar 3-graphs [15], subclasses of split matrogenic
graphs [5].
Moreover some classes of graphs are not pairwise compatibility, such as
some bipartite graphs [16], tolerance graphs [4], permutation graphs [7],
graphs that are the strong product between Cn and P2 , n > 4 [1] and
the square of a cycle [1].
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
[3]); wheel with 8 nodes has later been proved to be also in PCG (see
Fig. 3.b for a witness tree) while larger wheels (with 9 or more nodes)
are not PCGs anymore [1].
v7 v6
v2 u 3 u u
v4 u uv3
u uc 1 5 1 5
v5 u 1
u2 u2 u
1 3
u v2 u 3 3 3 uv1
v6 u 3 1 1 3 uv4 u
u u
3 6
v3 u 1 1 uv1 u u
c v5
a. b.
Fig. 3. a. Tree T such that W7 = P CG(T, 5, 7); b. Tree T such that W8 =
P CG(T, 9, 13).
The following results are not restricted to special classes of graphs and
are mainly based on the definition of tri-coloring:
Definition 2. [1] A tri-coloring C is an edge-coloring of a P CG(T, dmin , dmax )
such that:
– (u, v) is red in C if d(u, v) < dmin ,
– (u, v) is black in C if dmin ≤ d(u, v) ≤ dmax ,
– (u, v) is blue in C if d(u, v) > dmax .
We say that triple (T, dmin , dmax ) induces C.
In fig. 1.c a tri-coloring for the graph of fig. 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 [1].
– Let G be a graph and let Gc be its complement. If Gc has two disjoint
chordless cycles, then G is not a PCG. If Gc has no cycles, then G
is a PCG [11]
– A graph G consisting of two graphs G1 and G2 that share a node as
a cut-node in G is a PCG if and only if both G1 and G2 are PCG
[18].
In Fig. 4 an interesting picture shows how PCGs contain many well
known classes of graphs. Here there are the definitions 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 ) [2, 14];
– mLP G: Minimum Leaf Power Graphs, i.e. PCGs in which dmax is
always equal to ∞: G = mLP G(T, dmin ) = P CG(T, dmin , ∞) [6];
– T : threshold graphs, i.e. split graphs with the neighborhoods of the
vertices nested [10];
– SM: Split Matching graphs, i.e. split graphs where the subgraph
connecting the clique and the stable set is a perfect mathching [13];
– SA: Split Anti-matching graphs, i.e. split graphs where the subgraph
connecting the clique and the stable set is a perfect anti-mathching
[13].
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 [5]. It
would be interesting to understand which other graph classes are in PCG
and in particular to study if threshold graphs are the only graphs in the
intersection between LPG and mLPG or not.
PCG $ '
' $
SA
LPG T
mLPG
SM & %
& %
C
Fig. 4. Relationships between PCG and other interesting classes of graphs [6].
To conclude this brief presentation on PCGs, we make some considera-
tions on different 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 different 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 [2]. In [3] this result has been generalized to any value
of dmin . For what it concerns stars, it is known that PCGs of stars are
a superclass of threshold graphs; indeed, it is possible to partition the
nodes of a PCG of a star in such a way that one partition induces a
clique, while the other two induce two stable sets, where the subclasses
induced by the clique and each one of the stable sets are threshold graphs
(see fig. 5) [6].
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 [19].
K
u u u u
2 2 3 4
K u u u u
u
1 5
AAA ∗ u u u 1 u
AAA
u u u 6 u
u u u1 6 u
AAA
S1 S2
S1 S2
(a) (b) (c)
Fig. 5. (a) The structure of a PCG generated by a star; (b) the PCG generated by the
star depicted in (c).
References
1. P. Baiocchi, T. Calamoneri, A. Monti, R. Petreschi (2018) Graphs
that are Not Pairwise Compatible: A New Proof Technique (Ex-
tended Abstract), Proc. IWOCA 2018, Lecture Notes in Computer
Science, in press. Also presented at ICTCS 2017, CEUR Workshop
Proceedings 1949, 203–207.
2. A. Brandstädt, C. Hundt (2008) Ptolemaic graphs and interval
graphs are leaf powers, Proc. LATIN 2008, Lecture Notes in Com-
put. Sci. 4957, pp. 479–491.
3. T. Calamoneri, D. Frascaria, B. Sinaimeri (2014) All graphs with at
most seven vertices are Pairwise Compatibility Graphs, The Com-
puter Journal 56(7) 882–886.
4. T. Calamoneri, M. Gastaldello, B. Sinaimeri (2015) On Pairwise
Compatibility of Some Graph (Super)classes, arXiv:1504.06454.
5. T. Calamoneri, E. Montefusco, R. Petreschi, B. Sinaimeri (2013)
Exploring pairwise compatibility graphs, Theoret. Comput. Sci., 468
23–26.
6. T. Calamoneri, R. Petreschi, B. Sinaimeri (2013) Pairwise compat-
ibility property of some superclasses of threshold graphs, Discrete
Math. Algorithms Appl., 5.
7. T. Calamoneri, B. Sinaimeri (2016) On Pairwise Compatibility
Graphs: a Survey. SIAM Review 58(3) 445–460.
8. S. Durocher, D. Mondal, Md. S. Ramhan (2015) On graphs that are
not PCGs, Theoretical Computer Science 571 78–87.
9. J. Felsenstein (1978) Cases in which parsimony or compatibility
methods will be positively misleading, Systematic Zoology, 27 401–
410.
10. V. Chvátal, P. Hammer (1977) Aggregation of inequalities in integer
programming, Annals of Discrete Mathematics, 1 145–162.
11. Md.I. Hossain, S. A. Salma, Md. S. Rahman, D. Mondal (2017) A
Necessary Condition and a Sufficient Condition for Pairwise Com-
patibility Graphs, J. Graph Algorithms Appl. 21(3) 341–352.
12. P.E. Kearney, J. I. Munro, D. Phillips (2003) Efficient generation of
uniform samples from phylogenetic trees, Proc. Algorithms in Bioin-
formatics, Lecture Notes in Computer Science 2812 177–189.
13. N. Mahadev, U. Peled (1995) Threshold graphs and related topics,
Annals of Discrete Mathematics 56.
14. N. Nishimura, P. Ragde, D.M. Thilikos (2002) On graph powers for
leaf-labeled trees, Journal of Algorithms 42 (1) 69–108.
15. S. A. Salma, Md. S. Rahman, Md. I. Hossain (2013) Triangle-free
outerplanar 3-graphs are pairwise compatibility graphs, J. Graph
Algorithms Appl., 17 81–102.
16. M.N. Yanhaona, Md.S. Bayzid, Md. S. Rahman (2010) Discovering
Pairwise Compatibility Graphs, Discrete Mathematics, Algorithms
and Applications 2(4) 607–623.
17. M. N. Yanhaona, K. S. M. T. Hossain, Md. S. Rahman (2009) Pair-
wise compatibility graphs, J. Appl. Math. Comput., 30 479–503.
18. M. Xiao, H. Nagamochi (2018) Some reduction operations to pair-
wise compatibility graphs, arXiv: 1804.02887v1//9Apr
19. M. Xiao, H. Nagamochi (2018) Characterizing Star-PCGs, arXiv:
1804.02895v1//9Apr