Random Mate Graph Connectivity

This parallel algorithm finds the connected components of a graph using a randomized techinique called random mate. On each round it creates a collection of independent stars (a single central vertex with some number of neighbors connected to it) and then contracts each star into a single vertex. It is not hard to show that the number of vertices goes down geometrically (with high probability) and hence for n vertices algorithm finishes in O(log n) rounds. Each round takes constant depth so the overal depth is also O(log n). Although the work done on the vertices goes down geometrically and hence adds to a total of O(n) work, the number of edges does not necessarily go down geometrically and hence for m edges the algorithm runs in O(m log n) work (all bounds w.h.p.).

The code for random mate connectivity in NESL is included below. Here are some slides describing the algorithm and code using the same example graph. The argument L is the initial labeling for the graph, which needs to be the sequence [0, 1, ..., n-1], and the argument E is a sequence of edges each represented as its two enpoints, and each edge has to be represented in each direction. The output is returned as a rooted spanning tree for each component, i.e., every vertex points to a parent in the tree.

The example consists of a single component, and an answer such as:

it = [1, 2, 2, 6, 6, 6, 1]

is valid since it represents a tree rooted at vertex 2 (3, 4 and 5 point to 6, 6 and 0 point to 1, and 1 and 2 point to 2). Feel free to change the inputs: for example changing all 0s to 1s in E will disconnect the vertex 0.