Document Open Access Logo

Faster 3-Coloring of Small-Diameter Graphs

Authors Michał Dębski, Marta Piecyk, Paweł Rzążewski

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.37.pdf
  • Filesize: 0.9 MB
  • 15 pages

Document Identifiers

Author Details

Michał Dębski
  • Faculty of Mathematics and Information Science, Warsaw University of Technology, Poland
Marta Piecyk
  • Faculty of Mathematics and Information Science, Warsaw University of Technology, Poland
Paweł Rzążewski
  • Faculty of Mathematics and Information Science, Warsaw University of Technology, Poland
  • Institute of Informatics, University of Warsaw, Poland

Funding

Supported by Polish National Science Centre grant no. 2018/31/D/ST6/00062.

Acknowledgements

The authors are sincerely grateful to Carla Groenland for many inspiring discussions and useful comments on the manuscript.

Cite As Get BibTex

Michał Dębski, Marta Piecyk, and Paweł Rzążewski. Faster 3-Coloring of Small-Diameter Graphs. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ESA.2021.37

Abstract

We study the 3-Coloring problem in graphs with small diameter. In 2013, Mertzios and Spirakis showed that for n-vertex diameter-2 graphs this problem can be solved in subexponential time 2^{𝒪(√{n log n})}. Whether the problem can be solved in polynomial time remains a well-known open question in the area of algorithmic graphs theory. 
In this paper we present an algorithm that solves 3-Coloring in n-vertex diameter-2 graphs in time 2^{𝒪(n^{1/3} log² n)}. This is the first improvement upon the algorithm of Mertzios and Spirakis in the general case, i.e., without putting any further restrictions on the instance graph.
In addition to standard branchings and reducing the problem to an instance of 2-Sat, the crucial building block of our algorithm is a combinatorial observation about 3-colorable diameter-2 graphs, which is proven using a probabilistic argument.
As a side result, we show that 3-Coloring can be solved in time 2^{𝒪((n log n)^{2/3})} in n-vertex diameter-3 graphs. We also generalize our algorithms to the problem of finding a list homomorphism from a small-diameter graph to a cycle.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph coloring
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • 3-coloring
  • fine-grained complexity
  • subexponential-time algorithm
  • diameter

Metrics

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

