Partially Complemented Representations of Digraphs

153

By restricting the definition of a module to an undirected graph, we see that a module M is a set such that

for each vertex v

∈

(

)

M, M is either contained in v’s neighborhood or disjoint from v’s neighborhood.

Trivial examples of modules are V

(

)

, the singleton sets

{{

} |

∈

(

)

}

, and the empty set. A union

of connected components of G or of G is also an example of a module. However, G may have nontrivial
modules even when G and G are connected. The set of vertices numbered 1 to 6 in Figure It is easy to see that if M

and M

are disjoint modules, then either every member of M

is an arc or

none is. Thus, two disjoint modules are either adjacent or nonadjacent. It follows that if there is a partition

of V

(

)

into disjoint modules, the quotient G

uniquely specifies all arcs that connect members of

different partition classes. We will call such a partition and its quotient modular. The subgraph induced
in G by one of these modules is called a factor. Since G can be reconstructed uniquely from the factors
and the quotient, this gives a decomposition of G.

If G is disconnected and each element of

is a union of connected components, then

is a modular

partition, and G

is empty. Clearly, P

∈

is a single connected component iff there is no refinement

of P such that G

((

\ {

}

)

∪

)

is empty. If each member of

is a single connected component, then

is a parallel decomposition of G.
Similarly, if G is disconnected, and each member of

is a union of co-components, then G

complete. P

∈

is a single co-component iff there is no refinement

of P such that G

((

\ {

}

)

∪

)

is complete. If each member of

is a single co-component, then

is a serial decomposition of G.

In the case of digraphs, there is a third type of decomposition with analogous properties. A modular

partition

is linear if G

is a linear order. That is, there are arcs between each pair of partition classes,

but G

has no cycle. By analogy with the parallel and serial decomposition, let us say that P

∈

is a

linear component if there is no partition

of P such that G

((

\ {

}

)

∪

)

is linear. If each member

is a linear component, then

is a linear decomposition of G.

Because of their restricted structures, parallel, series, and linear nodes are known as degenerate nodes.

It is easily verified that a digraph admits at most one of these three decompositions, but it may also not
admit any of the three. The smallest examples of such digraphs have as few as three vertices. The digraph

−→

is such an example. The smallest example of an undirected graph that is not decomposable by any of these
two operations is P

, an undirected path on 4 vertices.

However, in such a case, the maximal modules that are proper subsets of G are a partition

of G, and

has only trivial modules. In this case,

is a prime decomposition of G.

Thus, G is uniquely decomposable with a parallel, series, linear, or prime decomposition. Applying this

idea recursively to the factors gives a unique hierarchical decomposition of G that implicitly represents all
modules of G. This is summarized by the structure produced by Algorithm Theorem 4 ⊆

is a module of G

X iff it is a module of G. If

is a modular partition of V

(

)

, then the inverse image of

⊆

is a module of G iff

is a module of G

The following is easily established using Theorem

154

Elias Dahlhaus and Jens Gustedt and Ross M. McConnell

Algorithm 1: MD(G)

if G has only one vertex then return v;
else

create a tree node r;
if G has more than one connected component then

let

be the connected components;

let r be labeled a parallel node

else if G has more than one connected component then

let

be the connected components of G;

let r be labeled a series node

else if G is linearly decomposable then

let

be the linear components;

let r be labeled a linear node

else

Let

be the maximal modules of G;

Let r be labeled a prime node

for each X

∈

Let r

(

)

;

add r

as a child of r

return r

Theorem 5 1. A node of the decomposition tree;

2. A union of children of a parallel or series node;

3. The union of a subset of the set

of children of a linear node X that are consecutive in the linear

order given by

(

)

We may think of r as synonymous with V

(

)

; applying this idea recursively, we see that the nodes of

the tree can be thought of as a tree-like hierarchy of subsets of V

(

)

, where each node is just the subset

of V

(

)

that make up its leaf descendants.

Properties of outward, inward, and two-way equivalence classes

Let G

= (

)

be a digraph. For any v

∈

V the minimum outdegree of v, mindeg

(

)

, is min

{

deg

(

)

(

)

−

deg

(

)

}

. The minimum outdegree, mindeg

(

)

, of G itself is n plus the sum of these values over all

the vertices. It is an important invariant of the outward equivalence class of G.

Remark 3.1 Let G

= (

)

be a digraph then mindeg

(

)

is the minimum size of a digraph F that is

outward equivalent to G. If

is even, F is unique.

Partially Complemented Representations of Digraphs

155

Proof: Just observe that flipping the out-list of some vertex v doesn’t affect the way we represent the out-
neighbors of any other vertex. Thus the minimal representation is that one where we flip the interpretation
if the size of the list is greater than

(

)

−

)

Remark 3.2 A minimum-size member of the outward equivalence class of a digraph G can be computed
in O

(

) +

(

))

time, by outwardly complementing any node of G whose outdegree exceeds

(

)

−

)

We call these representations partially complemented representations, and call G the base graph of the

representation.

Theorem 6 For any digraph G, G is in G’s outward class.

Proof: Immediate, since G is obtained from G by either complementing the list of outgoing arcs of each
vertex, or by complementing the list of incoming arcs of each vertex.

