Document Open Access Logo

Computing the Chromatic Number Using Graph Decompositions via Matrix Rank

Authors Bart M. P. Jansen, Jesper Nederlof

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.47.pdf
  • Filesize: 0.52 MB
  • 15 pages

Document Identifiers

Author Details

Bart M. P. Jansen
  • Eindhoven University of Technology, Eindhoven, The Netherlands
Jesper Nederlof
  • Eindhoven University of Technology, Eindhoven, The Netherlands

Funding

  • Jansen, Bart M. P.: NWO Veni grant "Frontiers in Parameterized Preprocessing" and NWO Gravitation grant "Networks"
  • Nederlof, Jesper: NWO Veni grant "Reducing small instances of complex tasks to large instances of simple ones" and NWO Gravitation grant "Networks"

Cite AsGet BibTex

Bart M. P. Jansen and Jesper Nederlof. Computing the Chromatic Number Using Graph Decompositions via Matrix Rank. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 47:1-47:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ESA.2018.47

Abstract

Computing the smallest number q such that the vertices of a given graph can be properly q-colored is one of the oldest and most fundamental problems in combinatorial optimization. The q-Coloring problem has been studied intensively using the framework of parameterized algorithmics, resulting in a very good understanding of the best-possible algorithms for several parameterizations based on the structure of the graph. For example, algorithms are known to solve the problem on graphs of treewidth {tw} in time O^*(q^{tw}), while a running time of O^*((q-epsilon)^{tw}) is impossible assuming the Strong Exponential Time Hypothesis (SETH). While there is an abundance of work for parameterizations based on decompositions of the graph by vertex separators, almost nothing is known about parameterizations based on edge separators. We fill this gap by studying q-Coloring parameterized by cutwidth, and parameterized by pathwidth in bounded-degree graphs. Our research uncovers interesting new ways to exploit small edge separators. We present two algorithms for q-Coloring parameterized by cutwidth {ctw}: a deterministic one that runs in time O^*(2^{omega * {ctw}}), where omega is the matrix multiplication constant, and a randomized one with runtime O^*(2^{{ctw}}). In sharp contrast to earlier work, the running time is independent of q. The dependence on cutwidth is optimal: we prove that even 3-Coloring cannot be solved in O^*((2-epsilon)^{{ctw}}) time assuming SETH. Our algorithms rely on a new rank bound for a matrix that describes compatible colorings. Combined with a simple communication protocol for evaluating a product of two polynomials, this also yields an O^*((floor[d/2]+1)^{{pw}}) time randomized algorithm for q-Coloring on graphs of pathwidth {pw} and maximum degree d. Such a runtime was first obtained by Björklund, but only for graphs with few proper colorings. We also prove that this result is optimal in the sense that no O^*((floor[d/2]+1-epsilon)^{{pw}})-time algorithm exists assuming SETH.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Parameterized Complexity
  • Chromatic Number
  • Graph Decompositions

Metrics

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

Related Versions

