Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Approximate Counting of k-Paths : Simpler, Deterministic, and in Polynomial Space

Lokshtanov, Daniel ; Björklund, Andreas LU ; Saurabh, Saket and Zehavi, Meirav (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)
Please use this url to cite or link to this publication:
author
; ; and
organization
publishing date
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}},
}