Theorem 7 Let G be a digraph, let F be a member of G’s outward equivalence class, and let X

⊆

(

)

Then F

X is in the outward equivalence class of G

X .

Proof:

Some subset of vertices of X are complemented in G to obtain F. Complementing these same

vertices in G

X obviously yields F

X .

Theorem 8 A digraph F is in the outward equivalence class of a digraph G if and only if F

is in the

inward equivalence class of G

Proof: Outwardly complementing a set of vertices of G and then taking the transpose of the result yields
the same result as taking the transpose of G and then inwardly complementing the same set of vertices.

Determining whether a member of

’s outward class is undi-

rected

In this section we illustrate the use of a classification of the vertices according to whether or not their
adjacency lists are complemented.

Let G be a digraph, and let F be a member of G’s outward equivalence class. Let V

be the set of

vertices of G that must be outwardly complemented to obtain F, and let V

be the remaining vertices of

G. Let G

be the digraph with V

(

) =

(

)

and

(

) =

(

)

∩

(

)

∪

(

)

(3)

That is, let G

give the arcs of G that go back and forth between V

and V

. In Figure V

{

}

and V

{

, . . . ,

}

Remark 4.1 F is undirected iff G

and G

are symmetric, and G

is antisymmetric. This fact can

be checked in O

(

) +

(

))

time.

156

Elias Dahlhaus and Jens Gustedt and Ross M. McConnell

Proof:

The ‘iff’ claim is immediate. For the time complexity it is easy to see that the three digraphs

, G

, and G

can be easily computed within the bound.

Given the adjacency-list representation for a digraph, we may determine whether it is symmetric in lin-

ear time as follows. For each arc

(

)

, create a record for

(

)

and a record for its transpose

(

)

. Radix

sort the resulting records using vertex of origin as primary sort key and destination vertex as secondary
sort key. This requires two passes, one for each sort key, and O

(

) +

(

))

time per pass. The graph

is undirected iff for every ordered pair

(

)

of vertices that occurs in the list occurs twice. This can be

determined in O

(

) +

(

))

time by traversing the sorted list of records.

To find out whether G

is antisymmetric, follow a similar procedure, but verify that each ordered pair

that occurs in the sorted list of records occurs only once.

Breadth-first search

Let us examine the running time of breadth-first search on a member F of G’s outward class. As in the
standard algorithm, divide V

(

)

into undiscovered nodes, queued nodes, and processed nodes. Initially

all nodes but the start node are undiscovered, and the start node is inserted to a queue. To process a node,
remove it from the front of the queue, and insert any undiscovered neighbors to the back of the queue,
marking them as discovered. Keep the undiscovered nodes in a doubly-linked list. This list will in fact
allow us to amortize the cost of processing complemented vertices.

To process an uncomplemented node, proceed as in the standard case. When processing a complemen-

ted node v, mark the members of N

(

) =

(

)

. Then traverse the list of undiscovered nodes, splicing

out any unmarked nodes and inserting them on the queue. We then remove the marks from N

(

)

Marking and unmarking nodes can be charged to the arcs of G that are responsible for applying the

marks. Touching an unmarked node can happen at most once per node, since the node is removed from
the list of undiscovered nodes whenever this happens. This gives the O

(

) +

(

))

bound.

Depth-first search

A depth-first visit at v visits all vertices reachable on a directed path from a starting vertex v, in a depth-first
order. In the special case of an undirected graph, these is just the vertices in v’s connected component.
This generates a depth-first tree which may not contain all vertices of G, since some vertices may not
be reachable from v. A depth-first search iteratively calls depth-first visits on unvisited vertices until all
vertices have been visited. When a depth-first visit finishes, the choice of next unvisited vertex is arbitrary.

The vertex sets of the trees are a partition of the vertices of G. The postorder numbering on the nodes

of a tree is a linear order on them, which can be expressed with an ordered list. The preorder numbering
can be represented similarly. Ordering the postorder lists in the order in which their trees were produced
and then concatenating them in this order gives a total order on vertices of G, called the finishing times,
which can be used in the solution of other problems on the graph. Similarly, ordering the preorder lists
in the order in which their trees were produced and then concatenating them gives a total order called the
discovery times.

Rather than performing depth-first search in the standard recursive fashion, we use an explicit stack to

maintain information relevant to the recursion stack. To be able to do this on any member of G’s outward
equivalence class, we must modify the basic operations that are supported by the stack.

Partially Complemented Representations of Digraphs

157

One way to implement this (for a standard graph) is by using a stack of vertices, where each popped

vertex is labeled with a push time that tells when it was last pushed. The time clock is a counter that is
periodically incremented. To select a vertex x to visit, pop it from S, and record the current time as its
discovery time. Look up the vertex y whose discovery time is x’s push time; if y exists, it is the parent of x
in the depth-first forest. Then push copies of all unvisited neighbors on S, deleting any lower occurrences
of them in S if they already reside on the stack. The lower occurrences may be deleted, because the
existence of a higher instance of a vertex guarantees that it will be visited before the lower instance is
popped. When these nodes are pushed, make the current time their push time. Then increment the time
clock by one unit.

To apply this technique for depth-first search on a a member of G’s outward equivalence class, we have

