Document Open Access Logo

List Colouring Trees in Logarithmic Space

Authors Hans L. Bodlaender , Carla Groenland , Hugo Jacob

PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.24.pdf
  • Filesize: 0.83 MB
  • 15 pages

Document Identifiers

Author Details

Hans L. Bodlaender
  • Utrecht University, The Netherlands
Carla Groenland
  • Utrecht University, The Netherlands
Hugo Jacob
  • ENS Paris-Saclay, France

Funding

  • Groenland, Carla: Supported by the project CRACKNP that has received funding from the European Research Council (grant agreement No 853234).

Acknowledgements

We thank Marcin Pilipczuk and Michał Pilipczuk for discussions.

Cite As Get BibTex

Hans L. Bodlaender, Carla Groenland, and Hugo Jacob. List Colouring Trees in Logarithmic Space. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ESA.2022.24

Abstract

We show that List Colouring can be solved on n-vertex trees by a deterministic Turing machine using O(log n) bits on the worktape. Given an n-vertex graph G = (V,E) and a list L(v) ⊆ {1,… ,n} of available colours for each v ∈ V, a list colouring for G is a proper colouring c such that c(v) ∈ L(v) for all v.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Mathematics of computing → Trees
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • List colouring
  • trees
  • space complexity
  • logspace
  • graph algorithms
  • tree-partition-width

Metrics

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

Related Versions

