Approximate counting of K-paths: Deterministic and in polynomial space

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding

Abstract

A few years ago, Alon et al. [ISMB 2008] gave a simple randomized O((2e)km∊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 ± ∊. 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 ∊1 = kO(1). Recently, Brand et al. [STOC 2018] provided a speed-up at the cost of reintroducing randomization. Specifically, they gave a randomized O(4km∊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 4k+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 4k+O(log k(log k+log ∊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 4k+o(k)m whenever ∊1 = 2o(k), while our deterministic and randomized algorithms run in time 4k+o(k)m log n whenever ∊1 = 2o(k 4 ) and 1 ∊1 = 2o(log k k ), respectively. Prior to our work, no 2O(k)nO(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.

Details

Authors
Organisations
External organisations
  • University of California, Santa Barbara
  • The Institute of Mathematical Sciences
  • Ben Gurion University of the Negev
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Discrete Mathematics

Keywords

  • Approximate counting, K-Path, Parameterized complexity
Original languageEnglish
Title of host publication46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
EditorsIoannis Chatzigiannakis, Christel Baier, Stefano Leonardi, Paola Flocchini
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume132
ISBN (Electronic)9783959771092
Publication statusPublished - 2019 Jul 1
Publication categoryResearch
Peer-reviewedYes
Event46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 - Patras, Greece
Duration: 2019 Jul 92019 Jul 12

Conference

Conference46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
CountryGreece
CityPatras
Period2019/07/092019/07/12