Parallel algorithms for matching and independence problems in graphs and hypergraphs

by 1977- Windsor, Aaron Andrew

We consider the following problem: Given a greedy graph algorithm that seems to be inherently sequential, to what extent can we expect to speed up the computation by making use of additional processors? We obtain several positive results for particular problems, showing that it is theoretically possible to parallelize some greedy graph algorithms to the extent that their parallel running times are asymptotically much faster than their sequential running times. Highlights of our results include: • A simple proof that a simple algorithm of Luby (“the permutation algorithm”) is an RN C algorithm for finding a maximal independent set in a graph, and the first known derandomization of that algorithm. • The first non-trivial upper bound on the deterministic time complexity of finding a maximal independent set in a hypergraph on a PRAM. • A partial analysis of the permutation algorithm generalized to hypergraphs, showing that it outperforms the best known algorithm for finding a maximal independent set in a hypergraph in the following sense: For hypergraphs of dimension at least 6, any set of vertices is at least as likely to be added to the independent set by an iteration of the permutation algorithm as it is to be added by an iteration of the other algorithm. • The first N C algorithm for finding a maximal forest in a hypergraph. • The first N C algorithm for finding a maximal acyclic set in an undirected graph.