Prof. Meirav Zehavi

A few years ago, Alon et al. [ISMB 2008] gave a simple randomized O((2e)^km∊⁻²)-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 ∊⁻¹ = 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∊⁻²)-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(√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 4^k+O(log k(log k+log ∊⁻¹⁾⁾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 ∊⁻¹ = 2^o(k⁾, while our deterministic and randomized algorithms run in time 4^k+o(k⁾m log n whenever ∊⁻¹ = 2^o(k 4 ⁾ and 1 ∊⁻¹ = 2^{o(log k 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.