Approximate Counting of k-Paths : Simpler, Deterministic, and in Polynomial Space
(2021) In ACM Transactions on Algorithms 17(3).- Abstract
Recently, Brand et al. [STOC 2018] gave a randomized mathcal O(4kmϵ-2-time exponential-space algorithm to approximately compute the number of paths on k vertices in a graph G up to a multiplicative error of 1 ± ϵ based on exterior algebra. Prior to our work, this has been the state-of-the-art. In this article, we revisit the algorithm by Alon and Gutner [IWPEC 2009, TALG 2010], and obtain the following results: •We present a deterministic 4k+ O(sk(log k+log2ϵ-1))m-time polynomial-space algorithm. This matches the running time of the best known deterministic polynomial-space algorithm for deciding whether a given graph G has a path on k vertices. •Additionally, we present a randomized 4k+mathcal O(logk(logk+logϵ-1))m-time... (More)
Recently, Brand et al. [STOC 2018] gave a randomized mathcal O(4kmϵ-2-time exponential-space algorithm to approximately compute the number of paths on k vertices in a graph G up to a multiplicative error of 1 ± ϵ based on exterior algebra. Prior to our work, this has been the state-of-the-art. In this article, we revisit the algorithm by Alon and Gutner [IWPEC 2009, TALG 2010], and obtain the following results: •We present a deterministic 4k+ O(sk(log k+log2ϵ-1))m-time polynomial-space algorithm. This matches the running time of the best known deterministic polynomial-space algorithm for deciding whether a given graph G has a path on k vertices. •Additionally, we present a randomized 4k+mathcal O(logk(logk+logϵ-1))m-time polynomial-space algorithm. Our algorithm is simple - we only make elementary use of the probabilistic method. Here, n and m are the number of vertices and the number of edges, respectively. Additionally, our approach extends to approximate counting of other patterns of small size (such as q-dimensional p-matchings).
(Less)
- author
- Lokshtanov, Daniel ; Björklund, Andreas LU ; Saurabh, Saket and Zehavi, Meirav
- organization
- publishing date
- 2021
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- k-path, Parameterized complexity, parameterized counting problems
- in
- ACM Transactions on Algorithms
- volume
- 17
- issue
- 3
- article number
- 26
- publisher
- Association for Computing Machinery (ACM)
- external identifiers
-
- scopus:85112070968
- ISSN
- 1549-6325
- DOI
- 10.1145/3461477
- language
- English
- LU publication?
- yes
- id
- 33da8859-e245-43c4-a8c5-b8bb2fe61b13
- date added to LUP
- 2021-09-01 15:06:01
- date last changed
- 2022-04-27 03:36:54
@article{33da8859-e245-43c4-a8c5-b8bb2fe61b13, abstract = {{<p>Recently, Brand et al. [STOC 2018] gave a randomized mathcal O(4kmϵ-2-time exponential-space algorithm to approximately compute the number of paths on k vertices in a graph G up to a multiplicative error of 1 ± ϵ based on exterior algebra. Prior to our work, this has been the state-of-the-art. In this article, we revisit the algorithm by Alon and Gutner [IWPEC 2009, TALG 2010], and obtain the following results: •We present a deterministic 4k+ O(sk(log k+log2ϵ-1))m-time polynomial-space algorithm. This matches the running time of the best known deterministic polynomial-space algorithm for deciding whether a given graph G has a path on k vertices. •Additionally, we present a randomized 4k+mathcal O(logk(logk+logϵ-1))m-time polynomial-space algorithm. Our algorithm is simple - we only make elementary use of the probabilistic method. Here, n and m are the number of vertices and the number of edges, respectively. Additionally, our approach extends to approximate counting of other patterns of small size (such as q-dimensional p-matchings). </p>}}, author = {{Lokshtanov, Daniel and Björklund, Andreas and Saurabh, Saket and Zehavi, Meirav}}, issn = {{1549-6325}}, keywords = {{k-path; Parameterized complexity; parameterized counting problems}}, language = {{eng}}, number = {{3}}, publisher = {{Association for Computing Machinery (ACM)}}, series = {{ACM Transactions on Algorithms}}, title = {{Approximate Counting of k-Paths : Simpler, Deterministic, and in Polynomial Space}}, url = {{http://dx.doi.org/10.1145/3461477}}, doi = {{10.1145/3461477}}, volume = {{17}}, year = {{2021}}, }