ℓ-layered reachability oracle conjecture
Let be an integer, and let be an -layered directed acyclic graph with layers , where every edge goes from to . An -layered reachability oracle is a data structure for answering whether a vertex in reaches a vertex in ; let denote the number of edges. Consider the word-RAM model with word length for inputs of length . -layered reachability oracle conjecture. There exists a constant such that every such oracle has preprocessing time or query time . This conjecture underlies conditional lower bounds for dynamic graph problems. The source attributes it to Alman et al. and gives no resolution; it also notes that the 3LRO conjecture follows from the Triangle and 3SUM conjectures.
References
- Jiehua Chen, Wojciech Czerwiński, Yann Disser, Andreas Emil Feldmann, Danny Hermelin, Wojciech Nadara, Michał Pilipczuk, Marcin Pilipczuk, Manuel Sorge, Bartłomiej Wróblewski and Anna Zych-Pawlewicz, “Efficient fully dynamic elimination forests with applications to detecting long paths and cycles”, arXiv:2006.00571 (2020).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.