Hamed Saleh

PhD student

Streaming and Massively Parellel Algorithms for Edge Coloring

  Friday, 03 January 2020
  09:00 - 09:45

Abstract

A valid edge-coloring of a graph is an assignment of “colors” to its edges such that no two incident edges receive the same color. The goal is to find a proper coloring that uses few colors. (Note that the maximum degree, ∆, is a trivial lower bound.) In this paper, we revisit this fundamental problem in two models of computation specific to massive graphs, the Massively Parallel Computations (MPC) model and the Graph Streaming model:

Massively Parallel Computation: We give a randomized MPC algorithm that with high probability returns a ∆ + Õ(∆^{3/4}) edge coloring in O(1) rounds using O(n) space per machine and O(m) total space. The space per machine can also be further improved to n^{1−Ω(1)} if ∆ = n^{Ω(1)}. Our algorithm improves upon a previous result of Harvey et al. [SPAA 2018].

Graph Streaming: Since the output of edge-coloring is as large as its input, we consider a standard variant of the streaming model where the output is also reported in a streaming fashion. The main challenge is that the algorithm cannot “remember” all the reported edge colors, yet has to output a proper edge coloring using few colors. We give a one-pass Õ(n)-space streaming algorithm that always returns a valid coloring and uses 5.44∆ colors with high probability if the edges arrive in a random order. For adversarial order streams, we give another one-pass Õ(n)-space algorithm that requires O(∆^2) colors.

Bio

I am a PhD student in the Computer Science Department at the University of Maryland, advised by Prof. Hajiaghayi. I work on combinatorial problems in distributed/parallel models, in particular models with sublinear memory such as MPC. Prior to joining the University of Maryland, I earned my BS degrees in Computer Engineering at Sharif University of Technology.