Document Open Access Logo

A Fine-Grained Classification of the Complexity of Evaluating the Tutte Polynomial on Integer Points Parameterized by Treewidth and Cutwidth

Authors Isja Mannens , Jesper Nederlof

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.82.pdf
  • Filesize: 0.83 MB
  • 17 pages

Document Identifiers

Author Details

Isja Mannens
  • Utrecht University, The Netherlands
Jesper Nederlof
  • Utrecht University, The Netherlands

Funding

Both 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).

Cite As Get BibTex

Isja Mannens and Jesper Nederlof. A Fine-Grained Classification of the Complexity of Evaluating the Tutte Polynomial on Integer Points Parameterized by Treewidth and Cutwidth. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 82:1-82:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ESA.2023.82

Abstract

We give a fine-grained classification of evaluating the Tutte polynomial T(G;x,y) on all integer points on graphs with small treewidth and cutwidth. Specifically, we show for any point (x,y) ∈ ℤ² that either  
- T(G; x, y) can be computed in polynomial time, 
- T(G; x, y) can be computed in 2^O(tw) n^O(1) time, but not in 2^o(ctw) n^O(1) time assuming the Exponential Time Hypothesis (ETH), 
- T(G; x, y) can be computed in 2^O(tw log tw) n^O(1) time, but not in 2^o(ctw log ctw) n^O(1) time assuming the ETH,  where we assume tree decompositions of treewidth tw and cutwidth decompositions of cutwidth ctw are given as input along with the input graph on n vertices and point (x,y).
To obtain these results, we refine the existing reductions that were instrumental for the seminal dichotomy by Jaeger, Welsh and Vertigan [Math. Proc. Cambridge Philos. Soc'90]. One of our technical contributions is a new rank bound of a matrix that indicates whether the union of two forests is a forest itself, which we use to show that the number of forests of a graph can be counted in 2^O(tw) n^O(1) time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Width Parameters
  • Parameterized Complexity
  • Tutte Polynomial

Metrics

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

Related Versions

Supplementary Materials

References

  1. Artur Andrzejak. An algorithm for the Tutte polynomials of graphs of bounded treewidth. Discret. Math., 190(1-3):39-54, 1998. URL: https://doi.org/10.1016/S0012-365X(98)00113-7.
  2. 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.
  3. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets Möbius: fast subset convolution, 2006. URL: https://doi.org/10.48550/arXiv.CS/0611101.
  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. Cornelius Brand, Holger Dell, and Marc Roth. Fine-grained dichotomies for the Tutte plane and Boolean #csp. Algorithmica, 81(2):541-556, 2019. URL: https://doi.org/10.1007/s00453-018-0472-z.
  6. Thomas H Brylawski. The Tutte polynomial. In Matroid Theory and Its Applications: Lectures Given at the Centro Internazionale Matematico Estivo. Springer Berlin, Heidelberg, Varenna (como), Italy, 1980. URL: https://doi.org/10.1007/978-3-642-11110-5.
  7. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009. URL: http://mitpress.mit.edu/books/introduction-algorithms.
  8. Radu Curticapean and Dániel Marx. Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus, pages 1650-1669. Society for Industrial and Applied Mathematics, 2015. URL: https://doi.org/10.1137/1.9781611974331.ch113.
  9. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  10. 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.
  11. 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. ACM Trans. Algorithms, 18(2):17:1-17:31, 2022. URL: https://doi.org/10.1145/3506707.
  12. Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlén. Exponential time complexity of the permanent and the Tutte polynomial. ACM Transactions on Algorithms, 10(4):1-32, August 2014. URL: https://doi.org/10.1145/2635812.
  13. 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), pages 36:1-36:20, 2022. URL: https://doi.org/10.48550/arXiv.2110.02730.
  14. 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.
  15. F. Jaeger, D. L. Vertigan, and D. J. A. Welsh. On the computational complexity of the Jones and Tutte polynomials. Mathematical Proceedings of the Cambridge Philosophical Society, 108(1):35-53, 1990. URL: https://doi.org/10.1017/S0305004100068936.
  16. Lars Jaffke and Bart M. P. Jansen. Fine-grained parameterized complexity analysis of graph coloring problems. Discret. Appl. Math., 327:33-46, 2023. URL: https://doi.org/10.1016/j.dam.2022.11.011.
  17. Mark Jerrum. Two-dimensional monomer-dimer systems are computationally intractable. Journal of Statistical Physics, 48(1-2):121-134, July 1987. URL: https://doi.org/10.1007/BF01010403.
  18. John E. Krizan, Peter F. Barth, and M.L. Glasser. Phase transitions for the Ising model on the closed Cayley tree. Physica A: Statistical Mechanics and its Applications, 119(1):230-242, 1983. URL: https://doi.org/10.1016/0378-4371(83)90157-7.
  19. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Slightly superexponential parameterized problems. SIAM J. Comput., 47(3):675-702, 2018. URL: https://doi.org/10.1137/16M1104834.
  20. Isja Mannens and Jesper Nederlof. A fine-grained classification of the complexity of evaluating the Tutte polynomial on integer points parameterized by treewidth and cutwidth. CoRR, To-appear, 2023. URL: https://arxiv.org/abs/2307.01046.
  21. Steven D. Noble. Evaluating the Tutte polynomial for graphs of bounded tree-width. Comb. Probab. Comput., 7(3):307-321, 1998. URL: http://journals.cambridge.org/action/displayAbstract?aid=46641.
  22. Xin-Zhuang Chen Peng-Fei Wan. Computing the number of k-component spanning forests of a graph with bounded treewidth. Journal of the Operations Research Society of China, 7(2):385, 2019. URL: https://doi.org/10.1007/s40305-019-00241-4.
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