Document Open Access Logo

Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs

Authors Christian Konrad, Viktor Zamaraev

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.21.pdf
  • Filesize: 0.62 MB
  • 15 pages

Document Identifiers

Author Details

Christian Konrad
  • Department of Computer Science, University of Bristol, UK
Viktor Zamaraev
  • Department of Computer Science, Durham University, UK

Funding

  • Konrad, Christian: C.K. carried out most work on this paper while being at the University of Warwick. He was supported by the Centre for Discrete Mathematics and its Applications (DIMAP) at Warwick University and by EPSRC award EP/N011163/1.
  • Zamaraev, Viktor: V.Z. is supported by EPSRC award EP/P020372/1.

Cite As Get BibTex

Christian Konrad and Viktor Zamaraev. Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.MFCS.2019.21

Abstract

We give deterministic distributed (1+epsilon)-approximation algorithms for Minimum Vertex Coloring and Maximum Independent Set on chordal graphs in the LOCAL model. Our coloring algorithm runs in O( (1 / epsilon) log n) rounds, and our independent set algorithm has a runtime of O( (1/epsilon) log(1/epsilon)log^* n) rounds. For coloring, existing lower bounds imply that the dependencies on 1/epsilon and log n are best possible. For independent set, we prove that Omega(1/epsilon) rounds are necessary.
Both our algorithms make use of the tree decomposition of the input chordal graph. They iteratively peel off interval subgraphs, which are identified via the tree decomposition of the input graph, thereby partitioning the vertex set into O(log n) layers. For coloring, each interval graph is colored independently, which results in various coloring conflicts between the layers. These conflicts are then resolved in a separate phase, using the particular structure of our partitioning. For independent set, only the first O(log (1/epsilon)) layers are required as they already contain a large enough independent set. We develop a (1+epsilon)-approximation maximum independent set algorithm for interval graphs, which we then apply to those layers. 
This work raises the question as to how useful tree decompositions are for distributed computing.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • local model
  • approximation algorithms
  • minimum vertex coloring
  • maximum independent set
  • chordal graphs

Metrics

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

Related Versions

  • This work has previously been presented as a Brief Announcement at PODC 2018. A full version of the paper is available at [Konrad and Zamaraev, 2018], https://arxiv.org/abs/1805.04544.

