Deterministically Counting k-Paths and Trees Parameterized by Treewidth in Single-Exponential Time
Publication date
2025-12-15
Authors
Visser, Jonne
Bodlaender, Hans L.
Editors
Agrawal, Akanksha
Leeuwen , Erik Jan van
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
cc_by
Abstract
In this paper, we give new and faster deterministic algorithms to count the number of k-paths and trees in host graphs of bounded treewidth. Our algorithms use time that is single-exponential in the treewidth, and employ the determinant method from [4]. Modifications of the algorithms count in single-exponential time the number of k-paths between specified end-points, the number of k-cycles, and the number of trees with k vertices that are a subgraph of the host graph.
Keywords
#k-path, Counting Subgraphs, Determinant Method, Dynamic Programming, Parameterized Complexity, Tree Decomposition, Software
Citation
Visser, J & Bodlaender, H L 2025, Deterministically Counting k-Paths and Trees Parameterized by Treewidth in Single-Exponential Time. in A Agrawal & E J V Leeuwen (eds), 20th International Symposium on Parameterized and Exact Computation, IPEC 2025., 20, Leibniz International Proceedings in Informatics, LIPIcs, vol. 358, Dagstuhl Publishing, 20th International Symposium on Parameterized and Exact Computation, IPEC 2025, Warsaw, Poland, 17/09/25. https://doi.org/10.4230/LIPIcs.IPEC.2025.20, conference