to ensure that we implement the push operation for complemented vertices efficiently. We use a data
structure, complement stack, which generalizes a stack.

6.1

Complement stacks

The complement stack is a data structure for managing members of V

(

)

. It can hold at most one copy of

any element. Let X be a set and V

(

)

X be its complement. One of the operations the complement stack

supports is purging the stack of any occurrences of members of V

(

)

X , and then pushing V

(

)

X to

the top of the stack. The amortized timed bound for this operation is O

(

)

, not O

(

)

Definition 6.1 A complement stack is a data structure that supports the following operations:

Initstack

(

)

initializes and returns an empty stack S that can hold elements of V .

Push

(

)

removes any occurrences of members of X from S, then pushes the mem-

bers of X to the top of S.

Cpush

(

)

performs

Push

(

)

Eliminate

(

)

Removes x from the universe V that applies in future calls to

Cpush

on S. If x is on S, it deletes it from S.

Pop

(

)

returns the top element of S.

Time

(

)

returns a timestamp that tells when the top element of S was pushed with a

Push

Cpush

operation.

Theorem 9 Complement stacks can be implemented in such a way that:

•

Initstack

requires O

(

)

time.

•

Push

(

)

requires O

(

)

time.

•

Cpush

(

)

requires O

(

)

time, amortized.

•

Eliminate

(

)

requires O

(

)

time.

•

Pop

and

Time

require O

(

)

time each.

158

Elias Dahlhaus and Jens Gustedt and Ross M. McConnell

Proof: If an element x is on the stack, then it has been pushed, and possibly repushed, by a sequence of
one or more calls to

Push

and

Cpush

that caused x to go to the top of the stack. If the last of these is

Cpush

, we say that x was last pushed by

Cpush

; otherwise, we say it was last pushed by

Push

. The

most recent call to

Cpush

is the most recent one of all those calls to

Cpush

that have occurred on the

stack, not just the most recent of those that moved x to the top of the stack.

Let L be the members of V that are not on the stack. We implement the stack by simulating it with

smaller stacks, as follows. A, T , B are doubly-linked lists that partition the members of the stack. A is a
stack of elements that were last pushed by a call to

Push

. T and B may be thought of as the “top” and

“bottom” of a separate stack, which holds those elements that were last pushed by a call to

Cpush

. T

holds those elements that were pushed by the most recent call to

Cpush

. B holds those elements that

were last pushed by an earlier call to

Cpush

, in the reverse order in which they were pushed.

Each element of V keeps track of which of L, A, T , B contains it. If A or B contains it, it carries a

timestamp that holds the time when the element was last pushed. To keep time, a global integer variable
is incremented after each call to

Pop

Push

, or

Cpush

For the elements in T we will not be able to maintain an individual timestamp when they have been

pushed into T . Instead, we maintain a common timestamp for all of T since these elements have all been
pushed by the same call to

Cpush

. If an element residing in T is popped, we label it with T ’s timestamp

at that time.

We maintain a credit invariant:

Each member of L, A, B carries a credit.

•

Initstack

(

)

creates a doubly-linked list L of the elements of V and assigns a credit to each of

them. It creates empty doubly-linked lists A, T , B.

•

Push

(

)

traverses each member of X , and if it is currently a member of V , it splices it from the

list in

{

}

that it currently resides in, pushes it to the front of A together with a timestamp,

and assigns a credit to it. This is clearly O

(

)

•

Cpush

(

)

must incur only O

(

)

amortized cost. It marks and adds one credit to each member

of X . It traverses X , removing those members of X

∩

T to auxiliary list T

. It then traverses L, A,

and B, moving unmarked members to T , and pays for visiting their members by using up a credit
at each. This still leaves credits on elements that remain in L, A, or B, since they are members of X
and have just received an extra credit from X . It then assigns each member of T

a credit and labels

it with T ’s timestamp and moves it to the front of B. If T is now nonempty, T is assigned a new
timestamp, which is interpreted as the collective timestamp of all members of T , and which serves
as a record of the push time of any member of T that gets popped.

This requires O

(

)

amortized time, since all operations are O

(

)

except for traversing L, A, B,

which is paid for by using a credit sitting on each visited item.

•

Eliminate

(

)

removes x from the member of

{

}

that contains it. This takes O

(

)

time.

•

Pop

looks at the timestamps of the top elements of T , B and A. It chooses the most recently pushed

element x, pops it from the appropriate list, and returns it.

Partially Complemented Representations of Digraphs

159

The time bound is observed, since each operation maintains the credit invariant, and

Cpush

pays for

its operations either with its budget of

new credits or with other credits it frees up from the structure.

Corollary 6.2 Computing a depth-first forest of a member of G’s outward equivalence class takes O

(

))

time.

Proof:

By calling

Eliminate

on each node when it is visited, we maintain the invariant that the

universe V that applies to the stack operations is the set of unvisited vertices. A vertex x is visited when
it is first popped. The time of this pop is the discovery time of x, and the parent of x is the vertex whose
discovery time is the the time of x’s last push, minus one. Since the push times and discovery times range
from 0 to 2n, the vertices may be indexed by discovery time, allowing the push times of the vertices to
serve as parent pointers in the depth-first forest. To complete the visit of x, push its unvisited neighbors
with a call to

Push

