Approximate counting of Kpaths: Deterministic and in polynomial space
Research output: Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
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 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.
Details
Authors  

Organisations  
External organisations 

Research areas and keywords  Subject classification (UKÄ) – MANDATORY
Keywords

Original language  English 

Title of host publication  46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 
Editors  Ioannis Chatzigiannakis, Christel Baier, Stefano Leonardi, Paola Flocchini 
Publisher  Schloss Dagstuhl LeibnizZentrum fur Informatik GmbH, Dagstuhl Publishing 
Volume  132 
ISBN (Electronic)  9783959771092 
Publication status  Published  2019 Jul 1 
Publication category  Research 
Peerreviewed  Yes 
Event  46th International Colloquium on Automata, Languages, and Programming, ICALP 2019  Patras, Greece Duration: 2019 Jul 9 → 2019 Jul 12 
Conference
Conference  46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 

Country  Greece 
City  Patras 
Period  2019/07/09 → 2019/07/12 