A Note on the Complexity of Computing the Number of Reachable Vertices in a Digraph

Abstract

In this work, we consider the following problem: given a digraph $G=(V,E)$, for each vertex $v$, we want to compute the number of vertices reachable from $v$. In other words, we want to compute the out-degree of each vertex in the transitive closure of $G$. We show that this problem is not solvable in time $\mathcal{O}\left(|E{|}^{2-\epsilon }\right)$ for any $\epsilon >0$, unless the Strong Exponential Time Hypothesis is false. This result still holds if $G$ is assumed to be acyclic.

References in corpus (3)

• Popular conjectures imply strong lower bounds for dynamic problems
• Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails
• Into the Square - On the Complexity of Quadratic-Time Solvable Problems