if it is uncomplemented, or push its unvisited non-neighbors with a call to

Cpush

if it is complemented. This takes O

(

)

time, whether or not x is complemented. The corollary

follows from the fact that each vertex is visited exactly once.

6.2

Set-complement stacks

We wish to compute the strongly-connected components of a graph F that is in the same outward equiva-
lence class as G in O

(

) +

(

))

time. To do this, it will be useful to find a depth-first forest of F

(

) +

(

))

time. For this, we need a generalized version these stacks.

Let V

, . . .

be a partition of a set V . A set-complement stack implements the complement-stack

operations, but with the following changes:

Initstack

(

, . . .

)

Initializes and returns an empty stack S.

Cpush

(

)

performs

Push

(

)

Eliminate

(

)

removes x from the set V

that contains it, and deletes x from S if x is currently on S.

Theorem 10 Set-complement stacks can be implemented in such a way that:

•

Initstack

requires O

(

)

time.

•

Push

(

)

requires O

(

)

time.

•

Cpush

(

)

requires O

(

)

time, amortized.

•

Eliminate

(

)

requires O

(

)

time.

•

Pop

and

Time

each require O

(

)

time, amortized.

Proof:

In any implementation, a

Push

Cpush

operation conceptually inserts a set of elements that

occupy an interval I at the top of S. After subsequent pushes, I is no longer at the top of S. Eventually,
a set of pop operations may pop everything above I and then pop everything in I. At this point, we may
think of I has having been popped.

160

Elias Dahlhaus and Jens Gustedt and Ross M. McConnell

Exploiting this idea, we employ a stack of intervals to help model the state of S. Each of the intervals

on S has a unique associated timestamp, and the timestamps are in ascending order from the bottom to
the top of S. It is important to note that some of the intervals may become empty, but still remain on our
stack of intervals. The reason for this is that after a

Push

Cpush

creates an interval I, elements of I

may be removed and moved to a new interval at the top of S by a subsequent

Push

Cpush

. Eventually

if I becomes empty, we treat it as an empty interval that continues to occupy the same place between
its neighboring intervals on the stack. I is removed from the stack only when all intervals above it are
explicitly popped, and then I is explicitly popped.

Using this idea, let us now prove the result. If p

1, the result follows from Theorem 4.1. When p

the stack may be simulated with p complement stacks, S

, . . . ,

, one for each V

, and an additional

(ordinary) stack R of

Push

and

Cpush

intervals that reside on S. R represents each interval with an

ordered pair

(

)

, where t is the timestamp of the

Push

Cpush

operation that created it, and i is the

index of the substack S

that it operated on.

Initstack

(

, . . .

)

initializes R to the empty stack, and executes S

Initstack

(

)

for each

i from 1 to p.

Push

(

)

looks up for each x

∈

X the set V

that contains x and calls

Push

(

{

}

)

. In addition it then

pushes the item

(

)

on the stack R.

Cpush

(

)

calls

Cpush

(

)

and pushes one instance of

(

)

on the stack R.

Eliminate

(

)

looks up the partition class V

containing x and calls

Eliminate

(

)

Time

(

)

lets

(

)

denote the pair on top of R. If this corresponds to a nonempty interval, we may return

t. However, it is possible that the interval corresponding to

(

)

has become empty, and it would

be incorrect to return t. In this case, we must disregard the interval and try again, by popping again
from R. The interval has become empty if and only if

Time

(

)

t. So

Time

(

)

iteratively lets

(

) =

Pop

(

)

until t

Time

(

)

Pop

(

)

calls

Time

(

)

. This may delete elements from the top of R. It then looks up the pair

(

)

that is

on top of R after that operation, and returns

Pop

(

)

Through the control of R, S clearly behaves as a single stack. Because of the properties described above

for the complement stacks S

, a push of an item causes any lower instances of that item to be deleted from

The time bounds clearly remain unchanged except for

Time

, and for

Pop

, since it calls

Time

can cause a large number of items to be popped from R. We charge this cost to the calls to

Push

and

Cpush

that originally pushed them to R, leaving O

(

)

operations charged to

Time

Corollary 6.3 If F is a member of G’s inward equivalence class, it takes O

(

) +

(

))

time to compute

a depth-first forest of F.

Proof:

For each vertex x, divide its neighbors into a set L

(

)

of vertices that are not inwardly comple-

mented, and a set L

(

)

of nodes that are inwardly complemented. Let V

and V

denote the inwardly-

uncomplemented and inwardly-complemented nodes of G, respectively. Call

Initstack

(

)

initialize a set-complement stack S. When x is visited, push its neighbors in F by making a call to

Partially Complemented Representations of Digraphs

161

Push

(

)

and a call to

Cpush

(

)

. This takes O

(

) +

(

)

amortized time. Each arc

of G appears once in L

()

or L

()

Corollary 6.4 If F is a member of G’s outward equivalence class, it takes O

(

) +

(

))

time to com-

pute a depth-first forest of F

Proof:

Radix sort all arcs of G with destination as primary sort key and origin as secondary sort key.

This gives an adjacency-list representation of G

in O

(

) +

(

))

time. By Theorem T

is in the

inward equivalence class of G

, so the result follows by Corollary 2

