Advanced

Approximate counting of K-paths : Deterministic and in polynomial space

Björklund, Andreas LU ; Lokshtanov, Daniel; Saurabh, Saket and Zehavi, Meirav (2019) 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 132.
Abstract

A few years ago, Alon et al. [ISMB 2008] gave a simple randomized O((2e)km∊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 ± ∊. Shortly afterwards, Alon and Gutner [IWPEC 2009, TALG 2010] gave a deterministic exponential-space algorithm with running time (2e)k+O(log3 k)m log n whenever ∊1 = kO(1). Recently, Brand et al. [STOC 2018] provided a speed-up at the cost of reintroducing randomization. Specifically, they gave a randomized O(4km∊2)-time exponential-space algorithm. In this article, we revisit the... (More)

A few years ago, Alon et al. [ISMB 2008] gave a simple randomized O((2e)km∊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 ± ∊. Shortly afterwards, Alon and Gutner [IWPEC 2009, TALG 2010] gave a deterministic exponential-space algorithm with running time (2e)k+O(log3 k)m log n whenever ∊1 = kO(1). Recently, Brand et al. [STOC 2018] provided a speed-up at the cost of reintroducing randomization. Specifically, they gave a randomized O(4km∊2)-time exponential-space algorithm. In this article, we revisit the algorithm by Alon and Gutner. We modify the foundation of their work, and with a novel twist, obtain the following results. We present a deterministic 4k+O(√k(log2 k+log2 ∊−1))m log n-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+O(log k(log k+log ∊1))m log n-time polynomial-space algorithm. While Brand et al. make non-trivial use of exterior algebra, our algorithm is very simple; we only make elementary use of the probabilistic method. Thus, the algorithm by Brand et al. runs in time 4k+o(k)m whenever ∊1 = 2o(k), while our deterministic and randomized algorithms run in time 4k+o(k)m log n whenever ∊1 = 2o(k 4 ) and 1 ∊1 = 2o(log k k ), respectively. Prior to our work, no 2O(k)nO(1)-time polynomial-space algorithm was known. Additionally, our approach is embeddable in the classic framework of divide-and-color, hence it immediately extends to approximate counting of graphs of bounded treewidth; in comparison, Brand et al. note that their approach is limited to graphs of bounded pathwidth.

(Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Approximate counting, K-Path, Parameterized complexity
host publication
46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
editor
Chatzigiannakis, Ioannis; Baier, Christel; Leonardi, Stefano; Flocchini, Paola; ; ; and
volume
132
publisher
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
conference name
46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
conference location
Patras, Greece
conference dates
2019-07-09 - 2019-07-12
external identifiers
  • scopus:85069148917
ISBN
9783959771092
DOI
10.4230/LIPIcs.ICALP.2019.24
language
English
LU publication?
yes
id
4089b07d-a744-4771-96e6-9a17bc5db8f5
date added to LUP
2019-07-26 10:33:32
date last changed
2019-08-28 04:57:27
@inproceedings{4089b07d-a744-4771-96e6-9a17bc5db8f5,
  abstract     = {<p>A few years ago, Alon et al. [ISMB 2008] gave a simple randomized O((2e)<sup>k</sup>m∊<sup>−</sup><sup>2</sup>)-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 ± ∊. Shortly afterwards, Alon and Gutner [IWPEC 2009, TALG 2010] gave a deterministic exponential-space algorithm with running time (2e)<sup>k</sup>+O<sup>(log3 k)</sup>m log n whenever ∊<sup>−</sup><sup>1</sup> = k<sup>O</sup><sup>(1)</sup>. Recently, Brand et al. [STOC 2018] provided a speed-up at the cost of reintroducing randomization. Specifically, they gave a randomized O(4<sup>k</sup>m∊<sup>−</sup><sup>2</sup>)-time exponential-space algorithm. In this article, we revisit the algorithm by Alon and Gutner. We modify the foundation of their work, and with a novel twist, obtain the following results. We present a deterministic 4<sup>k</sup>+O(√k<sup>(log2 k+log2 ∊−1))</sup>m log n-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 4<sup>k</sup>+O(log k(log k+log ∊<sup>−</sup><sup>1))</sup>m log n-time polynomial-space algorithm. While Brand et al. make non-trivial use of exterior algebra, our algorithm is very simple; we only make elementary use of the probabilistic method. Thus, the algorithm by Brand et al. runs in time 4<sup>k</sup>+o(k<sup>)</sup>m whenever ∊<sup>−</sup><sup>1</sup> = 2<sup>o</sup>(k<sup>)</sup>, while our deterministic and randomized algorithms run in time 4<sup>k</sup>+o(k<sup>)</sup>m log n whenever ∊<sup>−</sup><sup>1</sup> = 2<sup>o</sup>(k 4 <sup>)</sup> and 1 ∊<sup>−</sup><sup>1</sup> = 2<sup>o</sup><sup>(log k k )</sup>, respectively. Prior to our work, no 2<sup>O</sup>(k<sup>)</sup>n<sup>O</sup><sup>(1)</sup>-time polynomial-space algorithm was known. Additionally, our approach is embeddable in the classic framework of divide-and-color, hence it immediately extends to approximate counting of graphs of bounded treewidth; in comparison, Brand et al. note that their approach is limited to graphs of bounded pathwidth.</p>},
  author       = {Björklund, Andreas and Lokshtanov, Daniel and Saurabh, Saket and Zehavi, Meirav},
  editor       = {Chatzigiannakis, Ioannis and Baier, Christel and Leonardi, Stefano and Flocchini, Paola},
  isbn         = {9783959771092},
  keyword      = {Approximate counting,K-Path,Parameterized complexity},
  language     = {eng},
  location     = {Patras, Greece},
  month        = {07},
  publisher    = {Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing},
  title        = {Approximate counting of K-paths : Deterministic and in polynomial space},
  url          = {http://dx.doi.org/10.4230/LIPIcs.ICALP.2019.24},
  volume       = {132},
  year         = {2019},
}