References

  1. Noga Alon and Joel H. Spencer. The Probabilistic Method, Third Edition. Wiley-Interscience series in discrete mathematics and optimization. Wiley, 2008. Google Scholar
  2. Marthe Bonamy, Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Panos Giannopoulos, Eun Jung Kim, Paweł Rzążewski, Florian Sikora, and Stéphan Thomassé. EPTAS and subexponential algorithm for Maximum Clique on disk and unit ball graphs. J. ACM, 68(2):9:1-9:38, 2021. URL: https://doi.org/10.1145/3433160.
  3. Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma. Independent feedback vertex sets for graphs of bounded diameter. Inf. Process. Lett., 131:26-32, 2018. URL: https://doi.org/10.1016/j.ipl.2017.11.004.
  4. Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma. Independent feedback vertex set for P₅-free graphs. Algorithmica, 81(4):1342-1369, 2019. URL: https://doi.org/10.1007/s00453-018-0474-x.
  5. Christoph Brause, Petr Golovach, Barnaby Martin, Daniël Paulusma, and Siani Smith. Acyclic, star, and injective colouring: Bounding the diameter. CoRR, abs/2104.10593, 2021. URL: http://arxiv.org/abs/2104.10593.
  6. Victor A. Campos, Guilherme de C. M. Gomes, Allen Ibiapina, Raul Lopes, Ignasi Sau, and Ana Silva. Coloring problems on bipartite graphs of small diameter. CoRR, abs/2004.11173, 2020. URL: http://arxiv.org/abs/2004.11173.
  7. Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas. The strong perfect graph theorem. Ann. Math. (2), 164(1):51-229, 2006. Google Scholar
  8. Maria Chudnovsky and Paul D. Seymour. The three-in-a-tree problem. Comb., 30(4):387-417, 2010. URL: https://doi.org/10.1007/s00493-010-2334-4.
  9. Konrad K. Dabrowski, Matthew Johnson, and Daniël Paulusma. Clique-width for hereditary graph classes. CoRR, abs/1901.00335, 2019. URL: http://arxiv.org/abs/1901.00335.
  10. Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden. A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs. SIAM J. Comput., 49(6):1291-1331, 2020. URL: https://doi.org/10.1137/20M1320870.
  11. Erik D. Demaine, Mohammad Taghi Hajiaghayi, and Ken-ichi Kawarabayashi. Algorithmic graph minor theory: Decomposition, approximation, and coloring. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings, pages 637-646. IEEE Computer Society, 2005. URL: https://doi.org/10.1109/SFCS.2005.14.
  12. Keith Edwards. The complexity of colouring problems on dense graphs. Theor. Comput. Sci., 43:337-343, 1986. URL: https://doi.org/10.1016/0304-3975(86)90184-2.
  13. Tomás Feder, Pavol Hell, and Jing Huang. List homomorphisms and circular arc graphs. Comb., 19(4):487-505, 1999. URL: https://doi.org/10.1007/s004939970003.
  14. Tomás Feder, Pavol Hell, and Jing Huang. Bi-arc graphs and the complexity of list homomorphisms. J. Graph Theory, 42(1):61-80, 2003. URL: https://doi.org/10.1002/jgt.10073.
  15. Fedor V. Fomin, Erik D. Demaine, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos. Bidimensionality. In Encyclopedia of Algorithms, pages 203-207. Springer, 2016. URL: https://doi.org/10.1007/978-1-4939-2864-4_47.
  16. Peter Gartland and Daniel Lokshtanov. Independent set on P_k-free graphs in quasi-polynomial time. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 613-624. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00063.
  17. Petr A. Golovach, Matthew Johnson, Daniël Paulusma, and Jian Song. A survey on the computational complexity of coloring graphs with forbidden subgraphs. J. Graph Theory, 84(4):331-363, 2017. URL: https://doi.org/10.1002/jgt.22028.
  18. M. Grötschel, L. Lovász, and A. Schrijver. Polynomial algorithms for perfect graphs. In C. Berge and V. Chvátal, editors, Topics on Perfect Graphs, volume 88 of North-Holland Mathematics Studies, pages 325-356. North-Holland, 1984. URL: https://doi.org/10.1016/S0304-0208(08)72943-8.
  19. Jan Kratochvíl. Can they cross? and how?: (the hitchhiker’s guide to the universe of geometric intersection graphs). In Ferran Hurtado and Marc J. van Kreveld, editors, Proceedings of the 27th ACM Symposium on Computational Geometry, Paris, France, June 13-15, 2011, pages 75-76. ACM, 2011. URL: https://doi.org/10.1145/1998196.1998208.
  20. Jan Kratochvíl and Jirí Matousek. Intersection graphs of segments. J. Comb. Theory, Ser. B, 62(2):289-315, 1994. URL: https://doi.org/10.1006/jctb.1994.1071.
  21. Barnaby Martin, Daniël Paulusma, and Siani Smith. Colouring H-free graphs of bounded diameter. In Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen, editors, 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany, volume 138 of LIPIcs, pages 14:1-14:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.14.
  22. Barnaby Martin, Daniël Paulusma, and Siani Smith. Computing independent transversals for H-free graphs of bounded diameter. Abstract at Workshop on Graph Modification: algorithms, experiments and new problems, 23rd - 24th January 2020, Bergen, Norway, 2020. URL: https://graphmodif.ii.uib.no/abs/fri-2.pdf.
  23. Barnaby Martin, Daniël Paulusma, and Siani Smith. Colouring graphs of bounded diameter in the absence of small cycles. CoRR, abs/2101.07856, 2021. URL: http://arxiv.org/abs/2101.07856.
  24. Dániel Marx and Michal Pilipczuk. Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, volume 9294 of Lecture Notes in Computer Science, pages 865-877. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48350-3_72.
  25. Colin McDiarmid. Concentration. In J. Ramirez-Alfonsin M. Habib, C. McDiarmid and B. Reed, editors, Probabilistic methods for algorithmic discrete mathematics, volume 16 of Algorithms and Combinatorics, pages 195-248. Springer, 1998. Google Scholar
  26. George B. Mertzios and Paul G. Spirakis. Algorithms and almost tight results for 3-colorability of small diameter graphs. Algorithmica, 74(1):385-414, 2016. URL: https://doi.org/10.1007/s00453-014-9949-6.
  27. Christos H. Papadimitriou. Computational complexity. Addison-Wesley, 1994. Google Scholar
  28. Stefan Porschen. On variable-weighted exact satisfiability problems. Ann. Math. Artif. Intell., 51(1):27-54, 2007. URL: https://doi.org/10.1007/s10472-007-9084-z.
  29. Neil Robertson and Paul D. Seymour. Graph minors. v. excluding a planar graph. J. Comb. Theory, Ser. B, 41(1):92-114, 1986. URL: https://doi.org/10.1016/0095-8956(86)90030-4.
  30. Sebastian Schnettler. A structured overview of 50 years of small-world research. Soc. Networks, 31(3):165-178, 2009. URL: https://doi.org/10.1016/j.socnet.2008.12.004.
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