REALIZING DEGREE SEQUENCES IN PARALLEL^{∗}

SRINIVASA R. ARIKATI^{†} AND ANIL MAHESHWARI^{‡}

Abstract. A sequence d of integers is a degree sequence if there exists a (simple) graph G such that the components of d are equal to the degrees of the vertices of G. The graph G is said to be a realization of d. We provide an efficient parallel algorithm to realize d; the algorithm runs in O(log n) time using O(n + m) CRCW PRAM processors, where n and m are the number of vertices and edges in G. Before our result, it was not known if the problem of realizing d is in NC.

Key words. design and analysis of algorithms, parallel computation, graph algorithms, degree sequence, majorization, PRAM

AMS subject classifications. 68Q22, 68R10

1. Introduction.

1.1. Problem Definition. An important problem in graph algorithms is to compute a (simple undirected) graph satisfying the given degree constraints. An integer sequence d of length n is called a degree sequence if there exists a graph G on n vertices such that the degrees of its vertices are equal to the components of the sequence d. The graph G is said to be a realization of the sequence d. A pair (r, s) of integer sequences is called a bipartite sequence if there exists a bipartite graph H = (X∪Y, E) such that the components of r (respectively, s) are equal to the degrees of the vertices in X (respectively, Y). Degree sequences and bipartite sequences have been extensively studied in graph theory [6, 15, 21, 26]. Because of the strong connections between the structural properties of a graph and the degrees of its vertices, these sequences find significant applications in the areas of communication networks, structural reliability, and stereochemistry (cf. [7, 26]).

1.2. Previous Results. Given an integer sequence d, there are two problems of interest: the decision problem is to test if d is realizable; the search problem is to compute a realization of d. A characterization of degree sequences known as the Erdős-Gallai inequalities [10] results in an efficient sequential algorithm for the decision problem. Another characterization called the Havel-Hakimi characterization (cf. [15]) leads to an efficient sequential algorithm for the search problem. In the case of bipartite sequences, a characterization known as the Gale-Ryser theorem [13, 22, 24] leads to efficient sequential algorithms for the decision as well as the search problems. Recently, degree sequence problems have gained lot of attention, see for example [2, 3, 4, 9, 21, 23, 25, 26].

The Erdős-Gallai inequalities and the Gale-Ryser theorem imply efficient parallel algorithms for the decision problems on degree sequences and bipartite sequences, respectively. Recently, a parallel algorithm for a special case of the search problem, in which the maximum degree is bounded by the square-root of the sum of the degrees, is presented in [9]; it runs in O(log^{4} n) time using O(n^{10}) EREW PRAM processors.

∗ This work is partially supported by the EEC ESPRIT Basic Research Action No. 7141 (ALCOM II). A part of this paper appeared in 5th International Symposium on Algorithms and Computation, China, 1994.

† MPI Informatik, Im Stadtwald, 66123 Saarbrücken, Germany (arikati@mpi-sb.mpg.de).

‡ MPI Informatik, Germany. Author’s current address: School of Computer Science, Carleton University, Ottawa, Ontario K1S 5B6, Canada (maheshwa@chaos.scs.carleton.ca).

Network-flow based proofs [11, 12] give rise to randomized parallel algorithms for the search problems on degree sequences and bipartite sequences.

1.3. Our Results. The main contributions of this paper are deterministic parallel algorithms for the search problems on degree sequences and bipartite sequences. Our results are:

• An efficient parallel algorithm for realizing bipartite sequences; it runs in O(log n) time using O(n) EREW PRAM processors, where n is the number of vertices in the realization.

• A new proof of a relation between degree sequences and bipartite sequences.

• An efficient parallel algorithm for realizing degree sequences; it runs in O(log n) time using O(n + m) CRCW PRAM processors, where n and m denote the number of vertices and edges in the realization.

The complexity results of this paper are with respect to the PRAM computational model. For details on the PRAM and NC, see [18, 19]. The work, i.e. time×processor product, of our parallel algorithm for realizing bipartite sequences is o(n^{2}), whereas there are bipartite graphs that have Ω(n^{2}) edges (e.g. a complete bipartite graph on n vertices). The complexity results of this paper are feasible since the graphs computed by our algorithms possess implicit representations, i.e., the graphs can be stored in O(n) space, and the adjacency information between any two vertices can be reported in constant time [27].

Our result for realizing bipartite sequences is based on a non-trivial parallelization of the techniques from the theory of majorization [16, 22]. Our algorithm for realizing a degree sequence d is based on a new proof of a relation between degree sequences and bipartite sequences and it proceeds as follows. From d, we compute an appropriate bipartite sequence (c, c), and then compute a realization H of (c, c). Using the graph H, we compute a symmetric bipartite graph that leads to a realization of d. The computation of the symmetric bipartite graph from H is the crucial step, for which we provide two alternate parallel algorithms: the first one has higher complexity than the second. The latter algorithm exploits the implicit structure of the bipartite graph H computed by our algorithm and thus is efficient. The former algorithm does not assume any structural knowledge of H, and can work with any realization of (c, c). It is based on several interesting lemmas, which may be of independent interest in their own right.

1.4. Organization of the Paper. The rest of the paper is organized as follows. In Section 2 we introduce notation and state preliminaries. In Section 3 we state some of the classical characterizations of degree sequences and present simple algorithms for realizing the degree sequences corresponding to multigraphs and trees. In Section 4 we prove a relation between degree sequences and bipartite sequences. In Section 5 we present the required results from the theory of majorization, including an algorithm for computing unit transformations. In Section 6 we present a parallel algorithm for realizing bipartite sequences. In Section 7 we provide parallel algorithms for realizing degree sequences.

2. Preliminaries.

2.1. Basic Definitions. In a multigraph G = (V, E), V is a set of vertices and E is a multiset of edges (multiple edges may exist between two vertices but no self-loops). By a graph G = (V, E), we mean a simple graph—without multiple edges and selfloops. A bipartite graph H with the bipartition X ∪ Y is denoted by H = (X ∪ Y, E). In a multigraph G = (V, E), d_{G}(v) denotes the degree of a vertex v and N_{G}(v) denotes the multiset of the neighbors of v (we omit the subscript, if no confusion arises). Similarly, N_{G}(U) is defined as the union of the neighbors of the vertices of U ⊆ V. By definition, G is a graph if and only if the following hold for all v ∈ V:

(i) v ∉ N_{G}(v) and (ii) N_{G}(v) is a set. If (u, v) is an edge of a graph G, we say that (u, v) ∈ G. Throughout, by a sequence we mean a sequence of nonnegative integers.

2.2. Graph Matching. A matching M in a graph G = (V, E) is a collection of edges such that no two edges of M are incident at a common vertex. The size of M, denoted by |M|, is the number of edges in it. M is called a perfect matching if it matches all vertices of G. M is called a maximum matching if it has maximum size among all matchings. M is called a maximal matching if no other matching properly contains M. We will need the following theorem due to P. Hall (cf. [21]).

Theorem 2.1 (The Hall’s Theorem). Let H = (X∪Y, E) be a bipartite graph. Then H has a matching that matches all vertices of X, if and only if |N(A)| ≥ |A| for every A ⊆ X.

We need the following two lemmas; the first lemma can be proved easily.

Lemma 2.2. Let M (respectively, M′) be a maximal (respectively, maximum) matching in a graph G. Then |M| ≥ \frac{1}{2}|M′|.

Lemma 2.3. Let H = (X ∪ Y, E) be a bipartite graph such that (i) d(x) ≥ 1 for all x ∈ X and (ii) the inequality d(x) ≥ d(y) holds for every edge (x, y) of H. Then H has a matching that matches all vertices of X.

Proof. We show that H satisfies the sufficiency part of the Hall’s theorem. We use induction on |A|, where A ⊆ X. Since d(x) ≥ 1 for all x ∈ X, the basis case, |A| = 1, follows. Consider now the case that |A| = k, where k ≥ 2. We need to prove that |N(A)| ≥ k. Assume the contrary, namely that |N(A)| < k. Pick any vertex z ∈ A and put A′ = A − z. By induction, |N(A′)| ≥ k − 1. Since N(A′) ⊆ N(A), it follows (A′) = N(A) and |N(A′)| = |N(A)| = k − 1. Consider now the subgraph H′ = (A′ ∪ N(A′), E′) of H. By induction, H′ satisfies the sufficiency condition of the Hall’s theorem and hence has a perfect matching. Let the edges of the perfect matching be (x_{1}, y_{1}), (x_{2}, y_{2}), …, (x_{k−1}, y_{k−1}). Using condition (ii) of the lemma, we obtain ∑_{x∈A′} d(x) = ∑_{i=1}^{k−1} d(x_{i}) ≥ ∑_{i=1}^{k−1} d(y_{i}) = ∑_{y∈N(A′)} d(y). Since d(z) ≥ 1 and N(A) = N(A′), we have ∑_{x∈A} d(x) > ∑_{y∈N(A)} d(y), which contradicts ∑_{x∈A} d(x) ≤ ∑_{y∈N(A)} d(y); the latter inequality holds for any bipartite graph because every edge incident to a vertex in A contributes a 1 to both sides of the inequality. This completes the induction step and hence the lemma.

2.3. Digraphs. In a digraph D = (V, E), E is the set of arcs (directed edges); the arc from u to v will be denoted by the ordered pair (u, v). The indegree (respectively, outdegree) of a vertex v, denoted by d_{D}^{−}(v) (respectively, d_{D}^{+}(v)), is the number of arcs into (respectively, from) v. Call D symmetric if it has only symmetric arcs: (u, v) is an arc if and only if (v, u) is an arc. We will require the following lemma.

Lemma 2.4. ([12]) Let D̃ = (V, Ẽ) be a digraph such that indegree of each vertex v equals its outdegree, i.e., d− ; D̃(v) = d+ ; D̃(v) = d(v), and that ∑_{v∈V} d+ ; D̃(v) is even. Then there exists a symmetric digraph D = (V, E) such that d_{D}^{−}(v) = d_{D}^{+}(v) = d(v).

Proof. If D̃ is symmetric, then take D := D̃. Assume that D̃ is not symmetric and let D̂ = (V, Ê) be the ‘asymmetric part’ of D̃: (u, v) ∈ Ê iff (u, v) ∈ Ẽ and (v, u) ∉ Ẽ. Observe that d− ; D̂(v) = d+ ; D̂(v) for all v ∈ V. Define a trail to be a sequence of (not necessarily distinct) vertices v_{1}, …, v_{k}, v_{1} such that (v_{1}, v_{2}), (v_{2}, v_{3}), …, (v_{k−1}, v_{k}), (v_{k}, v_{1}) are distinct arcs of D̂. Call a trail even if it consists of an even number of edges, otherwise it is an odd trail.

Assume that D̂ has an even trail, say v_{1}, v_{2}, …, v_{2k}, v_{1}. Change D̃ as follows: Delete the arcs (v_{2}, v_{3}), (v_{4}, v_{5}), …, (v_{2k−2}, v_{2k−1}), (v_{2k}, v_{1}) and add the arcs (v_{2}, v_{1}), (v_{4}, v_{3}), …, (v_{2k−2}, v_{2k−3}), (v_{2k}, v_{2k−1}). Notice that this process does not create any multiple arcs or self-loops in D̃. Further, the hypothesis of the lemma is maintained. We repeat the above-mentioned process until D̂ contains no even trails. Then, it follows that ∑_{v∈V} d+ ; D̂(v) is even as ∑_{v∈V} d+ ; D̃(v) is even. Further, using d− ; D̂(v) = d+ ; D̂(v) for v ∈ V, we can decompose the arcs of D̂ into odd directed cycles. There are an even number of such cycles. Moreover, any two such cycles must be vertex-disjoint, otherwise they create an even trail. Let u_{0}, u_{1}, …, u_{2k}, u_{0} and v_{0}, v_{1}, …, v_{2ℓ}, v_{0} be any two odd cycles in Ĝ. The fact that (u_{0}, v_{0}) ∉ D̂ implies that either both (u_{0}, v_{0}) and (v_{0}, u_{0}) are arcs in D̃ or none is an arc in D̃. We distinguish between these two cases. Case 1: Both (u_{0}, v_{0}) and (v_{0}, u_{0}) are arcs in D̃. Change D̃ as follows: Delete the arcs (u_{0}, v_{0}), (v_{0}, u_{0}), (u_{1}, u_{2}), (u_{3}, u_{4}), …, (u_{2k−1}, u_{2k}) and (v_{1}, v_{2}), (v_{3}, v_{4}), …, (v_{2ℓ−1}, v_{2ℓ}); add the arcs (u_{2}, u_{1}), (u_{4}, u_{3}), …, (u_{2k}, u_{2k−1}) and (v_{2}, v_{1}), (v_{4}, v_{3}), …, (v_{2ℓ}, v_{2ℓ−1}). Case 2: None of (u_{0}, v_{0}) and (v_{0}, u_{0}) is an arc in D̃. Change D̃ as follows: Delete the arcs (u_{0}, u_{1}), (u_{2}, u_{3}), …, (u_{2k}, u_{0}), and (v_{0}, v_{1}), (v_{2}, v_{3}), …, (v_{2ℓ}, v_{0}); add the arcs (u_{0}, v_{0}), (v_{0}, u_{0}), (u_{2}, u_{1}), (u_{4}, u_{3}), …, (u_{2k}, u_{2k−1}) and (v_{2}, v_{1}), (v_{4}, v_{3}), …, (v_{2ℓ}, v_{2ℓ−1}). In each case no multiple arcs or self-loops are created, and the number of odd cycles in D̃ decreases. Eventually, D̃ contains no odd cycles and hence it becomes symmetric. The proof is completed by taking D := D̃.

2.4. Parallel Techniques. The complexity results of this paper are with respect to the PRAM. This is the synchronous parallel model in which all processors share a common memory. In this paper, we need the following techniques previously developed in parallel computing: Euler tour in a graph [5], merging and cross-ranking [14], sorting [8], maximal matching in a graph [17]. For other techniques such as parallel prefix and list ranking, see [18, 19].

Consider a sequence of n elements {x_{1}, x_{2}, ..., x_{n}} drawn from a set S with a binary associative operation ∗. The prefix sums of this sequence are the n partial sums (or products) defined by s_{i} = x_{1} ∗ x_{2} ∗ ...x_{i}, 1 ≤ i ≤ n. Consider a linked list L of n nodes whose order is specified by an array S such that S(i) contains a pointer to the node following node i on L, for 1 ≤ i ≤ n. We assume S(i) = 0 when i is the end of the list. The list ranking problem is to determine the distance of each node i from the end of the list. The rank of an element x in a given sequence X is the number of elements of X that are less than or equal to x. Let A and B be two sorted sequences. The cross-ranking problem is to find the rank of each element of A in B and vice-versa.

3. Characterizations and Algorithmic Aspects.

3.1. Multigraphs. Realizability problems, in general, tend to be simpler if multiple edges are allowed. We show that this is the case in parallel computation too. We first discuss realizing degree sequences of bipartite multigraphs and then show how to reduce the general case to the bipartite case. Recall that in a multigraph, multiple edges may exist between a pair of vertices but self-loops are not allowed.

Let (r, s), where r = (r_{1}, …, r_{m}) and s = (s_{1}, …, s_{n}), be a pair of sequences. Our problem is to compute a bipartite multigraph H = (X ∪ Y, E) satisfying the degree constraints r and s. It is easy to prove that H exists if and only if ∑_{i=1}^{m} r_{i} = ∑_{j=1}^{n} s_{j}.

To realize (r, s) in parallel, test if ∑_{i=1}^{m} r_{i} = ∑_{j=1}^{n} s_{j} and stop if the test fails. Then, compute the prefix sums of r and s and store them in the arrays R and S, respectively. Cross-rank S in R using the algorithm of [14]. Connect y_{j} to all the corresponding x_{i}’s using the required number of multiple edges.

We now discuss the general case. Given a sequence d, the problem is to compute a multigraph with degree sequence d. The following lemma characterizes d [6, 15, 21]. The proof given below results in a simple parallel algorithm.

Lemma 3.1. The sequence d = (d_{1}, …, d_{n}), where d_{1} = max(d), is the degree sequence of a multigraph if and only if ∑_{i=1}^{n} d_{i} is even and d_{1} ≤ ∑_{i=2}^{n} d_{i}.

Proof. We prove the sufficiency part, the other part being trivial. Sort the sequence d into nonincreasing order, i.e., let d_{1} ≥ d_{2} ≥ ⋯ ≥ d_{n}. Let v_{1}, v_{2}, …, v_{n} be the vertices of the multigraph G to be computed. Put m = \frac{1}{2} ∑_{i=1}^{n} d_{i} and let p be the index such that ∑_{i=1}^{p} d_{i} ≤ m < ∑_{i=p+1}^{n} d_{i}. We distinguish between two cases. Case 1: ∑_{i=1}^{p} d_{i} = m. Define sequences r and s by r = (d_{1}, d_{2}, …, d_{p}) and s = (d_{p+1}, …, d_{n}). Then r and s have the same component sum and thus (r, s) can be realized, using the procedure given above, as a bipartite multigraph G = (X ∪ Y, E), where X = {v_{1}, …, v_{p}} and Y = {v_{p+1}, …, v_{n}}. Case 2: ∑_{i=1}^{p} d_{i} < m. Put k = ∑_{i=p+1}^{n} d_{i} − m and define sequences r and s as follows: r = (d_{1} − k, d_{2}, …, d_{p}, d_{p+1} − k) and s = (d_{p+2}, …, d_{n}). Then r and s have the same component sum (= m−k) and thus (r, s) can be realized, using the procedure given above, as a bipartite multigraph H = (X ∪ Y, E), where X = {v_{1}, …, v_{p+1}} and Y = {v_{p+2}, …, v_{n}}. By adding k multiple edges between v_{1} and v_{p+1} in H we get the required multigraph G.

3.2. Trees. We now discuss the degree sequences of trees. The following characterization of such sequences is well known [6, 15, 21]. We will present a proof that leads to a simple parallel algorithm to realize these sequences.

Lemma 3.2. The sequence d = (d_{1}, …, d_{n}) is the degree sequence of a tree if and only if all d_{i}’s are positive and ∑_{i=1}^{n} d_{i} = 2n − 2.

Proof. The necessity part is trivial and we prove the other part. Sort the sequence d into nonincreasing order; denote the resulting sequence also by d. Let v_{1}, v_{2}, …, v_{n} be the vertices of the tree G to be computed. If d_{1} = 2 then G is a path and we are done. So assume that d_{1} ≥ 3 and let k be the largest index such that d_{k} ≥ 3. Put m = ∑_{i=1}^{k}(d_{i} − 2). Let A be the set of d_{i}’s that are equal to 1. The following claim will be proved after we describe the computation of G.

Claim: |A| = m + 2.

First we compute a path consisting of vertices v_{n−1}, v_{1}, v_{2}, …, v_{n−m−2}, v_{n}^{1}. Delete v_{n} and v_{n−1} from A. Then we compute ‘stars’ using A and v_{1}, v_{2}, …, v_{k} as follows: Connect the first d_{1} − 2 vertices of A to v_{1}, connect the next d_{2} − 2 vertices of A to v_{2}, …, and connect the remaining d_{k} − 2 vertices of A to v_{k}. This completes the computation of G.

We now prove the above claim. Observe that ∑_{i=1}^{k} d_{i} = m+2k and that there are n−k−|A| d_{i}’s that are equal to 2. So 2n−2 = ∑_{i=1}^{n} d_{i} = m+2k+2(n−k−|A|)+|A|. The claim follows by rearranging the terms.

3.3. Graphs. We now discuss degree sequences of graphs. Let d be an integer sequence of length n, where n > d_{1} ≥ d_{2} ≥ ⋯ ≥ d_{n} ≥ 0. The proofs of the following results may be found, e.g., in [6, 15, 21].

1 Observe that d_{n−1} = d_{n} = 1.

The Erdős-Gallai Inequalities (EGI): The sequence d is realizable if and only if ∑_{i=1}^{n} d_{i} is even and ∑_{i=1}^{k} d_{i} ≤ k(k − 1) + ∑_{i=k+1}^{n} min(d_{i}, k) for k = 1, 2, …, n.

The Havel-Hakimi Characterization: The sequence d is realizable if and only if the numbers d_{2} − 1, d_{3} − 1, …, d_{d_{1}+1} − 1, d_{d_{1}+2}, …, d_{n} are realizable.

Using EGI, we can test if d is realizable in linear time. We can use the second characterization to derive an efficient sequential algorithm to compute a realization of d.

In parallel computation, the inequalities of EGI can be tested optimally, and this implies an optimal parallel algorithm to test if d is a degree sequence. As for the problem of computing a realization of d, a proof of the EGI using network flows is given in [12] and this proof results in a randomized parallel algorithm. The proof consists of two steps. Step 1: Define a network with edge capacities in unary and solve the maximum flow problem on this network; then, construct a digraph D. Step 2: Obtain a symmetric digraph from D. Results of [20] imply a randomized parallel algorithm for Step 1. Based on the proof of Lemma 2.4, Step 2 can be performed in NC.

4. Degree Sequences and Bipartite Sequences. We study in this section a relation between degree sequences and bipartite sequences. The main result of this section is a new proof of a theorem given in [25]. The proof presented in [25] is via a cycle of eight implications and results in an inherently sequential algorithm to compute realizations of degree sequences, whereas our proof is simple and helps us to design a parallel algorithm.

Throughout this section, d denotes an integer sequence of length n, where n > d_{1} ≥ d_{2} ≥ ⋯ ≥ d_{n} ≥ 0. Let μ = max{k : d_{k} ≥ k}. Define a new sequence c = (c_{1}, …, c_{n}), where

