Graphs and metrics are two of the most ubiquitous, versatile and powerful tools in modern computing. Both are general enough to be widely applicable but structured enough to facilitate efficient algorithms. Furthermore, the modern proliferation of data has led to graphs and metrics of practical importance which are of unprecedented size. For this reason, now more than ever, understanding how to sparsify or otherwise effectively reduce the size of a graph or metric is of great importance. We give new results in graph and metric sparsification using tools from combinatorial optimization, metric embeddings, approximation algorithms and online algorithms.

In the first part of this thesis we provide two new so-called tree embeddings which represent relevant aspects of an arbitrary input graph by a tree. The first embeds the points in a metric into a single tree containing a small number of copies of each vertex. Using these embeddings we give the first non-trivial deterministic approximation algorithms for online group Steiner tree and the online covering Steiner tree problem. The second is the first embedding of the hop-constrained distances in a graph into a distribution over trees; the hop-constrained distance between two nodes is defined as the minimum weight of a connecting path consisting of at most some hop constraint many edges. Using these embeddings we give the first poly-log bicriteria algorithms for the hop-constrained version of many classic network design problems.

In the second part of this thesis we provide new algorithms for a primitive at the heart of recent advances in hop-constrained expander decompositions for graphs. Specifically, we give the first algorithms for (1 − ε)-approximate h-length flow running in sequential time Õ(m ⋅ poly(h, 1⁄ε)), parallel time Õ(poly(h, 1⁄ε)) with m processors and distributed CONGEST time Õ(2^O(√^{log n}) ⋅ poly(h, 1⁄ε)). Notably, these algorithms are also deterministic. We give a variety of applications including simplified distributed and deterministic constructions of expander decompositions, efficient algorithms for computing h-length cutmatches which form the backbone of recent work in hop-constrained expander decompositions and what is to our knowledge the first non-trivial distributed (1-ε)-approximation for b-matching.

In the last part of this thesis we investigate how graph structure can make metric sparsification easier. In particular, we study the Steiner point removal problem where we must vertex-sparsify a graph from a structured family. We give the first O(1) distortion Steiner point removal solutions on series-parallel graphs as well as new metric decompositions for series-parallel graphs.

226 pages

Thesis Committee:
Bernhard Haeupler (Co-Chair)
R. Ravi (Co-Chair)
Anupam Gupta
Michael Goemans (Massachusetts Institute of Technology)
Ola Svensson (École polytechnique fédérale de Lausanne (EPFL))

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu