A fully polynomial parameterized algorithm for counting the number of reachable vertices in a digraph

We consider the problem of counting the number of vertices reachable from each vertex in a digraph G, which is equal to computing all the out-degrees of the transitive closure of G. The current (theoretically) fastest algorithms run in quadratic time; however, Borassi has shown that this problem is not solvable in truly subquadratic time unless the Strong Exponential Time Hypothesis fails [Borassi, 2016 [13]]. In this paper, we present an O(f(3)n)-time exact algorithm, where n is the number of vertices in G and f is the feedback edge number of G. Our algorithm thus runs in truly subquadratic time for digraphs of f = O(f(1/3-epsilon)) for any epsilon > 0, i.e., the number of edges is n plus O(f(1/3-epsilon)), and is filly polynomial fixed parameter tractable, the notion of which was first introduced by Fomin et al. (2018) [22]. We also show that the same result holds for vertex-weighted digraphs, where the task is to compute the total weights of vertices reachable from each vertex. (C) 2021 Elsevier B.V. All rights reserved.