Deterministic Distributed (Delta + o(Delta))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity

ABSTRACT

In the distributed message-passing setting a communication network is represented by a graph whose vertices represent processors that perform local computations and communicate over the edges of the graph. In the distributed edge-coloring problem the processors are required to assign colors to edges, such that all edges incident on the same vertex are assigned distinct colors. The previously-known deterministic algorithms for edge-coloring employed at least (2Δ - 1) colors, even though any graph admits an edge-coloring with Δ + 1 colors [36]. Moreover, the previously-known deterministic algorithms that employed at most O(Δ) colors required superlogarithmic time [3,6,7,17]. In the current paper we devise deterministic edge-coloring algorithms that employ only Δ + o(Δ) colors, for a very wide family of graphs. Specifically, as long as the arboricity a of the graph is a = O(Δ^{1 - ε}), for a constant ε > 0, our algorithm computes such a coloring within polylogarithmic deterministic time. We also devise significantly improved deterministic edge-coloring algorithms for general graphs for a very wide range of parameters. Specifically, for any value κ in the range [4Δ, 2^{o(log Δ)} ⋅ Δ], our κ-edge-coloring algorithm has smaller running time than the best previously-known κ-edge-coloring algorithms. Our algorithms are actually much more general, since edge-coloring is equivalent to vertex-coloring of line graphs. Our method is applicable to vertex-coloring of the family of graphs with bounded diversity that contains line graphs, line graphs of hypergraphs, and many other graphs. We significantly improve upon previous vertex-coloring of such graphs, and as an implication also obtain the improved edge-coloring algorithms for general graphs.

Our results are obtained using a novel technique that connects vertices or edges in a certain way that reduces clique size. The resulting structures, which we call connectors, can be colored more efficiently than the original graph. Moreover, the color classes constitute simpler subgraphs that can be colored even more efficiently using appropriate connectors. We introduce several types of connectors that are useful for various scenarios. We believe that this technique is of independent interest.

References

1. N. Alon, L. Babai, and A. Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. of Algorithms, 7(4):567--583, 1986.
2. B. Awerbuch, A. V. Goldberg, M. Luby, and S. Plotkin. Network decomposition and locality in distributed computation. In Proc. of the 30th Annual Symposium on Foundations of Computer Science, pages 364--369, 1989.
3. L. Barenboim. Deterministic (Δ+1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic and Faulty Networks. In Proc of the 34th ACM Symp. on Principles of Distributed Computing, pages 345--354, 2015.
4. L. Barenboim, and M. Elkin. Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition. In Proc. of the 27th ACM Symp. on Principles of Distributed Computing, pages 25--34, 2008.
5. L. Barenboim, and M. Elkin. Distributed (Δ+1)-coloring in linear (in Δ) time. In Proc. of the 41th ACM Symp. on Theory of Computing, pages 111--120, 2009.
6. L. Barenboim, and M. Elkin. Deterministic distributed vertex coloring in polylogarithmic time. In Proc. 29th ACM Symp. on Principles of Distributed Computing, pages 410--419, 2010.
7. L. Barenboim, and M. Elkin. Distributed deterministic edge coloring using bounded neighborhood independence. In Proc. of the 30th ACM Symp. on Principles of Distributed Computing, pages 129 - 138, 2011.
8. L. Barenboim, and M. Elkin. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan-Claypool Synthesis Lectures on Distributed Computing Theory, 2013.
9. L. Barenboim, M. Elkin, and F. Kuhn. Distributed (Delta+1)-Coloring in Linear (in Delta) Time. SIAM Journal on Computing, 43(1): 72--95, 2014.
10. L. Barenboim, M. Elkin, S. Pettie, and J. Schneider. The locality of distributed symmetry breaking. In Proc. of the 53rd Annual Symposium on Foundations of Computer Science, pages 321--330, 2012.
11. B. Berger, and J. Rompel. Simulating (log cn)-wise independence in NC. Journal of the ACM, 38(4), pages 1026--1046. 1991.
12. R. Cole, and U. Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control, 70(1):32--53, 1986.
13. A. Czygrinow, M. Hanckowiak, and M. Karonski. Distributed O(Delta logn)-edge-coloring algorithm. In Proc. of the 9th Annual European Symposium on Algorithms, pages 345--355, 2001.
14. D. Dubhashi, D. Grable, and A. Panconesi. Nearly-optimal distributed edge-colouring via the nibble method. Theoretical Computer Science, a special issue for the best papers of ESA95, 203(2):225--251, 1998.
15. T. Erlebach, and K. Jansen. The complexity of path coloring and call scheduling. Theoretical Computer Science, 255 (1--2), pages 33--50, 2001.
16. M. Elkin, S. Pettie, and H. Su. (2Δ - 1)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting. In Proc. of the 26th ACM-SIAM Symp. on Discrete Algorithms, pages 355--370, 2015.
17. P. Fraigniaud, M. Heinrich, and A. Kosowski. Local Conflict Coloring. http://arxiv.org/abs/1511.01287. To appear in FOCS 2016.
18. M. Fürer, and B. Raghavachari. Parallel edge coloring approximation. Parallel processing letters, 6(3), pages 321--329, 1996.
19. S. Gandham, M. Dawande, and R. Prakash. Link scheduling in sensor networks: distributed edge coloring revisited. In Proc. of IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies, pp. 2492--2501, 2005.
20. M. Ghaffari and H. Su. Distributed Degree Splitting, Edge Coloring, and Orientations. https://arxiv.org/abs/1608.03220. To appear in SODA 2016.
21. A. Goldberg, S. Plotkin, and G. Shannon. Parallel symmetry-breaking in sparse graphs. SIAM Journal on Discrete Mathematics, 1(4):434--446, 1988.
22. D. Grable, and A. Panconesi. Nearly optimal distributed edge colouring in O(log log n) rounds. Random Structures and Algorithms, 10(3): 385--405, 1997.
23. Y. Han, W. Liang, and X. Shen. Very fast parallel algorithms for approximate edge coloring. Discrete applied mathematics, 108(3), 227--238, 2001.
24. M. Hanckowiak, M. Karonski, and A. Panconesi. On the distributed complexity of computing maximal matchings. SIAM Journal on Discrete Mathematics, 15(1):41--57, 2001.
25. H. Karloff, and D. Shmoys. Efficient parallel algorithms for edge coloring problems. Journal of Algorithms, 8(1), pages 39--52, 1987.
26. A. Korman, J. Sereni, and L. Viennot. Toward more localized local algorithms: removing assumptions concerning global knowledge. In Proc. of the 30th ACM Symp. on Principles of Distributed Computing, pages 49--58, 2011.
27. F. Kuhn. Weak graph colorings: distributed algorithms and applications. In Proc. of the 21st ACM Symposium on Parallel Algorithms and Architectures, pages 138--144, 2009.
28. F. Kuhn, and R. Wattenhofer. On the complexity of distributed graph coloring. In Proc. 25th ACM Symp. on Principles of Distributed Computing, pages 7--15, 2006.
29. W. Liang, X. Shen, and Q .Hu. Parallel Algorithms for the Edge-Coloring and Edge-Coloring Update Problems. Journal of Parallel and Distributed Computing, 32(1), Pages 66--73, 1996.
30. N. Linial. Distributive graph algorithms: Global solutions from local data In Proc. of the 28th Annual Symp. on Foundation of Computer Science, pp. 331--335, 1987.
31. J. Mycielski. Sur le coloriage des graphes. Colloq. Math. 3, pages 161--162, 1955.
32. R. Motwani, J. Naor, and M. Naor. The probabilistic method yields deterministic parallel algorithms. J. of Computer and System Sciences, 49(3), 478--516, 1994.
33. A. Panconesi, and R. Rizzi. Some simple distributed algorithms for sparse networks. Distributed Computing, 14(2):97--100, 2001.
34. A. Panconesi, and A. Srinivasan. Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds. SIAM Journal on Computing, 26(2):350--368, 1997.
35. D. Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000.
36. V. Vizing. On an estimate of the chromatic class of a p-graph. Metody Diskret. Analiz, 3: 25--30, 1964.
37. D. Williamson, L. Hall, J. Hoogeveen, C. Hurkens, J. Lenstra, S. Sevast'janov, and D. Shmoys. Short shop schedules. Operations Research, 45 (2), pp. 288--294, 1997.
38. X. Zhou, and T. Nishizeki. Edge-coloring and f-coloring for various classes of graphs. Journal of Graph Algorithms and Applications, 3(1), 1--18. 1998.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph coloring

• Theory of computation

  • Design and analysis of algorithms

    • Graph algorithms analysis