вход по аккаунту


код для вставкиСкачать
Linear time recognition of P4-indifference
M. Habib , C. Paul , L. Viennot
No 3779
Octobre 1999
ISSN 0249-6399
de recherche
Linear time reognition of P4-indierene graphs
M. Habib
, C. Paul
, L. Viennot
Thème 1 Réseaux et systèmes
Rapport de reherhe n3779 Otobre 1999 10 pages
A graph is a P4-indierene graph if it admits an ordering < on
its verties suh that every hordless path with verties a, b, , d and edges
ab, b, d has a<b<<d or d<<b<a. We present a linear time reognition
for these graphs.
P4-indierene, algorithm, reognition.
(Résumé : tsvp)
email :; LIRMM, Université Montpellier II, 161 rue Ada, 34392 Montpellier Cedex, Frane
y email :; LaBRI, Université Bordeaux I, 351 ours de la
Libération, 33405 Talene Cedex, Frane. Additional supports by the Region Aquitaine
Projet #98024002.
z email :; INRIA Roquenourt, Domaine de Volueau,
Roquenourt, BP 105, 78153 Le Chesnay Cedex, Frane
Unit´e de recherche INRIA Rocquencourt
Domaine de Voluceau, Rocquencourt, BP 105, 78153 LE CHESNAY Cedex (France)
T´el´ephone : 01 39 63 55 11 - International : +33 1 39 63 55 11
T´el´ecopie : (33) 01 39 63 53 30 - International : +33 1 39 63 53 30
Reonnaissane des graphes P4-indiérents en
temps linéaire
Résumé : Un graphe est dit P4-indiérent s'il admet un ordre total sur ses
sommets de sorte que tout hemin sans orde de sommets a, b, , d et d'arêtes
ab, b, d vérie a<b<<d ou d<<b<a. Un algorithme de reonnaissane
en temps linéaire est proposé.
Mots-lé :
P4-indiérent, algorithme, reonnaissane.
Linear time reognition of P4-indierene graphs
1 Introdution
A P4 is a hordless path of four verties. A graph is P4-indierene if it admits
an ordering < on its vertex set suh that every P4 abd has a < b < < d
or d < < b < a. Suh an ordering is alled a P4-indierene ordering. The
P4 -indierene graphs were introdued in [2℄ as a partiular lass of perfetly
orderable graphs. A graph is perfetly orderable if there exists an ordering on
its vertex set for whih the greedy olouring algorithm produes an optimal
The rst reognition algorithm for P4-indierene graphs is due to Hoàng
and Reed and has omplexity O(n6) [6℄. They ompute the equivalene lasses
of some relation on the P4's of the graph. Then they have to hek that this
lasses does not ontain a ertain subgraph with 6 verties. Later, Rashle
and Simon, studying more arefully the P4's relations, proposed an O(n2m)
reognition algorithm [10℄.
Reently, Hoàng, Maray and Noy gave a haraterization by forbidden
indued subgraphs [5℄ and raised the question of the existene of a linear time
reognition algorithm. We answer to this question by the armative thanks to
some of their theorems. Moreover our algorithm omputes an adequate ordering of the verties when it onludes that the input graph is P4 -indierene.
2 Theoretial basis
We use the following theorems from [5℄:
Theorem 1
[5℄ Any P4 -indierene graph fullls the following properties:
1. If it ontains a C4 (a hordless yle of length 4) then it ontains an
homogeneous set.
2. If it ontains no C4 then it is an interval graph.
These two properties inspire the following reognition algorithm: Compute
the modular deomposition tree of the input. For eah quotient graph of any
node of the tree verify that it is an interval graph. Compute an interval representation of it and use it to test whether it is a P4 -indierene graph and to
RR n3779
M. Habib , C. Paul , L. Viennot
ompute a good ordering of the verties if there exists one. The existene of
linear time algorithms for modular deomposition and interval graph reognition [9, 7℄ make this sheme possible for a linear time reognition algorithm.
To justify suh an algorithm, we rst need some additional theoretial
results linking P4-indierene graphs and modular deomposition.
Theorem 2
The omposition of two graphs is P4 -indierene i they are both
P4 -indierene graphs.
Proof: Let G be the omposition of two graphs G1 and G2 where G is obtained
from G1 by replaing a vertex u2 by G2 by linking all the verties of G2 to all
the neighbors of u2.
First suppose G is P4-indierene. We prove that G1 and G2 are also P4indierene. Let z1 < < zn be a P4-indierene ordering of the verties
of G. The indued order of the verties of G2 will obviously fulll the same
ondition. G2 is thus learly a P4 -indierene graph. Consider the ordering of
the verties of G1 obtained from z1 < < zn by erasing all the verties of G2
but one that is replaed by u2. It is learly a P4-indierene ordering.
Seond suppose G1 and G2 are P4-indierene graphs. We show that G is
also a P4 -indierene graph. Let y1 < < yp be a P4-indierene ordering
of the verties of G2 and x1 < < xm be a P4 -indierene ordering of the
verties of G1 where u2 = xk . Then x1 < < xk 1 < y1 < < yp < xk+1 <
< xm is learly a P4 -indierene ordering of the verties of G.
An immediate orollary of Theorem 2 is the following:
A graph is a P4 -indierene graph i all the quotient graphs of
its modular deomposition tree are P4 -indierene graphs.
Corollary 3
Notie that the seond part of the proof of theorem 2 also gives a simple
way to ompute a P4 -indierene ordering of the omposition of some P4indierene graphs from their P4 -indierene orderings.
A P4 -indierene ordering an be omputed in linear time from
the P4 -indierene orderings of the quotient graphs.
Corollary 4
Linear time reognition of P4-indierene graphs
Proof: Assume you are given a P4 -indierene ordering for eah quotient graph.
Then visit the modular tree deomposition in a post-order fashion, and for eah
node N do the following:
if N is a leaf, then it orresponds to a single vertex and the ordering is
if N is an internal node, then for eah son Si of N you have a P4indierene ordering i . Let H the P4 -indierene ordering of H , the
quotient graph assoiated to N . Eah Si orresponds to a vertex xi of H .
Then a P4 -indierene ordering of the graph whose tree deomposition
is rooted at N , an be obtained by substituting eah i to xi in H .
The linearity of the above algorithm omes from the linearity of the sum
of the sizes of the quotient graphs.
So now, to omplete our reognition algorithm of P4-indierene graphs,
we just need to ompute P4-indierene ordering and to reognize prime P4indierene graphs.
3 Reognition of prime interval P4-indierene
Let G be a prime interval graph. Let I1 ; : : : ; In be a minimal interval representation of it where eah Ik is an integer interval of [1; N ℄ (with N minimal).
If u is a vertex, we denote by Iu its assoiated interval. Reall that by denition, two verties u and v of G are linked i Iu intersets Iv . We say that two
intervals overlap when they interset without one being inluded in the other.
When two intervals do not interset, we say that the one with greater (resp.
smaller) elements is greater (resp. smaller) than the other.
We are now going to show how a minimal interval representation is lose to a
P4 -indierene ordering. Consider a P4 a; b; ; d with edges ab; b; d. We laim
that the intervals Ib and I assoiated to b and must overlap. They interset
sine the two verties are linked. Sine Ia intersets Ib but not I, Ib annot be
inluded in I. For a similar reason with Id, I annot be inluded in Ib. Thus
any P4 is of the form illustrated by Figure 3 in the interval representation.
RR n3779
M. Habib , C. Paul , L. Viennot
Figure 1: Any P4 a0; b0 ; 0; d0 is embedded in the interval representation as
shown. Either a0 = a; b0 = b; 0 = ; d0 = d or a0 = d; b0 = ; 0 = b; d0 = a
Conversely, when two intervals Ib and I overlap then b and are the middle
verties of at least one P4 . This is due to the fat that the interval representation has been hosen minimal. Suppose for example that some elements of Ib
are smaller than those of I (the other ase is symmetrial). Let i be the greatest integer of Ib that is not in I. There must exist an interval Ia ontaining i
without interseting I otherwise i ould be removed yielding a more ompat
representation (ontraditing the minimality of the present one). The same argument allows to onlude that there must exist some interval Id interseting
I but not Ib . a; b; ; d is then a P4 .
Figure 2: The three situations of Theorem 5 implying
indierene ordering.
x < y
for a
P4 -
The following theorem an easily be dedued from the proofs in [5℄. It links
minimal interval representations and P4-indierene orderings.
Consider a prime interval graph G and a minimal interval representation of it. Let be the relation satisfying x y for any verties x; y
Theorem 5
Linear time reognition of P4-indierene graphs
satisfying one of the three following properties (these situations are illustrated
by Figure 3):
1. Ix and Iy interset and the left bound of Ix is smaller than the left bound
of Iy .
2. Ix is inluded in Iy and there exists some interval Iz greater than Ix
overlapping Iy .
3. Iy is inluded in Ix and there exists some interval Iz smaller than Iy
overlapping Ix .
G is a P4 -indierene graph i is ayli. Moreover any extension of (i.e. for eah x; y x y implies x < y or for eah x; y x y implies x > y )
is a P4 -indierene ordering.
Notie that the previous remarks imply that x and y are verties of some
P4 in eah of the three situations of Theorem 5. Moreover any two onseutive
verties of some P4 are in relation by . And all above, any P4 a; b; ; d either
veries a b d or d b a. See [5℄ for the details of the proofs.
Corollary 6
linear time.
The reognition of prime P4 -indierene graphs an be done in
Proof: Let us briey desribe the reognition algorithm :
Test if the input graph is an interval graph and if so ompute a minimal interval representation. It an be done in linear time by any linear
interval graphs reognition algorithm (see [1, 8, 7, 4, 3℄ for example).
The relation an easily be omputed in linear time by storing for
eah interval the two intervals overlapping it whih have the rightmost
left bound and the leftmost right bound when they exist. During this
omputation, you an nd all the relations orresponding to overlapping
intervals (ase (1) of gure 3). Then the relations orresponding to ase
(2) and (3) of gure 3 an be omputed.
RR n3779
M. Habib , C. Paul , L. Viennot
Using a Depth First Searh, the ayliity of an be tested and a linear
extension of it an be omputed (it there exists one). It an be done in
linear time.
4 Conlusions
This paper shows how a linear time algorithm for the P4-indierene graphs
reognition an be designed. This algorithm strongly relies on modular deomposition as a preproessing. But linear time modular deomposition algorithms
are still ompliated to program. So the natural question is: an this preproessing step an be avoided ?
So it has been shown that prime P4 -indierene graphs are interval graphs.
It is well known that Lexiographi Breadth First Searh (Lex-BFS) [11℄ plays
an important role on interval graphs [7, 3, 4℄. The order Lex-BFS visits the
verties of the input graph an be seen as the output of Lex-BFS: a Lex-BFS
ordering. For example in [3℄, 4 sweeps of partiular Lex-BFS are used to
ompute a harateristi ordering of interval graphs (the i-th sweep starts on
the last visited vertex of the previous sweep). One an wonder if Lex-BFS an
be used to ompute a P4 -indierene ordering. As illustrated by the graph of
gure 4, the answer is no.
Figure 3: A graph suh that no Lex-BFS ordering is a P4 -indierene ordering
On the above graph, no Lex-BFS ordering is a P4-indierene ordering. So
there is no hope for some speial Lex-BFS as those dened in [3℄. We an
remark that this graph ontains modules ( a; a0 and d; d0 ). It seems that
restrited to prime P4 -indierene graphs, 2 sweeps of Lex-BFS omputes a
P4 -indierene ordering (it an be a simpliation of the presented algorithm).
But up to now, we do not know how to avoid the modular deomposition.
Linear time reognition of P4-indierene graphs
The presented algorithm relies on some properties of prime graphs and
also on some P4 relations. Can these strutural results be adapted to other
lasses of perfetly orderable graphs like for example P4-omparability graphs,
P4 -simpliial graphs : : : in order to design eient reognition algorithms ?
[1℄ K.S. Booth and G.S. Leuker. Testing for the onseutive ones property,
interval graphs and graph planarity using PQ-tree algorithm. J. Comput.
Syst. Si., 13:335379, 1976.
[2℄ V. Chvàtal. Perfetly ordered graphs. Annals of Disrete Mathematis,
21:6366, 1984.
[3℄ D.G. Corneil, S. Olariu, and L. Stewart. The ultimate interval graph
reognition algorithm ? In Proeedings of the 9th Annual ACM-SIAM
Symposium on Disrete Algorithms (SODA-98), pages 175180, 1998.
[4℄ M. Habib, R.M. MConnell, C. Paul, and L. Viennot. Lex-BFS a partition
rening tehnique, appliation to transitive orientation and onseutive
1's testing. Theoretial Computer Siene, 1997. To appear.
[5℄ C.T. Hoàng, F. Maray, and M. Noy. A haraterization of p4-indierene
graphs. To appear in Journal of Graph Theory, 1998.
[6℄ C.T. Hoàng and B.A. Reed. Some lasses of perfetly orderable graphs.
Journal of Graph Theory, 13(4):445463, 1989.
[7℄ W.L. Hsu and T.H. Ma. Substitution deomposition on hordal graphs
and appliations. In Proeedings of the 2nd ACM-SIGSAM Internationnal Symposium on Symboli and Algebrai Computation, number 557 in
LNCS, 1991.
[8℄ N. Korte and R. Möhring. An inremental linear-time algorithm for reognizing interval graphs. SIAM Journal of Computing, 18:6881, 1989.
RR n3779
M. Habib , C. Paul , L. Viennot
[9℄ R.M. MConnell and J.P. Spinrad. Linear-time modular deomposition
and eient transitive orientation of undireted graphs. In Proeedings of
the Fifth Annual ACM-SIAM Symposium on Disrete Algorithms, pages
536545, 1994.
[10℄ T. Rashle and K. Simon. On the p4-omponents of graphs. Tehnial
Report 261, Institute of Theoretial Computer Siene, ETH Zürik, 1997.
[11℄ D. J. Rose, R. E. Tarjan, and G. S. Leuker. Algorithmi aspets of vertex
elimination on graphs. SIAM Journal of Computing, 5(2):266283, 1976.
Unit´e de recherche INRIA Lorraine, Technopˆole de Nancy-Brabois, Campus scientifique,
615 rue du Jardin Botanique, BP 101, 54600 VILLERS LES
Unit´e de recherche INRIA Rennes, Irisa, Campus universitaire de Beaulieu, 35042 RENNES Cedex
Unit´e de recherche INRIA Rhˆone-Alpes, 655, avenue de l’Europe, 38330 MONTBONNOT ST MARTIN
Unit´e de recherche INRIA Rocquencourt, Domaine de Voluceau, Rocquencourt, BP 105, 78153 LE CHESNAY Cedex
Unit´e de recherche INRIA Sophia-Antipolis, 2004 route des Lucioles, BP 93, 06902 SOPHIA-ANTIPOLIS Cedex
INRIA, Domaine de Voluceau, Rocquencourt, BP 105, 78153 LE CHESNAY Cedex (France)
ISSN 0249-6399
Пожаловаться на содержимое документа