References

  1. Noga Alon and Michael Tarsi. Colorings and orientations of graphs. Combinatorica, 12(2):125-134, 1992. URL: http://dx.doi.org/10.1007/BF01204715.
  2. Noga Alon and Michael Tarsi. A note on graph colorings and graph polynomials. J. Comb. Theory, Ser. B, 70(1):197-201, 1997. URL: http://dx.doi.org/10.1006/jctb.1997.1753.
  3. Nikhil Bansal, Marek Eliás, Grigorios Koumoutsos, and Jesper Nederlof. Competitive algorithms for generalized k-server in uniform metrics. In Proc. 29th SODA, pages 992-1001, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.64.
  4. Andreas Björklund. Coloring graphs having few colorings over path decompositions. In Proc. 15th SWAT, volume 53 of LIPIcs, pages 13:1-13:9, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.SWAT.2016.13.
  5. Andreas Björklund and Thore Husfeldt. Exact graph coloring using inclusion-exclusion. In Ming-Yang Kao, editor, Encyclopedia of Algorithms. Springer, 2008. URL: http://dx.doi.org/10.1007/978-0-387-30162-4_134.
  6. Andreas Björklund, Thore Husfeldt, and Mikko Koivisto. Set partitioning via inclusion-exclusion. SIAM J. Comput., 39(2):546-563, 2009. URL: http://dx.doi.org/10.1137/070683933.
  7. Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci., 209(1-2):1-45, 1998. URL: http://dx.doi.org/10.1016/S0304-3975(97)00228-4.
  8. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput., 243:86-111, 2015. URL: http://dx.doi.org/10.1016/j.ic.2014.12.008.
  9. Hans L. Bodlaender and Arie M. C. A. Koster. Combinatorial optimization on graphs of bounded treewidth. Comput. J., 51(3):255-269, 2008. URL: http://dx.doi.org/10.1093/comjnl/bxm037.
  10. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  11. Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Fast hamiltonicity checking via bases of perfect matchings. In Proc. 45th STOC, pages 301-310. ACM, 2013. URL: http://dx.doi.org/10.1145/2488608.2488646.
  12. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In Proc. 52nd FOCS, pages 150-159, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.23.
  13. J. A. de Loera. Gröbner bases and graph colorings. Contributions to Algebra and Geometry, 35(1):89-96, 1995. Google Scholar
  14. Josep Díaz, Jordi Petit, and Maria J. Serna. A survey of graph layout problems. ACM Comput. Surv., 34(3):313-356, 2002. URL: http://dx.doi.org/10.1145/568522.568523.
  15. Stefan Fafianie, Hans L. Bodlaender, and Jesper Nederlof. Speeding up dynamic programming with representative sets: An experimental evaluation of algorithms for Steiner tree on tree decompositions. Algorithmica, 71(3):636-660, 2015. URL: http://dx.doi.org/10.1007/s00453-014-9934-0.
  16. Michael R. Fellows, Bart M. P. Jansen, and Frances Rosamond. Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. European J. Combin., 34(3):541-566, 2013. URL: http://dx.doi.org/10.1016/j.ejc.2012.04.008.
  17. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Intractability of clique-width parameterizations. SIAM J. Comput., 39(5):1941-1956, 2010. URL: http://dx.doi.org/10.1137/080742270.
  18. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM, 63(4):29:1-29:60, 2016. URL: http://dx.doi.org/10.1145/2886094.
  19. Jakub Gajarský, Michael Lampis, and Sebastian Ordyniak. Parameterized algorithms for modular-width. In Proc. 8th IPEC, volume 8246 of Lecture Notes in Computer Science, pages 163-176. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-319-03898-8_15.
  20. Robert Ganian. Twin-cover: Beyond vertex cover in parameterized algorithmics. In Dániel Marx and Peter Rossmanith, editors, Proc. 6th IPEC, volume 7112 of Lecture Notes in Computer Science, pages 259-271. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-28050-4_21.
  21. M.R. Garey, D.S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3):237-267, 1976. URL: http://dx.doi.org/10.1016/0304-3975(76)90059-1.
  22. Bas A.M. van Geffen, Bart M.P. Jansen, Arnoud A.W.M. de Kroon, and Rolf Morel. Lower bounds for dynamic programming on planar graphs of bounded cutwidth. CoRR, 2018. URL: http://arxiv.org/abs/1806.10513.
  23. Archontia C. Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, and Marcin Wrochna. Cutwidth: Obstructions and algorithmic aspects. In Proc. 11th IPEC, volume 63 of LIPIcs, pages 15:1-15:13, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2016.15.
  24. Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Cliquewidth III: The odd case of graph coloring parameterized by cliquewidth. In Proc. 29th SODA, pages 262-273, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.19.
  25. Russel Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. URL: http://dx.doi.org/10.1006/jcss.2000.1727.
  26. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. URL: http://dx.doi.org/10.1006/jcss.2001.1774.
  27. Lars Jaffke and Bart M. P. Jansen. Fine-grained parameterized complexity analysis of graph coloring problems. In Proc. 10th CIAC, Lecture Notes in Computer Science, pages 345-356, 2017. URL: http://dx.doi.org/10.1007/978-3-319-57586-5_29.
  28. Bart M. P. Jansen and Jesper Nederlof. Computing the chromatic number using graph decompositions via matrix rank. CoRR, 2018. URL: http://arxiv.org/abs/1806.10501.
  29. T.R. Jensen and B. Toft. Graph Coloring Problems. Wiley interscience publication. Wiley, 1995. Google Scholar
  30. David S. Johnson, Anuj Mehrotra, and Michael A. Trick. Special issue on computational methods for graph coloring and its generalizations. Discrete Applied Mathematics, 156(2):145-146, 2008. URL: http://dx.doi.org/10.1016/j.dam.2007.10.007.
  31. Daniel Kobler and Udi Rotics. Edge dominating set and colorings on graphs with fixed clique-width. Discrete Applied Mathematics, 126(2-3):197-221, 2003. URL: http://dx.doi.org/10.1016/S0166-218X(02)00198-1.
  32. Ephraim Korach and Nir Solel. Tree-width, path-width, and cutwidth. Discrete Applied Mathematics, 43(1):97-101, 1993. URL: http://dx.doi.org/10.1016/0166-218X(93)90171-J.
  33. R.M. R. Lewis. A Guide to Graph Colouring: Algorithms and Applications. Springer Publishing Company, 2015. Google Scholar
  34. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Known algorithms on graphs of bounded treewidth are probably optimal. In Proc. 22nd SODA, pages 777-789, 2011. URL: http://dx.doi.org/10.1137/1.9781611973082.61.
  35. L. Lovász. Bounding the independence number of a graph. In Achim Bachem, Martin Grötschel, and Bemhard Korte, editors, Bonn Workshop on Combinatorial Optimization, volume 66, pages 213-223. North-Holland, 1982. URL: http://dx.doi.org/10.1016/S0304-0208(08)72453-8.
  36. László Lovász. Flats in matroids and geometric graphs. In Combinatorial surveys (Proc. Sixth British Combinatorial Conf.), pages 45-86. Academic Press London, 1977. Google Scholar
  37. Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani. Matching is as easy as matrix inversion. Combinatorica, 7(1):105-113, 1987. URL: http://dx.doi.org/10.1007/BF02579206.
  38. P.M. Pardalos, T. Mavridou, and J. Xue. The graph coloring problem: A bibliographic survey, volume 2, pages 331-395. Kluwer Academic Publishers, Boston, 1998. Google Scholar
  39. Sigve Hortemo Sæther and Jan Arne Telle. Between treewidth and clique-width. Algorithmica, 75(1):218-253, 2016. URL: http://dx.doi.org/10.1007/s00453-015-0033-7.
  40. Jan Arne Telle and Andrzej Proskurowski. Algorithms for vertex partitioning problems on partial k-trees. SIAM J. Discrete Math., 10(4):529-550, 1997. URL: http://dx.doi.org/10.1137/S0895480194275825.
  41. Dimitrios M. Thilikos, Maria J. Serna, and Hans L. Bodlaender. Cutwidth I: A linear time fixed parameter algorithm. J. Algorithms, 56(1):1-24, 2005. URL: http://dx.doi.org/10.1016/j.jalgor.2004.12.001.
  42. Dimitrios M. Thilikos, Maria J. Serna, and Hans L. Bodlaender. Cutwidth II: algorithms for partial w-trees of bounded degree. J. Algorithms, 56(1):25-49, 2005. URL: http://dx.doi.org/10.1016/j.jalgor.2004.12.003.
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 Imprint Privacy Contact