Parallel and Distributed Algorithms

Prev: Approximate Counting Next: Online Algorithms

Problems

12.1

Show that the parallel variant of randomized quicksort described in Section 12.2 sorts $n$ elements with $n$ processors on a CREW PRAM, with high probability in $O({\log }^{2}n)$ steps.

---

12.2

Prove Lemma 12.1. The following outline is suggested (refer to Section 12.2 for the notation).

1. Bound the probability that $a(B_{i+1})=a(B_i)$ using the result of Exercise 12.6.
2. Bound the probability that for any particular $k$, the value $k$ is contained more than ${\tau }_k$ times in the sequence $a(B_1),\dots ,a(B_t)$.
3. Bound the probability that for $1\le k\le c\log \log n$, the value $k$ is contained more than ${\tau }_k$ times in the sequence $a(B_1),\dots ,a(B_t)$.

---

12.3

Suppose that the random samples in Stage 1 of BoxSort are chosen using pairwise independent, rather than completely independent random variables. The choices made by the various boxes are independent of each other, though. Derive the best upper bound you can on the number of parallel steps taken by BoxSort.

---

12.4

Using the ideas of Section 12.2, devise a CREW PRAM algorithm that selects the $k$th largest of $n$ input numbers in $O(\log n)$ steps using $n/\log n$ processors. Assume that the $n$ input numbers are initially located in global memory locations $1$ through $n$.

---

12.5

Devise an RNC algorithm for generating a random uniformly distributed permutation of a set $S$ containing $n$ elements. (Hint: Consider assigning random weights to the elements of $S$. If the weights are drawn from a sufficiently large set, each element will have a distinct weight.)

---

12.6

A maximal matching in a graph is a matching that is not properly contained in any other matching. Use the parallel algorithm for the MIS problem to devise an RNC algorithm for finding a maximal matching in a graph.

---

12.7

Consider a graph $G(V,E)$ with maximum degree $\Delta$. Show that a sequential greedy algorithm will color the vertices of the graph using at most $\Delta +1$ colors such that no two adjacent vertices are assigned the same color. Employing the parallel algorithm for MIS, devise an RNC algorithm for finding a $\Delta +1$ coloring of a given graph.

---

12.8

Due to M. Luby [282].

The vertex partition problem is defined as follows: given a graph $G(V,E)$ with edge weights, partition the vertices into sets $V_1$ and $V_2$ such that the net weight of the edges crossing the cut $(V_1,V_2)$ is at least a half of the total weight of the edges in the graph. Describe an RNC algorithm for this problem, and explain how you will convert this into an NC algorithm using the idea of pairwise independence.

---

12.9

Due to M. Luby [282].

In the Parallel MIS algorithm, suppose that the random marking of the vertices is only pairwise independent. Show that the probability that a good vertex belongs to $S\cup \Gamma (S)$ is at least $1/24$.

---

12.10

Due to M. Luby [282].

Suppose that you are provided with a collection of $n$ pairwise independent random numbers uniformly distributed over the set $\{0,1,\dots ,p-1\}$, where $p\ge 2n$. It is desired to construct a collection of $n$ pairwise independent Bernoulli random variables where the $i$th random variable should take on the value $1$ with probability $1/t_i$, for $1\le t_i\le n/8$. Show how you can achieve this goal approximately by constructing a collection of pairwise independent Bernoulli random variables such that the $i$th variable takes on the value $1$ with probability $1/T_i$, where for a constant $c>1$, $T_i$ satisfies

$$T_i\le t_i\le c{T}_i.$$

---

12.11

Due to M. Luby [282].

Combining the results of Problems 12.9 and 12.10, show that the Parallel MIS algorithm can be derandomized to yield an NC algorithm for the MIS problem. Note that the approach in Problem 12.10 will not work for marking vertices with degree exceeding $n/16$, and these will have to be dealt with separately.

---

12.12

Due to M. Luby [282].

