Deterministically Counting k-Paths and Trees Parameterized by Treewidth in Single-Exponential Time

Jonne Visser; Hans L. Bodlaender

doi:10.4230/LIPIcs.IPEC.2025.20

Deterministically Counting k-Paths and Trees Parameterized by Treewidth in Single-Exponential Time

Jonne Visser^*
, Hans L. Bodlaender^*

^*Corresponding author for this work

Sub Algorithms and Complexity

Utrecht University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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.

Original language	English
Title of host publication	20th International Symposium on Parameterized and Exact Computation, IPEC 2025
Editors	Akanksha Agrawal, Erik Jan van Leeuwen
Publisher	Dagstuhl Publishing
ISBN (Electronic)	9783959774079
DOIs	https://doi.org/10.4230/LIPIcs.IPEC.2025.20
Publication status	Published - 15 Dec 2025
Event	20th International Symposium on Parameterized and Exact Computation, IPEC 2025 - Warsaw, Poland Duration: 17 Sept 2025 → 19 Sept 2025

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	358
ISSN (Print)	1868-8969

Conference

Conference	20th International Symposium on Parameterized and Exact Computation, IPEC 2025
Country/Territory	Poland
City	Warsaw
Period	17/09/25 → 19/09/25

Bibliographical note

Publisher Copyright:
© Jonne Visser and Hans L. Bodlaender.

Keywords

#k-path
Counting Subgraphs
Determinant Method
Dynamic Programming
Parameterized Complexity
Tree Decomposition

Access to Document

10.4230/LIPIcs.IPEC.2025.20Licence: CC BY

Deterministically Counting k-Paths and Trees Parameterized by Treewidth in Single-Exponential TimeFinal published version, 845 KBLicence: CC BY

Cite this

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 Article 20 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 358). Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.IPEC.2025.20

@inproceedings{472772cd1a7c479d9cc658ea3f5862aa,

title = "Deterministically Counting k-Paths and Trees Parameterized by Treewidth in Single-Exponential Time",

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",

author = "Jonne Visser and Bodlaender, \{Hans L.\}",

note = "Publisher Copyright: {\textcopyright} Jonne Visser and Hans L. Bodlaender.; 20th International Symposium on Parameterized and Exact Computation, IPEC 2025 ; Conference date: 17-09-2025 Through 19-09-2025",

year = "2025",

month = dec,

day = "15",

doi = "10.4230/LIPIcs.IPEC.2025.20",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Dagstuhl Publishing",

editor = "Akanksha Agrawal and \{Leeuwen \}, \{Erik Jan van\}",

booktitle = "20th International Symposium on Parameterized and Exact Computation, IPEC 2025",

}

Visser, J & Bodlaender, HL 2025, Deterministically Counting k-Paths and Trees Parameterized by Treewidth in Single-Exponential Time. in A Agrawal & EJV 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

Deterministically Counting k-Paths and Trees Parameterized by Treewidth in Single-Exponential Time. / Visser, Jonne; Bodlaender, Hans L.
20th International Symposium on Parameterized and Exact Computation, IPEC 2025. ed. / Akanksha Agrawal; Erik Jan van Leeuwen . Dagstuhl Publishing, 2025. 20 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 358).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Deterministically Counting k-Paths and Trees Parameterized by Treewidth in Single-Exponential Time

AU - Visser, Jonne

AU - Bodlaender, Hans L.

N1 - Publisher Copyright: © Jonne Visser and Hans L. Bodlaender.

PY - 2025/12/15

Y1 - 2025/12/15

N2 - 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.

AB - 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.

KW - #k-path

KW - Counting Subgraphs

KW - Determinant Method

KW - Dynamic Programming

KW - Parameterized Complexity

KW - Tree Decomposition

UR - https://www.scopus.com/pages/publications/105031401528

U2 - 10.4230/LIPIcs.IPEC.2025.20

DO - 10.4230/LIPIcs.IPEC.2025.20

M3 - Conference contribution

AN - SCOPUS:105031401528

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 20th International Symposium on Parameterized and Exact Computation, IPEC 2025

A2 - Agrawal, Akanksha

A2 - Leeuwen , Erik Jan van

PB - Dagstuhl Publishing

T2 - 20th International Symposium on Parameterized and Exact Computation, IPEC 2025

Y2 - 17 September 2025 through 19 September 2025

ER -

Deterministically Counting k-Paths and Trees Parameterized by Treewidth in Single-Exponential Time

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this