WorksComputer Science
The k-Clique hypothesis is dead, for good
Abstract
We present an algorithm that solves the -Clique problem for any large enough and any -vertex graph in time, where is the matrix multiplication exponent and is a positive constant independent of both and . This refutes the long-standing -Clique conjecture, regardless of the value of the matrix multiplication constant, even if . In fact, our algorithm solves the more general problem of counting weighted -Cliques.