In this problem we consider a variant of the Parallel MIS algorithm. For each vertex $v\in V$, independently and uniformly choose a random weight $w(v)$ from the set $\{1,\dots ,n^4\}$. Repeatedly strip off an independent set $S$ and its neighbors $\Gamma (S)$ from the graph $G$, where at each iteration the set $S$ is the set of marked vertices generated by the following process: mark all vertices in $V$, and then in parallel for each edge in $E$ unmark the end-point of larger weight. Show that this yields an RNC algorithm for MIS. Can this algorithm be derandomized using pairwise independence?

---

12.13

Due to D.R. Karger [231].

Recall the randomized algorithm for min-cuts discussed in Section 1.1 (see also Section 10.2). Describe an RNC implementation of this algorithm. (Hint: While contracting the edges appears to be a sequential process, it can be implemented in parallel using the following observation. Consider generating a random permutation on the edges, as described in Problem 12.5 and using this to determine the order in which the edges are contracted. The contraction algorithm will terminate at that point in the permutation where the preceding edges constitute a graph with exactly two connected components. Assume that there is an NC algorithm for determining connected components.)

---

12.14

Due to M. Luby, J. Naor, and M. Naor [285].

Using the idea of pairwise independence, construct an RNC algorithm for the min-cut problem that uses only a polylogarithmic number of random bits (see also Problem 12.13). What implications does this have for placing the min-cut problem in NC? (Hint: Select a set of edges by choosing each edge pairwise independently with probability $1/c$, where $c$ is the size of the min-cut; see Problem 12.10. In parallel, contract all edges in this set. Repeat this process until the graph is reduced to two vertices.)

---

12.15

Due to M.O. Rabin and V.V. Vazirani [349].

Let $G(V,E)$ be a graph with a unique perfect matching. Devise an NC algorithm for finding the perfect matching in $G$. (Hint: Consider substituting $1$ for each indeterminate in the Tutte matrix. What is the significance of the entries in the adjoint of the Tutte matrix?)

---

12.16

Due to K. Mulmuley, U.V. Vazirani, and V.V. Vazirani [317].

Consider the problem of finding a minimum-weight perfect matching in a graph $G(V,E)$, given edge-weights $w(e)$ for each edge $e\in E$ in unary. Note that it is not possible to apply the Isolating Lemma directly to this case since the random weights chosen there would conflict with the input weights. Explain how you would devise an RNC algorithm for this problem. The parallel complexity of the case where the edge-weights are given in binary is as yet unresolved; do you see why the RNC algorithm does not apply to the case of binary weights? (Hint: Start by scaling up the input edge weights by a polynomially large factor. Apply random perturbations to the scaled edge weights and prove a variant of the Isolating Lemma for this situation.)

---

12.17

Due to K. Mulmuley, U.V. Vazirani, and V.V. Vazirani [317].

Devise an RNC algorithm for the problem of finding a maximum matching in a graph. Observe that the Parallel Matching algorithm does not work as stated when the maximum matching is not a perfect matching.

---

12.18

Due to H.J. Karloff [237].

Suppose you are given a Monte Carlo RNC algorithm for finding a maximum matching in a bipartite graph. Explain how you would convert this into a Las Vegas algorithm. Can the solution be generalized to the case of non-bipartite graphs? (Hint: While this conversion is trivial for perfect matching algorithms, for maximum matching algorithms you will need to devise a parallel algorithm for determining an upper bound on the size of a maximum matching in a graph. This requires a non-trivial use of structure theorems for matchings in graphs.)

---

12.19

This problem explores a different method for converting the Monte Carlo maximum matching into a Las Vegas one. Recall from Problem 7.7 that the rank of the matrix of indeterminates constructed for a bipartite graph is exactly equal to the size of the maximum matching (a similar result holds for the general case). Consider the following approach for determining the size of the maximum matching: replace the indeterminates by random values and compute the rank of the resulting matrix. The rank of an integer matrix can be computed in NC, and one would hope that the random substitution method would preserve the rank with high probability. We would like to use this to verify that the matching algorithm is indeed producing the maximum matching, and thereby obtain a Las Vegas algorithm. Does this method work?

---

12.20

Due to R.M. Karp, E. Upfal, and A. Wigderson [242].

