Amit Chakrabarti: Graph coloring via degeneracy in streaming and other space-conscious models
Time: Mon 2019-06-10 12.00
Lecturer: Amit Chakrabarti, Dartmouth College
Location: Room 4523, Lindstedtsvägen 5 - floor 5, KTH
- Lunch is served at 12:00 noon (register at www.csc.kth.se/tcs/seminars/lunch/2019-06-10 at the latest the Saturday before, but preferably earlier). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for 1½-2 hours of more technical discussions.
We study the problem of coloring a given graph using a small number of colors in several well-established models of computation for big data. These include the data streaming model, the general graph query model, the massively parallel computation (MPC) model, and the CONGESTED-CLIQUE and the LOCAL models of distributed computation. On the one hand, we give algorithms with sublinear complexity, for the appropriate notion of complexity in each of these models. Our algorithms color a graph G using about κ(G) colors, where κ(G) is the degeneracy of G: this parameter is closely related to the arboricity α(G). As a function of κ(G) alone, our results are close to best possible, since the optimal number of colors is κ(G)+1.
On the other hand, we establish certain lower bounds indicating that sublinear algorithms probably cannot go much further. In particular, we prove that any randomized coloring algorithm that uses κ(G)+1 many colors, would require Ω(n2) storage in the one pass streaming model, and Ω(n2) many queries in the general graph query model, where n is the number of vertices in the graph. These lower bounds hold even when the value of κ(G) is known in advance; at the same time, our upper bounds do not require κ(G) to be given in advance.
Joint work with Suman K. Bera and Prantar Ghosh.