c_{i} = \{ \begin{matrix}d_{i} + 1 & if i ≤ μ \\ d_{i} & otherwise. \end{matrix}

Observe that c_{i} = d_{i} + 1 ≥ μ + 1 for 1 ≤ i ≤ μ and c_{j} = d_{j} ≤ μ for μ + 1 ≤ j ≤ n.

Theorem 4.1. The sequence d is a degree sequence if and only if (c, c) is a bipartite sequence.

Before we prove this theorem, we remark that the ‘+1’ is required in the definition of c, since there are sequences d such that (d, d) is a bipartite sequence but d is not a degree sequence; for example, take d = (4, 2, 2, 2). The proof is based on the following lemmas.

Lemma 4.2. If d is a degree sequence then (c, c) is a bipartite degree sequence. Proof. Let G = (V, E) be a realization of d. We obtain a bipartite realization

H = (X ∪ Y, E′) of (c, c) as follows: X and Y are two copies of V; if (v_{i}, v_{j}) ∈ G then (x_{i}, y_{j}), (x_{j}, y_{i}) ∈ H; further, (x_{i}, y_{i}) ∈ H for all 1 ≤ i ≤ μ.

We need a few definitions before presenting the next lemmas. Let H = (X ∪Y, E) be a realization of (c, c). A vertex x_{i} (or y_{i}) is called a high-degree vertex if 1 ≤ i ≤ μ, otherwise it is a low-degree vertex. An edge (x_{i}, y_{i}) is called a high-degree edge if 1 ≤ i ≤ μ. Similarly, an edge (x_{j}, y_{j}) is called a low-degree edge if μ + 1 ≤ j ≤ n. Edges of the form (x_{i}, y_{j}), where i ≠ j, are neither high-degree edges nor low-degree edges. High-degree and low-degree edges play a very important role in our algorithms.

A pair of edges (x_{α}, y_{β}) and (x_{γ}, y_{δ}) form an exchange pair if (x_{α}, y_{δ}), (x_{γ}, y_{β}) ∉ H (see Figure 1). An exchange on the edges (x_{α}, y_{β}) and (x_{γ}, y_{δ}) consists of deleting (x_{α}, y_{β}) and (x_{γ}, y_{δ}) and inserting (x_{α}, y_{δ}) and (x_{γ}, y_{β}). The following two lemmas imply that, given any realization H of (c, c), we can always obtain another realization H′ such that H′ contains all high-degree edges and no low-degree edges.

[figure: x_{γ}; x_{α}; y_{δ}; y_{β}; ⟹; x_{γ}; x_{α}; y_{δ}; y_{β}]

Fig. 1. An exchange operation. A solid line indicates the presence of an edge and a dashed line its absence.

Lemma 4.3. Let H be a realization of (c, c) such that (x_{i}, y_{i}) ∉ H for some 1 ≤ i ≤ μ. Then there exist k and ℓ such that (x_{i}, y_{k}) and (x_{ℓ}, y_{i}) form an exchange pair, where k > μ and k ≠ ℓ.

Proof. Since c_{i} ≥ μ+1 there exists a k such that k > μ and (x_{i}, y_{k}) ∈ H. Further, c_{k} ≤ μ and c_{i} ≥ μ + 1 imply that there exist an ℓ ≠ k such that (x_{ℓ}, y_{i}) ∈ H and (x_{ℓ}, y_{k}) ∉ H.

Lemma 4.4. Let H be any realization of (c, c) such that (x_{j}, y_{j}) ∈ H for some j > μ. Then there exist k and ℓ such that (x_{j}, y_{j}) and (x_{ℓ}, y_{k}) form an exchange pair, where k ≤ μ and k ≠ ℓ.

Proof. Since c_{j} ≤ μ there exists a k such that k ≤ μ and (x_{j}, y_{k}) ∉ H. Further, c_{k} ≥ μ + 1 implies that there exists an ℓ ≠ k such that (x_{ℓ}, y_{k}) ∈ H and (x_{ℓ}, y_{j}) ∉ H.

Lemma 4.5. If (c, c) is a bipartite degree sequence then d is a degree sequence. Proof. Let H be any realization of (c, c). Assume that (x_{i}, y_{i}) ∉ H for some

1 ≤ i ≤ μ. Let k and ℓ be as defined in Lemma 4.3. Perform an exchange, by deleting the edges (x_{i}, y_{k}) and (x_{ℓ}, y_{i}) and adding the edges (x_{i}, y_{i}) and (x_{ℓ}, y_{k}). Observe that this process does not destroy any existing high-degree edges in H. We repeat this process until H contains all high-degree edges. Assume now that H contains a low-degree edge, say (x_{j}, y_{j}) for some j > μ. Let k and ℓ be as defined in Lemma 4.4. Delete the edges (x_{j}, y_{j}) and (x_{ℓ}, y_{k}) and add the edges (x_{j}, y_{k}) and (x_{ℓ}, y_{j}). Observe that this process does not destroy any existing high-degree edges and does not create any new low-degree edges in H. We repeat this process until H contains no low-degree edges.

Define a digraph D̃ = (V, Ẽ) on the vertex set V = {v_{1}, …, v_{n}}, where (v_{i}, v_{j}) ∈

D̃ iff (x_{i}, y_{j}) ∈ H and (x_{j}, y_{i}) ∉ H. Then d− ; D̃(v_{i}) = d+ ; D̃(v_{i}) = d_{i} for all 1 ≤ i ≤ n. By

Lemma 2.4, we obtain a symmetric digraph D = (V, E) such that d_{D}^{−}(v_{i}) = d_{D}^{+}(v_{i}) = d_{i} for all i. Obtain an undirected graph G from D by replacing the two symmetric arcs (v_{i}, v_{j}) and (v_{j}, v_{i}) with the edge (v_{i}, v_{j}). Then G is a realization of d.

Lemmas 4.2 and 4.5 imply Theorem 4.1. It is fairly easy to see that the proof of Lemma 4.5 implies a simple sequential algorithm to realize d from any realization of (c, c). In Section 7, parallel algorithms to achieve the same objective will be presented.

5. Majorization and Unit Transformations. Throughout this section, let a = (a_{1}, …, a_{n}) and b = (b_{1}, …, b_{n}) be sequences of length n, where a_{1} ≥ a_{2} ≥ ⋯ ≥ a_{n} ≥ 0 and b_{1} ≥ b_{2} ≥ ⋯ ≥ b_{n} ≥ 0.

5.1. Majorization. Majorization has been studied, over several decades, in the theory of inequalities [22, 16]. It captures the intuitive notion that the components of a vector are “less nearly equal” than are the components of another vector. Formally, we say that a majorizes b, denoted by a ⪰ b, if ∑_{i=1}^{k} a_{i} ≥ ∑_{i=1}^{k} b_{i} for k = 1, ..., n, with equality for k = n. For example, (4, 2, 1, 0) ⪰ (2, 2, 2, 1).

Majorization was used by economists in measuring inequality of incomes and in studying the principle of transfers (cf. [22]). If a_{i} ≥ a_{j} + 2 for some i and j, we say that the sequence c = (c_{1}, …, c_{n}), defined by c_{i} = a_{i} − 1, c_{j} = a_{j} + 1 and c_{k} = a_{k} for k ≠ i, j, is obtained from a by a unit transformation from i to j. Clearly, a ⪰ c. A classical result, known as the Muirhead Lemma (cf. [22]), states that the converse is also true: If a ⪰ b then a can be transformed to b by performing a finite number of (successive) unit transformations on a. The following lemma presents the details.

Lemma 5.1. Suppose that a ⪰ b. Define a sequence δ = (δ_{1}, …, δ_{n}) by δ_{i} = max{0, (a_{i} − b_{i})}, and define Δ(a, b) = ∑_{i=1}^{n} δ_{i}. Then a can be transformed to b by performing Δ(a, b) unit transformations. Further, Δ(a, b) equals the minimum number of unit transformations required to transform a to b.

Proof. If a = b then Δ(a, b) = 0. Assume that a ≠ b and let i be the smallest index such that a_{i} ≠ b_{i}. Observe that a_{i} > b_{i}, since a ⪰ b. Let j > i be the smallest index such that a_{j} < b_{j}. Define c to be the sequence obtained from a by performing a unit transformation from i to j. Clearly, a ⪰ c ⪰ b. By repeating this process on the sequence c, we can obtain b.

To prove the second part of the lemma, observe that if c is any sequence obtained from a by a unit transformation, then Δ(c, b) ≥ Δ(a, b) − 1.

5.2. An Algorithm for Computing Unit Transformations. In this subsection, we discuss the computation of unit transformations that are required to transform a to b. The basic idea is to compute the numbers t(i, j), for 1 ≤ i, j ≤ n, so that a can be transformed to b by performing t(i, j) unit transformations from position i to position j. We give an example to illustrate the idea. Example 1: Let a = (15, 12, 9, 8, 5, 4, 4, 0) and b = (11, 10, 9, 9, 9, 3, 3, 3). Put c = a − b = (4, 2, 0, −1, −4, 1, 1, −3) and define an array P (respectively, M) whose components are given by: P_{i} = max{0, c_{i}} (respectively, M_{i} = max{0, −c_{i}}) for 1 ≤ i ≤ 8, i.e., P = (4, 2, 0, 0, 0, 1, 1, 0) and M = (0, 0, 0, 1, 4, 0, 0, 3). Now, P_{1} and M_{4} are the left-most positive components of P and M, respectively. As M_{4} = 1 < P_{1}, we subtract 1 from P_{1} and M_{4} and add 1 to t(1, 4). Then P and M become (3,2,0,0,0,1,1) and (0,0,0,0,4,0,0,3), respectively. Now P_{1} and M_{5} are the left-most positive components of P and M and, as P_{1} = 3 < M_{5}, we subtract 3 from P_{1} and M_{5} and add 3 to t(1, 5). Then P and M become (0,2,0,0,0,1,1) and (0,0,0,0,1,0,0,3), respectively. We continue this process until all the components of P and M become 0’s, and we get t(1, 4) = 1, t(1, 5) = 3, t(2, 5) = t(2, 8) = t(6, 8) = t(7, 8) = 1.

A simple linear-time sequential algorithm, based on the procedure explained in the above example, for computing unit transformations is as follows. Compute the arrays P and M and then scan both the arrays from left to right, starting at the position i = 1 in P and j = 1 in M. In each step compute the appropriate t(i, j) and either increment i or j. Since the arrays P and M are scanned only once and the number of reported t(i, j)’s is linear, the algorithm runs in linear time.

A parallel implementation of this algorithm is presented in Algorithm 1. In Step 2 of the algorithm, P′[i] := ∑_{k=1}^{i} P [i] for 1 ≤ i ≤ n. Moreover the arrays P′ and M′ are obtained in the sorted order. After cross-ranking the elements of P′ in M′ and vice-versa, we know precisely the appropriate t(i, j)’s, for each value of i and j. For each value of i we can store the t(i, j)’s in an array, with respect to increasing j. Alternatively, we can store the t(i, j)’s in an n ∗ n matrix, without initializing the matrix, by a standard method (see [1]).

1. Compute c_{i} := a_{i} − b_{i} for 1 ≤ i ≤ n and the arrays P and M.

2. Compute prefix sums of P and M and store them in the arrays P′ and M′, respectively.

3. Cross-rank the arrays P′ and M′ by the algorithm of [14] and then compute t(i, j)’s. Algorithm 1: An algorithm for computing unit transformations.

Theorem 5.2. Let a and b be sequences of length n such that a ⪰ b. Algorithm 1 computes the numbers t(i, j), for 1 ≤ i, j ≤ n, such that a can be transformed to b by performing t(i, j) unit transformations from the position i to j in a. The algorithm runs in O(log n) time using O(n/log n) EREW PRAM processors.

Proof. The proof of correctness is straightforward. To analyze the complexity, note that the prefix sums and the cross ranking of two sorted arrays can be computed in O(log n) time using O(n/log n) processors.

5.3. Properties of Unit transformations. In this subsection we present properties of the numbers t(i, j) computed by Algorithm 1. These properties will be used to design a parallel algorithm for realizing bipartite sequences.

Observe t(i, j) = 0 whenever i ≥ j or a_{j} ≥ b_{j}. We need a few definitions to state additional properties of t(i, j)’s. For 1 ≤ i ≤ n, define A(i) to be the set of all j such that Algorithm 1 reports a unit transformation from i to j, i.e., A(i) = {j : t(i, j) ≠ 0} (see Example 2). Observe that A(i) = ∅ if and only if a_{i} ≤ b_{i}. Similarly, define B(j) = {i : t(i, j) ≠ 0}, and note that B(j) = ∅ if and only if a_{j} ≥ b_{j}. Furthermore, if k ∈ A(i) (respectively, B(j)), then k > i (resp. k < j) and a_{k} < b_{k} (respectively, a_{k} > b_{k}). The elements of A(i) and B(j) will always be listed in the increasing order. Example 2: In Example 1,

A(1) = {4, 5}, A(2) = {5, 8}, A(6) = A(7) = {8}; B(4) = {1}, B(5) = {1, 2}, B(8) = {2, 6, 7}; all other A(i)’s and B(j)’s are ∅.

Lemma 5.3.

1. If A(i) ≠ ∅, then a_{i} = b_{i} + ∑_{j∈A(i)} t(i, j).

2. If B(j) ≠ ∅, then b_{j} = a_{j} + ∑_{i∈B(j)} t(i, j).

Proof. Follows from the definition of t(i, j)’s in Algorithm 1. Let α(i) = min{A(i)}^{2}. For 1 ≤ i, j ≤ n, define (see Example 3)

β(i, j) = \{ \begin{matrix}0 & if i > j or a_{j} ≥ b_{j} \\ a_{j} + ∑_{k∈B(j),k≥i+1} t(k, j) & otherwise. \end{matrix}

2 By definition, max(∅) = 0 and min(∅) = ∞.

For 1 ≤ i ≤ n, define

γ(i) = \{ \begin{matrix}β(i + 1, α(i)) & if A(i) ≠ ∅ \\ 0 & otherwise. \end{matrix}

Example 3: In Example 2, α(1) = 4, α(2) = 5, α(6) = α(7) = 8; β(3, 5) = β(4, 5) = β(5, 5) = a_{5} = 5, β(1, 5) = a_{5} + t(2, 5) = 5 + 1 = 6;

γ(1) = β(2, α(1)) = β(2, 4) = β(3, 4) = β(4, 4) = a_{4} = 8.

Lemma 5.4. Let j be an integer such that the elements of B(j) are i_{1}, i_{2}, …, i_{k}, where k ≥ 2. Then A(i_{q}) = {j} for all 2 ≤ q ≤ k − 1, and α(i_{p}) = j for all 2 ≤ p ≤ k.

Proof. Follows from definitions.

Lemma 5.5. Let j be an integer such that the elements of B(j) are i_{1}, i_{2}, …, i_{k}, where k ≥ 2. Then γ(i_{k}) = a_{j} and γ(i_{p}) = a_{j} + ∑_{q=p+1}^{k} t(i_{q}, j) for all 2 ≤ p ≤ k − 1. Furthermore, if α(i_{1}) = j, then γ(i_{1}) = γ(i_{2}) + t(i_{2}, j).

Proof. By Lemma 5.4, γ(i_{k}) = j. So γ(i_{k}) = β(i_{k} + 1, j)) = a_{j}; the second equality follows from the fact that t(ℓ, j) = 0 for ℓ ≥ i_{k} + 1. Consider now any p such that 2 ≤ p ≤ k − 1. We have

γ(i_{p}) = β(i_{p+1} + 1, α(i_{p}))
= β(i_{p+1} + 1, j)  (by Lemma 5.4)
= a_{j} + ∑_{q=i_{p+1}}^{k} t(i_{q}, j).

The proof of the remaining part is similar.

6. Realizing Bipartite Sequences. We present in this section a parallel algorithm for computing a bipartite graph that realizes a given pair of sequences. Throughout this section, X = {x_{1}, x_{2}, …, x_{m}}, Y = {y_{1}, y_{2}, …, y_{n}}, and r and s denote two nonnegative integer sequences, where n ≥ r_{1} ≥ r_{2} ≥ ⋯ ≥ r_{m} ≥ 0 and m ≥ s_{1} ≥ s_{2} ≥ ⋯ ≥ s_{n} ≥ 0. Given the pair (r, s), the problem is to compute a bipartite graph H = (X, Y, E), if it exists, such that d(x_{i}) = r_{i} and d(y_{j}) = s_{j}.

6.1. The Characterization. The following theorem, known as the Gale-Ryser theorem, characterizes bipartite sequences [13, 24, 11, 22]. Before stating the theorem, we require a definition. The conjugate sequence of r, denoted by r^{⋆} = (r_{1}^{⋆}, …, r_{n}^{⋆}), is defined as r_{k}^{⋆} = |{i : r_{i} ≥ k}| for k = 1, …, n. Both r and r^{⋆} may be visualized by means of a (0,1)-matrix of size m×n in which the ith row contains r_{i} 1’s left-justified; then r_{k}^{⋆} is the number of 1’s in the kth column.

Theorem 6.1 (The Gale-Ryser Theorem). The pair (r, s) is a bipartite sequence if and only if r^{⋆} ⪰ s.

Theorem 6.1 suggests a simple parallel algorithm to decide if (r, s) is a bipartite sequence. Moreover, a network-flow based proof of this theorem (cf. [11]), combined with the results of [20], leads to a randomized parallel algorithm to realize (r, s).

6.2. An Algorithm. We present in this section a parallel algorithm for computing a bipartite graph H = (X ∪ Y, E) that realizes the pair (r, s). It follows from the Gale-Ryser theorem that the pair (r, r^{⋆}) is a bipartite sequence. In the corresponding realization F = (X, Y, E′), the neighbors of y_{j} are x_{1}, …, x_{p}, where p = r_{j}^{⋆}. Represent N_{F} (y_{j}) by the interval [1, …, p] of integers. Our algorithm is based on the following lemma.

Lemma 6.2. Suppose that (r, s) is a bipartite sequence. If the sequence t is obtained from s by a unit transformation, then (r, t) is also a bipartite sequence.

Proof. Let H = (X, Y, E) be a realization of (r, s) and t be obtained from s by a unit transformation from i to j. Since s_{i} ≥ s_{j} + 2, there exists a neighbor, say x_{k}, of y_{i} that is not a neighbor of y_{j}. Let H′ be obtained from H by deleting the edge (x_{k}, y_{i}) and adding the edge (x_{k}, y_{j}). Then H′ is a realization of (r, t).

We say that the graph H′ constructed in the above proof is obtained from H by a transfer of a neighbor between x_{i} and x_{j}. The main steps in our algorithm for computing a realization of (r, s) are: Step 1: Compute r^{⋆}. Test if r^{⋆} ⪰ s. If not, declare that (r,s) is not a bipartite sequence and stop. Step 2: Obtain the realization F = (X, Y, E′) of (r, r^{⋆}) by computing N_{F} (y_{j}) = [1, …, r_{j}^{⋆}]. Step 3: Transfer appropriate neighbors among the vertices of Y in F to obtain H.

The parallel implementation of Step 3, which is the difficult step, is based on the properties of the unit transformations (Section 5.3) required to transform the sequence r^{⋆} to s. For convenience of notation, we use the sequences a and b in place of r^{⋆} and s, respectively. Apply Algorithm 1 to the pair (a, b) and let t(i, j), 1 ≤ i, j ≤ n, be the unit transformations computed by the algorithm. Recall from Section 5.3 the definitions of A(i), B(j), α(i), β(i, j) and γ(i). Consider an i such that A(i) ≠ ∅. We define intervals T (i, j), where j ∈ A(i), as follows. In the realization F of (r, a), all vertices x_{p} such that p ∈ T (i, j) will be “transferred” from y_{i} to y_{j} to obtain the required bipartite graph H. Let the elements of A(i) (in the increasing order) be j_{1} = α(i), j_{2}, …, j_{k}. Define (see Figure 2 )

T (i, j_{1}) = [γ(i) + 1, …, γ(i) + t(i, j_{1})] and

T (i, j_{p}) = [a_{i} − ∑_{q=2}^{p} t(i, j_{q}) + 1, …, a_{i} − ∑_{q=2}^{p−1} t(i, j_{q})], for 2 ≤ p ≤ k.

Observe that |T (i, j_{p})| = t(i, j_{p}) for all 1 ≤ p ≤ k. We state in Algorithm 2 the procedure for realizing (r, s). Example 4: Let r = (4, 3, 3, 2, 2, 2, 1) and b = s = (4, 3, 3, 3, 2, 2). Then

X = {x_{1}, …, x_{7}}, Y = {y_{1}, …, y_{6}}, and a = r^{∗} = (7, 6, 3, 1, 0, 0).

Applying Algorithm 1 to the pair (a, b) we get t(1, 4) = 2, t(1, 5) = 1, t(2, 5) = 1, t(2, 6) = 2;

A(1) = {4, 5}, A(2) = {5, 6};
B(4) = {1}, B(5) = {1, 2}, B(6) = {2};
α(1) = 4, α(2) = 5, γ(2) = a_{5} = 0, γ(1) = a_{4} = 1.

The realization F of (r, a) has the following implicit representation. Recall that (x_{k}, y_{i}) ∈ F iff k ∈ N_{F} (y_{i}), and N_{F} (y_{i}) = [1, a_{i}] is represented by its endpoints.

N_{F} (y_{1}) = [1, 7], N_{F} (y_{2}) = [1, 6], N_{F} (y_{3}) = [1, 3],

N_{F} (y_{4}) = [1, 1], N_{F} (y_{5}) = N_{F} (y_{6}) = ∅,
T (1, 4) = [γ(1) + 1, γ(1) + t(1, 4)] = [2, 3],
T (1, 5) = [a_{1} − t(1, 5) + 1, a_{1}] = [7, 7],
T (2, 5) = [γ(2) + 1, γ(2) + t(2, 5)] = [1, 1],
T (2, 6) = [a_{2} − t(2, 6) + 1, a_{2}] = [5, 6].

[figure: y_{j_{2}}; y_{j_{p}}; y_{j_{k}}; y_{j_{1}}; a_{i}; a_{i} − t(i, j_{2}) + 1; a_{i} − ∑_{q=2}^{p−1} t(i, j_{q}); a_{i} − ∑_{q=2}^{p} t(i, j_{q}) + 1; a_{i} − ∑_{q=2}^{k−1} t(i, j_{q}); a_{i} − ∑_{q=2}^{k} t(i, j_{q}) + 1; γ(i) + t(i, j_{1}); γ(i) + 1; 1; T (i, j_{2}); T (i, j_{p}); T (i, j_{k}); T (i, j_{1})]

Fig. 2. Defining T (i, j). For example, T (i, j_{p}) is the set of elements a_{i} −∑_{q=2}^{p} t(i, j_{q})+1, a_{i} − ∑_{q=2}^{p} t(i, j_{q}) + 2, …, a_{i} − ∑_{q=2}^{p−1} t(i, j_{q}).

The desired realization H of (r, s) has the following implicit representation. N_{H}(y_{1}) = N_{F} (y_{1}) − (T (1, 4) ∪ T (1, 5)) = [1, 1] ∪ [4, 6],

N_{H}(y_{2}) = N_{F} (y_{2}) − (T (2, 5) ∪ T (2, 6)) = [2, 4],
N_{H}(y_{3}) = N_{F} (y_{3}) = [1, 3],
N_{H}(y_{4}) = N_{F} (y_{4}) ∪ T (1, 4) = [1, 3],
N_{H}(y_{5}) = N_{F} (y_{5}) ∪ (T (1, 5) ∪ T (2, 5)) = [1, 1] ∪ [7, 7],
N_{H}(y_{6}) = N_{F} (y_{6}) ∪ T (2, 6) = [5, 6].

Lemma 6.3. The bipartite multigraph H = (X ∪ Y, E) computed in Algorithm 2 is a simple bipartite graph.

Proof. It suffices to show that there are no multiple edges in H that are incident to any vertex y_{j}. This is equivalent to proving that N_{H}(y_{j}) is a set (i.e., it has no duplicate elements). If a_{j} ≥ b_{j}, N_{H}(y_{j}) is a set as N_{F} (y_{j}) is one. Consider now the case that a_{j} < b_{j}. Then N_{H}(y_{j}) = N_{F} (y_{j}) ∪ J, where J = ⋃_{i∈B(j)} T (i, j). We prove that N_{H}(y_{j}) has no duplicates by showing that J has no duplicates and that Input: A pair (r, s) of sequences. Output: A bipartite graph H = (X, Y, E), if it exists. H is specified implicitly by the neighborhoods of vertices in Y.

1. Compute r^{⋆}. Test if r^{⋆} ⪰ s. If the test fails, then declare that (r,s) is not a bipartite sequence and stop.

2. Set (a, b) := (r^{⋆}, s) and apply Algorithm 1 to compute the unit transformations t(i, j) for 1 ≤ i, j ≤ n.

3. Compute the bipartite graph F which realizes (r, a). F is represented implicitly: for each 1 ≤ j ≤ n, compute the set of neighbors of y_{j}, namely N_{F} (y_{j}) = [1, …, a_{j}].

4. Compute A(i) and B(j) for 1 ≤ i, j ≤ n.

5. Compute β(i, j) for all i and j such that t(i, j) ≠ 0; compute γ(i) for 1 ≤ i ≤ n.

6. Compute the intervals T (i, j) for 1 ≤ i ≤ n and j ∈ A(i).

7. For all i such that a_{i} > b_{i}, compute N_{H}(y_{i}) := N_{F} (y_{i}) − ⋃_{j∈A(i)} T (i, j).

8. For all j such that a_{j} < b_{j}, compute N_{H}(y_{j}) := N_{F} (y_{j}) ∪ (⋃_{i∈B(j)} T (i, j)).

9. For all i such that a_{i} = b_{i}, set N_{H}(y_{i}) := N_{F} (y_{i}).

Algorithm 2: Algorithm for computing a bipartite graph.

N_{F} (y_{j}) ∩ J = ∅. Recall that N_{F} (y_{j}) = [1, …, a_{j}].

Let the elements of B(j) (in the increasing order) be i_{1}, ⋯, i_{k}. Since j ∈ A(i_{1}), we have α(i_{1}) ≤ j. First consider the case α(i_{1}) = j. Case 1: k = 1. Then J = T (i_{1}, j) = [γ(i_{1}) + 1, …, γ(i_{1}) + t(i_{1}, j)] = [a_{j} + 1, …, a_{j} + t(i_{1}, j)]. Thus J is a set and N_{F} (y_{j}) ∩ J = ∅. Case 2: k ≥ 2. By Lemma 5.4, α(i_{q}) = j for 2 ≤ q ≤ k. By definition, T (i_{q}, j) = [γ(i_{q}) + 1, …, γ(i_{q}) + t(i_{q}, j)] for 1 ≤ q ≤ k. Then, by Lemma 5.5, T (i_{q}, j) = [γ(i_{q}) + 1, …, γ(i_{q−1})] for 2 ≤ q ≤ k and T (i_{1}, j) = [γ(i_{1}) + 1, …, γ(i_{1}) + t(i_{1}, j)]. Hence, for distinct p and q such that 1 ≤ p, q ≤ k, we obtain T (i_{p}, j) ∩ T (i_{q}, j) = ∅ and thus J has no duplicates. Further, J = ∪_{p=1}^{k}T (i_{p}, j) = [γ(i_{k}) + 1, …, γ(i_{k}) + ∑_{p=1}^{k} t(i_{p}, j)], and so min(J) = γ(i_{k}). We now obtain N_{F} (y_{j}) ∩ J = ∅, as max(N_{F} (j)) = a_{j} = γ(i_{k}) = min(J) − 1 (the second equality follows from Lemma 5.5).

Now consider the other case, namely α(i_{1}) < j. Let j_{1} = α(i_{1}), j_{2}, …, j_{p} = j be the elements of A(i_{1}) that are ≤ j. By definition

T (i_{1}, j) = [a_{i_{1}} − ∑_{q=2}^{p} t(i_{1}, j_{q}) + 1, …, a_{i_{1}} − ∑_{q=2}^{p−1} t(i_{1}, j_{q})].

Case 1: k = 1. Then J = T (i_{1}, j) and

max(N_{F} (j)) = a_{j}
< b_{j}
≤ b_{i_{1}}  (as i_{1} ≤ j and b is nonincreasing)
= a_{i_{1}} − ∑_{u∈A(i_{1})} t(i_{1}, u)  (by Lemma 5.3)

< a_{i_{1}} − ∑_{q=2}^{p} t(i_{1}, j_{q})
= min(J) − 1.

Hence N_{H}(y_{j}) ∩ J = ∅. Case 2: k ≥ 2. Put I = ⋃_{p=2}^{k} T (i_{p}, j); then J = T (i_{1}, j) ∪ I. We claim that I is a set. By Lemma 5.4, α(i_{p}) = j for all 2 ≤ p ≤ k. By Lemma 5.5, T (i_{p}, j) = [γ(i_{p}) + 1, …, γ(i_{p−1})] for 3 ≤ p ≤ k, and T (i_{2}, j) = [γ(i_{2}) + 1, …, γ(i_{2}) + t(i_{2}, j)]. Using γ(i_{k}) = a_{j}, we obtain I = [a_{j} + 1, …, γ(i_{2}) + t(i_{2}, j)], completing the claim. Now,

max(I) = γ(i_{2}) + t(i_{2}, j)
= a_{j} + ∑_{q=3}^{k} t(i_{q}, j) + t(i_{2}, j)  (by Lemma 5.5)
< a_{j} + ∑_{u∈B(j)} t(u, j)
= b_{j}  (by Lemma 5.3)
≤ b_{i_{1}}  (as i_{1} ≤ j and b is nonincreasing)
= a_{i_{1}} − ∑_{u∈A(i_{1})} t(i_{1}, u)  (by Lemma 5.3)

< a_{i_{1}} − ∑_{q=2}^{p} t(i_{1}, j_{q})
= min(T (i_{1}, j)) − 1.

Hence T (i_{1}, j) ∩ I = ∅, implying that J has no duplicates. Finally, max(N_{F} (y_{j})) = a_{j} = min(I) − 1 = min(J) − 1 and hence N_{F} (y_{j}) ∩ J = ∅.

Lemma 6.4. In the graph H = (X ∪ Y, E) computed by Algorithm 2, d_{H}(x_{i}) = r_{i} and d_{H}(y_{j}) = b_{j} (= s_{j}).

Proof. Clearly, d_{H}(x_{i}) = d_{F} (x_{i}) = r_{i}. If a_{j} = b_{j} then d_{H}(y_{j}) = b_{j}, since N_{H}(y_{j}) = N_{F} (y_{j}) and d_{F} (y_{j}) = a_{j}. Suppose next that a_{j} < b_{j}. Then

d_{H}(y_{j}) = |N_{F} (y_{j})|
= |N_{F} (y_{j})| + ∑_{i∈B(j)} |T (i, j)|
= a_{j} + ∑_{i∈B(j)} t(i, j)
= b_{j}.

Consider now the remaining case: a_{j} > b_{j}. Let i = j for convenience and put I = ∑_{u∈A(i)} T (i, u). Then N_{H}(y_{i}) = N_{F} (y_{i}) − I. Let the elements of A(i) be j_{i} = j, j_{2}, …, j_{k}. Now

γ(i) + t(i, j_{1}) ≤ a_{j_{1}} + ∑_{q∈B(j_{1})} t(q, j_{1})
= b_{j_{1}}
≤ b_{i}
= a_{i} − ∑_{q=1}^{k} t(i, j_{q})

< a_{i} − ∑_{q=2}^{k} t(i, j_{q}).

Thus I = [γ(i) + 1, …, γ(i) + t(i, j_{1})] ∪ [a_{i} − 1, …, a_{i} − ∑_{q=2}^{k} t(i, j_{q})] and hence I ⊆ N_{F} (y_{i}). Now

|I| = t(i, j_{1}) + ∑_{q=2}^{k} t(i, j_{q})
= ∑_{u∈A(i)} t(i, u)
= a_{i} − b_{i}.

Finally, d_{H}(y_{i}) = |N_{H}(y_{i})| = |N_{F} (y_{i})| − |I| = a_{i} − (a_{i} − b_{i}) = b_{i}.

We now outline the parallel complexity of Algorithm 2. As mentioned in Introduction, the graphs computed by our algorithms possess implicit representations: the graphs can be stored in O(n) space. For ease of notation, we assume that n denotes the total number of components of r and s (i.e., n := n + m). To analyze Step 1, we first sort the sequences r and s using the algorithm of [8] and store the sorted sequences in the arrays R and S, respectively. Sorting can be performed in O(log n) time using O(n) EREW PRAM processors. We show how to perform all other steps in O(log n) time using O(n/log n) EREW PRAM processors. r^{⋆} can be computed by cross-ranking [14] the array R with the array (1, 2, …, n). Step 2 can be performed by using Algorithm 1. It reports t(i, j)’s in a lexicographic order. Steps 4, 5, and 6 can be implemented by performing the appropriate prefix sums. In Step 7, observe that ⋃_{j∈A(i)} T (i, j) is union of at most three intervals, and hence can be computed within the same resource bounds. Therefore, Algorithm 2 can be implemented in O(log n) time using O(n) EREW PRAM processors. We summarize the result in the following.

Theorem 6.5. Given a pair (r, s) of nonnegative integer sequences, a bipartite graph that realizes (r, s) can be computed in O(log n) time using O(n) EREW PRAM processors, where n is the total number of components of r and s. Moreover, if the sequences r and s are given as sorted sequences, then the graph can be computed in O(log n) time using O(n/ log n) EREW PRAM processors.

7. Realizing Degree Sequences. Let d = (d_{1}, …, d_{n}) be a nonnegative integer sequence, where n > d_{1} ≥ d_{2} ≥ ... ≥ d_{n} ≥ 0. In this section we present parallel algorithms to compute a graph G = (V, E) on the vertex set V = {v_{1}, …, v_{n}} that realizes d. Our parallel algorithms are based on the proof of Theorem 4.1 and the main steps are: Step 1: From d, compute the sequence (c, c) and a realization H = (X, Y, E) of (c, c). From H compute another realization H′ of (c, c) such that (x_{i}, y_{i}) ∈ H′ if and only if 1 ≤ i ≤ μ. Step 2: Compute from H′ a symmetric digraph D = (V, E) such that d_{D}^{−}(v_{i}) = d_{D}^{+}(v_{i}) = d_{i}. Then compute G.

We first discuss the parallel implementation of Step 2; the essential ideas are described in the proof of Lemma 2.4. Compute the digraph D̃ = (V, Ẽ) on the vertex set V = {v_{1}, …, v_{n}}, where (v_{i}, v_{j}) ∈ D̃ if and only if (x_{i}, y_{j}) ∈ H′ and (x_{j}, y_{i}) ∉ H′. Then, the indegree of each vertex in D̃ is same as its outdegree. Compute Eulerian tours in D̃ using the algorithm of [5]; this algorithm computes an Eulerian tour for each connected component of D̃. Each trail is stored in an array. Using parallel list ranking, compute the number of edges in each trail. Consider first the even trails. Using the array representation of the trails, delete alternate arcs and insert the appropriate arcs as stated in the proof of Lemma 2.4. After this step, we are left with an even number of odd trails and we group them in pairs. For each pair, determine if it belongs to Case 1 or Case 2 in the proof of Lemma 2.4. In either case, delete and insert appropriate arcs. We now have the required symmetric digraph D = (V, E). Compute an undirected graph G from D by replacing the two symmetric arcs (v_{i}, v_{j}) and (v_{j}, v_{i}) with the edge (v_{i}, v_{j}). Then G is the desired realization of d.

We now analyze the complexity of Step 2. The graph H′ is represented in terms of adjacency lists: for each y ∈ Y, we maintain N_{H′} (y) as a list. Let m denote the number of edges of G. The digraph D̃ can be computed in O(log n) time using O(m) CRCW processors as follows. For each vertex, sort the vertices adjacent to it by the algorithm of [8], and test in O(log n) time if (x_{j}, y_{i}) ∈ H. The algorithm of [5] computes Eulerian tours in D̃ in O(log n) time using O(m) CRCW PRAM processors. Parallel list ranking requires O(log n) time using O(m) processors and the lists can be represented as consecutive elements in an array. Once we have the array representation, all other steps can be performed within the claimed complexity bounds. Hence the overall complexity of performing Step 2 is O(log n) time using O(m) CRCW PRAM processors.

In the remainder of this section, we discuss the parallel implementation of Step 1. Recall from Section 4 the definitions of high-degree and low-degree edges. In Step 1, we wish to compute a realization of (c, c) which has all high-degree edges and no lowdegree edges. The main steps involved in obtaining such a realization are (i) compute a bipartite realization H of (c, c) using, for example, Algorithm 2. (ii) compute appropriate exchange pairs in H to obtain all high-degree edges and (iii) compute appropriate exchange pairs in the resulting graph to remove the low-degree edges.

We provide two alternate parallel algorithms for implementing Step 1. The first algorithm is simple and intuitive and is based on several interesting lemmas. It has high complexity, since it proceeds by reducing the computation to that of recursively computing maximal matchings. On the other hand, the second algorithm is efficient, though involved: it is based on the implicit structure of H computed by Algorithm 2. We present the first algorithm Section 7.1 and the second one in Section 7.2.

7.1. The First Algorithm. Recall that H is a realization of (c, c). If there are missing high-degree edges in H, then we execute the procedure described in Section 7.1.1. This is followed by executing the procedure for low-degree edges, as described in Section 7.1.2. After performing these two steps, we are left with a bipartite realization H′ of H, which has all high-degree edges and no low-degree edges. This gives the outline of the first algorithm and we summarize the result in the following.

Theorem 7.1. Given an integer sequence d, a realization of d can be computed in O(log^{4} n) time using O(n^{3}) CRCW PRAM processors.

Proof. The proof and the complexity analysis follow from Lemmas 2.4, 7.4, and 7.5.

7.1.1. Procedure for High-Degree Edges. In this subsection, we present a parallel algorithm to compute appropriate exchange pairs in the realization H, so that by performing the corresponding exchanges (see Figure 1) we obtain another realization of (c, c) having all high-degree edges. The procedure has two phases.

In the first phase, we restrict ourselves to the subgraph of H induced by the high-degree vertices. Compute a maximal number of exchange pairs in this subgraph as follows. Define a graph G′ on the vertex set {1, 2, ..., μ}. There is an edge between i and j in G′ if and only if (x_{i}, y_{i}), (x_{j}, y_{j}) ∉ H and the edges (x_{i}, y_{j}) and (x_{j}, y_{i}) form an exchange pair. Compute a maximal matching M in G′ and then perform the corresponding exchanges in H. For notational simplicity, let H be the resulting bipartite graph after performing these exchanges.

In the second phase, we obtain the rest of the missing high-degree edges in H. Define as follows a bipartite graph H = (P, Q, E) over the missing high-degree edges and the corresponding exchange pairs in H. P = {p_{i} : (x_{i}, y_{i}) ∉ H, 1 ≤ i ≤ μ} and Q = {q_{lk} : (x_{l}, y_{k}) ∉ H, l ≠ k and n ≥ k > μ}. Further, (p_{i}, q_{lk}) ∈ E if and only if the edges (x_{i}, y_{k}) and (x_{l}, y_{i}) form an exchange pair in H. The following lemma establishes an important property of the bipartite graph H.

Lemma 7.2. Suppose that there is at least one high-degree edge missing in H and let the bipartite graph H = (P, Q, E) be as defined above. Then (i) d(p_{i}) ≥ 1 for all i and (ii) if (p_{i}, q_{lk}) ∈ E, then d(p_{i}) ≥ d(q_{lk}), where d(z) is the degree of vertex z in H.

Proof. Part (i) follows from Lemma 4.3. We say a vertex x_{i} is a high-degree neighbor of y_{k}, if (x_{i}, y_{k}) ∈ H and 1 ≤ i ≤ μ . Let A_{1} be the set of high-degree neighbors of y_{k}, which are not neighbors of y_{i} in H. Let A_{2} be the set of high-degree neighbors of y_{k} which are also neighbors of y_{i} in H. Observe that d(q_{lk}) ≤ |A_{1}|+|A_{2}|. To prove part (ii) of the lemma, we show that d(p_{i}) ≥ |A_{1}| + |A_{2}|. This is achieved by proving that N_{H}(p_{i}) ⊇ B_{1} ∪ B_{2}, where |B_{1}| ≥ |A_{1}|, |B_{2}| ≥ |A_{2}| and B_{1} ∩ B_{2} = ∅. Recall that c_{i} is the degree of y_{i} in H and that c_{i} > μ ≥ c_{k} (as i ≤ μ and k > μ).

This implies that |A1^{′}| ≥ |A_{1}|, where A1^{′} = {α : x_{α} ∈ N_{H}(y_{i}) − N_{H}(y_{k}), α ≠ k}.

The edges (x_{i}, y_{k}) and (x_{α}, y_{i}) form an exchange pair for every α ∈ A1^{′} and we define B_{1} = {q_{αk} : α ∈ A1^{′}}. Observe that B_{1} ⊆ N_{H}(p_{i}). We define B_{2} now. If (x_{j}, y_{i}) ∈ H for some 1 ≤ j ≤ μ and (x_{j}, y_{j}) ∉ H, then (x_{i}, y_{j}) ∉ H by the fact that a maximal matching is found in Phase 1 of the algorithm. Hence |A2^{′}| ≥ |A_{2}|, where A2^{′} = {β : (x_{i}, y_{β}) ∈ H, β > μ, β ≠ k}. For every β ∈ A2^{′}, there exists a vertex, say x_{β′}, such that β′ ≠ β and (x_{i}, y_{β}) and (x_{β′} , y_{i}) form an exchange pair in H. Define B_{2} = {q_{β′ β} : β ∈ A2^{′}} and note that B_{2} ⊆ N_{H}(p_{i}). To complete the proof, observe that B_{1} ∩ B_{2} = ∅.

Corollary 7.3. In H = (P, Q, E), there exists a matching that matches all vertices of P.

Proof. Follows from Lemmas 2.3 and 7.2.

We discuss some algorithmic aspects of Lemma 7.2. We compute the bipartite graph H = (P, Q, E) from H. From Corollary 7.3, we know that any maximum matching in H matches all vertices in P. By finding a maximum matching in H, we can compute the corresponding exchange pairs in H and hence obtain all the missing high-degree edges. Unfortunately, only randomized parallel algorithms are known for computing a maximum matching [19]. In order to solve our problem deterministically, we resort to the special structure of H stated in Lemma 7.2 and Corollary 7.3. The solution is presented in Algorithm 3.

Lemma 7.4. Algorithm 3 computes a bipartite realization of (c, c) having all high-degree edges. It runs in O(log^{4} n) time using O(n^{3}) CRCW PRAM processors.

Proof. We first show the correctness of the algorithm. In every step, observe that (c, c) is the degree sequence of the bipartite graph H. Consider an iteration of the while loop. The correctness of Phase 1 is obvious. Assume that H has some high-degree edges missing after Phase 1 and let H be as defined in Phase 2. Then E is not empty by condition (i) of Lemma 7.2. Thus H has more high-degree edges at the end of Phase 2 than it has in the beginning.

While there are missing high-degree edges in H do begin Phase 1:

1. Compute a graph G′ on the vertex set {1, 2, ..., μ}; there is an edge between i and j if and only if (x_{i}, y_{j}) and (x_{j}, y_{i}) form an exchange pair.

2. Compute a maximal matching M in G′ using the algorithm of [17].

3. From M, compute the exchange pairs in H and perform exchanges to obtain

the corresponding high-degree edges; let the resulting graph be H. Phase 2:

1. Compute a bipartite graph H = (P, Q, E) from H, where P = {p_{i} : (x_{i}, y_{i}) ∉ H, 1 ≤ i ≤ μ}, Q = {q_{lk} : (x_{l}, y_{k}) ∉ H, l ≠ k and n ≥ k > μ}, and (p_{i}, q_{lk}) ∈ E if and only if the edges (x_{i}, y_{k}) and (x_{l}, y_{i}) form an exchange pair in H.

2. Compute a maximal matching M in H using the algorithm of [17].

3. From M, compute the exchange pairs in H and perform exchanges to obtain

the corresponding high-degree edges; let the resulting graph be H. end. Algorithm 3: A parallel algorithm to obtain the missing high-degree edges in H

We now discuss the complexity of the algorithm. By Lemmas 2.2 and Corollary 7.3, the maximal matching computed in Step 2 of Phase 2 has size at least \frac{1}{2}|P|. Thus in each iteration of the while loop, the number of missing high-degree edges in H drops down by at least a factor of 2, which implies that the while loop is executed for at most O(log n) times. In each iteration, the graph G′ can be computed in O(1) time using O(n^{2}) processors and the graph H in O(1) time using O(n^{3}) processors. Computing maximal matchings in G′ and H takes O(log^{3} n) time using O(n^{3}) CRCW PRAM processors. Hence the overall complexity is as stated in the lemma.

7.1.2. Procedure for Low-Degree Edges. Let H be the bipartite graph computed by Algorithm 3; H has all high-degree edges and possibly some low-degree edges. Our aim in this subsection is to transform H into another bipartite realization H′ of (c, c) such that H′ has all high degree-edges and no low-degree edges. Our algorithm for achieving this is similar to Algorithm 3, and we present below the necessary modifications.

As before, there are two phases. In the first phase, we restrict ourselves to the subgraph of H induced by the low-degree vertices. Define a graph G′ on the vertex set {μ + 1, ..., n}. There is an edge between i and j in G′ if and only if the edges (x_{i}, y_{i}) and (x_{j}, y_{j}) form an exchange pair. In the second phase, define as follows a bipartite graph H = (P, Q, E) over the low-degree edges and the corresponding exchange pairs in H. P = {p_{i} : (x_{i}, y_{i}) ∈ H, μ < i ≤ n}, and Q = {q_{lk} : (x_{l}, y_{k}) ∈ H, l ≠ k and 1 ≤ k ≤ μ}. Further, (p_{i}, q_{lk}) ∈ E if and only if the edges (x_{i}, y_{i}) and (x_{l}, y_{k}) form an exchange pair in H. The results of Lemma 7.4 hold with this definition of H also. The rest of the discussion is similar to that of previous subsection. We conclude with the following.

Lemma 7.5. A bipartite realization of (c, c) having all high-degree edges and no low-degree edges can be computed in O(log^{4} n) time using O(n^{3}) CRCW PRAM processors.

7.2. An Efficient Algorithm. We present an efficient computation of the bipartite graph H′ introduced at the beginning of this section. The computation is based on the structure of the bipartite graph computed by Algorithm 2.

The main result of this section is the following.

Theorem 7.6. Given an integer sequence d of length n, a graph that realizes d can be computed in O(log n) time using O(n + m) CRCW PRAM processors, where m is the number of edges in the realization.

7.2.1. The Structure. We present in this section the structure of the bipartite graphs F and H computed by Algorithm 2.

Both graphs F and H (defined on the vertex set X ∪Y) are specified by giving the neighbors of the vertices in Y. For y_{i} ∈ Y, N_{F} (y_{i}) is an interval of vertices, namely N_{F} (y_{i}) = {x_{k} : 1 ≤ k ≤ a_{i}}, and we denote N_{F} (y_{i}) by the interval [1, …, a_{i}]. N_{H}(y_{i}) is a union of at most two disjoint intervals of vertices (cf. the proof of Lemma 6.3): N_{H}(y_{i}) = {x_{k} : k ∈ (L_{i} ∪M_{i})}, where L_{i} and M_{i} are defined below; we denote N_{H}(y_{i}) by L_{i} ∪ M_{i}. Recall the definitions of t(i, j), A(i), B(j), α(i), β(i, j), γ(i) and T (i, j) from Section 6. To define L_{i} and M_{i}, we distinguish between the following cases. Case 1: a_{i} = b_{i}. Then L_{i} = [1, …, a_{i}] and M_{i} = ∅. Case 2: a_{i} > b_{i}. Let the elements of A(i) be j_{1}, …, j_{k}. Then L_{i} = [1, …, γ(i)], and M_{i} = [γ(i) + t(i, j_{1}) + 1, …, a_{i} − ∑_{q=2}^{k} t(i, j_{q})]. Case 3: a_{i} < b_{i}. Put j = i and let the elements of B(j) be i_{1}, …, i_{k}. Case 3.1: α(i_{1}) = j. Then L_{j} = [1, …, a_{j} + ∑_{q=1}^{k} t(i_{q}, j)] and M_{j} = ∅. Case 3.2: α(i_{1}) < j. Let j_{1} = α(i_{1}), j_{2}, …, j_{p} = j be the elements of A(i_{1}) that are ≤ j. Then L_{j} = [1, …, a_{j} +∑_{q=2}^{k} t(i_{q}, j)] and M_{i} = [a_{i_{1}} −∑_{q=2}^{p} t(i_{1}, j_{q})+1, …, a_{i_{1}} − ∑_{q=2}^{p−1} t(i_{1}, j_{q})].

Example 5: In Example 4, L_{1} = [1, 1], M_{1} = [4, 6]; L_{2} = ∅, M_{2} = [2, 4]; L_{3} = [1, 3], M_{3} = ∅; L_{4} = [1, 3], M_{4} = ∅; L_{5} = [1, 1], M_{5} = [7, 7]; L_{6} = ∅, M_{6} = [5, 6].

Lemma 7.7. For all 1 ≤ i ≤ n, max(L_{i}) < min(M_{i}).

Proof. The neighborhoods N_{H}(y_{i}) are defined in the proof of Lemma 6.3. It is routine to verify that max(L_{i}) < min(M_{i}) holds in all the cases considered in that proof.

7.2.2. The Algorithm. Our algorithm computes four bipartite graphs, namely H_{0}, H_{1}, H_{2}, H_{3} = H′, on the same vertex set X ∪ Y. These graphs are represented implicitly using the neighborhoods of vertices in Y. Throughout, N_{i}(y) denotes the set of neighbors of y ∈ Y in H_{i}, where i ∈ {0, 1, 2, 3}.

The algorithm (Algorithm 4) has three steps. In the first step, we compute H_{0} and H_{1}; they are the realizations of (c, c^{⋆}) and (c, c), respectively.

In the second step, we compute H_{2} that has all high-degree edges, i.e., (x_{i}, y_{i}) ∈ H_{2} for all 1 ≤ i ≤ μ; no new low-degree edges are created in this step. Suppose the high-degree edge (x_{i}, y_{i}) is absent in H_{1}. To create the edge (x_{i}, y_{i}) by performing an exchange, we need to find vertices x_{l}, y_{k} such that (x_{i}, y_{k}) and (x_{l}, y_{i}) form an exchange pair. To make sure that no multiple edges are created when parallel exchanges are done, we select k = α(i) (see Lemma 7.11). Further, we impose the condition l ≠ k in order to avoid creating any low-degree edges. More precisely, we choose l = θ(i) = min{ℓ : ℓ ≠ α(i), x_{ℓ} ∈ N_{1}(y_{i}) − N_{1}(y_{α(i)})}. See Step 2 of Algorithm 4.

In the last step, we compute H_{3} by deleting from H_{2} all low-degree edges without destroying the high-degree edges. Suppose the low-degree edge (x_{j}, y_{j}) is present in H_{2}. To destroy the edge (x_{j}, y_{j}) by performing an exchange, we need to find vertices x_{l}, y_{k} such that (x_{j}, y_{j}) and (x_{l}, y_{k}) form an exchange pair. To make sure that no multiple edges are created when parallel exchanges are done, we select k = τ(j) = i, where j ∈ T (i, j) (see Lemma 7.14). Further, we impose the condition l ≠ k in order to avoid destroying the high-degree edges. More precisely, we choose l = ψ(j) = min{ℓ : ℓ ≠ τ(j), x_{ℓ} ∈ N_{2}(y_{τ(j)}) − N_{2}(y_{j})}. See Step 3 of Algorithm 4.

1. Let H_{0} and H_{1}, respectively, be the realizations of (c, c^{⋆}) and (c, c) computed by Algorithm 2.

2. Compute I = {i : i ≤ μ, (x_{i}, y_{i}) ∉ H_{1}}. Compute a new bipartite graph H_{2} from H_{1} by doing in parallel the following for all i ∈ I: Delete the edges (x_{i}, y_{α(i)}) and (x_{θ(i)}, y_{i}) and add the edges (x_{i}, y_{i}) and (x_{θ(i)}, y_{α(i)}).

3. Compute J = {j : j > μ, (x_{j}, y_{j}) ∈ H_{2}}. Compute a new bipartite graph H_{3} from H_{2} by doing in parallel the following for all j ∈ J: Delete the edges (x_{j}, y_{j}) and (x_{ψ(j)}, y_{τ(j)}) and add the edges (x_{ψ(j)}, y_{j}) and (x_{j}, y_{τ(j)}).

4. Output H_{3}.

Algorithm 4: An efficient algorithm.

The rest of this section is devoted to prove the following important result.

Lemma 7.8. Algorithm 4 computes a realization of (c, c) that has all high-degree edges and no low-degree edges. It runs in O(log n) time using O(n) EREW PRAM processors.

We let, for ease of notation, a = c^{⋆} and b = c. Recall from Section 6 that the condition k ∈ T (i, j) means: ‘y_{j} gets x_{k} from y_{i} in H_{0}’, i.e., (x_{k}, y_{i}) ∈ H_{0} − H_{1} and (x_{k}, y_{j}) ∈ H_{1} − H_{0}.

The following two lemmas are used to prove the correctness of Step 2 of Algorithm 4.

Lemma 7.9. Let i ≤ μ be such that (x_{i}, y_{i}) ∉ H_{1}. Then there exists a unique j such that i ∈ T (i, j). Furthermore, j = α(i) and j > μ.

Proof. The condition i ≤ μ implies that a_{i} ≥ μ, and thus (x_{i}, y_{i}) ∈ H_{0}. Further, the condition (x_{i}, y_{i}) ∉ H_{1} implies that a_{i} > b_{i} as N_{1}(y_{i}) ⊆ N_{0}(y_{i}) otherwise. Let the elements of A(i) be j_{1}, …, j_{k}. The condition (x_{i}, y_{i}) ∉ H_{1} implies that there exists a j_{ℓ} such that i ∈ T (i, j_{ℓ}). From the definition of T (i, j) it follows that j_{ℓ} is unique. We now show that j_{ℓ} satisfies the other properties of j stated in the lemma. Suppose for contradiction that j_{ℓ} ≠ α(i), i.e., j_{ℓ} > α(i). Then T (i, j_{ℓ}) = [a_{i} − ∑_{q=2}^{ℓ} t(i, j_{q}) + 1, …, a_{i} − ∑_{q=2}^{ℓ−1} t(i, j_{q})], and

b_{i} = |N_{1}(y_{i})|
= |L_{i}| + |M_{i}|
≤ max(M_{i})  (by Lemma 7.7)
= a_{i} − ∑_{q=2}^{k} t(i, j_{q})

≤ a_{i} − ∑_{q=2}^{ℓ} t(i, j_{q})
< min(T (i, j_{ℓ}))
≤ i  (as i ∈ T (i, j_{ℓ}))
≤ μ,

which contradicts b_{i} ≥ μ + 1. To prove the remaining part, observe that γ(i) ≥ a_{j_{ℓ}} and that i belongs to T (i, j_{ℓ}) only if γ(i) < i; the last inequality is possible only if j_{ℓ} > μ (as a_{j_{ℓ}} ≥ μ + 1 if j_{ℓ} ≤ μ).

Lemma 7.10. Let μ < j ≤ n. There exists at most one i such that i ∈ T (i, j). In that case, i ≤ μ and α(i) = j.

Proof. That there exists at most one i is clear from the definition of T (i, j) (cf. Figure 2). Observe that i belongs to T (i, j) only if i ≤ μ. Then α(i) = j by Lemma 7.9.

Lemma 7.11. The bipartite multigraph H_{2} computed in Step 2 of Algorithm 4 is a simple bipartite graph that realizes (c, c). Moreover, (x_{i}, y_{i}) ∈ H_{2} if 1 ≤ i ≤ μ.

Proof. Let the set I be as defined in Step 2 of the algorithm. Then, for distinct i and i′ in I we obtain α(i) ≠ α(i′) using Lemmas 7.9 and 7.10. Thus no multiple edges are created when new edges are added in Step 2, and hence H_{2} is a simple graph. The proof of the remaining part of the lemma is obvious.

The following two lemmas are needed to prove the correctness of Step 3 of Algorithm 4.

Lemma 7.12. Suppose (x_{j}, y_{j}) ∈ H_{2} for some j > μ. Then (x_{j}, y_{j}) ∈ H_{1}. Further, there exists a unique i such that j ∈ T (i, j), α(i) < j and i ≤ μ.

Proof. Recall that θ(i) ≠ α(i) in Step 2 of Algorithm 4. So no new ‘low-degree edges’ are created in H_{2}, i.e., no edge of the form (x_{k}, y_{k}), where k ≥ μ + 1, is introduced into H_{2}. Thus (x_{j}, y_{j}) ∈ H_{1}. The rest of the proof is similar to the proof of Lemma 7.9.

Lemma 7.13. Let i ≤ μ. There exists at most one j such that j ∈ T (i, j). In that case, j > α(i) and j > μ.

Proof. The proof is similar to the proof of Lemma 7.10.

Lemma 7.14. The bipartite multigraph H_{3} computed in Step 3 of Algorithm 4 is a simple bipartite graph that realizes (c, c). Moreover, (x_{i}, y_{i}) ∈ H_{3} if and only if 1 ≤ i ≤ μ.

Proof. Let J, τ(j) and ψ(j) be as in Step 3 of the algorithm. For distinct j and j′ in J we obtain τ(j) ≠ τ(j′) using Lemmas 7.12 and 7.13. Thus no multiple edges are created when new edges are added in Step 3 and hence H_{3} is a simple graph. Clearly, H_{3} is a realization of (c, c) and (x_{j}, y_{j}) ∉ H_{3} for all μ + 1 ≤ j ≤ n. By Lemma 7.11, (x_{i}, y_{i}) ∈ H_{2} for all 1 ≤ i ≤ μ. The fact that ψ(j) ≠ τ(j) implies that no such edge (high-degree edge) of H_{2} is destroyed when some edges are deleted in Step 3. Proof of Lemma 7.8: The correctness of the algorithm follows from Lemma 7.14. Recall that the graphs H_{0}, H_{1}, H_{2}, H_{3} are represented implicitly using the neighborhoods of vertices in Y. The complexity bounds for Step 1 follow from Theorem 6.5.

Suppose the neighborhood of some vertex y_{k} changes in Step 2. Then one of the following must hold: k ∈ I or k = α(i) for some i ∈ I. The following claim states that the neighborhood of y_{k} changes by exactly one vertex. Claim 1: |N_{2}(y_{k}) − N_{1}(y_{k})| = 1.

Consider first the case k ∈ I. Lemma 7.9 implies that α(i) ≥ μ + 1 for all i ∈ I. Since k ≤ μ, k ≠ α(i) for any i ∈ I. Consider now the case k = α(i) for some i ∈ I. Then i is unique by Lemmas 7.9 and 7.10, completing the proof of the claim. Since N_{1}(y) is a union of at most two disjoint intervals of vertices for all y ∈ Y, we can compute all θ(i)’s in constant time using O(n) processors. Further, the graph H_{2} in Step 2 can be computed in constant time using O(n) processors.

Suppose the neighborhood of some vertex y_{k} changes in Step 3. Then one of the following must hold: k ∈ J or k = τ(j) for some j ∈ J. The following claim states that the neighborhood of y_{k} changes by exactly one vertex.

Claim 2: |N_{3}(y_{k}) − N_{2}(y_{k})| = 1.

Consider first the case k ∈ J. Lemma 7.12 implies that τ(j) ≤ μ for all j ∈ J. Since k ≥ μ + 1, k ≠ τ(j) for any j ∈ J. Consider now the case k = τ(j) for some j ∈ J. Then j is unique by Lemmas 7.12 and 7.13, completing the proof of the claim. All τ(j)’s can be computed in constant time using O(n) processors. Claim 1 implies that N_{2}(y) is a union of at most three disjoint intervals of vertices for all y ∈ Y. Hence all ψ(j)’s can be computed in constant time using O(n) processors. Further, the graph H_{3} in Step 3 can be computed in constant time using O(n) processors.

Acknowledgments. We thank the referees for their comments and suggestions for improving the presentation of this paper. We also thank Shiva Chaudhuri for useful discussions.

REFERENCES

[1] A. Aho, J. Hopcroft and J. Ullman Design and Analysis of Computer Algorithms, (Exercises on pp. 71-72), Addison-Wesley, 1974.

[2] S. R. Arikati, New Results in Algorithmic Graph Theory, Ph.D. thesis, Department of Mathematics, University of Illinois, Chicago, 1993.

[3] S. R. Arikati and U. N. Peled, Degree sequences and majorization, Linear Algebra Appl., 199 (1994), pp. 179–211.

[4] T. Asano, Graphical degree sequence problems with connectivity requirements, Lecture Notes in Computer Science, Springer-Verlag, 762 (1993), pp. 38-47.

[5] B. Awerbuch, A. Israeli and Y. Shiloach, Finding Euler circuits in logarithmic parallel time, proceedings of the ACM Symposium on Theory of Computing, ACM Press, 1984, pp. 249-257.

[6] C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam, 1973.

[7] F.T. Boesch ed., Large-Scale Networks: Theory and Design, IEEE Press, New York, 1976.

[8] R. Cole, Parallel merge sort, SIAM J. Comput., 17 (1988), pp. 770–785.

[9] A. Dessmark, A. Lingas and O. Garrido, On the parallel complexity of maximum fmatching and the degree sequence problem, Lecture Notes in Computer Science, Springer-Verlag, 841 (1994), pp. 316–325.

[10] P. Erdős and T. Gallai, Graphs with prescribed degrees of vertices (in Hungarian), Mat. Lapok, II (1960), pp. 264–272.

[11] L. R. Ford, Jr., and D. R. Fulkerson, Flows in Networks, Princeton University Press, New Jersey, 1962.

[12] D. R. Fulkerson, A. J. Hoffman, and M. H. McAndrew, Some properties of graphs with multiple edges, Can. J. Math., 17 (1965), pp. 166–177.

[13] D. Gale, A theorem on flows in networks, Pacific J. Math., 7 (1957), pp. 1073–1082.

[14] T. Hagerup and C. Rüb, Optimal merging and sorting on the EREW PRAM, Infor. Proc. Letters, 33(4) (1989), pp. 181-185.

[15] F. Harary, Graph Theory, Addison-Wesley, New York, 1969.

[16] G. H. Hardy, J. E. Littlewood, and G. Pólya, Inequalities, Cambridge University Press, New York, 1952.

[17] A. Israeli and Y. Shiloach, An improved parallel algorithm for maximal matching, Infor. Proc. Letters, 22(2) (1986), pp. 57–60.

[18] J. JáJá, An Introduction to Parallel Algorithms, Addison-Wesley, New York, 1992.

[19] R. M. Karp and V. Ramachandran, Parallel algorithms for shared-memory machines, in J. van Leeuwen, ed., Handbook of Theoretical Computer Science, Elsevier, Amsterdam, Vol. A, 1990, pp. 869–942.

[20] R. M. Karp, E. Upfal, and A. Wigderson, Constructing a maximum matching in random NC, Combinatorica, 6(1) (1986), pp. 35–48.

[21] L. Lovász and M. Plummer, Matching Theory, Academic Press, Budapest, Hungary, 1986.

[22] A. W. Marshall and I. Olkin, Inequalities: Theory of Majorization and its Applications, Academic Press, New York, 1979.

[23] U. N. Peled and M. K. Srinivasan, The polytope of degree sequences, Linear Algebra Appl., 114 (1989), pp. 349–377.

[24] H. J. Ryser, Combinatorial properties of matrices of zeros and ones, Canad. J. Math., 9 (1957), pp. 371–377.

[25] G. Sierksma and H. Hoogeveen, Seven criteria for integer sequences being graphic, Journal of Graph Theory, 15 (1991), pp. 223–231.

[26] R. I. Tyshkevich, A. A. Chernyak and Zh. A. Chernyak, Graphs and degree sequences I, Cybernetics, 23 (1987), pp. 734-745.

[27] J. van Leeuwen, Graph algorithms, in J. van Leeuwen, ed., Handbook of Theoretical Computer Science, Elsevier, Amsterdam, vol. A, 1990, pp. 525–631.