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, {\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.