2026-07-21T14:51:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25152 2026-02-09T08:17:55Z ddc:004 open_access

Deterministically Counting k-Paths and Trees Parameterized by Treewidth in Single-Exponential Time Visser, Jonne Bodlaender, Hans L. Parameterized Complexity Counting Subgraphs #k-path Dynamic Programming Tree Decomposition Determinant Method 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 [Hans L. Bodlaender et al., 2015]. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jonne Visser and Hans L. Bodlaender 2025 Is Part Of LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2025.20 urn:nbn:de:0030-drops-251529 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.20 eng https://creativecommons.org/licenses/by/4.0/legalcode