Approximate counting of Kpaths : 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)^{k}m∊^{−}^{2})time exponentialspace 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 exponentialspace algorithm with running time (2e)^{k}+O^{(log3 k)}m log n whenever ∊^{−}^{1} = k^{O}^{(1)}. Recently, Brand et al. [STOC 2018] provided a speedup at the cost of reintroducing randomization. Specifically, they gave a randomized O(4^{k}m∊^{−}^{2})time exponentialspace algorithm. In this article, we revisit the... (More)
A few years ago, Alon et al. [ISMB 2008] gave a simple randomized O((2e)^{k}m∊^{−}^{2})time exponentialspace 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 exponentialspace algorithm with running time (2e)^{k}+O^{(log3 k)}m log n whenever ∊^{−}^{1} = k^{O}^{(1)}. Recently, Brand et al. [STOC 2018] provided a speedup at the cost of reintroducing randomization. Specifically, they gave a randomized O(4^{k}m∊^{−}^{2})time exponentialspace 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^{k}+O(√k^{(log2 k+log2 ∊−1))}m log ntime polynomialspace algorithm. This matches the running time of the best known deterministic polynomialspace algorithm for deciding whether a given graph G has a path on k vertices. Additionally, we present a randomized 4^{k}+O(log k(log k+log ∊^{−}^{1))}m log ntime polynomialspace algorithm. While Brand et al. make nontrivial 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^{k}+o(k^{)}m whenever ∊^{−}^{1} = 2^{o}(k^{)}, while our deterministic and randomized algorithms run in time 4^{k}+o(k^{)}m log n whenever ∊^{−}^{1} = 2^{o}(k 4 ^{)} and 1 ∊^{−}^{1} = 2^{o}^{(log k k )}, respectively. Prior to our work, no 2^{O}(k^{)}n^{O}^{(1)}time polynomialspace algorithm was known. Additionally, our approach is embeddable in the classic framework of divideandcolor, 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
 20190701
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 keywords
 Approximate counting, KPath, 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 LeibnizZentrum fur Informatik GmbH, Dagstuhl Publishing
 conference name
 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
 conference location
 Patras, Greece
 conference dates
 20190709  20190712
 external identifiers

 scopus:85069148917
 ISBN
 9783959771092
 DOI
 10.4230/LIPIcs.ICALP.2019.24
 language
 English
 LU publication?
 yes
 id
 4089b07da744477196e69a17bc5db8f5
 date added to LUP
 20190726 10:33:32
 date last changed
 20190828 04:57:27
@inproceedings{4089b07da744477196e69a17bc5db8f5, 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 exponentialspace 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 exponentialspace 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 speedup at the cost of reintroducing randomization. Specifically, they gave a randomized O(4<sup>k</sup>m∊<sup>−</sup><sup>2</sup>)time exponentialspace 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 ntime polynomialspace algorithm. This matches the running time of the best known deterministic polynomialspace 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 ntime polynomialspace algorithm. While Brand et al. make nontrivial 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 polynomialspace algorithm was known. Additionally, our approach is embeddable in the classic framework of divideandcolor, 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,KPath,Parameterized complexity}, language = {eng}, location = {Patras, Greece}, month = {07}, publisher = {Schloss Dagstuhl LeibnizZentrum fur Informatik GmbH, Dagstuhl Publishing}, title = {Approximate counting of Kpaths : Deterministic and in polynomial space}, url = {http://dx.doi.org/10.4230/LIPIcs.ICALP.2019.24}, volume = {132}, year = {2019}, }