• Calendar

May 20, Tuesday
11:00 – 12:00

The vertex coloring and maximal independent set (henceforth, MIS) problems are central problems in the field of distributed algorithms and are intensively studied. Currently there are no known deterministic distributed algorithms that solve these problems in polylogarithmic time on general graphs. Goldberg, Plotkin, and Shannon, STOC'87, devised a logarithmic time algorithm for these problems on planar graphs. We devise a technique based on Nash-Williams forests decomposition that enables to compute efficiently a vertex coloring that uses a small number of colors on graphs with bounded arboricity. Then this coloring is used to compute an MIS in sublogarithmic time on this family of graphs. This family includes planar graphs, graphs with bounded genus, and graphs that exclude fixed minors, and thus our result improves and generalizes the twenty-year old result of Goldberg, Plotkin, and Shannon. We also show a nearly tight lower bound for the time required for computing distributed O(a)-coloring and O(a)-forests-decomposition. Based on joint work with Michael Elkin.