The complexity of \((\Delta+1)\) coloring in congested clique, massively parallel computation, and centralized local computation. (English) Zbl 1530.68198
Nowak, Thomas (ed.), Proceedings of the 38th ACM symposium on principles of distributed computing, PODC ’19, Toronto, ON, Canada, July 29 – August 2, 2019. New York, NY: Association for Computing Machinery (ACM). 471-480 (2019).
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C15 | Coloring of graphs and hypergraphs |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68W10 | Parallel algorithms in computer science |
| 68W15 | Distributed algorithms |
| 68W20 | Randomized algorithms |
| 68W40 | Analysis of algorithms |
References:
| [1] | Kook Jin Ahn and Sudipto Guha. 2015. Access to Data and Number of Iterations: Dual Primal Algorithms for Maximum Matching Under Resource Constraints. In Proc. SPAA. 202-211. 10.1145/2755573.2755586 · Zbl 1333.68291 |
| [2] | Noga Alon and Joel H. Spencer. 2016. The Probabilistic Method 4th ed.). Wiley Publishing. · Zbl 1333.05001 |
| [3] | Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev. 2014. Parallel Algorithms for Geometric Graph Problems. In Proc. Symposium on Theory of Computation (STOC). 574-583. 10.1145/2591796.2591805 · Zbl 1315.05133 |
| [4] | Alexandr Andoni, Clifford Stein, Zhao Song, Zhengyu Wang, and Peilin Zhong. 2018. Parallel Graph Connectivity in Log Diameter Rounds. In Proceedings 59th IEEE Symposium on Foundations of Computer Science (FOCS). 674-685. |
| [5] | Sepehr Assadi. 2017. Simple round compression for parallel vertex cover. arXiv preprint arXiv:1709.04599 (2017). |
| [6] | Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab Mirrokni, and Cliff Stein. 2019. Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs. In Proceedings 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). · Zbl 1431.68143 |
| [7] | Sepehr Assadi, Yu Chen, and Sanjeev Khanna. 2019. Sublinear Algorithms for (Δ 1) Vertex Coloring. In Proceedings 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). · Zbl 1431.68174 |
| [8] | Sepehr Assadi, Xiaorui Sun, and Omri Weinstein. 2018. Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs. arXiv preprint arXiv:1805.02974 (2018). · Zbl 1542.68123 |
| [9] | Leonid Barenboim, Michael Elkin, and Uri Goldenberg. 2018. Locally-Iterative Distributed (Δ 1)-Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC). ACM, 437-446. 10.1145/3212734.3212769 · Zbl 1428.68365 |
| [10] | Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. 2016. The Locality of Distributed Symmetry Breaking. J. ACM, Vol. 63, 3, Article 20 (2016), pages 20:1-20:45 pages. 10.1145/2903137 · Zbl 1426.68020 |
| [11] | Leonid Barenboim and Victor Khazanov. 2018. Distributed Symmetry-Breaking Algorithms for Congested Cliques. In Computer Science - Theory and Applications - 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6-10, 2018, Proceedings. 41-52. · Zbl 1484.68320 |
| [12] | Paul Beame, Paraschos Koutris, and Dan Suciu. 2013. Communication Steps for Parallel Query Processing. In Proceedings of the 32Nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS). 273-284. 10.1145/2463664.2465224 · Zbl 1426.68074 |
| [13] | Paul Beame, Paraschos Koutris, and Dan Suciu. 2014. Skew in Parallel Query Processing. In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS). 212-223. 10.1145/2594538.2594558 · Zbl 1426.68074 |
| [14] | Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. 2017. Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. In 31st International Symposium on Distributed Computing (DISC 2017) (Leibniz International Proceedings in Informatics (LIPIcs)),, Andréa W. Richa (Ed.), Vol. 91. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 7:1-7:16. · Zbl 1515.68357 |
| [15] | Andrew Berns, James Hegeman, and Sriram V Pemmaraju. 2012. Super-fast distributed algorithms for metric facility location. In Automata, Languages, and Programming. Springer, 428-439. 10.1007/978-3-642-31585-5_39 · Zbl 1367.68338 |
| [16] | Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi, MohammadTaghi HajiAghayi, and Saeed Seddighin 2018. Approximating edit distance in truly subquadratic time: quantum and MapReduce. In Proc. Symposium on Discrete Algorithms (SODA). 1170-1189. · Zbl 1403.68367 |
| [17] | Sebastian Brandt, Manuela Fischer, and Jara Uitto. 2018. Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with n ε Memory per Machine. arXiv preprint arXiv:1802.06748 (2018). · Zbl 1535.68098 |
| [18] | Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. 2016. Algebraic methods in the congested clique. Distributed Computing (2016). · Zbl 1333.05283 |
| [19] | Keren Censor-Hillel, Dean Leitersdorf, and Elia Turner. 2018 Sparse Matrix Multiplication with Bandwidth Restricted All-to-All Communication. CoR, Vol. abs/1802.04789 (2018). · Zbl 07561432 |
| [20] | Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto, and Yufan Zheng. 2018a. The Complexity of (Δ 1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation. CoRR, Vol. abs/1808.08419 (2018). arxiv: 1808.08419 http://arxiv.org/abs/1808.08419 · Zbl 1530.68198 |
| [21] | Yi-Jun Chang, Wenzheng Li, and Seth Pettie. 2018b. An Optimal Distributed (Δ 1)-coloring Algorithm?. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018). ACM, New York, NY, USA, 445-456. 10.1145/3188745.3188964 · Zbl 1427.68355 |
| [22] | Artur Czumaj, Jakub Lacki, Aleksander Madry, Slobodan Mitrovic, Krzysztof Onak, and Piotr Sankowski. 2018. Round Compression for Parallel Matching Algorithms. In Proc. Symposium on Theory of Computation (STOC). 471-484. 10.1145/3188745.3188764 · Zbl 1427.68354 |
| [23] | Jeffrey Dean and Sanjay Ghemawat. 2004. MapReduce: Simplified Data Processing on Large Clusters. In Proceedings of the 6th Conference on Symposium on Operating Systems Design & Implementation (OSDI). USENIX Association, Berkeley, CA, USA, 10-10. http://dl.acm.org/citation.cfm?id=1251254.1251264 |
| [24] | Danny Dolev, Christoph Lenzen, and Shir Peled. 2012. “Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting. In Distributed Computing. Springer, 195-209. 10.1007/978-3-642-33651-5_14 · Zbl 1377.68316 |
| [25] | Andrew Drucker, Fabian Kuhn, and Rotem Oshman. 2014. On the Power of the Congested Clique Model. In Proc. Principles of Distributed Computing (PODC). ACM, 367-376. 10.1145/2611462.2611493 · Zbl 1321.68381 |
| [26] | Manuela Fischer and Mohsen Ghaffari. 2017. Sublogarithmic Distributed Algorithms for Lovász Local Lemma with Implications on Complexity Hierarchies. In Proceedings 31st International Symposium on Distributed Computing (DISC). 18:1-18:16. · Zbl 1515.68367 |
| [27] | Pierre Fraigniaud, Marc Heinrich, and Adrian Kosowski. 2016. Local conflict coloring. In Proceedings 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 625-634. |
| [28] | Francois Le Gall. 2016. Further Algebraic Algorithms in the Congested Clique Model and Applications to Graph-Theoretic Problems. In DISC. · Zbl 1393.68185 |
| [29] | Mohsen Ghaffari. 2016. An improved distributed algorithm for maximal independent set. In Proceedings 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 270-277. · Zbl 1411.68175 |
| [30] | Mohsen Ghaffari. 2017. Distributed MIS via All-to-All Communication. In Proc. Principles of Distributed Computing (PODC). 141-149. 10.1145/3087801.3087830 · Zbl 1380.68424 |
| [31] | Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrović, and Ronitt Rubinfeld. 2018. Improved massively parallel computation algorithms for mis, matching, and vertex cover. In Proc. Principles of Distributed Computing (PODC). arXiv:1802.08237. 10.1145/3212734.3212743 · Zbl 1428.68376 |
| [32] | Mohsen Ghaffari and Jara Uitto. 2019. Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation. In Proceedings 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). · Zbl 1431.68133 |
| [33] | Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. 2011. Sorting, searching, and simulation in the MapReduce framework. In Proc. ISAAC. Springer, 374-383. 10.1007/978-3-642-25591-5_39 · Zbl 1350.68085 |
| [34] | David G Harris, Johannes Schneider, and Hsin-Hao Su. 2018. Distributed (Δ 1)-Coloring in Sublogarithmic Rounds. J. ACM, Vol. 65, 4 (2018), 19:1-19:21. 10.1145/3178120 · Zbl 1426.68214 |
| [35] | Nicholas J. A. Harvey, Christopher Liaw, and Paul Liu. 2018. Greedy and Local Ratio Algorithms in the MapReduce Model. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM, New York, NY, USA, 43-52. 10.1145/3210377.3210386 |
| [36] | James W. Hegeman, Gopal Pandurangan, Sriram V. Pemmaraju, Vivek B. Sardeshmukh, and Michele Scquizzato. 2015. Toward Optimal Bounds in the Congested Clique: Graph Connectivity and MST. In Proc. Principles of Distributed Computing (PODC). ACM, 91-100. 10.1145/2767386.2767434 · Zbl 1333.68211 |
| [37] | James W Hegeman and Sriram V Pemmaraju. 2015a. Lessons from the congested clique applied to Map Reduce. Theoretical Computer Science, Vol. 608 (2015), 268-281. 10.1016/j.tcs.2015.09.029 · Zbl 1333.68277 |
| [38] | James W. Hegeman and Sriram V. Pemmaraju. 2015b. Lessons from the Congested Clique Applied to MapReduce. Theor. Comput. Sci., Vol. 608, P3 (Dec. 2015), 268-281. 10.1016/j.tcs.2015.09.029 · Zbl 1333.68277 |
| [39] | James W Hegeman, Sriram V Pemmaraju, and Vivek B Sardeshmukh. 2014. Near-constant-time distributed algorithms on a congested clique. In Distributed Computing. Springer, 514-530. · Zbl 1540.68307 |
| [40] | Sungjin Im, Benjamin Moseley, and Xiaorui Sun. 2017. Efficient Massively Parallel Methods for Dynamic Programming. In Proc. Symposium on Theory of Computation (STOC). 798-811. 10.1145/3055399.3055460 · Zbl 1370.68316 |
| [41] | Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly. 2007. Dryad: Distributed Data-parallel Programs from Sequential Building Blocks. SIGOPS Operating Systems Review, Vol. 41, 3 (2007), 59-72. 10.1145/1272998.1273005 |
| [42] | Tomasz Jurdzinski and Krzysztof Nowicki. 2018. 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. 2620-2632. · Zbl 1403.68335 |
| [43] | Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. 2010. A Model of Computation for MapReduce. In Proc. Symposium on Discrete Algorithms (SODA). 938-948. · Zbl 1288.68247 |
| [44] | Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii. 2011. Filtering: a method for solving graph problems in Map Reduce. In Proc. SPAA. 85-94. 10.1145/1989493.1989505 |
| [45] | Christoph Lenzen. 2013. Optimal Deterministic Routing and Sorting on the Congested Clique. In Proceedings 33rd ACM Symposium on Principles of Distributed Computing (PODC). 42-50. 10.1145/2484239.2501983 · Zbl 1323.68034 |
| [46] | Christoph Lenzen and Roger Wattenhofer. 2010. Brief Announcement: Exponential Speed-up of Local Algorithms Using Non-local Communication. In Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC). ACM, 295-296. 10.1145/1835698.1835772 · Zbl 1290.68130 |
| [47] | Reut Levi and Moti Medina. 2017. A (centralized) local guide. Bulletin of EATCS, Vol. 2, 122 (2017). · Zbl 1409.68218 |
| [48] | Nathan Linial. 1992. Locality in Distributed Graph Algorithms. SIAM J. Comput., Vol. 21, 1 (1992), 193-201. 10.1137/0221015 · Zbl 0787.05058 |
| [49] | Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, and David Peleg. 2005. Minimum-weight spanning tree construction in O(log log n) communication rounds. SIAM J. Comput., Vol. 35, 1 (2005), 120-131. 10.1137/S0097539704441848 · Zbl 1082.05522 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
