A Fully Polynomial Parameterized Algorithm for Counting the Number of Reachable Vertices in a Digraph
| Autor: | Naoto Ohsaka |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Polynomial Current (mathematics) Exponential time hypothesis Transitive closure Digraph 0102 computer and information sciences 02 engineering and technology 01 natural sciences Computer Science Applications Theoretical Computer Science Vertex (geometry) Combinatorics Exact algorithm 010201 computation theory & mathematics Signal Processing Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Data Structures and Algorithms (cs.DS) Time complexity Information Systems Mathematics |
| DOI: | 10.48550/arxiv.2103.04595 |
| Popis: | 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 probl m is not solvable in truly subquadratic time unless the Strong Exponential Time Hypothesis fails [Inf. Process. Lett., 116(10):628--630, 2016]. In this paper, we present an $\mathcal{O}(f^3n)$-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=\mathcal{O}(n^{\frac{1}{3}-\epsilon})$ for any $\epsilon > 0$, i.e., the number of edges is $n$ plus $\mathcal{O}(n^{\frac{1}{3}-\epsilon})$, and is fully polynomial fixed parameter tractable, the notion of which was first introduced by Fomin, Lokshtanov, Pilipczuk, Saurabh, and Wrochna [ACM Trans. Algorithms, 14(3):34:1--34:45, 2018]. 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. Comment: minor changes, acknowledgments added |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|