INSTITUT NATIONAL DE RECHERCHE EN INFORMATIQUE ET EN AUTOMATIQUE Efficient and Practical Algorithms for Sequential Modular Decomposition Elias Dahlhaus, Jens Gustedt, Ross M. McConnell N˚3804 Novembre 1999 ISSN 0249-6399 ISRN INRIA/RR--3804--FR+ENG THÈME 1 apport de recherche Eient and Pratial Algorithms for Sequential Modular Deomposition y Elias Dahlhaus , Jens Gustedt , Ross M. MConnell z Thème 1 Réseaux et systèmes Projet Résédas Rapport de reherhe n3804 Novembre 1999 23 pages A module of an undireted graph G = (V; E ) is a set X of verties that have the same set of neighbors in V n X . The modular deomposition is a unique deomposition of the verties into nested modules. We give a simpler approah to sequential linear-time modular deomposition. Key-words: modular deomposition, linear time algorithms Abstrat: (Résumé : tsvp) y z Dept. of Computer Siene and Dept. of Mathematis, Univ. of Cologne, Cologne, Germany. LORIA and INRIA Lorraine, 54506 Vand÷uvre lès Nany, Frane, Jens.Gustedtloria.fr. Dep. of Computer Siene and Engineering, Univ. of Colorado at Denver, Denver, CO 80217-3364 USA. Unité de recherche INRIA Lorraine Technopôle de Nancy-Brabois, Campus scientifique, 615 rue de Jardin Botanique, BP 101, 54600 VILLERS LÈS NANCY (France) Téléphone : 03 83 59 30 30 - International : +33 3 3 83 59 30 30 Télécopie : 03 83 27 83 19 - International : +33 3 83 27 83 19 Antenne de Metz, technopôle de Metz 2000, 4 rue Marconi, 55070 METZ Algorithmes pratiques et eaes pour la déomposition modulaire séquentielle Un module d'un graphe non-orienté G = (V; E ) est un ensemble X de sommets qui partage le même ensemble de voisins en V n X . La déomposition modulaire est une déomposition unique des sommets en modules emboîtés. Nous donnons une approhe simpliée à la déomposition modulaire en temps linéaire. Mots-lé : déomposition modulaire, algorithmes linéaires Résumé : Eient and Pratial Algorithms for Sequential Modular Deomposition 3 1 Introdution Modular deomposition is a tree-like deomposition of a graph that we desribe below. When the resulting tree is nontrivial, it provides a way to apply a divide-and-onquer strategy to a number of NP-omplete problems. Thus, a large number of NP-omplete problems an be solved reursively on the tree in time proportional to the number of verties times 2(k) , where k is the maximum number of hildren of a node in this tree, whih gives rise to polynomial algorithms for graphs whose deomposition trees are of bounded degree. Let n denote the number of verties, and let m denote the number of edges. There have been a number of O(n4), O(n3), O(nm), and O(n2) algorithms for nding modular deomposition, suh as Buer and Möhring (1983), Ehrenfeuht et al. (1994), Golumbi (1977), Habib and Maurer (1979), MConnell (1995), Muller and Spinrad (1989), Steiner (1982), some of them for speial ases or generalizations of the problem. The otree deomposition of ographs and the series-parallel deomposition of series-parallel partial orders are speial ases on graphs and digraphs, respetively, for whih lineartime solutions have been given, see Corneil et al. (1985), Valdes et al. (1982). O(n + m log n), bounds for arbitrary undireted graphs were then given in Cournier and Habib (1993), and an O(n + m(m; n)) bound was given in Spinrad (1992). The rst linear-time algorithm was given in MConnell and Spinrad (1994). An altogether dierent linear-time was given shortly thereafter in Cournier and Habib (1994). Both of these algorithms are lengthy and quite hallenging to understand. We derive a oneptually simpler linear-time sequential algorithm than was previously available. In addition, we give O(n + m(m; n)) variant that we believe is simple enough to be haraterized as pratial. We skethed this version in Dahlhaus et al. (1997). 2 Preliminaries This setion gives the basi denitions of the objets and algorithmi features that we are talking about. It is split into two parts. The rst part introdues the basi notation and fats about modular deomposition. The seond desribes some essential data strutures that are needed to handle graphs eiently. 2.1 Modular deomposition of undireted graphs In this paper, the term graph will denote an undireted graph, while the term digraph will denote a direted graph. We let n denote the number of verties and m the number of edges. Let G = (V; E ) be a graph with vertex set V and edge set E . If X is a subset of V , then GjX is the subgraph indued by G. The omplement of a graph G is the graph G with the same set of verties, but where fu; vg is an edge i it is not an edge of G. A onneted omponent is a maximal set of verties that are all onneted by paths. A o-omponent is a onneted omponent of the omplement. The neighborhood of a vertex v is the set N (v) = fw j fv; wg is an edge of Gg: A pair fu; vg of verties that is not an edge is a non-edge. The set of verties in V n fvg that are not neighbors of v are its non-neighbors, and is denoted N (v). A strong neighbor of a set X V of verties is a vertex y 2 V n X that is a neighbor of every vertex of X . A non-neighbor of X is a vertex z 2 V n X that is not a neighbor of any vertex in X . A module of an undireted graph G = (V; E ) is a set X of verties that all have the same set of neighbors in V n X , see Figure 1. That is, X is a module i every member of V n X is either a strong neighbor or a non-neighbor. Though there is a generalization of modules to digraphs, we will not refer to them in this paper. RR n3804 4 Elias Dahlhaus, Jens Gustedt, Ross M. MConnell Figure 1: A graph and its modules. Two sets X and Y overlap if X n Y , Y n X , and Y \ X are all nonempty. X Y denotes (X n Y ) [ (Y n X ), the symmetri dierene of Y and X . The following two observations are not hard to verify. Lemma 2.1 (Möhring (1985)) If X and Y are overlapping modules, then X n Y , Y n X , Y Y [ X , and Y X are also modules. \ X, A pair X , Y of disjoint modules is adjaent if every member of Y is adjaent to every member of X , and nonadjaent if no member of Y is adjaent to any member of X . Lemma 2.2 (Möhring (1985)) Any pair X and Y of disjoint modules is either adjaent or nonadjaent. A ongruene partition is a partition of V where eah partition lass is a module. The adjaeny relation on members of a ongruene partition is itself a graph, where eah set of the ongruene partition is treated as a single vertex. This graph is denoted G=P . G=P ompletely speies those edges of G that are not subsets of a single partition lass (see Figure 2). A fator in a ongruene {A..I}: Members of congruence partition P G C G: H A E I D F B A C E D G/P: B G H I F Figure 2: A graph with ongruene partition and the orresponding quotient. partition P is an indued subgraph GjX for some X 2 P . The subgraphs indued by the parts speify INRIA 5 Eient and Pratial Algorithms for Sequential Modular Deomposition j l d a g i k b e c h f V(R) {a,b,c,d,e,f,g,h} {a,b,c} (0) (0) (1) {i,j,k,l} (P) {d,e} (0) {g,h} (1) {i,j,k} (0) l f {a,b} (1) c a d e g h i j k b Figure 3: The modular deomposition tree of the graph of Figure 1. preisely those edges of G that are not speied by the quotient. Thus, given a ongruene partition P , we may speify G by giving the quotient G=P and GjX for eah partition lass X 2 P . V , ; and the singleton subsets of V satisfy the denition of a module, and are the trivial modules of G. As a result, every graph has at least two ongruene partitions, one with a single part V , and one with jV j parts, where eah part is a singleton subset of V . A graph is prime if it has only trivial modules, hene only the two trivial ongruene partitions. The quotient and substrutures also preserve information about the arrangement of other modules of G: Lemma 2.3 (Möhring (1985)) If P is a ongruene partition on G, and S module in G=P i M is a module of G. M P, then M is a Lemma 2.4 (Möhring (1985)) If X is a module of G = (V; E ) and Y is a subset of X , then Y is a module of G i it is a module of GjX . By these two lemmas, it follows that if no module overlaps a partition lass of a ongruene partition P , the modules of the quotient and the substrutures give the modules of G. This makes it desirable to speify G using ongruene partitions whose parts do not overlap any modules. A strong module is a module that overlaps no other module of G, while a strong quotient is one whose parts are strong modules. The modular deomposition of G is the unique deomposition of G obtained by nding a oarsest strong quotient P that has more than one part, and then deomposing its fators reursively, see Figure 3. The deomposition of eah fator speies the fator. As observed above, the fators and the quotient then speify G. RR n3804 6 Elias Dahlhaus, Jens Gustedt, Ross M. MConnell V is the only maximal module. We will let the highest submodules be those modules that are not ontained in any other module exept V . To desribe how the deomposition is derived, we use three ases. prime ase: G and G are eah onneted. One onsequene of Lemmas 2.1 and 2.2 is that if a graph and its omplement are both onneted, the oarsest strong ongruene partition of G is given by the highest submodules. To see this, note that Lemma 2.1 implies that if two highest submodules X and Y overlap, their union is a module, and sine X and Y are highest submodules, their union must be V . It also implies that X and Y n X are modules. Thus, X [ Y = V , and fX; Y n X g is a partition of V into two modules. Then Lemma 2.2 implies that either G or its omplement is disonneted, a ontradition. We onlude that if neither G nor G is disonneted, we may let P be the highest submodules of G. Other than V , no union of members of P is a module of G, sine they are highest submodules. By Lemma 2.3, it follows that G=P has no nontrivial modules, hene we have vauously enumerated its modules. parallel ase: G is disonneted. The highest submodules are not a partition of V , so we must resort to another method of nding the oarsest ongruene partition. A onneted omponent is a module that may not overlap any other module, so it must be strong. In addition, every nontrivial union of omponents other than V is a module, but sine eah suh union overlaps another, no suh module obtained in this way is strong. It follows that the set P of onneted omponents of G is the oarsest strong ongruene partition of G. Moreover, G=P is empty, so the modules of G=P are just the power set of P . series ase: G is disonneted. Sine the modules of G and its omplement are idential, reasoning symmetri to that of the parallel ase ditates that the oarsest strong ongruene partition P of G is given by the onneted omponents of G. The quotient G=P is omplete, sine G=P is empty, and the modules of G=P , hene the modules of G=P , are again the power set of P . Summarizing, given some proedure for nding the highest submodules of a graph, we may ompute the modular deomposition as follows. If G is disonneted, let P be the onneted omponent, and if G is disonneted, let P be its omponents. Otherwise, let P be the highest submodules of G. G=P is a strong quotient. Reursively ompute the rest of the deomposition on GjX for eah X 2 P . By Lemmas 2.3 and 2.4, a subset X of V is a module i it is S X for some module X of one of the reursively omputed quotients. Eah suh quotient either has no nontrivial modules, or else every subset of its verties is a module. Listing the members of all of the reursively omputed ongruene partitions takes (n2) spae in the worst ase. However, we may represent the deomposition tree in O(n) spae by using an O(1)spae representation for eah node of the tree, and letting this node arry a pointer to a list of its hildren. In this tree, the leaf desendants of eah node x give the orresponding module X . Sine eah node of the tree has at least two hildren, we may reover X from x in O(jX j) time, so this representation of X is as eient as any. For notational onveniene, we will identify x and X . For instane, we may speak of two modules X and Y as being siblings in the tree; this means that X is the leaf desendants of a tree node x, Y is the leaf desendants of a tree node y, and x and y are siblings. For any internal node X , the subgraph of G indued by a set onsisting of one member of eah hild of Y of X gives the quotient produed by the reursive all on X . A degenerate node is a parallel or series node in the deomposition tree. Every module of G that is not already a node of the tree is a union of hildren of a degenerate node. Every union of hildren of a degenerate node is a module. Thus, the deomposition also represents impliitly all modules of G. INRIA Eient and Pratial Algorithms for Sequential Modular Deomposition 7 Algorithm 1: MD(G) if G has only one vertex v then return v; let r be a new internal tree node; if G is disonneted then label r `parallel ' for eah onneted omponent G0 , make MD(G0 ) a hild of r else if G is disonneted then label r `series ' for eah onneted omponent G0 of G, make MD(G0 ) a hild of r else label r `prime ' for eah highest submodule X , make MD(GjX ) a hild of r return r 2.2 Basi proedures Now we present the basi data strutures and algorithms that we need to eiently represent and handle graphs and their modular deompositions. 2.2.1 Radix partitioning Consider the following problem. Given a set of strings of integers from 1 to n and an array of empty bukets (lists of strings), we want to partition the strings into groups so that two strings are in the same group if and only if they are idential, and then leave the bukets in their initial state. This an be aomplished by radix sorting in O(n + m) time, where m is the sum of lengths of the strings. However, we will nd it useful to observe that we an aomplish it in just O(m) time sine the problem does not plae any restrition on the order in whih the partition lasses must be presented. Like radix sorting, the algorithm proeeds in rounds. In round i, we assume by indution that we have already found the partition lasses of the strings that have length less than i 1, and that groups of strings that have idential (i 1)-integer prexes appear together in our list. The algorithm distributes the strings to the ordered bukets aording to the integer that appears in some position i. A string is always added to the front of a buket's list of strings when it is inserted. If a string is the rst string to be inserted in a buket, that buket is added to a list of nonempty bukets. One the strings are distributed, it onatenates the lists of strings that appear in the nonempty bukets, emptying the bukets in the proess. It uses the list of nonempty bukets to avoid visiting any empty bukets during this step. After round i, a set of strings that have idential i-integer prexes are onseutive in the list. Partition lasses orresponding to i-integer strings an be removed from the list at this point. The running time an be harged at O(1) to the ith integers of the strings examined, and O(1) to eah integer of the i-integer strings that are removed from the list. Beause of the similarity of this algorithm to radix sorting, we will all it radix partitioning. 2.2.2 Sorting Adjaeny Lists Given a numbering of verties of a graph, we may sort all adjaeny lists so that neighbors appear in asending order, in O(n + m) time, by onatenating all adjaeny lists and then radix-sorting the resulting list using vertex of origin as primary sort key and ending vertex as seondary sort key. This is aomplished with two stable O(n + m) sorts, a rst one on the seondary key and a seond one on the primary key, see Cormen et al. (1990). We obtain the adjaeny lists by utting this nal list at points where the primary sort key hanges. RR n3804 8 Elias Dahlhaus, Jens Gustedt, Ross M. MConnell 2.2.3 Union-Find We need a Union-Find data struture for some of our operations. This is any struture that maintains a partition P of a set V , and supports the following operations: Initialize : Set P := ffv g j v 2 V g. Find : Find a pointer to the member of P that ontains a given v 2 V . Union : Given v; w 2 V , merge the the two sets of P that ontain v and w by replaing them with their union in P . An arbitrary sequene starting with one Initialize, on a set of size n, and a mixed sequene of n 1 Union and m Find operations takes O(n(m; n)) time, see Tarjan (1983), Cormen et al. (1990). The is an extremely slow-growing but unbounded funtion that has value at most four in any pratial appliation of the data struture. To ahieve a linear time bound for modular deomposition, a ertain restrition of the union-nd problem will be relevant. We say that a sequene of Union operations on the set V respets a graph G = (V; E ) if, for any of the subsets S that are reated via the Unions, GjS is onneted. Another formulation of this property is the assertion that whenever two sets S1 and S2 are merged via a Union operation there will always be an edge in G that joins a member of S1 to a member of S2. For an overview of these onepts see e.g Gustedt (1998). The following theorem is ruial for the linear time bound of our algorithm. Theorem 1 (Gabow and Tarjan (1985)) Let T = (V; E ) be a tree. Any sequene of n Union and m Find operations on V that respets T an be performed in O(n + m) time. 2.2.4 Partially Complemented Representations In a onventional adjaeny-list representation of a direted graph G, eah vertex arries a list of its neighbors. Suh a representation learly has a disadvantage when we also have to deal with the omplement of the graph, or more generally, with non-edges: passing from a standard enoding of a graph to suh an enoding of its omplement rules out any possibility of a linear time algorithm. We irumvent this kind of problem with the following data struture. Denition 2.5 In a partially omplemented, or mixed representation of G = (V; E ) every vertex maintains a list of either N (v) or N (v) and a label that is either standard or omplemented that tells whih of the two ases applies for v. We dene the size of a mixed representation to be n + m0 , where n is the number of verties, and m0 is the sum of ardinalities of their assoiated lists. Denition 2.6 (Dahlhaus et al. (1997)) Let the bipartite omplement of a direted bipartite graph (V1 ; V2 ; A) be the graph (1) V1 ; V2 ; V1 V2 [ (V2 V1 ) n A : In a mixed bipartite representation, eah vertex in V1 (resp. V2 ) has either a list of those members of V2 (resp. V1 ) that are out-neighbors, or else a list of those members of V2 (resp. V1 ) that are not out-neighbors. This representation has many interesting properties whih are beyond the sope of this paper. The relevant result for our algorithm is the following: Theorem 2 (Dahlhaus et al. (1997)) Given a mixed representation of a direted graph or direted bipartite graph, nding the strongly-onneted omponents takes time linear in the size of the representation. INRIA Eient and Pratial Algorithms for Sequential Modular Deomposition 9 3 A Strategy for Modular Deomposition Our approah uses elements from a previous strategy, see Ehrenfeuht et al. (1994), whih we desribe rst. If v is a vertex of G, let M(G; v) denote fvg and the set of maximal modules of G that do not ontain v. That is, X 2 M(G; v) if either X = fvg, or X is a module of G that does not ontain v, and every proper superset that is a module of G ontains v. M(G; v) is a partition of V . The following are easy onsequenes of Lemma 2.3. Lemma 3.1 (Ehrenfeuht et al. (1994)) All nontrivial modules of G=M(G; v0 ) ontainSfv0 g. A subset X of M(G; v0 ) is an internal node of the modular deomposition of G=M(G; v0 ) i X is an anestor of fv0 g in the modular deomposition of G. All other strong modules are subsets of some member of M(G; v0 ). Lemma 3.2 (Ehrenfeuht and Rozenberg (1990)) If X is a module of G, then the strong modules of G that are proper subsets of X are the strong modules of GjX that are proper subsets of X . The foregoing two lemmas give a strategy for nding the modular deomposition of G from the modular deompositions of subgraphs. Algorithm 2: Ehrenfeuht et al. (1994) Input: Let v0 be an arbitrary vertex. MD(G=M(G; v0 )) and fMD(GjX ) j X 2 M(G; v0 )g, Output: MD(G) Let T be the modular deomposition of G=M(G; v0 ); foreah leaf X of T do omment: X 2 M(G; v0 ); Let TX be the modular deomposition of GjX ; Replae X with TX in T ; if X and its parent p(X ) are both parallel or both series nodes in T then Remove X from T and attah its hildren as hildren of p(X ) The proof of orretness follows from Lemmas 3.1 and 3.2, and an observation that the inner if statement removes X if and only if X fails to be strong in G. The implementation of Ehrenfeuht et al. (1994) omputes the modular deompositions of GjX by reursion, and uses a separate tehnique to nd the modular deomposition of G=M(G; v0 ) that takes advantage of its simple struture. The best bound so far for this approah is O(min((n2 ); m log n)), see MConnell and Spinrad (1998). The bottlenek is a step alled alled vertex partitioning, whih is used to ompute M(G; v0 ). We now desribe a signiant improvement on the strategy, whih is due to Dahlhaus (1995), who used it to obtain the parallel time bound for modular deomposition that we give below. We use it to obtain a linear-time sequential algorithm, and a parallel algorithm for transitive orientation. The strategy alls for omputing MD(GjN (v0 )) and MD GjN (v0) by reursion, and then nding fMD(GjX ) j X 2 M(G; v0 )g by a tehnique alled restrition. If Y V , let the restrition to Y of the modular deomposition of G be the set of modular deompositions of the members of f(GjX ) j X is a maximal module of G that is ontained in Y g. For a; b 2 Y , let aRb be the relation where a and b have the same set of neighbors in V n Y . Sine this is an equivalene relation, this gives a partition of Y , whih we will all the same-neighbor partition. For the orretness, note that a X Y is a module of G i all of its members have the same set of neighbors in V n X . This happens i it is a module in GjY and all members of X have the same neighbors in V n Y . The proedure nds eah maximal X that is a module of GjY and has only strong neighbors and non-neighbors in G n Y , and makes it the root of a tree in a forest. That this tree is the modular deomposition of GjX follows from Lemma 3.2. RR n3804 10 Elias Dahlhaus, Jens Gustedt, Ross M. MConnell Algorithm 3: The Restrit Step Input: Y V and the modular deomposition T of GjY Output: the restrition to Y of the modular deomposition of G Delete from T all nodes that represent sets that interset more than one same-neighbor lass; In the remaining forest, group together any roots that are former hildren of a ommon degenerate node and are ontained in a ommon same-neighbor lass, and make them hildren of a new degenerate node. Lemma 3.3 The modular deompositions of the members of f(GjX ) j X 2 M(G; v0 ) n ffv0 ggg are given by the restritions of the modular deomposition of G to N (v0 ) and N (v0 ). Proof: The restritions give the modular deomposition of GjX for eah maximal module of G ontained in N (v0) and N (v0 ). No suh module ontains v0 . If X 2 M(G; v0 ) nffv0 gg, it is a maximal module of G that does not ontain v0, and sine v0 is either a strong neighbor or a non-neighbor, it must be ontained in N (v0 ) or N (v0 ). Algorithm 4 gives a high-level overview of the strategy. We make one nal observation. Algorithm 4: Dahlhaus (1995) if G has only one vertex v then return v as a tree node else reurse: Selet a vertex v0, and reursively ompute the modular deompositions of GjN (v0) and GjN (v0 ). restrit step: Using these trees, Algorithm 3, and Lemma 3.3, nd, for eah X 2 M(G; v0 ) n ffv0 gg, the modular deomposition of GjX . v0 -modules step: Compute the modular deomposition of G=M(G; v0 ); assemble step: Using Algorithm 2, assemble these modular deompositions to form the modular deomposition of G. Lemma 3.4 (Dahlhaus (1995)) If v0 is an an arbitrary vertex of G, then for any module M ontaining v0 , M \ N (v0 ) is a union of zero or more omponents of GjN (v0 ), and M \ N (v0 ) is a union of zero or more o-omponents of GjN (v0 ). Proof: If a module M ontains v0 , then sine v0 is nonadjaent to every vertex in M n N (v0 ), every vertex in M \ N (v0 ) is nonadjaent to very vertex in M n N (v0). Thus M \ N (v0 ) is a union of zero or more onneted omponents of GjN (v0). That M \ N (v0) is a union of o-omponents of GjN (v0 ) is proved in a symmetri way, by reversing the roles of edges and non-edges. 4 Sequential Modular Deomposition in Near Linear Time We now desribe an algorithm that is based on Algorithm 4 and that runs in O(n + m(m; n)) time. The union-nd operations are the only obstale to a linear time bound. This algorithm is simpler than any previous algorithm with this bound. 4.1 A data struture for the deomposition tree We use the following data struture to represent modular deomposition trees. INRIA Eient and Pratial Algorithms for Sequential Modular Deomposition 11 Data Struture 4.1 (Representation of a modular deomposition tree.) representative: Eah node of the tree arries a pointer to a vertex of the graph whih is one of its leaf desendants, alled its representative. siblings: Eah node of the tree is a member in a list that maintains the hildren of its parent. parent: Eah node u of the tree arries a pointer to its parent. This pointer is up-to-date exept under speial irumstanes that are desribed below. omponents: Eah vertex of the subgraph under onsideration resides in a union-nd struture that reet the onneted omponents of G. For eah vertex of the graph that atually is a representative of a omponent, we maintain a pointer to the orresponding node of the deomposition tree. The list of siblings maintains the operations of deleting elements and of onatenation of suh lists in O(1) time. This an be ahieved by a irular doubly-linked list. The parent pointer might not be up-to-date in the following ases: 1. The parent is V ; 2. The parent is a onneted omponent. We summarize the properties of our data struture in the following lemma: Lemma 4.2 A data struture for modular deomposition trees an be maintained in a way that it allows the following operations in O(f (m; n)) amortized time, where f (m; n) is the amortized bound on the union-nd data struture that is used: Parent : For any node we an aess its parent in the tree (if it exists) . Delete : Any node of a deomposition tree an be deleted at any time. Fuse : Any two nodes u and v that are the hildren of the same parent p an be fused into one. Proof: : The absene of up-to-date parent pointers in some of the nodes does not prevent the data struture from nding the parent of an arbitrary node X 6= V eiently. If X does not have an up-to-date parent pointer, a Find operation on its representative produes the omponent C that ontains X . If X = 6 C , the parent is C ; otherwise it is V . Timestamping parent pointers and nodes of the tree when they are reated gives a way of deteting whether a parent pointer is out of date, in O(1) time. Delete : Deletion of a node u an be ahieved by spliing it out of the doubly-linked list of its siblings, updating the hild pointer of the parent p if neessary, and spliing the list of hildren of u into the list of hildren at p. Fuse : We rst take the lists of hildren of u and v and onatenate them. We give this new list to u, say, as list of hildren, by updating the hild pointer and the union-nd data struture aordingly. Then we may delete the tree node v. Parent RR n3804 12 Elias Dahlhaus, Jens Gustedt, Ross M. MConnell 4.2 The harging disipline The following is our harging disipline for bounding the ost of operations during the indutive step of Algorithm 4. 1. There are O(n) Union operations over an entire run of the algorithm, so the ost of these is aounted for separately, and take O(n + m(m; n)) time, see Cormen et al. (1990). 2. A harge onsists of a xed number of O(1) operations and a xed number of Find operations in union-nd data strutures. 3. We maintain the redit invariant that eah node of a deomposition tree arries a redit that an pay for a harge. A node's redit an only be released to pay for operations when it is deleted. 4. Let the ative edges of G be those edges that are not subsets of N (v0 ) or N (v0 ). Let m0 be the number of ative edges. We adhere to the disipline that we inur O(m0) harges that are not paid for by released redits, and we deposit O(m0 ) new redits in the tree. Eah edge is ative in exatly one reursive all in the reursion tree. If we adhere to the harging disipline, it reeives O(1) harges in this reursive all, and no harges elsewhere. This gives a bound of O(m) harges over the entire reursion tree. This gives a bound of O(m) Find operations, whih is O(n + m(m; n)), and O(m) onstant-time operations. In addition, we have an O(n+m(m; n)) preproessing step. Suessfully maintaining the disipline will imply the O((n + m)(m; n)) bound, sine an edge only beomes ative one, hene the number of xed-ost operations and Find operations will be bounded by the O(m) redits initially available on the edges. However, an O((n + m)(m; n)) bound for any modular deomposition algorithm implies an O(n + m(m; n)) bound, sine, if n > m +1 in the original graph, we an spend O(n + m) preproessing time dividing the initial graph into its onneted omponents, solve the problem on eah omponent, where n is O(m), and then make the root of these trees be the hildren of a new parallel root node, to obtain the deomposition of G. Let the ative neighbors of a set X of verties be those members of V n X that are adjaent to a member of X on an ative edge. Lemma 4.3 If X is a node of MD(GjN (v0 )) or MD GjN (v0 ) that is a module of G, the harging disipline allows us to inur one harge at X for eah ative neighbor of X . Proof: We show that the sum of lengths of ative neighbor lists of suh nodes is O(m0). The sum of lengths of the ative neighbor lists of of all leaves of MD(GjN (v0 )) and MD GjN (v0 ) is exatly m0. Any internal node that remains a module of G has an ative neighbor list that is idential to that of eah of its hildren. Thus, the length of its ative neighbor list is at most half of the sum of lengths of ative neighbor lists of its hildren. Let h(X ) be the length of the shortest path from X to a leaf. The sum of lengths of neighbor lists of fX j h(X ) = k and X is node of MD(GjN (v0)) or MD GjN (v0) is a module of Gg is at most m0=2k . Summing this over inreasing values of k gives a geometri series that sums to less than 2m0 . Corollary 4.4 The harging disipline allows us to inur a harge at every node of MD(GjN (v0 )) and MD GjN (v0 ) that is not a module of G but has an inident ative edge. Proof: If the node remains a module of G, this follows from Lemma 4.3. Otherwise, the harge is paid for by the redit that is freed when it is Deleted during the restrit step of Algorithm 4. (The Delete operation refers to the one provided by Data Struture 4.1). INRIA 13 Eient and Pratial Algorithms for Sequential Modular Deomposition Note that we may inur a harge at every node of MD(GjN (v0 )) and MD GjN (v0) that has an inident ative edge; if the node is a module of G, the harge is overed by Lemma 4.3, and if it is not, the harge an be paid for by the redit that is released if it is Deleted during the restrit step. Thus, the only type of node at whih we may not spend O(1) time isone that has no inident ative edge. Let X be suh a node. X must be a node of MD GjN (v0 ) , sine all nodes of MD(GjN (v0)) have v0 as an ative neighbor. X is represented by a node of Data Struture 4.1 that is returned by the reursive all to GjN (v0 ). X remains a module of G,so it must be used in the assembly of MD(G) during the indutive step. If the parent Y of X in MD GjN (v0) has inident ative edges, Y is not a module of G , so Y is not a node of MD(G). In this ase, X has a dierent parent in MD(G) than it does in MD GjN (v0) , but our harging disipline does not allow us to inur a harge at X by resetting its parent pointer, or by spliing it into the hild list of its new parent. Let us all any node of MD GjN (v0) that has no inident ative edges and a new parent in MD(G) a problem node. There are three triks that we use for bounding the ost of spliing the problem nodes into the Data Struture 4.1 representation of MD(G): Trik 1: A list of problem hildren of a node X an be obtained without violating the harging disipline, as follows. If X remains a module of G, none of its hildren are problem hildren. Otherwise, X must have inident ative edges. We may inur a harge at X and at eah hild of X that has an inident ative edge, by Corollary 4.4. One-by-one, we splie these hildren out of the doubly-linked hild list of X . What remains is the list of X 's problem hildren. We may spend O(1) time handling this list, sine there is only one of them at X . These hildren beome hildren of a single node W in MD(G), and we an splie them as a group into the hild list of W in O(1) time. Trik 2: If X is a node of MD GjN (v0) that gets Deleted, and its hildren are onneted omponents of G, or the new parent of its problem hildren in MD(G) is a onneted omponent of G, then we do not need to update expliitly the parent pointers of its problem hildren, by the exeptions we made for Data Struture 4.1. Trik 3: If the union P of the problem hildren is their new parent in MD(G), then the node struture x that formerly represented X may be splied in diretly as the node struture p representing P in the representation of MD(G). The parent pointers on the problem hildren still orretly point to the parent in MD(G), but we do not have to spend any time updating them. Lemma 4.5 The three triks always apply to the problem hildren of any node that is Deleted during the indutive step. Proof: X is a parallel node. The problem hildren are onneted omponents of GjX , and, sine they have no inident ative edges, they are also onneted omponents of G, hene hildren of the root. Triks 1 and 2 sue to splie them into MD(G). X is a series node with several problem hildren. Then the union P of problem hildren beomes the new parent of those same problem hildren in MD(G), sine P is a module of G, and no larger union of hildren of X is a module of G. Trik 3 sues to splie them into MD(G). X is a series node with one problem hild, or X is a prime node. Then GjX is onneted, and X is ontained in a single onneted omponent of GjN (v0 ). In MD(G), every vertex in this omponent has the same least ommon anestor W with RR n3804 14 Elias Dahlhaus, Jens Gustedt, Ross M. MConnell ative edges non-neighbors of v0 v0 neighbors of v0 Figure 4: Splitting the graph aording to a pivot v0 , by Lemma 3.4. The problem hildren of X are maximal subsets of X that remain modules of G. By Algorithm 2, the problem hildren all beome hildren of W , and the rst ondition applies. Trik 1 may be used to splie them into MD(G), but not to update their parent pointers. It remains to show that Trik 2 applies, that is, that the parent pointers of the problem hildren do not need to be updated. Suppose z is a neighbor of W in V n W . It annot be a member of N (v0 ), sine then it would be in the same onneted omponent of N (v0 ) as X , and would be ontained in W , a ontradition. But z annot be a member of N (v0): It is adjaent to every vertex in W , sine W is a module in G, hene it is an ative neighbor of the problem hildren of X , whih, by assumption, have no inident ative edges. Sine W has no neighbors in G, it is either a onneted omponent of G or a union of onneted omponents of G. It annot be a union of onneted omponents of G, sine there edges between some of its hildren, namely between any problem hild of X and any hild of X that is not a problem hild. W is a onneted omponent, hene Trik 2 applies. 4.3 Preproessing Let an ative group of edges be the group of edges that beomes ative when some reursive all is ativated. The ative groups are a partition of the edges. Clearly, we may know the ative groups after Algorithm 4 has run, but we will nd it useful to know them in advane. This requires us to preompute the reursion tree before we atually run Algorithm 4. For this, we run Algorithm 5. See Figure 4 for an illustration. Algorithm 5: ReursionTree(G) if G has no nodes then return nil; else selet v0 using whatever riterion is used in Algorithm 4; r1 = ReursionT ree(GjN (v0 )); r2 = ReursionT ree(GjN (v0 )); make r1 ; r2 be the left and right hildren of v0 , respetively; return v0 Call this tree the reursion tree R. Sine the verties of the tree are verties of G, the least-ommon anestor of an edge of G is well-dened. Two edges are in the same ative group i they have the same least-ommon anestor in the reursion tree. There are simple algorithms for nding the least-ommon INRIA Eient and Pratial Algorithms for Sequential Modular Deomposition 15 anestor in R of eah edge (u; v) of G. One simple approah, see Cormen et al. (1990), ahieves this O(n + m(m; n)), by maintaining a union-nd struture during a traversal of the tree. Moreover, one eah edge is labeled with its least-ommon anestor, we may radix sort all edges with the ative edge group as primary sort key, starting vertex as seondary sort key, and ending vertex as tertiary sort key. This gives, for eah vertex and for eah ative group, a sorted list of neighbors of the vertex that are reahable on an edge in the ative group. This entire preproessing step takes O(n + m(m; n)) time. We may thus assume that a sorted adjaeny list of urrently ative inident edges is available at eah vertex in a all to Algorithm 4. 4.4 The restrit step. We assume by indution that the two reursive alls have returned Data Struture 4.1 for GjN (v0 ) and GjN (v0). We must arry out the two steps of Algorithm 3. The rst step requires us to Delete nodes of MD GjN (v0 ) that are not modules in G. We do this by working indutively up the tree, starting at the leaves that have inident ative edges. As a base ase, leaves are verties of G, and for eah of them, the neighbors in N (v0 ) are given by the sorted lists of ative edges. If the hildren of an internal node X are modules and arry idential ative neighbor lists, mark X as a module, and give X a opy of the ative neighbor list of one of the hildren. Otherwise, mark X for deletion. This proedure marks for deletion exatly those members of MD GjN (v0 ) that are not modules of G and that have inident ative edges. We touh only nodes of the tree that have leaf desendants with inident ative edges. All untouhed nodes are modules of G. Thus, all nodes of the tree that are not modules in G are expliitly Deleted. In the proess, eah node gets a list of its hildren that are deleted, and a list of its hildren that are not deleted and have inident ative edges. The onformity with the harging disipline is immediate, by Lemma 4.3. For the seond step of Algorithm 3, it sues to identify for eah deleted degenerate node those groups of hildren that are not deleted, but that have idential neighbor lists. If Y is a degenerate node, we remove deleted hildren and hildren with inident ative edges from its doubly-linked list of hildren. The remaining list gives those hildren with no inident ative edges. If there is more than one hild in this list, then the union of these hildren is a member U of M(G; v0 ), so we reate a new node representing U , and make this list be its list of hildren. This takes O(1) time, whih we ount as part of touhing Y . We group those undeleted hildren that have nonempty neighbor lists using the radix partitioning proedure (Setion 2.2), on the neighbor lists arried by those hildren, and reate a parent for eah group with more than one hild. This takes time proportional to the number of elements in those neighbor lists, and thus does not aet the time bound of the algorithm. Thus, the number of members of M(G; v0 ) that are the union of hildren of a degenerate node u is at most one plus the number of ative edges inident to the set of verties that u represents. The same annot be said of a prime node. Thus, if a prime node is deleted, we may not individually touh those members of M(G; v0 ) that it ontains and that have no inident ative edges. However, we may touh all other hildren. For any deleted prime node p, we may obtain a doubly-linked list of the hildren with no inident ative edges by removing all other hildren from its doubly-linked list of hildren. Call this doubly-linked list of problem hildren an untouhable list. The restrition of the deomposition to N (v0 ) is found in the same way. The next remark follows from the fat that we get at most one untouhable list for eah deleted node, and the observation that a node is only deleted if it has an inident ative edge. Remark 4.6 At the end of the restrit step, the only verties without urrent parent pointers are members of M(G; v0 ). There are O(1 + m0 ) untouhable lists, and O(1 + m0 ) members of M(G; v0 ) that are not in untouhable lists, where m0 is the number of ative edges. RR n3804 16 4.5 Elias Dahlhaus, Jens Gustedt, Ross M. MConnell The v0 modules step. We dene an equivalene relation on verties of N (v0 ), where for x; y 2 V , xKy if and only if: x and y are ontained in the same onneted omponent of G N (v0) , or their onneted omponents are both ontained in a module of G that is a subset of N (v0 ). Clearly, K is an equivalene relation, so this gives a partition of N (v0 ); let us all the partition lasses the basi bloks of N (v0). The basi bloks of N (v0 ) are omputed in a omplementary way: xKy if and only if: x and y are ontained in the same o-omponent or their o-omponents are both ontained in a module of G that is a subset of N (v0 ), Let B denote the basi bloks of N (v0) and let B0 denote the basi bloks of N (v0 ). The reursive all to N (v0) has omputed the onneted omponents of N (v0 ) as a union-nd struture. The restrit step in the main all has omputed the maximal modules of G that are ontained in N (v0 ). These two strutures give an impliit representation of the basi bloks of N (v0). The basi bloks of N (v0) are dened in a similar way, but it is not neessary to maintain a speial union-nd data struture for them. We have an ative edge to eah vertex in N (v0). If there are more than one basi blok, they are the hildren of the root, and, sine these have inident ative edges from v0 , we may touh and update a blok label for every member of them during the v0 -modules step. To nd strong modules ontaining v0 , we dene a direted bipartite graph F = (B; B0; EF ). For B 2 B and B 0 2 B0 , (B; B 0 ) is an edge of F if and only if there is an edge of G between B and B 0 , and (B 0 ; B ) is an edge of F if and only if there is a non-edge between B and B 0 . We nd the strongly-onneted omponents of F , and the omponent graph, whih has one node for eah strong omponent of F , and edges telling whih whih strongly-onneted omponents are reahable from whih on a single edge of F , see Cormen et al. (1990). Lemma 4.7 There is a unique topologial sort of F . A set ontaining v0 is an anestor of v0 if and only if it is a union of fv0 g and the members of strong omponents in a sux of that sort. Proof: We show that a set X is a strong module ontaining v0 if and only if it is a union of fv0 g and basi bloks, and there is no edge of F from a basi blok X to a basi blok in V n X . Sine the strong modules ontaining v0 are totally ordered by the inlusion relation, this establishes the laim. Observation 4.8 Let X be a set that ontains v0 . Sine v0 is adjaent to every member of N (v0 ) and nonadjaent to every member of N (v0 ), X is a module if and only if every member of X is adjaent to every member of N (v0 ) n X and nonadjaent to every member of N (v0 ) n X . Observation 4.9 Every module ontaining v0 is a union of v0 and zero or more onneted omponents of N (v0 ) and o-omponents of N (v0 ). This follows immediately from Observation 4.8. Observation 4.10 If X is a union of v0 and basi bloks, it is a module if and only if there is no edge of F from a basi blok in X to a basi blok not in X . To see this, note that if X is a union of v0 and basi bloks, then it is also a union of onneted omponents of G N (v0) and o-omponents of G jN (v0) . Every member of N (v0) \ X is nonadjaent to every member of N (v0 ) n X , and every member of N (v0 ) \ X is adjaent to every member of N (v0 ) n X . The observation then follows from Observation 1 and the denition of F . INRIA Eient and Pratial Algorithms for Sequential Modular Deomposition 17 It remains to show that a module X that ontains v0 is a strong only if it is a union of fv0g and zero or more basi bloks, and a weak only if it is not suh a union. Suppose X is not suh a union. By Observation 2 and the denition of basi bloks, X overlaps a maximal module of G that is ontained in N (v0) or N (v0 ), and is therefore not strong. Suppose X is suh a union. Sine all modules not ontaining v0 are ontained in N (v0) or N (v0), they are ontained in basi bloks. Any module Y that overlaps X must ontain v0 . By Lemma 2.1, (X n Y ) [ (Y n X ) is a module that overlaps X , a ontradition, so Y does not exist, and X is strong. For the time bound, note that we may touh eah omponent or o-omponent that has an inident ative edge. We may also touh those that merge with others, sine there are O(n) merges over a run of the algorithm. Co-omponents with no inident ative edges merge with some other o-omponent, so all o-omponents may be touhed. Components that have no inident ative edges annot be touhed, but their union is a module that does not ontain v0, hene they are hidden inside a basi blok, and reside under a single root of the forest produed by the restrit step. Sine this blok is unique in eah of the O(n) inarnations of the reursive algorithm, it may be touhed. F is too large to ompute expliitly, so we work with a mixed representation where the set of neighbors of B is represented in a standard way and the set of neighbors of B0 is represented with its omplement. The number of edges and non-edges given expliitly in this representation is learly bounded by the number of urrently ative edges. Sine eah omponent and o-omponent knows the number of ative edges to other omponents, we may ompute the mixed representation of the foring graph F with a number of Find and onstant-time operations proportional to the number of ative edges. Creating the strong omponents and their topologial sort then follows in time proportional to the size of this mixed representation by Theorem 2. This ompletes the v0-modules step, by Lemma 4.7. 4.6 The assemble step. Lemma 4.11 If X is a hild of an anestor A of v0 in MD(G), and X has no inident ative edges, then either A or X is a onneted omponent of G. Proof: We laim that if M is an anestor of v0 that has a member x with no inident ative edges, then M has no neighbors in V n M . This is obvious if M = V . Suppose M 6= V . All verties of N (v0 ) have ative edges to v0 . Thus, M must interset N (v0 ), and all verties of M without ative edges reside in N (v0). If N (v0 ) n M is nonempty, let y be a member of N (v0 ) n M . Sine y is adjaent to v0 , it is adjaent to every member of M \ N (v0) via ative edges, a ontradition. So N (v0) is a subset of M . There is no edge from v0 to N (v0 ), and sine v0 2 M and M is a module, there is no edge from M to N (v0 ) n M . Sine M ontains v0 and N (v0 ), N (v0 ) n M = V n M , proving the laim. Thus, A must have no neighbors in V n A. If A = 6 V , A is a onneted omponent, and the lemma is satised. If A = V and G is onneted, then it is one again satised. Otherwise, A is a parallel node, and X is a onneted omponent, and, again, the lemma is satised. The v0-modules step gives for eah basi blok B the smallest anestor AB of v0 that ontains it. B is a union of a set X of members of M(G; v0 ), eah of whih appears as the root of a tree in the forest produed by the restrit step. To implement Algorithm 2 without its inner if -statement, we must establish the members of X as hildren of AB . If X has only one member, then this member is B , and we simply attah it as a hild of AB in O(1) time. Otherwise, the blok ontaining X 2 X is just the onneted omponent of GjN (v0 ) or the o-omponent of N (v0) that ontains it. If X has an inident ative edge, then by Data Struture 4.1, we an perform a Find operation to nd its blok, and the minimum anestor of v0 that ontains the blok gives the parent in O(1) time. We then establish X as a hild of this anestor, omplete with an updated parent pointer, in O(1) time. The remainder of members of M(G; v0 ) reside in untouhable lists. Sine eah untouhable list resides in RR n3804 18 Elias Dahlhaus, Jens Gustedt, Ross M. MConnell one onneted omponent of GjN (v0), we perform a single find for eah untouhable list to nd its basi blok. This identies the single basi blok that ontains them. If the list only has one member, we add it as a hild of the parent, omplete with a parent pointer. Otherwise, we splie the untouhable list into its parent's hild list in O(1) time. We needn't update the parent pointers of the elements of the untouhable list, sine, by Lemma 4.11, the parent is the onneted omponent of G that ontains them, and no parent pointer is required under Data Struture 4.1. Next, we need to simulate the eet of the inner if -statement of Algorithm 2. We may spend O(1) time at eah anestor of v0 , sine these were reated during the indutive step. If X is a parallel anestor of v0 with at least three hildren, and Y is its hild that ontains v0, then the union of all siblings of Y is a single member Z of M(G; v0 ). Thus, in the urrent tree, X will have two hildren, Y and Z . We must delete Z from the tree, and let X inherit its hildren. If X = V , we just splie Z 's doubly-linked list of hildren into those of X 's. The hildren of X are onneted omponents of G, so Data Struture 4.1 does not require parent pointers. Otherwise, by Lemma 4.11, eah hild of X in MD(G) has an inident ative edge, so we may touh eah of them, and make the parent pointer point to X . The proedure when X is a series node is similar. To omplete Data Struture 4.1 for MD(G), we must also produe the union-nd strutures for G. The reursive alls return union-nd strutures that give the onneted omponents and o-omponents of GjN (v0 ) and GjN (v0 ). Sine fv0 g [ N (v0) is a onneted omponent, and all ative edges are inident to it, we must do a union on all omponents of GjN (v0) and GjN (v0) that have inident ative edges. Identifying these omponents requires a find on the end verties of eah ative edge. No other omponents are aeted. For the o-omponents, symmetri reasoning shows that all oomponents of fv0 g [ N (v0 ) must be subsets of a single o-omponent. A o-omponent C of GjN (v0 ) must be merged together with this set if the number of inident ative edges that go to N (v0 ) is less than jN (v0) j. 5 Obtaining a Linear Time Bound The only bottlenek preventing a linear time bound that remains is the (m; n) term. We will show how to irumvent this fator by some preproessing on the reursion tree. One plae where we inurred the term was in nding the least-ommon anestors of edges in the reursion tree. This an be eliminated here by using the o-line least-ommon anestors algorithm of Harel and Tarjan (1984). The other plae was in making the onneted omponents of the indued subgraph passed to a reursive all available in that all. These omponents are represented with a union-nd struture in the tree data struture in Lemma 4.2. We solve this problem by restriting the possible hoies for the reursion tree, so that the union-nd strutures an be managed without inurring the (m; n) fator. When running Algorithm 5 on vertex set X , let us number the verties that have already been seleted as the initial pivot in prior alls, in the order in whih they were seleted. This numbering onstitutes a preorder numbering of the portion of the reursion tree already omputed. No vertex in X has yet been numbered. Let the reeny of a vertex x in X be the maximum of the preorder numbers among neighbors of x that have already been numbered. If x has no suh neighbor, its reeny is dened to be -1. Our modiation to Algorithm 5 is to selet v0 to be the vertex with greatest reeny, rather than seleting it arbitrarily. Algorithm 6 gives the algorithm for omputing a reursion tree R satisfying this onstraint. The orretness follows from the following points, whih are trivial to establish by indution on the number of verties already seleted: 1. There is one doubly-linked list for eah reursive all that has not yet been initiated, but whose parent has already been initiated, and this list gives the set of verties that will be passed to the all. INRIA Eient and Pratial Algorithms for Sequential Modular Deomposition 19 Algorithm 6: Input: A doubly-linked list L representing subset X of verties of G, ordered by their reeny. Eah member of L arries a label that identies it as a member of L Output: a reursion tree R. Remove the rst vertex v0 from L; Create an empty list L1 that will hold the neighbors of v0; foreah y 2 N (v0 ) do if y has not been seleted then if y is a member of L then remove y from L, put it into L1, and label it aordingly else move y to the front of the list L0 that urrently ontains it Let R1 be the tree obtained by reursion on L1; // The all to R1 may have modied the order of verties in L; Let R2 be the tree obtained by reursion on L; Make R1 and R2 hildren of v0; return v0 . 2. The order of eah linked list is desending in order of reeny. Together, these two invariants imply that the vertex v0 seleted as the initial pivot when a all is initiated has greatest reeny among those verties passed to the reursive all. Lemma 5.1 Algorithm 6 runs in linear time. Proof: All doubly-linked list operations take O(1) time, and an be harged to an edge of v0 . Aside from the time required by the reursive alls it generates, the all requires O(1 + N (v0 )) time. This gives an O(n + m) bound for all reursive alls, sine eah vertex of G has the role of v0 in only one all. Let Vv denote the subset of verties that are leaf desendants of that node, inluding v itself. The reursion tree R has an important property with respet to the onnetivity struture of G: Lemma 5.2 Let v 2 V be a vertex and C a onneted omponent of GjVv . Then there is exists w 2 C that is anestor to all other members of C in R. Proof: We proeed by indution from the bottom of R to the top. If v 2 C , the laim is learly satised by v. Otherwise, C N (v), C is a onneted omponent of N (v), and N (v) is the set of nodes in Tx, where x is one of the two hildren of v. By the indutive hypothesis, applied to Tx, the laim holds for C . Denition 5.3 Let S be a tree dened on the vertex set V and R a reursion tree. We say that S is oherent with R and G if for every v 2 V and every onneted omponent C of GjVv the restrition S jC is onneted. Observe that R is not neessarily oherent to itself. If we are able to ompute suh a oherent tree, it fullls the neessary onditions to apply Theorem 1, and thus to perform all union-nd operations in amortized linear time. Thus, the problem of eliminating the fator redues to omputing a oherent tree for R and G. There are many trees on G that are oherent with a given R. We will ompute a unique one that is dened as follows. RR n3804 20 Elias Dahlhaus, Jens Gustedt, Ross M. MConnell Denition 5.4 Let R be the reursion tree of graph and v 2 V . We say that v is subordinate to some other vertex w 2 V i w is an anestor of v in R v and w are joined by a path in GjVw . For eah v 2 V that is not the root of R there is a unique minimal w 2 V suh that v is subordinate to w. We all this unique node w the boss of v. The boss relation is the parent relation in a tree S on V , whih we all the subordinate tree of R. Lemma 5.5 The subordinate tree S is oherent with R. Proof: We proeed by indution from the bottom of R to the top. Let v be some vertex of G and C a onneted omponent of GjVv and assume that the laim is given for all Vw for w 2 Vv , w 6= v. We have to show that S jC is onneted. Let y0 2 C be the vertex in C with earliest preorder number. By Lemma 5.2, y0 is an anestor of the other members of C . If y0 = 6 v the indution hypothesis shows the laim. So suppose now that y0 = v. Set G0 to be the graph that is obtained by removing v and all edges that are ative at v from GjC . G0 might not be onneted. Let C1 ; : : : ; Ck be the new omponents. Eah Ci is ompletely ontained in either N (v) or N (v). By Lemma 5.2, Ci has a vertex yi that is an anestor of all other members of Ci. Ci is a onneted omponent in GjVy . Thus, by the indution hypothesis we may assume that S jCi is onneted. By denition yi is below v in R, and yi and v are joined by a path in C and thus in GjVv . So yi is subordinate to v. We show that v is, in fat, the boss of yi. Suppose this is not the ase. Then there must be some vertex w that is a desendant of yi and an anestor of v to whih yi is subordinate. But then w 2 Ci and yi is not the highest node in Ci, a ontradition. So in S , all verties yi are diret hildren of v, and v is onneting all the S jCi. i Algorithm 7: Compute a reursion tree R and its subordinate tree for a onneted graph G. Let R be a reursion tree omputed with Algorithm 6; Label eah edge (x; y) of G with the least-ommon anestor la(x; y) in R; foreah vertex v of G do Let S be the neighbors of v with earlier preorder number than v; Assign b = maxfla(v; s) : s 2 S g as boss of v; Lemma 5.6 Algorithm 7 is orret. Proof: If a and b are two verties, we say that a < b if the preorder number of a is less than that of b. Let u be an arbitrary vertex. Suppose the algorithm assigns no boss to u. Then u has no neighbor x suh that x < u. It follows that u is not in the left subtree of any anestor a of u, sine then it has a < u as a neighbor. Thus, every vertex of G is either a desendant of u or has earlier preorder number than u. If a desendant d of u is a neighbor of < u, then d would have been seleted before u, a ontradition. The verties that are desendants of u are a union of one or more onneted omponents of G. Sine G is assumed to be onneted, u must be the root, so failure of the algorithm to assign a boss to it is orret. Let us now assume that w is the boss of u and b is the vertex the algorithm assigns as the boss of w. We must show b = w. It sues to show that b w and b w. To show b w, we let (u; x) be any edge from u to a vertex with lower preorder number than u. If y = la(u; x) > w then u or x is in the left subtree of y, and a neighbor of y. Either (y; u) or (y; x; u) INRIA Eient and Pratial Algorithms for Sequential Modular Deomposition 21 is a path, and y supersedes w status as boss of u, a ontradition. Thus, y w, and, sine b is suh a y , b w. We now show that w b. If u is a neighbor of w, la(u; w) = w, establishing that w b. If u is not a neighbor of w, u is in w's right subtree. Let P be a path in Tw from w to u. Sine w is the boss of u, P must exist. The seond vertex of P is in w's left subtree, sine it is a neighbor of w. Let be the last vertex of P that is not a member Tu , and let d be its suessor on the path. Sine u was seleted before d, u has a neighbor z suh that z < u. This establishes that z is in Tw , and w la(w; z ) b. We have already shown that the rst step of Algorithm 7 is linear. We use the least-ommon anestors algorithm of Harel and Tarjan (1984) to ompute the least ommon anestors of the edges in R. One this is aomplished, eah vertex x may be labeled with its boss in O(jN (x)j) time, whih gives an O(n + m) bound for omputing the subordinate tree. This onludes the proof of the linear time bound of the modular deomposition algorithm on onneted graphs. If G is not onneted, its onneted omponents an be found in linear time, and the modular deomposition algorithm applied to eah omponent. Making the resulting trees hildren of a parallel node ompletes the modular deomposition of G. As desribed, the algorithm to ompute R and S requires two passes, rst to run Algorithm 6, and then to use Harel and Tarjan to nd the least-ommon anestor of eah edge in the resulting tree, and nally, to use the least-ommon anestors of the edges to ompute S . The least-ommon anestors of the edges are also required by the modular deomposition algorithm, to organize the edges into groups that are ative at the same time. Algorithm 6 an be modied to produe all of this information in a single pass. The modied version is given as Algorithm 8. Algorithm 8: Input: A doubly-linked list L representing a set X of verties of G that are passed to a reursive all, ordered by their reeny. Eah member of L arries a label that identies it as a member of L, and L is labeled with a generator, whih is the initial pivot in the parent of the reursive all that it represents. Output: A parent labeling giving a reursion tree R, a labeling of eah edge with its least ommon anestor in R, and a boss labeling giving a tree S that is oherent with R and G Remove the rst vertex v0 from the front of L; Create an empty list L1 that will hold the neighbors of v0; Assign v0 as the generator of L1 and of L; foreah y 2 N (v0 ) do if y has not been seleted then if y is a member of L then remove y from L; put y into L1 and relabel it as a member of L1 ; provisionally assign v0 as the boss of y; assign v0 as the least-ommon anestor of (v0 ; y) else move y to the front of the list L0 that urrently ontains it; provisionally assign the generator of L0 as the boss of y; assign the generator of L0 as the least-ommon anestor of (v0 ; y) Let R1 be the tree obtained by reursion on L1; // The all to R1 may have modied the order of verties in L; Let R2 be the tree obtained by reursion on what remains of L; Make R1 and R2 hildren of v0; return v0 . RR n3804 22 Elias Dahlhaus, Jens Gustedt, Ross M. MConnell Lemma 5.7 Algorithm 8 is orret. Proof: The reursion tree returned is the same as the one returned by Algorithm 6. Eah vertex is hosen as the initial pivot v0 in some reursive all. Let (x; y) be an arbitrary edge, and let u be its least-ommon anestor. Assume without loss of generality that x is hosen before y. It must be that x 2 N (u) and y 2 N (u). Let L and L1 be the lists with those names in the reursive all where u is the initial pivot. Then x is moved to L1, y remains in L, and u is the generator of L. L is not touhed between the time when the reursive all on L1 is generated and when it ompletes. During this time, x is seleted as the initial pivot v0 in some lower reursive all. At this time, the generator of L, whih is u, is orretly assigned as the least-ommon anestor of (x; y). When y is seleted later, there is no reassignment of a least-ommon anestor to (x; y); sine x has already been seleted, the edge is ignored. We onlude that eah edge gets assigned its orret least-ommon anestor. The boss of y is the maximum preorder number of the least-ommon anestors of the set f(x; y) : (x; y) is an edge of G and x has earlier preorder number than yg. By the foregoing, these are the edges inident to y whose least-ommon anestor has already been assigned when y is seleted. Eah time suh an edge was assigned a least-ommon anestor u, y was given u as its boss. The preorder number of the generators of the lists ontaining y are inreasing as the algorithm proeeds, so the last boss label assigned to y is the one with largest preorder number, as desired. No boss is subsequently assigned to y, sine it has already been seleted. Referenes [Buer and Möhring, 1983℄ Buer, B. and Möhring, R. H. (1983). A fast algorithm for the deomposition of graphs and posets. Mathematis of Operations Researh, 8:170184. [Cormen et al., 1990℄ Cormen, T. H., Leiserson, C. E., and Rivest, R. L. (1990). Cambridge, Massahusetts. . MIT Press, Algorithms [Corneil et al., 1985℄ Corneil, D. G., Perl, Y., and Stewart, L. K. (1985). A linear reognition algorithm for ographs. SIAM J. Comput., 3:926934. [Cournier and Habib, 1993℄ Cournier, A. and Habib, M. (1993). An eient algorithm to reognize prime undireted graphs. In Mayr, E. W., editor, Graph-theoreti onepts in omputer siene, 18th international workshop, WG '92, volume 657 of Leture Notes in Computer Siene, pages 114122. Springer Verlag. [Cournier and Habib, 1994℄ Cournier, A. and Habib, M. (1994). A new linear algorithm for modular deomposition. In Tison, S., editor, Trees in Algebra and Programming, CAAP '94, 19th International Colloquium, volume 787 of Leture Notes in Computer Siene, pages 6882. Springer Verlag, Edinburgh, UK. [Dahlhaus, 1995℄ Dahlhaus, E. (1995). Eient parallel modular deomposition. Theoreti Conepts in Comp. Si. (WG 95), 21. 21st Int'l Workshop on Graph [Dahlhaus et al., 1997℄ Dahlhaus, E., Gustedt, J., and MConnell, R. M. (1997). Eient and pratial modular deomposition. Proeedings of the eighth annual ACM-SIAM symposium on disrete algorithms, 8:2635. [Ehrenfeuht et al., 1994℄ Ehrenfeuht, A., Gabow, H. N., MConnell, R. M., and Sullivan, S. J. (1994). An O(n2 ) divide-and-onquer algorithm for the prime tree deomposition of two-strutures and modular deomposition of graphs. Journal of Algorithms, 16:283294. [Ehrenfeuht and Rozenberg, 1990℄ Ehrenfeuht, A. and Rozenberg, G. (1990). Theory of 2-strutures, part 1: Clans, basi sublasses, and morphisms. Theoretial Computer Siene, 70:277303. [Gabow and Tarjan, 1985℄ Gabow, H. N. and Tarjan, R. E. (1985). A linear-time algorithm for a speial ase of disjoint set union. Journal of Computer and System Sienes, 30:209221. [Golumbi, 1977℄ Golumbi, M. C. (1977). The omplexity of omparability graph reognition and oloring. Combin. Theory Ser. B, 22:6890. J. [Gustedt, 1998℄ Gustedt, J. (1998). Eient union-nd for planar graphs and other sparse graph lasses. Theoret. Comput. Si., 203(1):123141. INRIA 23 Eient and Pratial Algorithms for Sequential Modular Deomposition [Habib and Maurer, 1979℄ Habib, M. and Maurer, M. C. (1979). On the X-join deomposition for undireted graphs. Disrete Applied Mathematis, 1:201207. [Harel and Tarjan, 1984℄ Harel, D. and Tarjan, R. (1984). Fast algorithms for nding nearest ommon anestors. SIAM Journal on Computing, 13:338355. [MConnell, 1995℄ MConnell, R. M. (1995). An O(n2 ) inremental algorithm for modular deomposition of graphs and 2-strutures. Algorithmia, 14:229248. [MConnell and Spinrad, 1994℄ MConnell, R. M. and Spinrad, J. P. (1994). Linear-time modular deomposition and eient transitive orientation of omparability graphs. Proeedings of the Fifth Annual ACM-SIAM Symposium on Disrete Algorithms, 5:536545. [MConnell and Spinrad, 1998℄ MConnell, R. M. and Spinrad, J. P. (1998). Ordered vertex partitioning. submitted. [MConnell and Spinrad, 1999℄ MConnell, R. M. and Spinrad, J. P. (1999). Modular deomposition and transitive orientation. Disrete Mathematis, 201(1-3):189241. [Möhring, 1985℄ Möhring, R. H. (1985). Algorithmi aspets of the substitution deomposition in optimization over relations, set systems and boolean funtions. Annals of Operations Researh, 4:195225. [Muller and Spinrad, 1989℄ Muller, J. H. and Spinrad, J. P. (1989). Inremental modular deomposition. nal of the ACM, 36:119. [Spinrad, 1992℄ Spinrad, J. P. (1992). 39:263291. [Steiner, 1982℄ Steiner, G. (1982). Waterloo, Waterloo, Ont. P4 trees and substitution deomposition. Jour- , Disrete applied mathematis . PhD thesis, University of Mahine sheduling with preedene onstraints [Tarjan, 1983℄ Tarjan, R. E. (1983). Math., Philadelphia. . Soiety for Industrial and Applied Data strutures and network algorithms [Valdes et al., 1982℄ Valdes, J., Tarjan, R. E., , and Lawler, E. L. (1982). The reognition of series-parallel digraphs. Siam J. Comput., 11:299313. RR n3804 Unité de recherche INRIA Lorraine, Technopôle de Nancy-Brabois, Campus scientifique, 615 rue du Jardin Botanique, BP 101, 54600 VILLERS LÈS NANCY Unité de recherche INRIA Rennes, Irisa, Campus universitaire de Beaulieu, 35042 RENNES Cedex Unité de recherche INRIA Rhône-Alpes, 655, avenue de l’Europe, 38330 MONTBONNOT ST MARTIN Unité de recherche INRIA Rocquencourt, Domaine de Voluceau, Rocquencourt, BP 105, 78153 LE CHESNAY Cedex Unité de recherche INRIA Sophia-Antipolis, 2004 route des Lucioles, BP 93, 06902 SOPHIA-ANTIPOLIS Cedex Éditeur INRIA, Domaine de Voluceau, Rocquencourt, BP 105, 78153 LE CHESNAY Cedex (France) http://www.inria.fr ISSN 0249-6399

1/--страниц