I/O-Complexity of Graph Algorithms

M. V. Kameshwar Abhiram Ranade Department of Computer Science and Engg. Indian Institute of Technology Bombay Powai, Mumbai 400076 India

                 {kamesh,ranade}@cse.iitb.ernet.in

September 1, 1998

Abstract

We show a lower bounds Ω(\frac{E}{V} Sort(V)) for the I/O-complexity of graph theoretic problems like connected components, biconnected components, and minimum spanning trees, where E and V are the number of edges and vertices in the input graph, respectively. We also present a deterministic O(\frac{E}{V} Sort(V) · max(1, log log \frac{V BD}{E})) algorithm for the problem of graph connectivity, where B and D denote respectively the block size and number of disks. Our algorithm includes a breadth first search; this maybe of independent interest.

1 Introduction

Data sets of many modern applications are too large to fit into main memory, and must reside on disk. To run such applications efficiently, it is often necessary to explicitly manage disk accesses as a part of the algorithm. In other words, the algorithm must be designed for a model that includes disk, rather than the customary RAM model. Recently, this area has received a lot of attention, and algorithms have been developed for many problems using the Parallel Disk Model[7]. In this paper, we study several graph problems using this model and present improved upper and lower bounds.

The Parallel Disk Model consists of a processor, its memory, and D disks which can be accessed in parallel. Data is organized in records, with the memory able to hold M records. A record maybe thought of as a constant number of words. Records are stored sequentially on each disk, and the disk is divided into fixed contiguous blocks of B records, called tracks. The global disk address space is striped across the disks in the following manner: record i in track j of disk k is the i + B(k − 1) + BD(j − 1) th record in the global disk address space. In one I/O step B records from any single track on each disk maybe exchanged with B records in the RAM, so that in a single step a total of at most BD records can be read or written from disk. The time required for computation is ignored; but computations can only be performed on records in memory. This is reasonable since typically disk accesses are orders of magnitude slower than CPU cycle times. It is customary to assume that M > BD. The following expressions are useful[7]:

Scan(N) = \frac{N}{BD}: The number of disk accesses needed just to read N records stored contiguously in the global disk address space. Because the address space is striped across disks, the records must be in N/BD tracks on each disk, and thus that many parallel steps suffice. Scan(N) is usually a lower bound if input size is N.

Sort(N) = \frac{N log N/B}{BD log M/B}: The optimal number of I/Os needed to sort N records stored contiguously in the disk address space using just comparisons[7]. This number is important because sorting forms an important primitive in many external memory algorithms.

The main problem considered in this paper is the connected component labelling problem. We assume that the input is provided as an unordered Edge List. We will use E to denote the number of edges and V the number of vertices. The edge list is given as a sequence of E records stored contiguously in the global disk address space, with each record consisting of a pair of integers in the range [1,V] indicating the edge endpoints. The output is an array L[1 … V] stored contiguously as V records; we require L[i] = L[j] iff i and j are in the same component.

We also study the problem of duplicate elimination, for itself and because it arises naturally while developing upper and lower bounds for many graph problems. The input in this case is a sequence of N records where each record is an integer in the range [1, P], for any given P. The output is an array C[1 … P] stored contiguously in P records on disk, with C[i] = 1 if i occurs in the input, and 0 otherwise.

Our main results are as follows:

1. Lower bounds for graph problems: We show that the connected component labelling problem requires time Ω(\frac{E}{V} Sort(V)). We extend this bound to several problems including biconnectivity, minimum spanning tree, and decision versions of these problems.

2. Upper bounds for connected component labelling: We present a deterministic algorithm which can do labelling in time O(\frac{E}{V} Sort(V) · max(1, log log \frac{V BD}{E})). This is optimal for graphs with average degree Ω(BD).

3. Duplicate elimination: We show a lower bound of Ω (\frac{N}{P} Sort P ) and give a matching upper bound. We also extend the upper and lower bound to problems such as histogram computation, and more generally, multiprefix computation.

Previously the only lower bounds known for graph problems were the obvious bound Scan(E) and a bound Sort(V) for sparse graphs (E = O(V)) proved by Chiang et al[2]. Our bound is stronger if the graph is not sparse, and further our bound applies to other problems besides connected component labelling. We note however that the bound of [2] applies also when the input is presented as an adjacency list (defined in Section 5.2), while ours applies only if the input is an edge list.

The best previous deterministic algorithm for connected component labelling is by Kumar and Schwabe[5], and this works in time O(log M · \frac{E}{V} Sort(V)). Our algorithm is much faster than this, since M > BD > V BD/E, and in fact optimal when the average degree of the graph is Ω(BD). Earlier an O(log \frac{V}{M} ·Sort(E)) algorithm was given by Chiang et al[2]. For sparse graphs(E = O(V)) closed under edge contraction, the algorithm is shown to work in time O(Sort(V)), and is hence optimal. Our algorithm also has this property, and is of course far better for general sparse graphs.

Chiang et al[2] also give a O(\frac{E}{V} Sort(V)) randomized algorithm, which is optimal.

Duplicate elimination was investigated by Arge et al[1], who present a general lowerbound technique for comparison based external memory algorithms. We extend their work in two ways. In Arge et al’s model, the records being compared are assumed to come from an unbounded set. In our model, the records come from a finite set of integers [1, P], which makes the problem harder. Our second extension is that we allow indirect addressing while performing I/O; we believe that this is a very natural operation to use when the records come from a finite set, and thus lower bounds must account for it. Also, our model is powerful enough to express I/O cacheing.

Throughout this paper we assume that V and P are larger than M, (if not there are simple algorithms which work in a single scan of data) but that log V and log P are smaller than B log \frac{M}{B}.^{1}

Paper Outline: After a discussion of the lower bound framework, we derive lower bounds for the problem of eliminating duplicates from a multiset whose elements can take values only from a finite domain. We then reduce this problem to the problem of graph connectivity, and other related graph problems, thereby finding lower bounds for them. We then describe improved upper bounds for the connected components problem.

2 Lower Bound Framework

The computational model we use for proving lower bounds is called the P -way Indexed I/O tree, which is an extension of the I/O tree of Arge et al[1]. In addition to the operations allowed in the I/O Tree, our model allows P -way indexed accesses to disk, with P a parameter to be fixed later. We first discuss a restricted model, which has D = 1 disks. The case of general D and an additional extension is considered in section 2.3.

2.1 Restricted model

A restricted indexed I/O tree T is similar to a decision tree, with execution starting at the root and travelling to a leaf. Initially, the disk holds the input in contiguous records, and the memory is empty. The tree may have three kinds of non-leaf nodes:

1The pagesize for many disks is several kilobytes; assuming one kilobyte for our problems, say 50 records fit in a kilobyte, i.e. B = 50. Even for a trivial memory size of 1 Megabyte we get log \frac{M}{B} = 10. Thus we require V, P < 2^{500} which is reasonable.

Comparison Node: Each such node is labelled by pair of numbers < i, j >, and has outgoing edges labelled {<, =, >}. The node causes a comparison to be performed between the ith input record and the jth input record which must be present somewhere in main memory. Depending upon the outcome, the appropriate outgoing edge is taken.

Indexed Input node: Each node has a label < i, m_{1}, m_{2}, …, m_{B}, t_{1}, t_{2}, …, t_{P} >, with P outgoing edges labelled 1 through P. This node causes a track to be read into main memory record positions m_{1}, …, m_{B}. The track is determined by the value of the ith input record which must be present somewhere in main memory: if the value is j then track t_{j} is read, and the corresponding outgoing edge traversed. The value j is required to lie in the range [1, P]. If all t_{1} = t_{2} = ⋯ = t_{P}, then the parameter i is ignored and the track is read into the specified positions, and the first outgoing edge is traversed (we dont require that all tree edges be traversible for some input). This corresponds to non-indexed input– this would be necessary sometimes, say at the beginning of execution.