The following extension of complement representations to bipartite graphs is critical for the linear time

bound of the modular decomposition algorithm of Let the bipartite complement of a directed bipartite graph

(

)

be the graph

(

)

∪

(

)

(4)

In a mixed bipartite representation, each vertex in V

(

)

has either a list of those members of V

(

)

that are neighbors, or else a list of those members of V

(

)

that are not neighbors.

Theorem 11 Given a mixed representation of a directed bipartite graph G, constructing a depth-first
forest for G or G

takes time that is linear in the size of the representation.

Proof:

For the depth-first forest on G, execute S

Initstack

(

)

. When visiting a node x,

suppose without loss of generality that it is in V

Push

its neighbors in V

with a call to

Push

(

)

or else with a call to

Cpush

(

)

, depending on whether x is complemented.

For a depth-first on G

, divide V

into sets V

and V

, and V

into sets V

and V

, according to

whether the vertices are complemented. Without loss of generality, suppose a vertex x is in V

, and

that it carries the list L

(

)

of uncomplemented vertices in V

that have an arc to it in G, as well as

the list L

(

)

of complemented vertices in V

that do not have an arc to it in G. This is obtained for

all vertices in a preprocessing step, by radix sorting the explicit arcs and non-arcs given in the mixed
representation of G. Call S

Initstack

(

)

. When a vertex x is first visited, suppose

without loss of generality that it is in V

Push

its neighbors in V

, with a call to

Push

(

)

and a

call to

Cpush

(

)

[

])

Topological sort

A dag, or directed acyclic graph, is a digraph that has no cycles. A topological sort of a digraph is an
ordering of its vertices so that every arc goes from an earlier to a later vertex in that ordering. A digraph
has a topological sort iff it is a dag, and, ordering the vertices of a dag in descending order of finishing
time in any depth-first search gives a topological sort, see (

(

) +

(

))

time.

162

Elias Dahlhaus and Jens Gustedt and Ross M. McConnell

Longest path in a dag

We will let the length of a path denote the number of arcs in it. The length of the longest path in a digraph
is finite iff it is a dag; otherwise a cycle exists, and by repeatedly traveling the cycle, one may demonstrate
paths of arbitrarily large lengths.

The following well-known approach finds a longest path in a dag F, given its adjacency-list represen-

tation in standard form. Label each vertex with the length of the longest path originating at that vertex.
Given a topological sort, we may observe that as long as vertices are labeled in reverse topological order,
then when it is time to label any vertex v, the members of N

(

)

are already labeled. We may then apply

the rule that the length of a maximum-length path beginning at v is one plus the maximum of the labels of
N

(

)

. Given an adjacency-list representation of G, we may charge the cost of labeling v to arcs out of v,

and we get an O

(

)

-time algorithm.

We now show that if F is a member of G’s outward equivalence class, we may find a longest path in

F in O

(

) +

(

))

time. To find longest paths in F, there is not time to apply the foregoing algorithm

directly, since we do not always have time to examine the labels of vertices in N

(

)

when it is time to

assign a longest-path label to v. We may nevertheless solve the problem by keeping all labeled vertices
bucket-sorted according to their label. A key observation is that if a vertex w has label k

0, then there

is a member of N

(

)

with label k

−

1. By induction, the buckets from k down to 0 are all nonempty.

When it is time to label vertex v, then if v is not outwardly complemented, apply the standard approach
of visiting the labels of N

(

)

. If v is outwardly complemented, then mark its neighbors in G; these are

the vertices that are not neighbors in F. Then, starting at the highest nonempty bucket, descend through
the buckets sequentially until an unmarked vertex is found. This is a neighbor in F with highest label, so
assign v’s label to be one plus this label, and add v to the appropriate bucket. In either case, the operation
can be charged to v and arcs out of v in G. Thus it takes O

(

) +

(

))

Connectivity

Let us define an equivalence relation R on vertices of a digraph G where for vertices u

v, we say uRv

iff there is a directed path from u to v and a directed path from v to u. In each equivalence class there is
always a path from any vertex to any other, but this is never the case for two vertices in different classes.
The equivalence classes are known as strongly-connected components. If G

= (

)

is a digraph and

are the strongly connected components of G, then the component graph G

is a dag. The component

graph tells which components have a path to which.

Below, we will find it useful to compute not just the strongly-connected components of a member of G’s

outward equivalence class, but a topological sort of its component graph. An algorithm given in Let us define the finishing time of a set S of vertices to be the latest of the finishing times of members

of S.

Lemma 9.1 In a depth-first search of G, the strongly connected components, taken in descending order
of finishing time, give a topological sort of the component graph.

Partially Complemented Representations of Digraphs

163

Proof:

Let

(

)

be an arc of the component graph. Since the component graph is a dag, there is no

directed path from Y to X . Let v be the first-discovered vertex in X

∪

Y . If v

∈

X , then every vertex in

∪

Y becomes a descendant of v, and v has latest finishing time of any vertex in X

∪

Y . It follows that the

finishing time of X is later than the finishing time of Y . If v

∈

Y , then Y finishes when v does, since every

vertex in Y is reachable from v. Since there is no directed path from Y to X in the component graph, there
is no directed path from v to any member of X in G. It follows that v finishes before any member of X is
discovered, and once again, X has later finishing time. Thus,

