SUBLINEAR GRAPH SPARSIFICATION WITH APPLICATIONS TO CUTS, MATCHINGS, AND FLOWS

In recent years there has been a rapid increase in the volume of data across various types of computational tasks. Consequently, there has been growing interest in developing algorithms that are highly resource-efficient in terms of time, space, and communication. Although some algorithms in the existing literature are deemed efficient in the conventional sense that they require polynomial time and space in the input size, their resource demand can still be too high for computation on massive datasets. For instance, modern social networks have more than billions of edges, and thus even a linear dependence of time or space on the size of the data can be resource-prohibitive. As a result, it has been an increasingly important topic to design sublinear algorithms, whose resource consumption is smaller than the size of the data. In this thesis, we focus on developing sublinear algorithms for datasets with graph structures, such as social networks, biological networks and Web networks, where pairwise relationship between data points is captured. We obtain close-to-optimal results for the sublinear computation of several fundamental graph problems - this involves both designing efficient sublinear algorithms and proving lower bounds showing their optimality. The specific problems we study in this thesis include graph sparsification, hierarchical clustering, maximum matchings, maximum flows, and minimum cuts. A common and unifying theme underlying these problems is {\em graph sparsification}, a powerful tool that significantly reduces the size of the graph while preserving some fundamental properties of the graph. This tool can easily be seen to imply substantially more efficient algorithms, as it allows one to compress any given graph and then run any efficient algorithm on the resulting sparse representation of significantly smaller size while only incurring a negligible loss in the solution quality. The problems we study either are directly related to graph sparsification with outputting a graph sparsifier (i.e. a sparse representation of the graph) as a goal, or require crucial use of graph sparsification as a building block in designing efficient sublinear algorithms. Our work demonstrates the power of graph sparsification in algorithm design beyond traditional computational models, and we hope it spurs future research on graph sparsification in additional applications.

Author dc:creator

• Li, Huan

Advisors dc:contributor.advisor

• Khanna, Sanjeev
• De, Anindya

• Computer Sciences
• Mathematics

Language dc:language.iso

en

Repository record dc:identifier.uri

https://repository.upenn.edu/handle/20.500.14332/61258

OAI identifier oai:identifier

oai:repository.upenn.edu:20.500.14332/61258