On graph sparsifiers, graph sketches, fast linear solvers and network flow optimization

Abstract

Most graph algorithms run faster, sometimes by orders of magnitude, on sparse graphs (graphs containing few edges). By approximating a dense input graph by a suitable sparse graph or other data structure, one can improve an algorithm’s computation and storage efficiency. With this motivation, this thesis concentrates on the problem of how to construct a compact data structure that closely represents a given graph, as well as its related applications. Our first focus is graph sparsification. The generic graph sparsification problem is to approximate a given graph by a sparse graph (i.e., the graph sparsifier) on the same vertex set but retaining only a smaller subset of edges. Such a sparsifier usually preserves, with bounded error, some quantitative properties of the original graph, making it an appropriate candidate to replace the old graph in some computations. We present faster randomized and deterministic algorithms for constructing graph sparsifiers that preserve (up to small error) the value of every Laplacian quadratic form. We then extend the idea of graph sparsification to creating a novel data structure—graph sketches. Graph sketches differ from graph sparsifiers in two aspects: (i) Sketches can be any data structure, not limited to graphs, and (ii) Sketches only preserve the value of every fixed Laplacian quadratic form, with high probability. We present an algorithm for constructing nearly optimal graph sketches, which uses much less storage than even the graph sparsifier, matching the lower bound on the space size of sketches for storing graphs. Finally, we investigate two problems closely related to graph theory: the design of solvers for linear systems of equations, and the optimization of confluent network flows. For the former, we develop a new algorithm for solving a linear system for a special class of PSD matrices, those which can be decomposed into the sum of two almost commuting matrices. Our solver runs in time nearly linearly depending on the input size, beating previous best solvers. For the latter, we prove the logarithmic non-approximability of the single-sink Confluent Quickest Flow and Confluent Maximum Flow Over Time problems, and present polylogarithmic approximation algorithms. To the best of our knowledge, our algorithms are the first polynomial-time polylogarithmic approximation algorithms for these problems in a general network.

Date of Award	2017
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology