Counting Paths and Trees via Exterior Algebra

Abstract

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, ε is the relative error, and δ 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){\epsilon }^{-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)}{\epsilon }^{-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,{\epsilon }^{-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.

Counting k-paths, Counting k-trees, Exterior Algebra