close

Вход

Забыли?

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

Очная форма обучения;pdf

код для вставкиСкачать
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/--страниц
Пожаловаться на содержимое документа