(

)

is directed from a later-finishing to

an earlier-finishing component. Since

(

)

is arbitrary, this must be true of all arcs of the component

graph, yielding the result.

This does not immediately help find the strongly-connected connected components, since, without

knowing the members of the components, one cannot find the finishing times of the components. There is
a fortunate exception to this: the vertex x of G with latest finishing time in all of G must give the finishing
time of the component X that contains it, and X must be a source in the component graph, since it is first
in topological sort of the component graph. To find X , call depth-first visit on x in G

. Since X is a sink

in G

, no other vertices are reachable from x, and the first depth-first visit visits precisely the members of

X .

Let SCCGraph

(

)

be the component graph of G, which we seek to find. The above step shows how to

find the first component X in the topological sort of SCCGraph

(

)

given by Lemma that G

= (

)

, and SCCGraph

(

) =

SCCGraph

(

)

X . Also, in any topological sort of

SCCGraph

(

)

, removing X yields a topological sort of SCCGraph

(

)

. Thus, recursing on G

X gives the remaining strongly-connected components in topological order. This recursive algorithm
amounts to a second depth-first search on G

, except that when a new depth-first visit is initiated, it must

be initiated on the unvisited vertex with latest finishing time from the first depth-first search. This vertex
is selected by traversing downward through a list of vertices from the first depth-search that gives the
vertices in descending order of finishing time.

Theorem 12 It takes O

(

) +

(

))

time to find the strongly-connected components of a member of

G’s outward equivalence class, as well as a topological sort of its component graph. Given a mixed
representation of a directed bipartite graph, finding the strongly-connected components and a topological
sort of its component graph takes time linear in the size of the representation.

Proof: The algorithm given above reduces the problem to a depth-first search on G, a depth-first search
on G

, and finding finishing times of the vertices. The bound follows from Corollary 2

Theorem 13 It takes O

(

) +

(

))

time to find the biconnected components of a member of G’s out-

ward equivalence class. Given a mixed representation of an undirected bipartite graph, finding the bicon-
nected components takes time linear in the size of the representation.

Proof:

Let d

[

]

give the preorder number for vertex v in a depth-first forest on G. Let low

[

] =

min

{

[

]

{

low

[

]

: w is a child of v in the depth-first forest

}}

. Clearly, low

[]

can be computed for all vertices

in O

(

)

time, by traversing the forest in postorder. Computation of the biconnected components reduces

in linear time to computation of low

[]

, see 2

The following extends the techniques to graphs that are not necessarily in the outward or inward equiv-

alence classes of G or its transpose, but which may be expressed as a union of such graphs.

164

Elias Dahlhaus and Jens Gustedt and Ross M. McConnell

Theorem 14 Let G

= (

)

be a digraph, and let H

= (

∪

...

∪

)

, where for each i from 1 to k

(

)

or its transpose is in the outward equivalence class of G or of G

. It takes O

(

) +

(

)))

time to find a depth-first forest of H, to compute its strongly-connected components, and to produce a
topological sort of its component graph.

Proof:

We have shown that it takes O

(

) +

(

))

time to find a depth-first forest of each F

or its

transpose. This requires the use of a stack S

to compute the forest on F

, and the structure of S

depends

on whether F

or its transpose is in the outward equivalence of G or G

. For a depth-first search of H,

initialize the same set of stacks and have them collectively simulate a single depth-first search stack on
H. A vertex may occur once in each of the stacks. To select the next vertex to be visited, search the
tops of these k stacks for the vertex x with the earliest time stamp.

Pop

x from its stack, and then call

Eliminate

on the remaining stacks to eliminate x from them. This takes O

(

)

time. Then visit each

, performing a

Push

or a

Cpush

to push the neighbors of x in F

onto S

. This takes O

(

)

time on each stack. The total time spent visiting x is O

(

)

, so the whole algorithm takes

(

) +

(

)))

time.

To find the strongly-connected components and a topological sort of the component graph, we must

also perform a depth-first search on H

. But H

∪

...

∪

, so it takes O

(

) +

(

)))

time to perform the search on H

by the foregoing.

An application to modular decomposition

Let G be an undirected or directed graph, and let v be a vertex. Let

(

)

denote the partition of V

(

)

given by

{

}

and the maximal modules of G that do not contain v. That this is a partition of V

(

)

is easy

to verify using Theorem We now give the restriction to digraphs of the modular decomposition algorithm of Partition

operation for finding

(

)

Algorithm 2:

Decomp

(

)

, compute the modular decomposition of G.

if G has only one node then return a one-node tree;
else

Select a vertex v of G;

(

) =

Partition

(

)

;

for each ancestor U of

{

}

in G

in descending order do

Create a tree node t

;

Make t

a child of the tree node corresponding to its parent in G

;

for each member X of

that is a child of U do

Decomp

(

)

;

Let t

be a child of t

return the root of the resulting tree

This algorithm produces a tree that is the modular decomposition of G, except that it allows a parallel

node to be a child of another, and a series node to be a child of another. To fix this, visit the nodes of the
tree in postorder, deleting any such node and letting its parent inherit its children.

Partially Complemented Representations of Digraphs

165

The original time bound given there was O

(

)

