Document Open Access Logo

Streaming and Massively Parallel Algorithms for Edge Coloring

Authors Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Marina Knittel, Hamed Saleh

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.15.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Soheil Behnezhad
  • University of Maryland, College Park, MD, USA
Mahsa Derakhshan
  • University of Maryland, College Park, MD, USA
MohammadTaghi Hajiaghayi
  • University of Maryland, College Park, MD, USA
Marina Knittel
  • University of Maryland, College Park, MD, USA
Hamed Saleh
  • University of Maryland, College Park, MD, USA

Funding

Supported in part by Guggenheim Fellowship, NSF grants CCF:SPX 1822738, IIS:BIGDATA 1546108, DARPA grant SI3CMD, UMD Year of Data Science Program Grant, and Northrop Grumman Faculty Award.

Acknowledgements

We thank the anonymous reviewers for many helpful comments and suggestions.

Cite As Get BibTex

Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Marina Knittel, and Hamed Saleh. Streaming and Massively Parallel Algorithms for Edge Coloring. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ESA.2019.15

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, Delta, 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 Delta+O~(Delta^(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-Omega(1)) if Delta = n^Omega(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 O~(n)-space streaming algorithm that always returns a valid coloring and uses 5.44 Delta colors with high probability if the edges arrive in a random order. For adversarial order streams, we give another one-pass O~(n)-space algorithm that requires O(Delta^2) colors.

Subject Classification

ACM Subject Classification
  • Theory of computation → Massively parallel algorithms
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • Massively Parallel Computation
  • Streaming
  • Edge Coloring

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Kook Jin Ahn and Sudipto Guha. Access to Data and Number of Iterations: Dual Primal Algorithms for Maximum Matching under Resource Constraints. In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA, June 13-15, 2015, pages 202-211, 2015. URL: https://doi.org/10.1145/2755573.2755586.
  2. Noga Alon, László Babai, and Alon Itai. A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem. J. Algorithms, 7(4):567-583, December 1986. URL: https://doi.org/10.1016/0196-6774(86)90019-2.
  3. Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev. Parallel algorithms for geometric graph problems. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 574-583, 2014. URL: https://doi.org/10.1145/2591796.2591805.
  4. Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, and Peilin Zhong. Parallel Graph Connectivity in Log Diameter Rounds. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 674-685, 2018. URL: https://doi.org/10.1109/FOCS.2018.00070.
  5. Eshrat Arjomandi. An efficient algorithm for colouring the edges of a graph with Δ+ 1 colours. INFOR: Information Systems and Operational Research, 20(2):82-101, 1982. Google Scholar
  6. Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, and Cliff Stein. Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. Proceedings of the 30th annual ACM-SIAM Symposium on Discrete Algorithms (SODA), to appear, 2019. Google Scholar
  7. Sepehr Assadi, Yu Chen, and Sanjeev Khanna. Sublinear Algorithms for (Δ + 1) Vertex Coloring. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 767-786, 2019. URL: https://doi.org/10.1137/1.9781611975482.48.
  8. Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The Locality of Distributed Symmetry Breaking. J. ACM, 63(3):20:1-20:45, June 2016. URL: https://doi.org/10.1145/2903137.
  9. MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Raimondas Kiveris, Silvio Lattanzi, and Vahab S. Mirrokni. Affinity Clustering: Hierarchical Clustering at Scale. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pages 6867-6877, 2017. URL: http://papers.nips.cc/paper/7262-affinity-clustering-hierarchical-clustering-at-scale.
  10. Paul Beame, Paraschos Koutris, and Dan Suciu. Communication Steps for Parallel Query Processing. J. ACM, 64(6):40:1-40:58, 2017. URL: https://doi.org/10.1145/3125644.
  11. Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi. Brief Announcement: Semi-MapReduce Meets Congested Clique. CoRR, abs/1802.10297, 2018. URL: http://arxiv.org/abs/1802.10297.
  12. Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, and Richard M. Karp. Massively Parallel Symmetry Breaking on Sparse Graphs: MIS and Maximal Matching. CoRR, abs/1807.06701, 2018. URL: http://arxiv.org/abs/1807.06701.
  13. Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, and Vahab Mirrokni. Near-Optimal Massively Parallel Graph Connectivity. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, to appear, 2019. Google Scholar
  14. Soheil Behnezhad, MohammadTaghi Hajiaghayi, and David G. Harris. Exponentially Faster Massively Parallel Maximal Matching. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, to appear, 2019. Google Scholar
  15. Sebastian Brandt, Manuela Fischer, and Jara Uitto. Matching and MIS for Uniformly Sparse Graphs in the Low-Memory MPC Model. CoRR, abs/1807.05374, 2018. URL: http://arxiv.org/abs/1807.05374.
  16. Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto, and Yufan Zheng. The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation. CoRR, abs/1808.08419, 2018. URL: http://arxiv.org/abs/1808.08419.
  17. Artur Czumaj, Jakub Lacki, Aleksander Madry, Slobodan Mitrovic, Krzysztof Onak, and Piotr Sankowski. Round Compression for Parallel Matching Algorithms. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 471-484, 2018. URL: https://doi.org/10.1145/3188745.3188764.
  18. Camil Demetrescu, Irene Finocchi, and Andrea Ribichini. Trading off space for passes in graph streaming problems. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006, pages 714-723, 2006. URL: http://dl.acm.org/citation.cfm?id=1109557.1109635.
  19. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On Graph Problems in a Semi-streaming Model. In Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings, pages 531-543, 2004. URL: https://doi.org/10.1007/978-3-540-27836-8_46.
  20. Pierre Fraigniaud, Marc Heinrich, and Adrian Kosowski. Local Conflict Coloring. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 625-634, 2016. URL: https://doi.org/10.1109/FOCS.2016.73.
  21. H. N. Gabow, T. Nishizeki, O. Kariv, D. Leven, , and O. Terada. Algorithms for edgecoloring graphs. Technical report, Tohoku University, 1985. Google Scholar
  22. Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrovic, and Ronitt Rubinfeld. Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018, pages 129-138, 2018. URL: https://doi.org/10.1145/3212734.3212743.
  23. Christian Glazik, Jan Schiemann, and Anand Srivastav. Finding Euler Tours in One Pass in the W-Streaming Model with O(n log(n)) RAM. CoRR, abs/1710.04091, 2017. URL: http://arxiv.org/abs/1710.04091.
  24. A. Goldberg, S. Plotkin, and G. Shannon. Parallel Symmetry-breaking in Sparse Graphs. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC '87, pages 315-324, New York, NY, USA, 1987. ACM. URL: https://doi.org/10.1145/28395.28429.
  25. Andrew V. Goldberg and Serge A. Plotkin. Parallel (Δ+1)-coloring of Constant-degree Graphs. Inf. Process. Lett., 25(4):241-245, June 1987. URL: https://doi.org/10.1016/0020-0190(87)90169-4.
  26. Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, Searching, and Simulation in the MapReduce Framework. In Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings, pages 374-383, 2011. URL: https://doi.org/10.1007/978-3-642-25591-5_39.
  27. David G Harris, Johannes Schneider, and Hsin-Hao Su. Distributed (Δ+1)-coloring in sublogarithmic rounds. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 465-478. ACM, 2016. Google Scholar
  28. Nicholas J. A. Harvey, Christopher Liaw, and Paul Liu. Greedy and Local Ratio Algorithms in the MapReduce Model. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, SPAA '18, pages 43-52, New York, NY, USA, 2018. ACM. URL: https://doi.org/10.1145/3210377.3210386.
  29. Öjvind Johansson. Simple Distributed Delta+1-coloring of Graphs. Inf. Process. Lett., 70(5):229-232, 1999. URL: https://doi.org/10.1016/S0020-0190(99)00064-2.
  30. Tomasz Jurdzinski and Krzysztof Nowicki. MST in O(1) rounds of congested clique. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2620-2632, 2018. URL: https://doi.org/10.1137/1.9781611975031.167.
  31. Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. A Model of Computation for MapReduce. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 938-948, 2010. URL: https://doi.org/10.1137/1.9781611973075.76.
  32. Fabian Kuhn and Rogert Wattenhofer. On the Complexity of Distributed Graph Coloring. In Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing, PODC '06, pages 7-15, New York, NY, USA, 2006. ACM. URL: https://doi.org/10.1145/1146381.1146387.
  33. Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii. Filtering: a method for solving graph problems in MapReduce. In SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, San Jose, CA, USA, June 4-6, 2011 (Co-located with FCRC 2011), pages 85-94, 2011. URL: https://doi.org/10.1145/1989493.1989505.
  34. Nathan Linial. Locality in Distributed Graph Algorithms. SIAM J. Comput., 21(1):193-201, February 1992. URL: https://doi.org/10.1137/0221015.
  35. M Luby. A Simple Parallel Algorithm for the Maximal Independent Set Problem. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, STOC '85, pages 1-10, New York, NY, USA, 1985. ACM. URL: https://doi.org/10.1145/22145.22146.
  36. Alessandro Panconesi and Aravind Srinivasan. Improved Distributed Algorithms for Coloring and Network Decomposition Problems. In Proceedings of the Twenty-fourth Annual ACM Symposium on Theory of Computing, STOC '92, pages 581-592, New York, NY, USA, 1992. ACM. URL: https://doi.org/10.1145/129712.129769.
  37. Merav Parter. (Δ+1) Coloring in the Congested Clique Model. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 160:1-160:14, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.160.
  38. Merav Parter and Hsin-Hao Su. Randomized (Δ+1)-Coloring in O(log^* Δ) Congested Clique Rounds. In 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018, pages 39:1-39:18, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.39.
  39. Vadim G Vizing. On an estimate of the chromatic class of a p-graph. Discret Analiz, 3:25-30, 1964. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact