Overview

The state of the art in distributed symmetry breaking

A curated database of algorithms and lower bounds for six fundamental problems in distributed graph algorithms, in the LOCAL and CONGEST models, deterministic and randomized. For every range of the maximum degree Δ, the atlas highlights which results are the state of the art.

Maximal matching A set of disjoint edges that cannot be extended. Maximal independent set A set of pairwise non-adjacent nodes that cannot be extended. Vertex coloring Colors for the nodes so that adjacent nodes differ. Edge coloring Colors for the edges so that adjacent edges differ. Network decomposition Low-diameter clusters, colored so that adjacent clusters differ. Degree splitting Two colors or an orientation for the edges, balanced at every node.

Many results follow from others through reductions, for example a maximal matching from an MIS of the line graph; the tables show them next to the results they are derived from. The bibliography lists every paper the atlas draws on.

The data is open: every entry is a file in the GitHub repository, licensed under CC BY 4.0. Missing a result or found a mistake? Use the Report an issue button next to any result or paper.

Back to my homepage