Triangle Conjecture
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
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).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.