INSTITUT NATIONAL DE RECHERCHE EN INFORMATIQUE ET EN AUTOMATIQUE Linear time recognition of P4-indifference graphs M. Habib , C. Paul , L. Viennot No 3779 Octobre 1999 ISSN 0249-6399 ISRN INRIA/RR--3779--FR+ENG ` THEME 1 apport de recherche Linear time reognition of P4-indierene graphs M. Habib , C. Paul y , L. Viennot z Thème 1 Réseaux et systèmes Projet HIPERCOM 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. Key-words: P4-indierene, algorithm, reognition. Abstrat: (Résumé : tsvp) email : habiblirmm.fr; LIRMM, Université Montpellier II, 161 rue Ada, 34392 Montpellier Cedex, Frane y email : paullabri.u-bordeaux.fr; LaBRI, Université Bordeaux I, 351 ours de la Libération, 33405 Talene Cedex, Frane. Additional supports by the Region Aquitaine Projet #98024002. z email : Laurent.Viennotinria.fr; 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 3 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 olouring. 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 4 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 INRIA 5 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 trivial. 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 graphs 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 6 M. Habib , C. Paul , L. Viennot Ib Id Ia I 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 . (1) (2) (3) Ix Iy Iy Ix Iz Iz Ix Iy 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 INRIA Linear time reognition of P4-indierene graphs 7 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 8 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. d a b a0 d0 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. f g f g INRIA Linear time reognition of P4-indierene graphs 9 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 ? Referenes [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 10 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. INRIA Unit´e de recherche INRIA Lorraine, Technopˆole de Nancy-Brabois, Campus scientifique, ` NANCY 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 ´ Editeur INRIA, Domaine de Voluceau, Rocquencourt, BP 105, 78153 LE CHESNAY Cedex (France) http://www.inria.fr ISSN 0249-6399

1/--страниц