betaFeedback

WorksComputer Science

The k-Clique hypothesis is dead, for good

Abstract

We present an algorithm that solves the kk-Clique problem for any large enough kk and any nn-vertex graph in n(ω3−c)kn^{\left(\fracω{3}-c\right)k} time, where ω≥2ω\geq 2 is the matrix multiplication exponent and c>0c>0 is a positive constant independent of both ωω and kk. This refutes the long-standing kk-Clique conjecture, regardless of the value of the matrix multiplication constant, even if ω=2ω=2. In fact, our algorithm solves the more general problem of counting weighted kk-Cliques.

Paper details

vlnc:W_hw3tqamm
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC-BY-NC-ND-4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…