c

O M



Parallel Ear Decomposition Search (EDS)
And ST-Numbering In Graphs

bv



Yael Maon



Baruch Schieber



1.3



Uzi Vishkin



1,2.3



Ultracomputer Note #102

Computer Science Department Technical Report #222

February, 1986




Ultracomputer Research Laboratory



CM

CM

CM

I

«

En



CO I
O En CO



W CD

o



E
O T3
O C

CD 03

Wi CO
(0 Q

CD iv,



to
CT>



CP

C



c
o



at jz w

-( o ai

tc to s

M CD 3

m co c



New York University

Courant Institute of Mathematical Sciences

Division of Computer Science

251 Mercer Street, New York, NY 10012



Parallel Ear Decomposition Search (EDS)
And ST-Numbering In Graphs

by

Yael Maon

Baruch Schieber 13

Uzi Vishkin U ' 3

Ultracomputer Note #102

Computer Science Department Technical Report #222

February, 1986



1 Department of Computer Science School of Mathematical Sciences Tel Aviv University
Tel Aviv, Israel 69978.

2 Department of Computer Science Courant Institute of Mathematical Sciences New York
University 251 Mercer St., New York, N.Y. 10012. The research of this author was
supported by NSF grant NSF-DCR-8318874 and ONR grant N0014-85-K-0046.

The research of these authors was supported by the Applied Mathematical Sciences
subprogram of the Office of Energy Research. U. S. Department of Energy under contract
number DE-AC02-76ERO3O77.



ABSTRACT

[LEC-671 linear time serial algorithm for testing planarity of graphs uses the linear
time serial algorithm of [ET-76] for .^-numbering. This ^-numbering algorithm is
based on depth-first search (DFS). A known conjecture states that DFS, which is a
key technique in designing serial algorithms, is not amenable to poly-log time
parallelism using "around linearly" (or even polynomially) many processors. The
first contribution of this paper is a general method for searching efficiently in
parallel undirected graphs, called ear-decomposition search (EDS).
The second contribution demonstrates the applicability of this search method. We
present an efficient parallel algorithm for 5f-numbering in a biconnected graph. The
algorithm runs in logarithmic time using a linear number of processors on a
concurrent-read concurrent-write iCRCW) PRAM. An efficient parallel algorithm
for the problem did not exist before. The problem was not even known to be in
NC.

1. Introduction

We define the problems considered in this paper. For all these problems we use the
same input.

Input. An undirected graph G(V,E) and some specified edge e = (s,t) in E . (Denote « = |V|
and m = \E\.)

Let Pq be the path that consists of the edge e . An ear decomposition of G starting with
P Q is a decomposition E = P Q U P l U ■ • U P k , where P,_ t is a simple path whose
endpoints belong to P U • ■ ■ U P,, but its internal vertices do not. A simple path P t is
called an ear. It is called an open ear if the two endpoints of P, do not coincide, and a
closed ear otherwise. An ear decomposition is called open if all its ears are open.

The ear decomposition problem. Find an ear decomposition starting with P .

The open ear decomposition problem. Find an open ear decomposition starting with Pq.

An one-to-one function / from V to {1 /;} is called an st- numbering if it satisfies:

(i) f(s)=\ and /(;)=«, and (ii) for each viV— {s,t} there exist adjacent vertices Vj and v 2
such that/(v : X/(r)
The st-numbering problem. Find an 5f-numbering of G.

A graph G has an open ear decomposition starting with an edge iff G is biconnected
(see [W-32]). A graph G is biconnected iff it has an •rr-numbering for every given edge
is .t) ( see [LEC-67]).



The model of parallel computation used in this paper is the concurrent-read
concurrent write (CRCW) parallel random access machine (PRAM). A PRAM employs p
synchronous processors all having access to a common memory. A CRCW PRAM allows
simultaneous access by more than one processor to the same memory location for either
reads or writes. We use the following concurrent-write convention. In case several
processors seek access to the same memory location for write purposes, one of them
succeeds but we do not know in advance which. See [V-83] for a survey of results
concerning PRAMs.

For each of the three problems mentioned above we give a parallel algorithm which
runs in 0(\ogn) time using n + m processors on a CRCW PRAM. Alternative parallel
implementations attaining optimal speed up where m>n\ogn are also given for each
problem. These alternative algorithms run in time 0(log«log ( " «log ( ~ ] n). where log 1 *' is the
k' h iterate of the log function.

[L-85] showed that the ear decomposition problem has a parallel algorithm which runs
in poly-log time using -a polynomial number of processors and is therefore in the class NC.
A remark at the end of Section 2.1, explains why we believe that it was not known whether
the open ear decomposition problem is in the class NC. We are also not aware of any
parallel algorithm for 5f-numbenng Apparently, it was not even known if ?r-numbering is
in NC. Here, we do not only determine that these two problem are in NC, but actually give
very efficient parallel algorithms Each of these algorithms runs in logarithmic time using a
linear number of processors.

Serial graph algorithms use two main techniques for searching graphs: Depth-First
Search (DFS) and Breadth-First Search (BFSi. Both techniques seem to be not ideal for
parallel computation. The mo^t efficient poly-log time parallel implementations of BFS
require a number of processors which is cubic in the number of vertices. Many researchers
have conjectured that DFS is not even in NC One of the most challenging tasks in parallel
computation is to cope to with this apparent intractability of DFS. One approach is not to
give up and try to get the most out of DFS as in [A-85] This approach is interesting from
the theoretical point of view since it bounds the limits of DFS in parallel. We believe,
however, that when it comes to actually designing efficient parallel algorithms, a more
realistic approach should be taken That is. BFS and DFS should be replaced b> new

L llracomputer Note 102 Page 1



















TARGET « COMPUTER
NETWORK










i


'












HOST i SHARED MEMORY
MIND MACHINE


















i


'




HOST SIMULATOR: A SERIAL MACHINE



THREE LAYERS OF SIMULATION



FIG. 1



Page 2A



techniques which are amenable to parallel computation. This approach of looking for new
techniques to replace DFS has been practiced in designing efficient parallel algorithms for
biconnectivity [TV-85] and strong orientation [V-85]. Observe, however, that unlike our
problems, it was trivial to establish the membership of biconnectivity and strong orientation
in NC using simple transitive closure algorithms.

Ear-decomposition has the flavor of a general search technique in graphs. It arranges
the vertices of the graph by partitioning them into paths. This enables further exploration
of the graph in an "orderly" manner We call this search technique ear - decomposition
search fEDS).

For more motivation for considering the ear decomposition problems, we refer the
reader to [L-85].

The serial algorithm for algorithms (see [E-79]i. The linear time algorithm for the problem [ET-76J is heavily based
on DFS The present paper copes with the apparent intractability of DFS for parallel
computation by providing a new algorithm tor the problem. The new algorithm is based
on the new EDS technique for ear decomposition of a graph, thereby demonstrating its
applicability. The algorithm is also based on refined insights into the .^-numbering
problem. Interestingly, our algorithm provides also a new linear time serial algorithm for
sr-numbering.

The sf-numbering is used as an important component in several serial algorithms.
Most known is the planarity testing algorithm of [LEC-67] which was improved to run in
linear time, following the linear time algorithm for .sr-numbering of [ET-76]. Our algorithm
gives hope for finding efficient parallel planarity testing using the approach of [LEC-67]. It
is yet unresolved whether there exists an efficient parallel algorithm for planarity testing.
Note that the involved planarity testing of [JS-82] still leaves much to be desired, as it runs
on O(\oz~n) time using 0(n~ /log";? I processors.

Another application for sr-numbering is mentioned in [IR-84] for the following
problem. Given an undirected biconnected graph fine two ^panning trees T and 7 ; which
are rooted at the same vertex r so mat the paths from r to v in T and T~_ are vertex
disjoint i except r and v) This problem is important tor reliable communication as was
indicated in that paper

lltracomputer Note 102 Page 3



In Section 2 we present a parallel algorithm for computing an ear-decomposition and
an open ear-decomposition. In Section 3 we use the open ear decomposition to compute
^/-numbering of a biconnected graph G. The numbering is done in two stages: (1) We
orient the edges of the input graph. As a result we get a directed acyclic graph such that
each of its vertices is on a path from 5 to r. (2) We topo logically sort of this digraph to get
the .^-numbering. The whole subtlety of the algorithm lies in the orientation of Stage 1.
Through a careful case analysis we perform this orientation based on considerations which
are essentially local. We were surprised by the fact that these local considerations were
sufficient. Another intriguing comment is that one of the interesting open problems in
parallel computation is whether there is a poly-log time algorithm for topological sort that
uses linearly many processors. We have examples where our topological sort algorithm
fails on some acyclic digraphs. However, we can prove that this topological sort algorithm
will work correctly on all acyclic digraphs which can be obtained as outcome of the first
stage.

2. Ear-Decomposition In Parallel

Let G(V,E) be an undirected biconnected graph. We give an algorithm for finding an
open ear decomposition of G starting with (s,t), where (s,t)dE. A parallel
implementation of this algorithm is described at the end of the section.

Definitions: Let T(V.E) be a tree which is rooted at t.

(1) For viV, LEVEL(v) is the length, counting edges, of the unique path in T from t to v.

(2) For viV, F(v) is the father of v in T.

(3) For u,v i V, LCA(u,v) is the lowest common ancestor of a and v in T.

(4) Let u,v€V, where u is not an ancestor of v. We denote by e uy the first edge in the
unique path in T from LCA(u,v) to u.

In order to compute an open ear-decomposition, we first find an ear-decomposition of
G which is not necessarily open. This is described in the first subsection below. The second
subsection shows how to modify this ear-decomposition into an open ear-decomposition.



Ultracomputer Note 102 Page 4



2.1. Finding an ear-decomposition

instead of designing a new algorithm for finding an ear decomposition, we use a
parallel algorithm for a different problem which was given in fV-85]. There, the algorithm
assigns directions to the edges of a connected bndgeless undirected graph so that the
resulting directed graph is strongly connected We note that we obtain the same ear-
decomposition as in [L-85]. However, our parallel algorithm is more efficient. For
completeness of the presentation, we outline below the algorithm for finding an ear-
decomposition

Step t, Find a spanning tree T(V.E T ) rooted at r of G . such that (s.t) will be the only tree
edge whose endpoint is r. This is done as follow^: First, find a spanning tree of the
subgraph induced by the vertices V— {t}. Finally, add the vertex r and the edge (s.t) to the
tree 'Remark: The fact that G is biconnected implies that the subgraph induced by V-{r}
is connected.) Step 1 is the only step in this subsection which is not completely identical to
the algorithm of [V-851. There, any spanning tree will do

Edges in E T - {(.? ,r)} will be referred to as tree edges Edges in E — E T will be
referred to as non-tree edges The edge (s,t) will have a special status.

In Step 2 we assign a number to each non-tree edge.

Step 2.

(a) For each vd V. compute LEVEL(v) and F(v).
For each non-tree edge («,v) compute LCAi «,v).

(b) Assume that each edge etE has a serial number 1 tree edge e , let NUMBER {e) = ( LEVEL ( LCA ie\) SERIAL (e)).

vV. define a lexicographic order < L on these numbers as follows Let e ,e' be non-
tree edges. MUBERieXfSUUBER^e' > if NUMBER(e).KNUMBER(e').l, or
NUMBER(e) .] = XUUBERi s' • ! and SUMBERie ) 2 stands tor the i' h coordinate of the pair M'MBERi x)

..et f be a non-tree edge We call the simple cycle which is formed by / together with
the edge* in E r the cycle of f

Step 3. Each tree edge ,. considers" ail non-tree edge* / such thai is in their cycle.
Among them e selects an edge ; whose \'L'MBER(f) is minimal (according to < L â– â–  to be its

Ultracomputer Note 102 Page 5



master edge. The edge / is denoted MASTER(e) .

Proposition 2.1.1. Each non-tree edge e together with all the tree edges which selected it as
their master edge form a simple path or a simple cycle. We call this path or cycle the ear
of e.

Observe that the order < L on the non-tree edges induces an order on the defined ears. In
addition, define the edge (s,t) as the first ear.

Proposition 2.1.2. The defined ears and the order yield an ear-decomposition.

Note that some of these ears may be simple cycles and therefore the resulted ear-
decomposition may be not open. A closed ear may occur when a non-tree edge (u,v) is a
master edge of all the tree edges in its cycle. (For an example where an arbitrary order on
the serial numbers of the non-tree edges imply such a closed ear, see edge n 2 in Fig. 2.1.
assuming that the serial number of n 2 is smaller than that of « 1# )

Remark: Unlike a remark in Lovasz"s paper. Fig. 2.1 demonstrates that it is possible to get
a closed ear whose endpoint is neither the root nor a separating vertex. The open ear
decomposition proposed in [L-85] is based on this erroneous remark.

2.2. Finding an open ear-decomposition

In order to have a decomposition into open ears we have to define a subtler order on
the non-tree edges. We show how to do it by reordering the non-tree edges which have the
same LCA. Specifically, this reordering is achieved by changing only the second component
in the pair (LEVEL(LCAie)) .SERIAL! e )). First, we take a closer look at the situation where
a closed ear occurs. Let (u.v) iE — E T and x = LCA(u.v) and suppose xi= u. If v = x then the
ear of (u.v) is closed iff e ux chooses (u.v) as its master. Otherwise (i.e., v¥^x and hence
e vu is defined), the ear of («,v) is closed iff both e u , and e, u choose («,v) as their master.
Suppose, for instance, that e uv (or e u ) is on the cycle of a non-tree edge / such that
LEVEL(LCA(f)) initialization of SERIAL, the ear of e cannot be closed since (u,v) will never be the master
of e ui . Therefore, we can characterize all the difficult cases, as the ones in which
LCA(MASTER(e u ,,) = LCAi MASTER! e ji = r if v*x and LCA(MASTER(e UA .)) = x
otherwise. following observation, which motivated us in changing the above ear-decomposition into an

L Itracomputer Note 102 Page 6



to



*W\



V



{3/ ^
/ \






Fig. 2 .1.



&-M




tM V



6 V,



ff t>



Hg.



Page 6A



open ear-decomposition.

Observation. Consider any assignment of numbers into SERIAL of the non-tree edges so
that for each non-tree edge (m,v), at least one of e uv or e v u does not choose (u,v) as its
master. Then, the above ear-decomposition must be open.

This change is done using an auxiliary (not necessarily connected) graph H x for every
vertex r in V— {t}.

Step 4. For every vertex x in V— {;}, we construct the bipartite undirected graph
H x = (V X ,E X ) , as follows:

V x = {[u ,v] |( u ,v ) € £ - E r and LCA ( u ,v) = r} (J { [a ,F( u)] \F( u ) = x} .

In words, the vertices V x are all non-tree edges whose LCA is v (to be called non-tree
vertices) and all tree edges connecting x with a son in the tree (to be called tree vertices).

Let [«,v] be a non-tree vertex in V x such that u is not an ancestor of v in T. Let e ux be the
tree edge (w,je). Then the edge ([«,v],[w,jc]) is in E x .

The graph H i which relates to the graph G of Fig. 2.1 is given in Fig. 2.2.

Step 5. For each graph H x , compute its connected components and a spanning forest.

Main Lemma. Consider a spanning tree of a connected component of one of these auxiliary
graphs H x . Then, at least one of its tree vertices [w,x] (where x — F(w)) must satisfy
LEVEL(LCA(MASTER(w,x)))
Relevance of Main Lemma. Let [u,v] be a non-tree vertex in H x and let (w,x) be a tree
vertex in the spanning tree of the connected component of [u,v] in H x whose existence is
guaranteed by the Main Lemma. Consider the path leading from [w,x] to [u,v] in this
spanning tree. This path alternates between tree and non-tree vertices. Let us denote it

ti( = [w ,x]),n l ,t 2 ,n2 f a ,« a ( = [M,v]), where t, stands for a tree vertex and n, for a non-tree

vertex. Observe that the edge (represented by) ;, belongs to the cycle of (the edge
represented by) n h for l the ears of n\,n 2 ....,n a will be closed. In view of the above Observation, we simply take
care that the edge of each tree vertex t. will not select the edge of the non-tree vertex n ; as
its master. For this. Step 6 below numbers the non-tree vertices on this path in ascending
order (i.e.. so that SERIAL(n-J < < SERIAHn x )) . This implies that for 2<;^a. the

Ultracomputer Note 102 Page 7




THE TARGET SYSTEM



Figure 2



Page 7A






edge



of t, will not select the edge of «, as its master. In addition, the Main Lemma implies that
LEVEL(LCA(MASTER(w,x))) is not included in the ear of ri\.

Proof of Main Lemma. Take any spanning tree as in the Lemma. The proof proceeds as
follows. We define a non empty subgraph G x of G which is a function of this spanning
tree. We show that if the Lemma does not hold with respect to this spanning tree then
Gi^G and G] is a biconnected component of G. This would contradict the biconnectivity
of G and therefore the Lemma is correct. Let us define G X {V y ,E \) â–  Recall that all the tree
vertices in the spanning tree are of the form (v,F(v)), where F(v)=x. The vertices of Gj
are: (1) All the vertices v such that [v,x] is a tree vertex in the spanning tree. (2) All
vertices of G which are descendants of the vertices in Item (1) in the spanning tree of G
which was found in Step 1. (3) x itself.

G[ is induced by these vertices. That is, the edges of G\ are all the edges of G which are
incident to two vertices in Gj.

Suppose H x has more than one connected component. Let G^Vi^i) be a similar subgraph
of G which is defined for the spanning tree of another connected component of H x . We
first show that it is impossible to have an edge (u,v) in E connecting any vertex // of
V^-f.v} with any vertex v of V' : -{.v}. Clearly, LCA(u,v) must be x itself. The edge e u v is
in the connected component of Gy in H x and e vll is in the connected component of G 2 in
H x . Therefore, if (u,v) exists, then it must be connected to the tree vertices of e u , and e vu
and therefore Gj and G? are the same, contrary to our assumption.

Hence, if there is no edge (u.v) in E such that u is a vertex of V,-{x} and
LEVEL(v) contradicts the biconnectivity of G .

Step 6.

i a) For the spanning tree of each connected component in each auxiliary graph H.. find a
tree edge (w,x) 'where F(w)=x) such that LEVELiLCAi MASTERl u\.v) ) ) (Its existence is guaranteed by the Main Lemma.) This tree edge will be referred to as

Ultracomputer Note 102 Page 8



the edge of its component

(b) Root each such spanning tree at the edge of its component Compute the numbering of
the non-tree edges in a preorder traversal of the spanning tree. For every non-tree
edge e, this numbering will be stored in PREORDER(e)

(c) For each non-tree edge e, let NEWNUMBER(e) = (LEVEL(LCA(e)),PREORDER(e)).

For example, notice that the edge of the component given in Fig. 2.2 is fj.

Step 7. Each tree edge reselects a master edge according to XEWXUMBER in the same way
as the selection of a master edge in Step 3 above.

Proposition 2.2.1. Each non-tree edge e together with all the tree edges which selected it as
their master edge form a simple path (which is not a cycle). This path is the ear of e.

Again, observe that the order < L on the non-tree edges induces an order on these ears. In
addition, define the edge (s.t) as the first ear.

Proposition 2.2.2. These ears and order yield an open ear-decomposition

Remarks:

il) This algorithm can be extended to check if G is biconnected. In case that G is not
biconnected it can be modified to compute the open ear-decomposition of each biconnected
component.

(2) For the ^-numbering algorithm, we may omit each non-tree edge e of G which forms
an ear that consists of e only.

2.3, Parallel Implementation

We first present an implementation which runs in OdogMi time using n+m
processors. Appendix 1 presents an alternative implementation which runs in time
dogf/log' ^log'-'rt) using an optimal number of processors when m >nlosn.

Steps 1. 2 and 3 are essential!;* taken from [V-85]. These steps take O(logn) time
using n + m processors.

Remark. The algorithm of [V-85] implements steps 2 and 3 in three stages: i ! I Fach vertex
v selects a single non-tree edge (u.v) sucn that LCA(u.\ • is the lowest common ancestor of

(v.v< .-..). where v ; . . .v k are all the vertices which are adjacent to v by an edge in

E — Ej. ■ 2) The original serial numbers of the non-tree edges, which were set arbitrarily,

Uhracomputer Note 102 Page 9



are modified in the following way. All the non-tree edges which were not selected in Stage
1 are assigned serial numbers which are greater than those assigned to the selected non-
tree edges. (3) Each tree edge selects its master as in Step 3 above. In [V-85], it is shown
that this, rather tedious, implementation is more efficient. It requires only n computations
of LCA instead of m computations as in the direct implementation.

Finding the edges of the H x 's in Step 4 can be done in O(losn) time using n + m processors.
Note that the total number of edges in all auxiliary graphs is 0(n + m). Step 5 takes
O(logn) time using n + m processors using the parallel connectivity algorithm of [SV-82].
Step 6(a) (i.e., finding the edge of each component) needs 0(1) time using n processors,
since we check for each tree edge whether it satisfies the inequality of Step 6(a). Step 6(b)
requires rooting of each spanning tree and computation of preorder numbering. Using the
Euler tour technique on trees, which has already been used extensively in our above
references to [V-85], this can be done in 0(\ogn) time using n + m processors.

( Remark: Step 6(b) requires an adjacency list representation of the spanning forest. To
obtain adjacency lists from a list of / edges, one may consider applications of the sorting
algorithm of [AKS-83] that uses / processors to sort / elements in time <9(log/) (when
edges are compared according to a lexicographic order). Since we only need to sort
numbers which are in a restricted domain we can apply the recent randomized radix sort
algorithm of [R-85] which achieves almost-surely the same asymptotic time (with much
more acceptable constants) using only //log/ processors. A third possibility is to perform
this sorting in time O(logZ) and / processors, using an adaptation of the simple notion of
"orthogonal trees" (see [Th-83]). However, this takes more space. )

Step 6(c) needs 0(\) time using m processors. Step 7 can be implemented in the same way
as Step 3 above. (Recall that for the ir-numbering we may omit the edges which form an
ear of length one. This can be done in 0(log«) time using m/\osn processors by applying a
variation of a parallel "prefix sums" algorithm. See [FL-80].)

3. ST-Numbering In Parallel

In this section we describe how to compute in parallel the u-numbermg of a
biconnected graph G. given an open ear-decomposition of G

1 2 3