arXiv preprint ·
Counting Paths and Trees via Exterior Algebra
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
A $(p+q)^{O(pq)}$-approximation for $(p, q)$-Flexible Graph Connectivity
A Strongly Subquadratic $(3+\varepsilon)$-Approximation for Weighted Edit Distance over Arbitrary Metrics
Sharp Norms from Finite Structure: Graph Matrices and Structured Chaoses
Fast Stencil Computations on a Single Arbitrarily Moving Interval
Approximating Optimal Welfare in Complementary Allocation under Decentralized Information
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.