文章基本信息

标题：Approximate Counting of k-Paths: Deterministic and in Polynomial Space
本地全文：下载
作者：Andreas Bj{"o}rklund ; Daniel Lokshtanov ; Saket Saurabh 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：132
页码：1-15
DOI：10.4230/LIPIcs.ICALP.2019.24
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：A few years ago, Alon et al. [ISMB 2008] gave a simple randomized O((2e)^km epsilon^{-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 +/- epsilon. Shortly afterwards, Alon and Gutner [IWPEC 2009, TALG 2010] gave a deterministic exponential-space 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 speed-up at the cost of reintroducing randomization. Specifically, they gave a randomized O(4^km epsilon^{-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 4^{k+O(sqrt{k}(log^2k+log^2 epsilon^{-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 4^{k+O(log k(log k + log epsilon^{-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 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 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.
关键词：parameterized complexity; approximate counting; { k}-Path