Triangle Conjecture

From papers

Consider the word-RAM model of computation with word length O(logb)O(\log b) for inputs of length bb. An undirected graph GG has mm edges. Triangle Conjecture. There exists a constant ϵ>0\epsilon>0 such that every algorithm in this model that correctly reports whether GG contains a triangle has running time Ω(m1+ϵ)\Omega(m^{1+\epsilon}). 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

No solutions have been posted yet.