Recently, Brand et al. [STOC 2018] gave a randomized O(4(k)m 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 +/- ...
详细信息
Recently, Brand et al. [STOC 2018] gave a randomized O(4(k)m 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 +/- c based on exterior algebra. Prior to our work, this has been the state-of-the-art. In this article, we revisit the algorithm by Alon and Grauer [IWEC 2009, TALC 2010], and obtain the following results: We present a deterministic 4(k+O(root k(log2k+log2 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 (3 has a path on k vertices. Additionally, we present a randomized 4(k+O(logk(log k+log) (epsilon-1)))m log n-time polynomial-space algoritlun. Our algoritlun is simple we only make elementary use of the probabilistic method. Here, n and m are the number of vertices and the number of edges, respectively. Additionally, our approach extends to approximate counting of other patterns of small size (such as q-dimensionalp-matchings).
parameterized complexity has, so far, been largely confined to consideration of computational problems as decision or search problems. However, it is becoming evident that the parameterized point of view can lead to n...
详细信息
parameterized complexity has, so far, been largely confined to consideration of computational problems as decision or search problems. However, it is becoming evident that the parameterized point of view can lead to new insight into countingproblems. The goal of this article is to introduce a formal framework in which one may consider parameterized counting problems. (c) 2005 Elsevier B.V. All rights reserved.
暂无评论