Distributed Deterministic Edge Coloring using Bounded Neighborhood Independence

摘要

We study the edge-coloring problem in the message-passing model of distributed computing. This is one of the most fundamental problems in this area. Currently, the best-known deterministic algorithms for (2△ - 1)-edge-coloring requires O(△) + log* n time [23], where △ is the maximum degree of the input graph. Also, recent results of [5] for vertex-coloring imply that one can get an O(△)-edge-coloring in O(△~∈ ·log n) time, and an O(△~(1+∈))-edge-coloring in O(log △ log n) time, for an arbitrarily small constant ∈ > 0. In this paper we devise a significantly faster deterministic edge-coloring algorithm. Specifically, our algorithm computes an O(△)-edge-coloring in O(△~∈) + log* n time, and an O(△~(1+∈))-edge-coloring in O(log △) + log* n time. This result improves the state-of-the-art running time for deterministic edge-coloring with this number of colors in almost the entire range of maximum degree △. Moreover, it improves it exponentially in a wide range of △, specifically, for 2~(Ω(log* n)) ≤ △ ≤ polylog(n). In addition, for small values of △ (up to log~(1-δ) n, for some fixed δ > 0) our deterministic algorithm outperforms all the existing randomized algorithms for this problem. On our way to these results we study the vertex-coloring problem on graphs with bounded neighborhood independence. This is a large family of graphs, which strictly includes line graphs of r-hypergraphs (i.e., hypergraphs in which each hy-peredge contains r or less vertices) for r = O(1), and graphs of bounded growth. We devise a very fast deterministic algorithm for vertex-coloring graphs with bounded neighborhood independence. This algorithm directly gives rise to our edge-coloring algorithms, which apply to general graphs. Our main technical contribution is a subroutine that computes an O(△/p)-defective p-vertex coloring of graphs with bounded neighborhood independence in O(p~2) +log* n time, for a parameter p, 1 ≤ p ≤ △. In all previous efficient distributed routines for m-defective p-coloring the product m·p is super-linear in △. In our routine this product is linear in △, and this enables us to speed up the coloring drastically.