Björklund, Andreas ;
Lokshtanov, Daniel ;
Saurabh, Saket ;
Zehavi, Meirav
Approximate Counting of kPaths: Deterministic and in Polynomial Space
Abstract
A few years ago, Alon et al. [ISMB 2008] gave a simple randomized O((2e)^km epsilon^{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 +/ epsilon. Shortly afterwards, Alon and Gutner [IWPEC 2009, TALG 2010] gave a deterministic exponentialspace algorithm with running time (2e)^{k+O(log^3k)}m log n whenever epsilon^{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^km epsilon^{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(sqrt{k}(log^2k+log^2 epsilon^{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 epsilon^{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 epsilon^{1}=2^{o(k)}, while our deterministic and randomized algorithms run in time 4^{k+o(k)}m log n whenever epsilon^{1}=2^{o(k^{1/4})} and epsilon^{1}=2^{o(k/(log 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.
BibTeX  Entry
@InProceedings{bjrklund_et_al:LIPIcs:2019:10600,
author = {Andreas Bj{\"o}rklund and Daniel Lokshtanov and Saket Saurabh and Meirav Zehavi},
title = {{Approximate Counting of kPaths: Deterministic and in Polynomial Space}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {24:124:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10600},
URN = {urn:nbn:de:0030drops106001},
doi = {10.4230/LIPIcs.ICALP.2019.24},
annote = {Keywords: parameterized complexity, approximate counting, { k}Path}
}
04.07.2019
Keywords: 

parameterized complexity, approximate counting, { k}Path 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

04.07.2019 