A Lower Bound on Cycle-Finding in Sparse Digraphs

Autor:	Chen, Xi, Randolph, Tim, Servedio, Rocco A., Sun, Timothy
Rok vydání:	2019
Předmět:	Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	We consider the problem of finding a cycle in a sparse directed graph $G$ that is promised to be far from acyclic, meaning that the smallest feedback arc set in $G$ is large. We prove an information-theoretic lower bound, showing that for $N$-vertex graphs with constant outdegree any algorithm for this problem must make $\tilde{\Omega}(N^{5/9})$ queries to an adjacency list representation of $G$. In the language of property testing, our result is an $\tilde{\Omega}(N^{5/9})$ lower bound on the query complexity of one-sided algorithms for testing whether sparse digraphs with constant outdegree are far from acyclic. This is the first improvement on the $\Omega(\sqrt{N})$ lower bound, implicit in Bender and Ron, which follows from a simple birthday paradox argument. Comment: 25 pages, 2 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1907.12106 Zobrazit plný text záznamu View this record from Arxiv