Indexed Output node: Similar to indexed input nodes, except the track is written from the specified records in memory.

We will use the term I/O node to mean either in indexed input node or an indexed output node.

Each leaf v has a label Solution(v). Let π denote the problem being solved, x an input instance, π(x) the output required, and T (x) the leaf reached during execution. The tree T is said to solve the problem π if for every x, Solution(T (x)) = π(x). Let I/O_{T} (x) be the number of I/O-nodes, i.e. indexed input nodes and indexed output nodes on the path from the root to T (x). Let I/O_{T} denote the maximum value of I/O_{T} (x), this is the quantity we will lower bound. Note finally that we dont insist that the correct answer be written out on disk; only that the correct answer (leaf with the correct label) be identified by the algorithm. This is adequate since we are only interested in using the model to prove lower bounds.

I/O trees vs. Decision trees: It turns out that an Indexed I/O tree for solving a problem can be transformed to a (short) binary decision tree for solving the same problem. Then by bounding the number of comparisons in the decision tree we can establish a bound on the number of I/O operations. Our notion of a decision tree is standard. We only allow comparison nodes in it with only two going edges labelled {<, ≥}. Further at each node, comparisons are allowed between arbitrary records, whether or not they are in memory. In a decision tree we also allow comparison between records and constants, this is not allowed in the restricted model (but also see section 2.3). For a tree T (indexed I/O tree or decision tree) and input instance x let Path_{T} (x) denote the number of comparison nodes on the path from the root to v_{T} (x). The result stated below is a generalization of the one stated for I/O-trees in [1].

Lemma 1. Let π be problem solved by a restricted indexed I/O tree T, with n the number of records constituting the input. There exists a decision tree T_{c} solving π, such that:

Path_{T_{c}}(x) ≤ n log B + I/O_{T} (x) · O (B log \frac{M − B}{B} + log P )

Proof. We will first apply a sequence of transformations to T to get another indexed I/O tree T′ solving π in which the number of comparisons between successive I/O nodes is small. Next we will modify T′ to the required decision tree T_{c}.

Constructing T′: Initially all the I/O nodes in T except the root are coloured white, the root is coloured black. Each basic transformation alters the tree and colours some nodes black. After all nodes have been coloured black we get T′. After each transformation, the resulting tree will continue to be an indexed I/O tree solving π. Further, it will satisfy the following Ordering Assertion: If execution reaches any black node, the comparisons performed till then will be sufficient to construct the total order of the records in main memory at that time.

The basic transformation is applied at any black node v having some white descendants and no black descendants. Let v_{1}, …, v_{k} be descendant I/O nodes that can be reached from v without passing through another I/O node. Only comparison nodes occur between v and all v_{i} and these form a subtree S.

If v is an output node, then notice that by the ordering assertion the outcome of every comparison inside S is already known! Thus we can directly connect v to a single v_{i} and colour that v_{i} black, completing the transformation.

If v is an input node there are two cases depending upon whether or not the track t read at v was read for the first time. In case t had been read earlier, we know the ordering of the records in t. By the ordering assertion we know the total order on the M − B records in main memory as well. Thus to maintain the ordering assertion at the next I/O node, we simply need to do a merge; this can be done using a decision tree S′ of height O(B log \frac{M−B}{B}). This tree S′ is attached below v instead of S. Of course, S′ will in general have more leaves than S. Say the leaves of S′ are v′_{1}, v′_{2}, …, v′_{l}. Let I(u) denote the set of input instances for which a given node u is visited. It is easily seen that I(v′_{1}), …, I(v′_{l}) and I(v_{1}), …, I(v_{k}) are both partitions of I(v), and that the former is a refinement of the latter. Thus beneath each v′_{j} we attach the subtree that is under v_{i}, where I(v′_{j}) ⊆ I(v_{i}). Clearly, the new tree that results also solves π.

In case t is being read for the first time, we may not know the ordering of the records in t. So we use a decision tree to sort these records first, and then do the merge with the M − B records in main memory. Subtrees are attached below the leaves of this as in the previous case. Thus the total height needed is at most B log B + O(B log \frac{M−B}{B}).

When all I/O nodes become black, we are guaranteed to have a tree T′ which solves π, and in which between consecutive I/O nodes there are at most B log B + O(B log \frac{M−B}{B}) comparison nodes. Further, the term B log B can arise only while reading inputs for the first time– thus only n/B times. Thus the total number of comparison nodes encountered on input x is n log B + I/O_{T′}(x) · O(B log \frac{M−B}{B}) = n log B + I/O_{T} (x) · O(B log \frac{M−B}{B}).

Constructing T_{c}: T′ is almost a decision tree, except that the I/O nodes in T′ effectively allow a P way branch based on the index variable. But we can replace this with a decision tree of depth O(log P). When this is done, we get the required decision tree T_{c}. Since each I/O node contributes a log P additional height, the result follows.

2.2 I/O Cacheing

In our full model the indexed input nodes are adaptive: when control reaches such a node with label < i, m_{1}, m_{2}, …, m_{B}, t_{1}, t_{2}, …, t_{P} >, a check is first made to see if track t_{j} is already in memory, where j is the value of input record i. If t_{j} is already in memory, then no I/O is actually performed, but the data is copied within the memory into memory positions m_{1}, …, m_{B}. If the track is not in memory, then an I/O is performed as usual.

Say a value i is a key for a record r if r is the label on the ith outgoing edge from some indexed input node. In other words, some input record must take the value i in order for r to be fetched. It is legal for a record to have many keys; however, it will be observed that generally the number of keys will be small. For instance, if our algorithm only contains array references of the form A[X] (where X is some input record), then clearly the record A[j] will only have j as the key. If for instance if our algorithm allows references of the form A[X + K] where K is a constant, then the key for A[j] would have to be j + K.

Under the assumption that every record has O(1) keys, Lemma 1 can be shown to hold with small modification. The key idea is to extend the ordering assertion to be: If execution reaches any black node, the comparisons performed till then will be sufficient to construct the total order of the records in main memory at that time and the keys of these records. Note that at any instant the memory can hold only M records, and by the O(1) keys assumption there are only O(M) keys to consider (the key for any record is known by examining the indexed input nodes that can potentially read that record). Thus the ordering assertion now requires us to maintain a total order over O(M) values instead of the M earlier. The rest of the details are omitted from this abstract.

We note that this change makes our model very powerful: using it we can implement dynamic behaviour such as LRU block replacement policy. We also note that it is possible to enhance the model so that cacheing happens at the granularity of records than tracks. We will discuss this at length in the final version.

2.3 Full Model

Our full model extends the restricted model in the following manner. First we allow D Disks. Instead of one track being read/written in a single I/O node, we allow D tracks to be read or written. Each I/O node now has D labels of the form described for the restricted model. Further, there are P^{D} outgoing edges, one edge for each of the P^{D} tuples that can be the values for the D index variables. Second, we allow Compiler generated constants. At the start of execution, we allow the disk to hold tracks containing constants that might be needed by the program in addition to the program input. The constants would have to be read in explicitly in order to be used, just like input records, of course.

Theorem 1. Let π be problem solved by an indexed I/O tree T, with n the number of records constituting the input. There exists a decision tree T_{c} solving π, such that:

Path_{T_{c}}(x) ≤ n log B + D · I/O_{T} (x) · O (B log \frac{M − B}{B} + log P )

Proof. Follows along the lines of Lemma 1, after noting that compiler generated constants do not need to be sorted even when read for the first time.

Following [1] we note that Lemma 1 and Theorem 1 also applies to algorithms having some other operations besides comparisons and indexed I/O. In particular, we can allow assignment statements which copy records within memory. These copying statements do not even need to be represented in our tree, since our comparison nodes refer to input records directly and not the positions at which the records are held in memory.

