Document Open Access Logo

Tight Bounds for Counting Colorings and Connected Edge Sets Parameterized by Cutwidth

Authors Carla Groenland , Isja Mannens , Jesper Nederlof , Krisztina Szilágyi

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.36.pdf
  • Filesize: 0.92 MB
  • 20 pages

Document Identifiers

Author Details

Carla Groenland
  • Utrecht University, The Netherlands
Isja Mannens
  • Utrecht University, The Netherlands
Jesper Nederlof
  • Utrecht University, The Netherlands
Krisztina Szilágyi
  • Utrecht University, The Netherlands

Funding

All authors are supported by the project CRACKNP that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 853234).

Acknowledgements

We thank the anonymous reviews for their detailed comments.

Cite As Get BibTex

Carla Groenland, Isja Mannens, Jesper Nederlof, and Krisztina Szilágyi. Tight Bounds for Counting Colorings and Connected Edge Sets Parameterized by Cutwidth. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.STACS.2022.36

Abstract

We study the fine-grained complexity of counting the number of colorings and connected spanning edge sets parameterized by the cutwidth and treewidth of the graph. While decompositions of small treewidth decompose the graph with small vertex separators, decompositions with small cutwidth decompose the graph with small edge separators.
Let p,q ∈ ℕ such that p is a prime and q ≥ 3. We show:  
- If p divides q-1, there is a (q-1)^{ctw}n^{O(1)} time algorithm for counting list q-colorings modulo p of n-vertex graphs of cutwidth ctw. Furthermore, there is no ε > 0 for which there is a (q-1-ε)^{ctw} n^{O(1)} time algorithm that counts the number of list q-colorings modulo p of n-vertex graphs of cutwidth ctw, assuming the Strong Exponential Time Hypothesis (SETH). 
- If p does not divide q-1, there is no ε > 0 for which there exists a (q-ε)^{ctw} n^{O(1)} time algorithm that counts the number of list q-colorings modulo p of n-vertex graphs of cutwidth ctw, assuming SETH.  The lower bounds are in stark contrast with the existing 2^{ctw}n^{O(1)} time algorithm to compute the chromatic number of a graph by Jansen and Nederlof [Theor. Comput. Sci.'18].
Furthermore, by building upon the above lower bounds, we obtain the following lower bound for counting connected spanning edge sets: there is no ε > 0 for which there is an algorithm that, given a graph G and a cutwidth ordering of cutwidth ctw, counts the number of spanning connected edge sets of G modulo p in time (p - ε)^{ctw} n^{O(1)}, assuming SETH. We also give an algorithm with matching running time for this problem.
Before our work, even for the treewidth parameterization, the best conditional lower bound by Dell et al. [ACM Trans. Algorithms'14] only excluded 2^{o(tw)}n^{O(1)} time algorithms for this problem.
Both our algorithms and lower bounds employ use of the matrix rank method, by relating the complexity of the problem to the rank of a certain "compatibility matrix" in a non-trivial way.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • connected edge sets
  • cutwidth
  • parameterized algorithms
  • colorings
  • counting modulo p

Metrics

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

Related Versions

References

  1. James Douglas Annan. The complexity of counting problems. PhD thesis, University of Oxford, 1994. Google Scholar
  2. Andreas Björklund and Thore Husfeldt. Inclusion-exclusion based algorithms for graph colouring. In Electronic Colloquium on Computational Complexity (ECCC), volume 13. Citeseer, 2006. Google Scholar
  3. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Computing the tutte polynomial in vertex-exponential time. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 677-686. IEEE Computer Society, 2008. URL: https://doi.org/10.1109/FOCS.2008.40.
  4. 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: https://doi.org/10.1016/j.ic.2014.12.008.
  5. Chris Calabro, Russell Impagliazzo, Valentine Kabanets, and Ramamohan Paturi. The complexity of unique k-sat: An isolation lemma for k-cnfs. Journal of Computer and System Sciences, 74(3):386-393, 2008. Google Scholar
  6. Radu Curticapean, Nathan Lindzey, and Jesper Nederlof. A tight lower bound for counting hamiltonian cycles via matrix rank. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1080-1099. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.70.
  7. Radu Curticapean and Dániel Marx. Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1650-1669. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch113.
  8. Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Fast hamiltonicity checking via bases of perfect matchings. J. ACM, 65(3):12:1-12:46, 2018. URL: https://doi.org/10.1145/3148227.
  9. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Joham MM van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 150-159. IEEE, 2011. Google Scholar
  10. Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlen. Exponential time complexity of the permanent and the tutte polynomial. ACM Trans. Algorithms, 10(4):21:1-21:32, 2014. URL: https://doi.org/10.1145/2635812.
  11. Martin Dyer and Catherine Greenhill. The complexity of counting graph homomorphisms. Random Structures & Algorithms, 17(3-4):260-289, 2000. Google Scholar
  12. Jacob Focke, Dániel Marx, and Paweł Rzążewski. Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 431-458. SIAM, 2022. Google Scholar
  13. 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: https://doi.org/10.1145/2886094.
  14. Catherine Greenhill. The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. Computational Complexity, 9(1):52-72, 2000. Google Scholar
  15. Carla Groenland, Jesper Nederlof, Isja Mannens, and Krisztina Szilágyi. Tight bounds for counting colorings and connected edge sets parameterized by cutwidth. arXiv preprint, 2021. URL: http://arxiv.org/abs/2110.02730.
  16. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. J. Comput. Syst. Sci., 62(2):367-375, 2001. URL: https://doi.org/10.1006/jcss.2000.1727.
  17. François Jaeger, Dirk L Vertigan, and Dominic JA Welsh. On the computational complexity of the Jones and Tutte polynomials. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 108(1), pages 35-53. Cambridge University Press, 1990. Google Scholar
  18. Bart MP Jansen and Jesper Nederlof. Computing the chromatic number using graph decompositions via matrix rank. Theoretical Computer Science, 795:520-539, 2019. Google Scholar
  19. Amirhossein Kazeminia and Andrei A Bulatov. Counting homomorphisms modulo a prime number. arXiv preprint, 2019. URL: http://arxiv.org/abs/1905.10682.
  20. Mikko Koivisto. An o^*(2ⁿ) algorithm for graph coloring and other partitioning problems via inclusion-exclusion. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 583-590. IEEE Computer Society, 2006. URL: https://doi.org/10.1109/FOCS.2006.11.
  21. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Known algorithms on graphs of bounded treewidth are probably optimal. ACM Trans. Algorithms, 14(2):13:1-13:30, 2018. URL: https://doi.org/10.1145/3170442.
  22. Jesper Nederlof. Bipartite TSP in O(1.9999ⁿ) time, assuming quadratic time matrix multiplication. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 40-53. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384264.
  23. James G Oxley, Dominic JA Welsh, et al. The tutte polynomial and percolation. Graph Theory and Related Topics, pages 329-339, 1979. Google Scholar
  24. Leslie G. Valiant. Accidental algorithms. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 509-517. IEEE Computer Society, 2006. URL: https://doi.org/10.1109/FOCS.2006.7.
  25. Johan M. M. van Rooij, Hans L. Bodlaender, and Peter Rossmanith. Dynamic programming on tree decompositions using generalised fast subset convolution. In Amos Fiat and Peter Sanders, editors, Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings, volume 5757 of Lecture Notes in Computer Science, pages 566-577. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-04128-0_51.
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