References

  1. Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, and Bangsheng Tang. Width-parametrized SAT: Time-space tradeoffs. Theory of Computing, 10:297-339, 2014. URL: https://doi.org/10.4086/toc.2014.v010a012.
  2. Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. URL: http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264.
  3. Hans L. Bodlaender, Carla Groenland, and Hugo Jacob. List colouring trees in logarithmic space. arXiv, CoRR(2206.09750), 2022. URL: https://doi.org/10.48550/ARXIV.2206.09750.
  4. Hans L. Bodlaender, Carla Groenland, Jesper Nederlof, and Céline M. F. Swennenhuis. Parameterized problems complete for nondeterministic FPT time and logarithmic space. In Proceedings 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, pages 193-204, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00027.
  5. Hans L. Bodlaender, Carla Groenland, and Céline M. F. Swennenhuis. Parameterized complexities of dominating and independent set reconfiguration. In Petr A. Golovach and Meirav Zehavi, editors, Proceedings 16th International Symposium on Parameterized and Exact Computation, IPEC 2021, volume 214 of LIPIcs, pages 9:1-9:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.IPEC.2021.9.
  6. Li-Hsuan Chen, Felix Reidl, Peter Rossmanith, and Fernando Sánchez Villaamil. Width, depth, and space: Tradeoffs between branching and dynamic programming. Algorithms, 11(7):98, 2018. URL: https://doi.org/10.3390/a11070098.
  7. Yijia Chen, Jörg Flum, and Martin Grohe. Bounded nondeterminism and alternation in parameterized complexity theory. In Proceedings 18th Annual IEEE Conference on Computational Complexity, CCC 2003, pages 13-29. IEEE Computer Society, 2003. URL: https://doi.org/10.1109/CCC.2003.1214407.
  8. Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner. Planar graph isomorphism is in log-space. In Proceedings 24th Annual IEEE Conference on Computational Complexity, CCC 2009, pages 203-214. IEEE Computer Society, 2009. URL: https://doi.org/10.1109/CCC.2009.16.
  9. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate Texts in Mathematics. Springer, 2012. Google Scholar
  10. Guoli Ding and Bogdan Oporowski. Some results on tree decomposition of graphs. J. Graph Theory, 20(4):481-499, 1995. URL: https://doi.org/10.1002/jgt.3190200412.
  11. Guoli Ding and Bogdan Oporowski. On tree-partitions of graphs. Discret. Math., 149(1-3):45-58, 1996. URL: https://doi.org/10.1016/0012-365X(94)00337-I.
  12. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Springer, 1999. Google Scholar
  13. László Egri, Pavol Hell, Benoît Larose, and Arash Rafiey. Space complexity of list H-colouring: A dichotomy. In Chandra Chekuri, editor, Proceedings 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pages 349-365. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.26.
  14. Michael Elberfeld, Andreas Jakoby, and Till Tantau. Logspace versions of the theorems of Bodlaender and Courcelle. In Proceedings 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, pages 143-152. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/FOCS.2010.21.
  15. Michael Elberfeld, Christoph Stockhusen, and Till Tantau. On the space and circuit complexity of parameterized problems: Classes and completeness. Algorithmica, 71(3):661-701, 2015. URL: https://doi.org/10.1007/s00453-014-9944-y.
  16. Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances A. Rosamond, Saket Saurabh, Stefan Szeider, and Carsten Thomassen. On the complexity of some colorful problems parameterized by treewidth. Inf. Comput., 209(2):143-153, 2011. URL: https://doi.org/10.1016/j.ic.2010.11.026.
  17. Naveen Garg, Marina Papatriantafilou, and Philippas Tsigas. Distributed list coloring: How to dynamically allocate frequencies to mobile base stations. In Proceedings 8th IEEE Symposium on Parallel and Distributed Processing, SPDP 1996, pages 18-25. IEEE Computer Society, 1996. URL: https://doi.org/10.1109/SPDP.1996.570312.
  18. Sylvain Gravier, Daniel Kobler, and Wieslaw Kubiak. Complexity of list coloring problems with a fixed total number of colors. Discrete Applied Mathematics, 117(1-3):65-79, 2002. Google Scholar
  19. Klaus Jansen and Petra Scheffler. Generalized coloring for tree-like graphs. Discrete Applied Mathematics, 75(2):135-155, 1997. URL: https://doi.org/10.1016/S0166-218X(96)00085-6.
  20. Shiva Kintali and Sinziana Munteanu. Computing bounded path decompositions in logspace. Electron. Colloquium Comput. Complex. (ECCC), page 126, 2012. URL: https://eccc.weizmann.ac.il/report/2012/126.
  21. Jan Kynčl and Tomáš Vyskočil. Logspace reduction of directed reachability for bounded genus graphs to the planar case. ACM Trans. Comput. Theory, 1(3), 2010. URL: https://doi.org/10.1145/1714450.1714451.
  22. Steven Lindell. A logspace algorithm for tree canonization (extended abstract). In Proceedings 24th Annual ACM Symposium on Theory of Computing, STOC 1992, STOC '92, pages 400-404, New York, NY, USA, 1992. Association for Computing Machinery. URL: https://doi.org/10.1145/129712.129750.
  23. Michal Pilipczuk and Marcin Wrochna. On space efficiency of algorithms working on structural decompositions of graphs. ACM Trans. Comput. Theory, 9(4):18:1-18:36, 2018. URL: https://doi.org/10.1145/3154856.
  24. Krishna N. Ramachandran, Elizabeth M. Belding-Royer, Kevin C. Almeroth, and Milind M. Buddhikot. Interference-aware channel assignment in multi-radio wireless mesh networks. In Proceedings 25th IEEE International Conference on Computer Communications, INFOCOM 2006, pages 1-12. IEEE Computer Society, 2006. URL: https://doi.org/10.1109/INFOCOM.2006.177.
  25. Omer Reingold. Undirected connectivity in log-space. J. ACM, 55(4), 2008. URL: https://doi.org/10.1145/1391289.1391291.
  26. Detlef Seese. Tree-partite graphs and the complexity of algorithms. In Lothar Budach, editor, Proceedings 5th International Conference on Fundamentals of Computation Theory, FCT 1985, volume 199 of Lecture Notes in Computer Science, pages 412-421. Springer, 1985. URL: https://doi.org/10.1007/BFb0028825.
  27. David R. Wood. On tree-partition-width. Eur. J. Comb., 30(5):1245-1253, 2009. URL: https://doi.org/10.1016/j.ejc.2008.11.010.
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