In a bipartite graph $G(U,V,E)$, for any set $F\subseteq E$ define the rank $r(F)$ as the maximum size of intersection of $F$ with a perfect matching, i.e., $r(F)$ is the largest number of edges in $F$ that appear together in some perfect matching. Devise an RNC algorithm for computing the rank for any given set $F$. Can this be generalized to non-bipartite graphs?

---

12.21

Due to R.M. Karp, E. Upfal, and A. Wigderson [242].

Assume you are given the algorithm from Problem 12.20. Using this, we will outline the construction of an alternative RNC algorithm for perfect matchings.

• Assuming that the input graph is sparse in that it has a total of $n$ vertices and fewer than $3n/4$ edges, devise an NC algorithm for finding a large set $S$ of edges that are guaranteed to belong to every perfect matching in $G$.
• Suppose now that the input graph has more than $3n/4$ edges. Using the rank algorithm, devise an RNC algorithm for finding a large set $T$ of edges such that there exists a perfect matching in $G$ none of whose edges belong to $T$.

Using the above tools, describe an alternative RNC algorithm for perfect matchings.

---

12.22

Due to V.V. Vazirani [405].

Prove that the Isolating Lemma holds even when the weight of a set is defined to be the product instead of sum of the weights of its elements. Can you identify any general family of mappings from the weights of elements to the weights of sets for which the Isolating Lemma is guaranteed to be valid?

---

12.23

Due to K. Mulmuley, U.V. Vazirani, and V.V. Vazirani [317].

An intriguing application of the Isolating Lemma is to the class of “uniqueness” problems, i.e., determining whether some problem in NP has a unique solution. Consider the following two problems, which take as input a graph $G(V,E)$ and a positive integer $k$:

CLIQUE: Determine whether the graph has a clique of size $k$.

UNIQUE CLIQUE: Determine whether there is exactly one clique of size $k$.

The complexity of unique solutions has been studied with respect to randomized reductions, which are the natural generalization of polynomial time reductions to allowing randomized polynomial time reductions. Devise a randomized polynomial time reduction from the CLIQUE problem to the UNIQUE CLIQUE.

---

12.24

Due to J. Naor.

Let $G(V,E)$ be an unweighted, undirected graph with $n$ vertices and $m$ edges. Under any weight function $w:E\to \{0,\dots ,W\}$, the length of a path in $G$ is the sum of the weights of the edges in that path. A weight function is said to be good if the following two conditions hold for each vertex $x\in V$.

1. For all vertices $y\in V$, the shortest path from $x$ to $y$ is unique.
2. For any pair of vertices $y,z\in V$, the net weight of the shortest path from $x$ to $y$ is different from the net weight of the shortest path from $x$ to $z$.

What is the smallest value of $W$ as a function of $n$ and $m$ for which you can guarantee the existence of a good weight assignment?

---

12.25

Due to K. Mulmuley, U.V. Vazirani, and V.V. Vazirani [317].

An even more intriguing application of the Isolating Lemma is to the Exact Matching problem: given a graph $G(V,E)$ with a subset of edges $R\subseteq E$ colored red, and a positive integer $k$, determine whether there is a perfect matching using exactly $k$ red edges. This problem is not known to be in P, but can be shown to be in RNC via a non-trivial application of the Isolating Lemma. Devise RNC algorithms for the decision and search versions of this problem.

---

12.26

Due to M.O. Rabin [344].

Show that Algorithm ASYNCH-CCP works equally well in the case where the numbers of processors and choices are both greater than $2$. How does the complexity depend on the number of processors and choices?

---

12.27

How large a value of $t$ can the ByzGen algorithm tolerate? (Modify the parameters $L$, $H$, and $G$ if necessary.)

---

12.28

Consider what happens if the outcome of the coin toss generated by the trusted party in the ByzGen algorithm is corrupted before it reaches some good processors.

(a) Can disagreement occur if different good processors see different outcomes? What happens if, instead of a global coin toss, each processor chooses a random coin independently of other processors, at every round?

(b) Suppose that we were guaranteed that at least $H$ good processors receive the correct outcome of each coin toss. Give a modification for the protocol ByzGen that achieves agreement in an expected constant number of rounds, under this assumption.