. The bottlenecks are finding

(

)

and finding the

ancestors of v in G

(

)

. (

(

) +

(

)

log n

(

))

bound for

undirected graphs, by solving the following problems:

•

Problem 1: Find

(

)

in each recursive call, without exceeding an O

((

)

log n

)

time bound.

•

Problem 2: Find the ancestors of v in G

(

)

in time linear in the size of G

(

)

Their algorithm for the first problem is trivial to generalize to digraphs. Their algorithm for the second

one makes use of the so-called

relation on edges of an undirected graph (see not generalize to digraphs. Thus, to get an O

(

) +

(

)

log n

(

))

bound for digraphs, it is necessary

to find an alternative approach to the second problem.

Suppose v

∈

(

)

. Define the forcing graph to F

(

)

be the following graph on V

(

)

v as follows:

there is an arc from x to y if

{

}

is not a module in G

}

. It follows that if there is an arc of F

(

)

from x to y, then every module M that contains y and v must also contain x, i.e that y forces x into any
module M common with v. On the other hand, if X

⊂

(

)

contains v, and there is no arc in F from

(

)

X to X

\ {

}

, then X is a module: any vertex in V

(

)

X must have the same relationship to all

members of X as it does to v.

Using a simple argument based on these observations, ancestors of v in G

reduces to finding a topological sort of the strongly-connected components of F

(

)

in O

(

) +

(

))

time. Because F

(

)

can be much larger than G

, there initially seemed to be no

hope of this. However, the following lemma shows that this conclusion is not true. Applying this lemma
to G

, then applying Theorems (

(

) +

(

))

Lemma 10.1 Let G be a digraph and v be a vertex. Then:

1. If G is symmetric (undirected), then F

(

)

is in the outward equivalence class of G

2. If G is not symmetric, then F

(

)

(

−

)

(

)

∪

(

))

, where F

is in the outward equiv-

alence class of G

v, and F

is in the outward equivalence class of

(

)

Proof: If G is undirected, there is an arc from x to y if y is a neighbor of x but v is not, or else if y is not a
neighbor of x but v is. Therefore, the neighbors of x in F

(

)

are the same as its neighbors in G

v if v is

not a neighbor in G and the complement of its neighbors in G

v if v is a neighbor. In summary, F

(

)

is obtained from G

v by complementing the neighbors of v.

In F

(

)

, there is an arc from x to y under the following circumstances:

1. y is a neighbor of x and v is not;

2. v is a neighbor of x and y is not;

3. x is a neighbor of y but not a neighbor of v;

4. x is a neighbor of v but not a neighbor of y.

166

Elias Dahlhaus and Jens Gustedt and Ross M. McConnell

Let F

denote the digraph on V

(

)

whose arcs are given by conditions one and two, and let F

denote

the one whose arcs are the transposes of those given by conditions three and four. The arcs of F

(

)

are

the union F

and F

. If v is not a neighbor of x, then x’s neighbors in F

are the same as its neighbors in

G. If v is a neighbor of x, then its neighbors in F

are the complement of its neighbors in G. Since x is

arbitrary, F

is in the outward equivalence class of G

v. By symmetry,

(

)

is in the inward equivalence

class of G

v. By Theorem 2

is in the outward equivalence of

(

)

Proof of Theorem Let H be a digraph and let G be an undirected member of the outward equivalence class of H, and
suppose that we want the modular decomposition of G. For Theorem (

(

) +

(

)

log n

(

))

time bound for

modular decomposition of G.

11.1

Problem 2

Let

be a partition of vertices of a graph. A set of representatives of

is a set that contains exactly one

element from each partition class. Recall that if

is a partition of the vertices of G into classes that are

modules, then G

is isomorphic to the subgraph of G induced by any set of representatives of G. The

following generalizes this idea to members of G’s outward equivalence classes.

Lemma 11.1 Let G be a digraph, let

be a partition of the vertices where each partition class is a

module of G, and let H be a member of G’s outward equivalence class. The subgraph of H induced by
any set of representatives of

is in the outward equivalence class of G

Proof: This is immediate from Theorem /

Let P be a set of representatives of

. We must find F

(

)

for G

P. By Lemma the fact that G is undirected, F

(

)

is in the same outward equivalence class as G

, and by Lemma G

is in the same outward equivalence class as H

P. Transitively, F

(

)

is in the same outward equiva-

lence class as H

P. By Lemma (

(

) +

(

))

to find the strongly-connected compo-

nents of H

P, hence to find the ancestors of v in G

. It is now trivial to establish that the sum of costs of

this step over all recursive calls is O

(

) +

(

))

11.2

Problem 1

Let

be a partition of vertices of G, and let X be a union of partition classes in

, and u

∈

(

)

X .

Pivot

(

)

denotes the following operation. For each C

∈

that is contained in X , we refine

splitting C into two sets, C

∩

(

)

and C

∩

(

)

Pivot

on different

vertices of the graph. The technique is called vertex partitioning. They show that in all recursive calls of
Algorithm Pivot

on O

(

log n

)

occasions. By giving an imple-

mentation of

Pivot

(

)

that requires O

(

)

time, they obtain an O

