Approximate counting of K-paths : Deterministic and in polynomial space
(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)
- author
- Björklund, Andreas LU ; Lokshtanov, Daniel ; Saurabh, Saket and Zehavi, Meirav
- organization
- publishing date
- 2019-07-01
- 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 and Flocchini, Paola
- volume
- 132
- article number
- 24
- publisher
- Schloss Dagstuhl - Leibniz-Zentrum für Informatik
- 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
- 2022-04-26 03:26:06
@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}},
booktitle = {{46th International Colloquium on Automata, Languages, and Programming, ICALP 2019}},
editor = {{Chatzigiannakis, Ioannis and Baier, Christel and Leonardi, Stefano and Flocchini, Paola}},
isbn = {{9783959771092}},
keywords = {{Approximate counting; K-Path; Parameterized complexity}},
language = {{eng}},
month = {{07}},
publisher = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}},
title = {{Approximate counting of K-paths : Deterministic and in polynomial space}},
url = {{http://dx.doi.org/10.4230/LIPIcs.ICALP.2019.24}},
doi = {{10.4230/LIPIcs.ICALP.2019.24}},
volume = {{132}},
year = {{2019}},
}