Fast approximate counting of paths and forests in large graphs
Counting Paths and Trees via Exterior Algebra
Data Structures and Algorithms
Summary
Counting specific patterns like paths and forests in large networks is a hard problem. The authors present new algorithms that quickly approximate how many such patterns appear in directed graphs, with controllable accuracy and failure risk. Their techniques combine advanced math tools, including exterior algebra and random matrix methods, to efficiently handle the counting. This work solves some open problems posed by previous researchers, providing the fastest known approximation method for these tasks.
What this means in practice
- •For network analysts: Quickly estimate the frequency of specific connectivity patterns like paths and forests in large communication or social networks to support structural analysis.
- •For bioinformatics software teams: Speed up approximate counting of pathway patterns in large biological networks for understanding molecular interactions.
Authors
Fahad Panolan, Saket Saurabh, Meirav Zehavi, Jie Xue
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)\varepsilon^{-2}\log(2/δ)$ arithmetic operations. 2. Trees and forests: For every fixed $η>0$, we approximate the number of non-induced copies of a given forest on $k$ vertices in $(2+η)^k n^{O_η(1)}\varepsilon^{-2}\log(2/δ)$ 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.