Document Open Access Logo

Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models

Authors Suman K. Bera, Amit Chakrabarti , Prantar Ghosh

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.11.pdf
  • Filesize: 0.65 MB
  • 21 pages

Document Identifiers

Author Details

Suman K. Bera
  • University of California at Santa Cruz, CA, USA
Amit Chakrabarti
  • Dartmouth College, Hanover, NH, USA
Prantar Ghosh
  • Dartmouth College, Hanover, NH, USA

Funding

This work was supported in part by NSF under award CCF-190773 and by the Simons Institute for the Theory of Computing, which hosted the second author while the work was in progress.

Acknowledgements

The authors gratefully acknowledge several helpful discussions with Sepehr Assadi (especially those that called to their attention a nuance with the Congested Clique algorithm) and Deeparnab Chakrabarty.

Cite As Get BibTex

Suman K. Bera, Amit Chakrabarti, and Prantar Ghosh. Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.11

Abstract

We study the problem of coloring a given graph using a small number of colors in several well-established models of computation for big data. These include the data streaming model, the general graph query model, the massively parallel communication (MPC) model, and the CONGESTED-CLIQUE and the LOCAL models of distributed computation. On the one hand, we give algorithms with sublinear complexity, for the appropriate notion of complexity in each of these models. Our algorithms color a graph G using κ(G)⋅(1+o(1)) colors, where κ(G) is the degeneracy of G: this parameter is closely related to the arboricity α(G). As a function of κ(G) alone, our results are close to best possible, since the optimal number of colors is κ(G)+1. For several classes of graphs, including real-world "big graphs," our results improve upon the number of colors used by the various (Δ(G)+1)-coloring algorithms known for these models, where Δ(G) is the maximum degree in G, since Δ(G) ⩾ κ(G) and can in fact be arbitrarily larger than κ(G).
On the other hand, we establish certain lower bounds indicating that sublinear algorithms probably cannot go much further. In particular, we prove that any randomized coloring algorithm that uses at most κ(G)+O(1) colors would require Ω(n²) storage in the one pass streaming model, and Ω(n²) many queries in the general graph query model, where n is the number of vertices in the graph. These lower bounds hold even when the value of κ(G) is known in advance; at the same time, our upper bounds do not require κ(G) to be given in advance.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming models
  • Theory of computation → Dynamic graph algorithms
  • Theory of computation → Sketching and sampling
  • Theory of computation → Lower bounds and information complexity
Keywords
  • Data streaming
  • Graph coloring
  • Sublinear algorithms
  • Massively parallel communication
  • Distributed algorithms

Metrics

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

Related Versions

