2026-08-11T00:28:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18735 2024-03-06T11:02:35Z ddc:004 open_access

A Fine-Grained Classification of the Complexity of Evaluating the Tutte Polynomial on Integer Points Parameterized by Treewidth and Cutwidth Mannens, Isja Nederlof, Jesper Width Parameters Parameterized Complexity Tutte Polynomial 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Isja Mannens and Jesper Nederlof 2023 Is Part Of LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2023.82 urn:nbn:de:0030-drops-187354 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.82 eng https://creativecommons.org/licenses/by/4.0/legalcode