((

(

) +

(

)

log n

(

))

time

bound for solving Problem 1 in all recursive calls. Thus, to get an O

((

(

) +

(

))

log n

(

))

bound for

all of these calls to

Pivot

, it suffices to implement

Pivot

(

)

in time proportional to the outdegree

of u in H.

Partially Complemented Representations of Digraphs

167

Because G is undirected, the procedure is identical to the original. If C

⊆

X ,

Pivot

(

)

splits C

into two sets, C

∩

(

)

and C

∩

(

)

. Whether or not u is outwardly complemented, C

∩

(

)

and

∩

(

)

induces the same partition of C. We implement each partition class C of

with a doubly-

linked list, and maintain a pointer on each vertex to the front of its list. Extracting neighbors of u from
each class C and placing them in a twin class C

can be performed in a single traversal of the adjacency

list for u. When a new neighbor is examined, it is required only to check which class C contains it in order
to determine which twin class C

to put it in. This takes time proportional to the outdegree of u in H, as

required.

Proof of Theorem Let the prime quotients in the modular decomposition tree be quotients of the form

(

)

, where X is

a prime node and

is its children.

Let H be a digraph, and let G be a comparability graph in the outward equivalence class of H. Each

prime quotient

(

)

is isomorphic to G

, where X

consists of one representative of each member

. By Lemma |

is in the outward equivalence class of H

. Let us call H

a representation

of the prime quotient. The modular decomposition on G is a tree whose leaves are also the vertices of H.
Applying the off-line least-common ancestors algorithm of There is at most one vertex of a prime quotient for each node of the decomposition tree, the total number

of such nodes is O

(

)) =

(

))

. No edge of H appears in more than one of the representations of

prime quotients, so the total number of edges in all representations is O

(

))

Since the prime quotients are in the outward equivalence classes of their representations, we may per-

form a pivot on a vertex of the prime quotient in time proportional to the degree of the corresponding
vertex u in the representation. (

log n

)

Pivot

operations on each node a prime quotient. The total time to find the linear extension of

the transitive orientation of G is therefore O

((

(

) +

(

))

log n

(

))

References

A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-

Wesley, Reading, Massachusetts, 1974.

T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Algorithms. MIT Press, Cambridge, Massachusetts,

1990.

A. Cournier and M. Habib. A new linear algorithm for modular decomposition. In S. Tison, editor, Trees

in Algebra and Programming, CAAP ’94, 19th International Colloquium, volume 787 of Lecture Notes
in Computer Science, pages 68–82. Springer Verlag, Edinburgh, UK, 1994.

E. Dahlhaus, J. Gustedt, and R. M. McConnell. Efficient and practical modular decomposition. Proceed-

ings of the eighth annual ACM-SIAM symposium on discrete algorithms, 8:26–35, 1997.

168

Elias Dahlhaus and Jens Gustedt and Ross M. McConnell

E. Dahlhaus, J. Gustedt, and R. M. McConnell. Efficient and pratical algorithms for sequential modular

decomposition. Journal of Algorithms, 41(2):360–387, November 2001.

A. Ehrenfeucht, H. N. Gabow, R. M. McConnell, and S. J. Sullivan. An O

(

)

divide-and-conquer algo-

rithm for the prime tree decomposition of two-structures and modular decomposition of graphs. Journal
of Algorithms, 16:283–294, 1994.

A. Ehrenfeucht and G. Rozenberg. Theory of 2-structures, part 1: Clans, basic subclasses, and morphisms.

Theoretical Computer Science, 70:277–303, 1990a.

A. Ehrenfeucht and G. Rozenberg. Theory of 2-structures, part 2: Representations through labeled tree

families. Theoretical Computer Science, 70:305–342, 1990b.

A. Ehrenfeucht and G. Rozenberg. Angular 2-structures. Theoretical Computer Science, 92:227–248,

1992.

A. Ehrenfeucht and G. Rozenberg. Dynamic labeled 2-structures. Math. Struct. in Comp. Science, 4:

433–455, 1994.

M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980.

D. Harel and R. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal on Com-

puting, 13:338–355, 1984.

R. McConnell. Complement-equivalence classes on graphs. In J. Mycielski, G. Rozenberg, and A. Salo-

maa, editors, Structures in Logic and Computer Science. Springer, 1997.

R. M. McConnell and J. P. Spinrad. Linear-time modular decomposition and efficient transitive orien-

tation of comparability graphs. Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete
Algorithms, 5:536–545, 1994.

R. M. McConnell and J. P. Spinrad. Modular decomposition and transitive orientation. Discrete Mathe-

matics, 201(1-3):189–241, 1999.

R. M. McConnell and J. P. Spinrad. Ordered vertex partitioning. Discrete Mathematics and Theoretical

Computer Science, 4:45–60, 2000. URL

http://dmtcs.loria.fr/volumes/abstracts/

dm040104.abs.html

R. H. M¨ohring. Algorithmic aspects of the substitution decomposition in optimization over relations, set

systems and boolean functions. Annals of Operations Research, 4:195–225, 1985.

J. H. Muller and J. P. Spinrad. Incremental modular decomposition. Journal of the ACM, 36:1–19, 1989.

J. P. Spinrad. P

trees and substitution decomposition. Discrete Applied Mathematics, 39:263–291, 1992.

Document Outline