3 Duplicate Elimination in a Multiset

The DE(N, P) duplicate elimination problem is as follows. The input is a sequence of N records where each record is an integer in the range [1, P]. The output is an array C[1 … P] stored contiguously in P records on disk; we require that C[i] = 1 if i occurs in the input, and 0 otherwise.

Lemma 2. The depth of any decision tree solving DE(N, P) is at least N log \frac{P}{2} .

Proof. Say an input instance is odd if all the integers in it are odd. Else it is non odd. We will show that in any decision tree solving DE(N, P), distinct leaf nodes will be visited for distinct odd input instances. From this the Lemma follows since there are (\frac{P}{2} )^{N} odd instances, and thus at least that many number of leaves.

Let S = [s_{1}, s_{2}, …, s_{N}] be the input records. Suppose that leaf l is reached in execution for an odd input instance. At l the set S is partitioned into subsets S_{1}, …, S_{k}, such that all elements within each subset are known to be equal, and the subsets are related by <, ≤, >, ≥. Further since we allow comparisons between constants and records as well, for some of the S_{i} we know the precise value of the records in them. Suppose U_{i} and D_{i} are respectively the maximum and minimum values that are assigned to S_{i} over all odd input instances that visit l. If U_{i} = D_{i} for all i, then we are done, since this means there is a unique odd instance visiting l.

Else there exists S_{j} for which U_{j} > D_{j}. Let σ_{u} denote the set of subsets S_{i} the records in which are required to have values ≥ the value assigned to the records in S_{j}. Let A_{u} and A_{d} respectively denote input instances in which records in each S_{i} are respectively assigned values U_{i} and D_{i}. It is easily verified that these input instances visit l. Let E denote an even integer in the range [D_{j}, U_{j}].

Now it will be observed that there exists a non-odd input instance which visits l in which the records in S_{i} are assigned value E. To complete this instance, we simply assign records in sets in σ_{u} their values in A_{u}, and the rest their values in A_{d}.

Theorem 2 (Duplicate Elimination). For any indexed I/O-tree T solving DE(N, P), we have I/O_{T} = Ω(\frac{N}{P} Sort(P)) assuming log P < B log \frac{M}{B}.

Proof. Using Theorem 1 and Lemma 2 we have

N log \frac{P}{2} = N log B + D · I/O_{T} · O (B log \frac{M − B}{B} + log P ) = N log B + D · I/O_{T} · O (B log \frac{M}{B} )

using the assumption log P < B log \frac{M}{B}. The bound follows after rearranging.

3.1 Upper Bounds

The lower bound stated in Theorem 2 can be met using a simple algorithm as follows.

Divide the N input records into N/P groups of P records each. Sort the records within each group. For each group construct the solution to the duplicate elimination problem, i.e. construct a vector of size P where the ith entry indicates whether or not i occurs in the group. At this point there are N/P bit vectors, each of size P. The result of “OR”ing the bit vectors is clearly the solution to the original problem.

Sorting each group takes time Sort(P), so for N/P groups the time is \frac{N}{P} Sort(P). Each individual vector can clearly be constructed in time Scan(P) and hence the total time for constructing the vectors is Scan(N). Computing the OR of the vectors can also be done in time Scan(N). The total time is thus O(\frac{N}{P} Sort(P) + Scan(N)) = O(\frac{N}{P} Sort(P)).

3.2 Generalization

It is easily seen that the upper bound as well as the lower bound applies to operations such as histogramming, where the ith output record must be set to the number of times i occurs in the input.

In fact we can define a generalized Multiprefix operation as in [6]. The input in this case consists of 3 arrays Colour[1..N] and V alue[1..N] and T able[1..P]. The output is a single array R[1..N].