References

  1. Pierre Aboulker, Marthe Bonamy, Nicolas Bousquet, and Louis Esperet. Distributed Coloring in Sparse Graphs with Fewer Colors. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC '18, pages 419-425, New York, NY, USA, 2018. ACM. URL: https://doi.org/10.1145/3212734.3212740.
  2. 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. URL: https://doi.org/10.1016/0196-6774(86)90019-2.
  3. Baruch Awerbuch, Michael Luby, Andrew V Goldberg, and Serge A Plotkin. Network Decomposition and Locality in Distributed Computation. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, SFCS '89, pages 364-369, Washington, DC, USA, 1989. IEEE Computer Society. URL: https://doi.org/10.1109/SFCS.1989.63504.
  4. Leonid Barenboim. On the Locality of Some NP-complete Problems. In Proceedings of the 39th International Colloquium Conference on Automata, Languages, and Programming - Volume Part II, ICALP'12, pages 403-415, Berlin, Heidelberg, 2012. Springer-Verlag. URL: https://doi.org/10.1007/978-3-642-31585-5_37.
  5. Leonid Barenboim. Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic and Faulty Networks. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC '15, pages 345-354, New York, NY, USA, 2015. ACM. URL: https://doi.org/10.1145/2767386.2767410.
  6. Leonid Barenboim and Michael Elkin. Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition. Distributed Computing, 22(5):363-379, 2010. Google Scholar
  7. Leonid Barenboim, Michael Elkin, and Cyril Gavoille. A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation. In Post-Proceedings of the 22nd International Colloquium on Structural Information and Communication Complexity - Volume 9439, SIROCCO 2015, pages 209-223, New York, NY, USA, 2015. Springer-Verlag New York, Inc. URL: https://doi.org/10.1007/978-3-319-25258-2_15.
  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. Philip A Bernstein and Nathan Goodman. Power of natural semijoins. SIAM Journal on Computing, 10(4):751-771, 1981. Google Scholar
  10. Jean RS Blair and Barry Peyton. An introduction to chordal graphs and clique trees. In Graph theory and sparse matrix computation, pages 1-29. Springer, 1993. Google Scholar
  11. Marijke H.L. Bodlaender, Magnús M. Halldórsson, Christian Konrad, and Fabian Kuhn. Brief Announcement: Local Independent Set Approximation. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC '16, pages 93-95, New York, NY, USA, 2016. ACM. URL: https://doi.org/10.1145/2933057.2933068.
  12. Yi-Jun Chang, Wenzheng Li, and Seth Pettie. An optimal distributed (Δ+1)-coloring algorithm? In Proceedings 50th ACM Symposium on Theory of Computing (STOC), pages 445-456, 2018. Google Scholar
  13. Yi-Jun Chang and Seth Pettie. A time hierarchy theorem for the LOCAL model. SIAM Journal on Computing, 48(1):33-69, 2019. Google Scholar
  14. Richard Cole and Uzi Vishkin. Deterministic Coin Tossing with Applications to Optimal Parallel List Ranking. Inf. Control, 70(1):32-53, July 1986. URL: https://doi.org/10.1016/S0019-9958(86)80023-7.
  15. Andrzej Czygrinow, Michal Hańćkowiak, and Wojciech Wawrzyniak. Fast Distributed Approximations in Planar Graphs. In Gadi Taubenfeld, editor, Distributed Computing, pages 78-92, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. Google Scholar
  16. Yon Dourisboure and Cyril Gavoille. Tree-decompositions with Bags of Small Diameter. Discrete Math., 307(16):2008-2029, July 2007. URL: https://doi.org/10.1016/j.disc.2005.12.060.
  17. Peter C Fishburn. Interval orders and interval graphs: A study of partially ordered sets. John Wiley & Sons, 1985. Google Scholar
  18. 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. Google Scholar
  19. Mohsen Ghaffari. An Improved Distributed Algorithm for Maximal Independent Set. In Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '16, pages 270-277, Philadelphia, PA, USA, 2016. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=2884435.2884455.
  20. Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, and Yannic Maus. Improved Distributed Delta-Coloring. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC '18, pages 427-436, New York, NY, USA, 2018. ACM. URL: https://doi.org/10.1145/3212734.3212764.
  21. Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus. On the Complexity of Local Distributed Graph Problems. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 784-797, New York, NY, USA, 2017. ACM. URL: https://doi.org/10.1145/3055399.3055471.
  22. Mohsen Ghaffari and Christina Lymouri. Simple and Near-Optimal Distributed Coloring for Sparse Graphs. In Distributed Computing: 31th International Symposium, DISC 2017, Vienna, Austria, October 16-20, 2017. Proceedings, 2017. Google Scholar
  23. Andrew V. Goldberg, Serge A. Plotkin, and Gregory E. Shannon. Parallel Symmetry-Breaking in Sparse Graphs. SIAM J. Discrete Math., 1(4):434-446, 1988. URL: https://doi.org/10.1137/0401044.
  24. Magnús M. Halldórsson and Christian Konrad. Distributed Algorithms for Coloring Interval Graphs, pages 454-468. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-45174-8_31.
  25. Magnús M. Halldórsson and Christian Konrad. Improved Distributed Algorithms for Coloring Interval Graphs with Application to Multicoloring Trees. In Post-Proceedings of the 24th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2017, 2017. Google Scholar
  26. 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, STOC '16, pages 465-478, New York, NY, USA, 2016. ACM. URL: https://doi.org/10.1145/2897518.2897533.
  27. Richard M Karp. Reducibility Among Combinatorial Problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85-103. Plenum Press, 1972. Google Scholar
  28. Christian Konrad and Viktor Zamaraev. Brief Announcement: Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018, pages 159-161, 2018. URL: https://doi.org/10.1145/3212734.3212787.
  29. Christian Konrad and Viktor Zamaraev. Distributed Coloring and Independent Set in Chordal Graphs. arXiv preprint arXiv:1805.04544., 2018. Google Scholar
  30. Christoph Lenzen and Roger Wattenhofer. Leveraging Linial’s Locality Limit. In Gadi Taubenfeld, editor, Distributed Computing, pages 394-407, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. Google Scholar
  31. Nathan Linial. Locality in Distributed Graph Algorithms. SIAM J. Comput., 21(1):193-201, February 1992. URL: https://doi.org/10.1137/0221015.
  32. Nathan Linial and Michael Saks. Low diameter graph decompositions. Combinatorica, 13(4):441-454, December 1993. URL: https://doi.org/10.1007/BF01303516.
  33. Michael Luby. A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM J. Comput., 15(4):1036-1053, 1986. URL: https://doi.org/10.1137/0215074.
  34. Gary L. Miller and John H. Reif. Parallel Tree Contraction-Part I: Fundamentals. In Randomness and Computation, volume 5, pages 47-72. JAI Press, 1989. Google Scholar
  35. 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.
  36. Alessandro Panconesi and Aravind Srinivasan. The Local Natur of Delta-Coloring and its Algorithmic Applications. Combinatorica, 15(2):255-280, 1995. URL: https://doi.org/10.1007/BF01200759.
  37. Johannes Schneider and Roger Wattenhofer. A New Technique for Distributed Symmetry Breaking. In Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC '10, pages 257-266, New York, NY, USA, 2010. ACM. URL: https://doi.org/10.1145/1835698.1835760.
  38. Johannes Schneider and Roger Wattenhofer. An optimal maximal independent set algorithm for bounded-independence graphs. Distributed Computing, 22(5):349-361, August 2010. URL: https://doi.org/10.1007/s00446-010-0097-1.
  39. David Zuckerman. Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. Theory of Computing, 3(1):103-128, 2007. 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