References

  1. Amir Abboud, Keren Censor-Hillel, Seri Khoury, and Ami Paz. Smaller cuts, higher lower bounds. CoRR, abs/1901.01630, 2019. URL: http://arxiv.org/abs/1901.01630.
  2. Farid Ablayev. Lower bounds for one-way probabilistic communication complexity and their application to space complexity. Theor. Comput. Sci., 175(2):139-159, 1996. Google Scholar
  3. Noga Alon, László Babai, and Alon Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. Journal of algorithms, 7(4):567-583, 1986. Google Scholar
  4. Sabeur Aridhi, Martin Brugnara, Alberto Montresor, and Yannis Velegrakis. Distributed k-core decomposition and maintenance in large dynamic graphs. In Proceedings of the 10th ACM International Conference on Distributed and Event-based Systems, DEBS '16, Irvine, CA, USA, June 20 - 24, 2016, pages 161-168, 2016. Google Scholar
  5. Sepehr Assadi, Yu Chen, and Sanjeev Khanna. Sublinear algorithms for (Δ+ 1) vertex coloring. In Proc. 30th Annual ACM-SIAM Symposium on Discrete Algorithms, page To Appear, 2019. Google Scholar
  6. Gary D. Bader and Christopher WV Hogue. An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics, 4(1):2, January 2003. Google Scholar
  7. Bahman Bahmani, Ravi Kumar, and Sergei Vassilvitskii. Densest subgraph in streaming and mapreduce. International Conference on Very Large Data Bases, 5(5):454-465, 2012. Google Scholar
  8. Balabhaskar Balasundaram and Sergiy Butenko. Graph domination, coloring and cliques in telecommunications. In Handbook of Optimization in Telecommunications, pages 865-890. Springer, 2006. Google Scholar
  9. Luis Barba, Jean Cardinal, Matias Korman, Stefan Langerman, André van Renssen, Marcel Roeloffzen, and Sander Verdonschot. Dynamic graph coloring. Algorithmica, 81(4):1319-1341, 2019. Google Scholar
  10. Leonid Barenboim. Deterministic (Δ+ 1)-coloring in sublinear (in Δ) time in static, dynamic, and faulty networks. Journal of the ACM (JACM), 63(5):47, 2016. Google Scholar
  11. Leonid Barenboim and Michael Elkin. Sublogarithmic distributed mis algorithm for sparse graphs using nash-williams decomposition. Distributed Computing, 22(5-6):363-379, 2010. Google Scholar
  12. Leonid Barenboim and Michael Elkin. Deterministic distributed vertex coloring in polylogarithmic time. Journal of the ACM (JACM), 58(5):23, 2011. Google Scholar
  13. Leonid Barenboim and Michael Elkin. Distributed Graph Coloring: Fundamentals and Recent Developments. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers, 2013. Google Scholar
  14. Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of distributed symmetry breaking. Journal of the ACM (JACM), 63(3):20, 2016. Google Scholar
  15. Nicolas Barnier and Pascal Brisset. Graph coloring for air traffic flow management. Annals of operations research, 130(1-4):163-178, 2004. Google Scholar
  16. Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. Journal of the ACM (JACM), 64(6):40, 2017. Google Scholar
  17. Soheil Behnezhad, Mahsa Derakhshan, and Mohammad Taghi Hajiaghayi. Brief announcement: Semi-mapreduce meets congested clique. CoRR, abs/1802.10297, 2018. Google Scholar
  18. Suman K. Bera, Amit Chakrabarti, and Prantar Ghosh. Graph coloring via degeneracy in streaming and other space-conscious models. CoRR, abs/1905.00566, 2019. URL: http://arxiv.org/abs/1905.00566.
  19. Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, and Danupon Nanongkai. Dynamic algorithms for graph coloring. In Proc. 39th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1-20, 2018. Google Scholar
  20. K. Bhawalkar, J. Kleinberg, K. Lewi, T. Roughgarden, and A. Sharma. Preventing unraveling in social networks: The anchored k-core problem. SIAM Journal on Discrete Mathematics, 29(3):1452-1475, 2015. Google Scholar
  21. Gregory J Chaitin. Register allocation & spilling via graph coloring. In ACM Sigplan Notices, volume 17, pages 98-105, 1982. Google Scholar
  22. Gregory J Chaitin, Marc A Auslander, Ashok K Chandra, John Cocke, Martin E Hopkins, and Peter W Markstein. Register allocation via coloring. Computer languages, 6(1):47-57, 1981. Google Scholar
  23. 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. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, page 471–480, 2019. Google Scholar
  24. Yi-Jun Chang, Wenzheng Li, and Seth Pettie. An optimal distributed (Δ+ 1)-coloring algorithm. In Proc. 50th Annual ACM Symposium on the Theory of Computing, pages 445-456, 2018. Google Scholar
  25. Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan. Approximating the minimum spanning tree weight in sublinear time. SIAM Journal on computing, 34(6):1370-1379, 2005. Google Scholar
  26. Fred C Chow and John L Hennessy. The priority-based coloring approach to register allocation. ACM Transactions on Programming Languages and Systems (TOPLAS), 12(4):501-536, 1990. Google Scholar
  27. Jeffrey Dean and Sanjay Ghemawat. Mapreduce: Simplified data processing on large clusters. In 6th Symposium on Operating System Design and Implementation (OSDI 2004), San Francisco, California, USA, December 6-8, 2004, pages 137-150, 2004. Google Scholar
  28. P. Erdős and A. Hajnal. On chromatic number of graphs and set-systems. Acta Mathematica Academiae Scientiarum Hungarica, 17(1):61-99, March 1966. Google Scholar
  29. Hossein Esfandiari, Silvio Lattanzi, and Vahab S. Mirrokni. Parallel and streaming algorithms for k-core decomposition. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, pages 1396-1405, 2018. Google Scholar
  30. Martín Farach-Colton and Meng-Tsung Tsai. Tight approximations of degeneracy in large graphs. In LATIN 2016: Theoretical Informatics, pages 429-440. Springer Berlin Heidelberg, 2016. Google Scholar
  31. Uriel Feige and Joe Kilian. Zero knowledge and the chromatic number. In Annual IEEE Conference on Computational Complexity, page 278, 1996. Google Scholar
  32. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On graph problems in a semi-streaming model. Theor. Comput. Sci., 348(2-3):207-216, 2005. Preliminary version in Proc. 31st International Colloquium on Automata, Languages and Programming , pages 531-543, 2004. Google Scholar
  33. Pierre Fraigniaud, Marc Heinrich, and Adrian Kosowski. Local conflict coloring. In Proc. 57th Annual IEEE Symposium on Foundations of Computer Science, pages 625-634, 2016. Google Scholar
  34. Eugene C. Freuder. A sufficient condition for backtrack-free search. J. ACM, 29(1):24-32, 1982. Google Scholar
  35. Mohsen Ghaffari and Christiana Lymouri. Simple and near-optimal distributed coloring for sparse graphs. In 31st International Symposium on Distributed Computing (DISC 2017), page 20, 2017. Google Scholar
  36. Mohsen Ghaffari and Ali Sayyadi. Distributed Arboricity-Dependent Graph Coloring via All-to-All Communication. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 142:1-142:14, 2019. Google Scholar
  37. Anna C. Gilbert and Piotr Indyk. Sparse recovery using sparse matrices. Proceedings of the IEEE, 98(6):937-947, 2010. Google Scholar
  38. Oded Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. Google Scholar
  39. Oded Goldreich and Dana Ron. Approximating average parameters of graphs. Random Structures & Algorithms, 32(4):473-493, 2008. Google Scholar
  40. David G Harris, Johannes Schneider, and Hsin-Hao Su. Distributed (Δ+ 1)-coloring in sublogarithmic rounds. In Proc. 48th Annual ACM Symposium on the Theory of Computing, pages 465-478, 2016. Google Scholar
  41. 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 2018, Vienna, Austria, July 16-18, 2018, pages 43-52, 2018. Google Scholar
  42. Monika Henzinger, Stefan Neumann, and Andreas Wiese. Explicit and implicit dynamic coloring of graphs with bounded arboricity. CoRR, abs/2002.10142, 2020. URL: http://arxiv.org/abs/2002.10142.
  43. Monika Henzinger and Pan Peng. Constant-time dynamic (Δ+1)-coloring. In 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, volume 154 of LIPIcs, pages 53:1-53:18, 2020. Google Scholar
  44. Öjvind Johansson. Simple distributed Δ+ 1-coloring of graphs. Information Processing Letters, 70(5):229-232, 1999. Google Scholar
  45. Subhash Khot and Ashok Kumar Ponnuswami. Better inapproximability results for maxclique, chromatic number and min-3lin-deletion. In International Colloquium on Automata, Languages and Programming, pages 226-237, 2006. Google Scholar
  46. L. Kirousis and D. Thilikos. The linkage of a graph. SIAM Journal on Computing, 25(3):626-647, 1996. Google Scholar
  47. Kishore Kothapalli and Sriram Pemmaraju. Distributed graph coloring in a few rounds. In Proc. 30th ACM Symposium on Principles of Distributed Computing, pages 31-40, 2011. Google Scholar
  48. Frank Thomson Leighton. A graph coloring algorithm for large scheduling problems. Journal of research of the national bureau of standards, 84(6):489-506, 1979. Google Scholar
  49. Vahid Lotfi and Sanjiv Sarin. A graph coloring algorithm for large scale scheduling problems. Computers & operations research, 13(1):27-32, 1986. Google Scholar
  50. Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, and David Peleg. Minimum-weight spanning tree construction in O(log log n) communication rounds. SIAM J. Comput., 35(1):120-131, 2005. Google Scholar
  51. Michael Luby. A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput., 15(4):1036-1053, 1986. Google Scholar
  52. Andrew McGregor, David Tench, Sofya Vorotnikova, and Hoa T Vu. Densest subgraph in dynamic graph streams. In International Symposium on Mathematical Foundations of Computer Science, pages 472-482, 2015. Google Scholar
  53. Michael Mitzenmacher, Jakub Pachocki, Richard Peng, Charalampos Tsourakakis, and Shen Chen Xu. Scalable large near-clique detection in large-scale networks via sampling. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '15, 2015. Google Scholar
  54. Farnaz Moradi, Tomas Olovsson, and Philippas Tsigas. A local seed selection algorithm for overlapping community detection. In 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2014), pages 1-8, 2014. Google Scholar
  55. Alessandro Panconesi and Aravind Srinivasan. On the complexity of distributed network decomposition. Journal of Algorithms, 20(2):356-374, 1996. Google Scholar
  56. Taehoon Park and Chae Y Lee. Application of the graph coloring algorithm to the frequency assignment problem. Journal of the Operations Research society of Japan, 39(2):258-265, 1996. Google Scholar
  57. Michal Parnas and Dana Ron. Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theoretical Computer Science, 381(1-3):183-196, 2007. Google Scholar
  58. Merav Parter. (Δ+1) coloring in the congested clique model. In Proc. 45th International Colloquium on Automata, Languages and Programming, pages 160:1-160:14, 2018. Google Scholar
  59. Merav Parter and Hsin-Hao Su. Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds. In Proc. 32nd International Symposium on Distributed Computing, pages 39:1-39:18, 2018. Google Scholar
  60. Jaikumar Radhakrishnan, Saswata Shannigrahi, and Rakesh Venkat. Hypergraph two-coloring in the streaming model. arXiv preprint, 2015. URL: http://arxiv.org/abs/1512.04188.
  61. Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015. URL: http://networkrepository.com.
  62. Václav Rozhon and Mohsen Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Proc. 52nd Annual ACM Symposium on the Theory of Computing, 2020. URL: http://arxiv.org/abs/1907.10937.
  63. Johannes Schneider and Roger Wattenhofer. A new technique for distributed symmetry breaking. In Proc. 29th ACM Symposium on Principles of Distributed Computing, pages 257-266, 2010. Google Scholar
  64. Shay Solomon and Nicole Wein. Improved dynamic graph coloring. In 26th Annual European Symposium on Algorithms, ESA 2018, volume 112 of LIPIcs, pages 72:1-72:16, 2018. Google Scholar
  65. Michael Stiebitz and Bjarne Toft. A Brooks type theorem for the maximum local edge connectivity. Electronic Journal of Combinatorics, 25, March 2016. Google Scholar
  66. George Szekeres and Herbert S. Wilf. An inequality for the chromatic number of a graph. Journal of Combinatorial Theory, 4(1):1-3, 1968. Google Scholar
  67. Simon Thevenin, Nicolas Zufferey, and Jean-Yves Potvin. Graph multi-coloring for a job scheduling application. Discrete Applied Mathematics, 234:218-235, 2018. Google Scholar
  68. David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. In Proc. 38th Annual ACM Symposium on the Theory of Computing, pages 681-690, 2006. 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