Let i_{1}, …, i_{k} denote in ascending order the indices for which the values in Colour all equal i. Then we require that R[i_{j}] = T able[i] + V alue[i_{1}] + ⋯ + V alue[i_{j}]. Further it is required to set T able[i] = T able[i]+V alue[i_{1}]+⋯+V alue[i_{k}]. Clearly this operation has upper and lower bounds same as DE(N, P). Note that the multiprefix operation is very versatile, by using appropriate associative operators + we can implement several operations such as table lookup/update, ranking keys of the same value, concurrent read/write operations as on PRAMs.

4 Lower Bound for Connected Components

We reduce the problem of duplicate elimination of certain kinds of sequences to the problem of computing connected components on graphs. Consider a sequence b of length N of numbers from the range [P + 1, 2P]. Suppose that b can be divided into P contiguous sequences, b_{1}, b_{2}, …, b_{P} each of length N/P such that all the elements in each sequence b_{i} are distinct. Let DE′(N, P) denote the problem of removing duplicates from such sequences.

Lemma 3. The depth of any decision tree solving problem DE′(N, P) is N log Ω(P).

Proof. Similar to the proof of Lemma 2, and thus omitted.

Theorem 3 (Connected Components). Any indexed I/O-tree T finding the connected components of a V vertex, E edge graph has I/O_{T} = \frac{E}{V} Sort(V) assuming E ≥ V and log V < B log \frac{M}{B}.

Proof. We transform the problem DE′ to connected component labelling. For any instance b of a DE′(E − V/2, V/2) problem let b_{j} denote the jth subsequence of b of length (E − V/2)/(V/2). Consider a graph G with V vertices and E edges as follows:

1. If V/2 + i ∈ b_{j}, then edge (j, V/2 + i) present.

2. If i ∈ {1, 2, …, V/2 − 1}, then the edge (i, i + 1) is present.

Clearly the edge list of G can be constructed in Scan(E) time given the input instance b.

Given a connected component labelling L[1..V] of G, we can solve duplicate elimination by noting that i ∈ b iff L[V/2 + i] = L[1]. Thus, in O(Scan(E)) extra time, we can find the array specifying which elements are present in b, thereby solving problem DE′ for b. The bound then follows, using Theorem 1 and Lemma 3 and noting that Scan(E) = o(\frac{E}{V} Sort(V).

4.1 Other Graph Problems

The lower bound in Theorem 3 actually applies to other problems such as biconnected components labelling, minimum spanning trees and their decision versions. Details are omitted from this abstract.

5 Upper Bounds for Connected Components

We first show how to implement Breadth First Search (BFS) in time O(\frac{E}{V} Sort(V) + V). This by itself is an optimal labelling algorithm for \frac{E}{V} ≥ BD. We then present a preprocessing step that transforms a labelling problem on V vertices to one on E/BD vertices. By running BFS after this we get a nearly optimal algorithm for sparse graphs as well.

5.1 Breadth First Search

We first convert the input to adjacency list form. This consists of two arrays P tr[1...V] and Adj[1...2E], with Adj[P tr[i]...P tr[i] + d_{i} − 1] holding the list of vertices adjacent to vertex i (d_{i} is the degree of vertex i). It is easily seen however that the conversion requires time O(\frac{E}{V} Sort(V)).

Our connected components algorithm based on breadth first search is shown below. The difference from the natural implementation is best explained by considering the execution for a connected graph. In this case, Front(t) as constructed by the algorithm is simply the set of vertices at distance t from the source (say vertex 1). On a RAM, it is customary to construct Front(t) by taking all the vertices that are adjacent to Front(t − 1) but which havent been marked visited. Here we proceed differently. For vertex x let Nbr(x) denote its neighbouring vertices. For a set of vertices X let Nbr(X) denote the multiset formed by concatenating Nbr(x) for all x ∈ X. We construct Front(t) by (1) constructing Nbr(Front(t−1)), (2) removing duplicates from it, (3) eliminating from it those elements that occur in Front(t − 1) ∪ Front(t − 2).

Algorithm 1: Breadth First Search

(1) for i = 1 to V do L[i] = 0

(2) Front(−1) = Front(−2) = null

(3) t = l = 0

(4) while Front(t − 1) is nonempty or unvisited vertices exist

(5) if Front(t − 1) is empty

(6) Front(t) = next unvisited vertex

(7) l = l + 1

(8) else

(9) Nbr(t) = concatenation of adjacency lists of vertices in Front(t − 1).

(10) Remove duplicates from Nbr(t).

(11) Front(t) = vertices in Nbr(t) not in Front(t − 1) ∪ Front(t − 2)

(12) for all v ∈ Front(t) do L[v] = l

(13) t = t + 1

(14) endwhile

Because of the adjacency list representation the total time spent in concatenating the lists (step 9 above) over the course of the entire algorithm is at most ∑_{v∈V} ⌈\frac{Nbr(v)}{BD}⌉ = \frac{E}{BD} +V = Scan(E)+V. The time for duplicate elimination is

∑_{t} ⌈\frac{|Nbr(Front(t))|}{V} Sort(V)⌉ = \frac{∑_{t} Nbr(Front(t))}{V} Sort(V) + V = O (\frac{E}{V} Sort(V) + V )

since each edge occurs at most twice in the sum. To eliminate from Nbr(t) those elements that occur in Front(t − 1) ∪ Front(t − 2), we simply need to scan through these (sorted) lists. But ∑_{t} Nbr(t) = O(E), and ∑_{t} Front(t) = V. Thus the time for scanning is clearly O(Scan(E) + V), with the term V again accounting for the possible round off.

Finally, we need to mark each vertex as visited, and scan through the vertices in step 6; the total time for this is clearly O(V). The total time is thus O(\frac{E}{V} Sort(V) + V).

5.2 Preprocessing

The preprocessing phase is based on a PRAM algorithm for computing connected components due to Cole and Vishkin[4]. This in turn uses an idea from the algorithm due to Chin et al[3] (lines 6–9). The basic step in Chin et al’s algorithm (originally due to Hirschberg) is to (a) identify a group of vertices as being in the same connected component (b) identify a leader vertex from the group, (c) move edges incident on every vertex in the group to the leader. In the preprocessing phase, we simply repeat this step several times while keeping track of the leader for each vertex. Clearly if we now find a labelling for the graph induced by the remaining leaders we can construct a labelling for all the vertices.

The following terminology is useful. A leader is passive if it spans a complete component, else it is active. The size of a leader is the number of vertices having it as their leader. Edges connecting distinct leaders are active, otherwise passive.

Algorithm 2: Preprocessing

(1) Make each vertex its own leader: for each vertex v set L(v) = v.

(2) for i = 1 to log_{1.5} log \frac{V BD}{E}

(3) Let n_{i} be the size of the smallest size active leader. If n_{i} = 1, then exit.

(4) For each active leader, choose upto d = \sqrt{n_{i}} active edges. If fewer than d active edges are available, choose all of them. From these edges form a graph G_{i} on the active leaders.

(5) for j = 1 to log d

(6) For each active leader v set L(v) = smallest neighbour of v in G_{i}. This partitions active leaders into pseudotrees.

(7) Use pointer doubling to identify the smallest numbered supervertex min(T) in each pseudotree T.

(8) For each v in each pseudotree T set L(v) = min(T).

(9) Replace each active edge (u, v) in G_{i} with an edge (L(u), L(v)).

(10) endfor

(11) Replace each active edge (u, v) in G with an edge (L(u), L(v)).

(12) endfor

We first estimate the number of active leaders at the end. Consider any single component. A single iteration of Chin et al’s algorithm (steps 6–9) halves the number of active leaders[3]. Thus log d iterations reduce the number of active leaders by a factor d = \sqrt{n_{i}} (if the number of leaders reduced to 1, then the leader is inactive– in fact the leader is itself the label for the component). Thus we know that n_{i+1} ≥ dn_{i} = n_{i}^{3/2}. Given that n_{1} ≥ 2, we see that if some leader is active after k iterations of the outer loop (steps 3–11) its size must be at least 2^{1.5^{k}}. For k = log_{1.5} log V BD/E this is V BD/E. Thus the number of active leaders is no more than E/BD, as claimed.

5.3 Running Time

Step 1 clearly takes time Scan(V). For step 3, the size of each vertex can be computed using a histogram operation (see section 3.2). To determine if a vertex is active, we simply need to know if there are nontrivial (non self loop) edges incident on it. This can be done by a suitable duplicate elimination problem. For step 4, we first number the edges incident on each vertex (done using multiprefix of section 3.2), and collect together those with number at most d. We also collect together the relevant entries from the array L, to prepare the data structures of graph G_{i} for the loop in lines 5–10. Step 11 is just a table lookup, and can be done using the ideas of section 3.2. All these operations can be done in time O(\frac{E}{V} Sort(V)).

To estimate the time for steps 6–9, let V_{i} and E_{i} respectively be the number of vertices and edges in G_{i}. Steps 7–8 are analyzed by Chiang et al[2], who show that these can be done in time O(Sort(V_{i})).^{2} Step 6 can be done by a multiprefix, step 9 is similar to step 12. Both these can be done in time O(\frac{E_{i}}{V_{i}} Sort(V_{i})). Noting that E_{i} ≤ V_{i}\sqrt{n_{i}} and V_{i} ≤ V/n_{i}, the time for a single iteration of lines 6–9 is O(\sqrt{n_{i}} Sort(V_{i})) = O(\frac{Sort(V)}{\sqrt{n_{i}}}). Thus the time for the entire loop 5–10 is clearly O(Sort(V)).

Thus the time for a single iteration of lines 3–11 is O(\frac{E}{V} Sort V).

5.4 Final Algorithm

The total time is for preprocessing is thus O(max(1, log log \frac{V BD}{E})\frac{E}{V} Sort V). The number of vertices left after preprocessing is clearly min(V, \frac{E}{BD}). When BFS is run on this the time required is O(\frac{E}{V} Sort V + \frac{E}{BD}) = O(\frac{E}{V} Sort(V)). Thus the time is O(max(1, log log \frac{V BD}{E})\frac{E}{V} Sort V).

References

[1] Lars Arge, Mikael Knudsen, and Kirsten Larsen. A general lower bound on the I/O-complexity of comparison-based algorithms. In The Third Workshop on Algorithms and Data Structures(WADS’93), 1993.

[2] Yi-Jen Chiang, Michael Goodrich, Edward Grove, Roberto Tamassia, Darren Vengroff, and Jeff Vitter. External-memory graph algorithms. In The 6th SIAM-ACM Symposium on Discrete Algorithms(SODA’95), pages 139–149, 1995.

[3] F. Y. Chin, J. Lam, and I. Chen. Efficient parallel algorithms for some graph problems. Communications of the ACM, 25(9):659–665, 1982.

[4] R. Cole and U. Vishkin. Approximate parallel scheduling Part II: Applications To Optimal Parallel graph algorithms in in logarithmic time. Information and Computation, 92(1):1–47, 1991.

[5] Vijay Kumar and Eric Schwabe. Improved data structures and algorithms for solving graph problems in external memory. In Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing, pages 169–176, 1996.

[6] Abhiram G. Ranade, Sandeep N. Bhatt, and S. Lennart Johnsson. The Fluent Abstract Machine. In Proceedings of the Fifth MIT Conference on Advanced Research in VLSI, pages 71–94, March 1988. Also available as Yale Univ. Comp. Sc. TR-573.

[7] Jeff Vitter and E. A. M. Shriver. Algorithms for parallel memory I: Two-level memories. Algorithmica, 12:110–147, 1994.

2Actually, Chiang et al’s connected algorithm is simply log V/M iterations of this loop for the original graph G.

We could use their analysis completely, but our analysis is slightly tighter.