Metraipolis › archive › dc_8a84ef314e71

Counting Paths and Trees via Exterior Algebra — arXiv:2609.14682

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.14682
License (as archived): CC0-1.0
Archived: 2026-10-16T02:15:21.656Z
SHA-256 of the archived text: a7163d89f1aaecc1c41555b436dae1147826ba151cc2791d2a1f0787faa06585
Stable URL of this page: https://metraipolis.com/documento/dc_8a84ef314e71

How to cite

Counting Paths and Trees via Exterior Algebra — arXiv:2609.14682 — arXiv (en), https://arxiv.org/abs/2609.14682 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8a84ef314e71 (Metraipolis archive dc_8a84ef314e71, sha256 a7163d89f1aaecc1c41555b436dae1147826ba151cc2791d2a1f0787faa06585)

BibTeX

@misc{dc8a84ef314e71,
  title = {Counting Paths and Trees via Exterior Algebra — arXiv:2609.14682},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.14682},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8a84ef314e71; sha256 a7163d89f1aaecc1c41555b436dae1147826ba151cc2791d2a1f0787faa06585},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.14682. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We give randomized approximation algorithms for counting k-paths and k-forests in a host graph. Here k denotes the number of pattern vertices, n and m denote the numbers of host vertices and edges or arcs, {\epsilon} is the relative error, and {\delta} is the failure probability. Our main results are: 1. Paths: We approximate the number of directed paths on $k$ vertices in $2^k k^{O(1)}(n+m)\varepsilon^{-2}\log(2/\delta)$ arithmetic operations. 2. Trees and forests: For every fixed $\eta>0$, we approximate the number of non-induced copies of a given forest on $k$ vertices in $(2+\eta)^k n^{O_\eta(1)}\varepsilon^{-2}\log(2/\delta)$ arithmetic operations. Our path algorithm resolves a conjecture of Koutis and Williams~[CACM 2016] and answers an open question of Lokshtanov, Saurabh, and Zehavi~[SODA 2021] by giving a $2^k poly(n,\varepsilon^{-1})$-time approximation scheme. Our algorithms combine exterior algebra with random matrix estimators, using the tensor-train moment bound of Rakhshan and Rabusseau~[AISTATS 2020]. For forests, we use a small-component separator to evaluate the estimator efficiently.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-15 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.14682 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T01:54:07.126Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).