Sublinear Time Algorithms for Graph Problems

Abstract

Processing massive graphs is becoming a more-and-more essential task in big-data analysis nowadays. Many graph problems require running time linear in the input size on the traditional RAM model. But linear time is not good enough in many real-life applications. In this thesis, we focus on theoretical analysis of solving fundamental graph problems on practical big-data platforms such as streaming and parallel computation models, with an emphasis on time efficiency and simplicity. In the first part of this thesis, we study the connected components problem in the parallel computation model. Our first result includes several simple parallel algorithms with a state-of-the-art running time, which are significantly easier to implement comparing to the existing ones. Our second result includes simpler algorithms for connected components and spanning forest that are faster than any previous algorithms when the graph has small diameter -- which is usually true in many graphs generated from real-life instances -- albeit in a much weaker computation model.

For the second part of this thesis, we study the graph matching problem. We first give a simple algorithm for approximate bipartite matching on streaming and massively parallel computation models that improve upon the existing ones on the number of passes or space usage. Then we present the first semi-streaming algorithm for exact maximum weight bipartite matching that breaks the linear-pass barrier whenever the graph is not super dense.

Our approaches not only leverage the combinatorial properties in the graph, but also reformulate the graph problem and use continuous optimization techniques. We hope the new general techniques developed in this thesis can find further applications in algorithm design emerged in big-data analysis.