Triangle Conjecture
Consider the word-RAM model of computation with word length for inputs of length . An undirected graph has edges. Triangle Conjecture. There exists a constant such that every algorithm in this model that correctly reports whether contains a triangle has running time . This conjecture is a standard conditional assumption for lower bounds in dynamic graph algorithms; the source gives no resolution of it.
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
Never refreshed
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.