2018 · 18 citations · 23 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationComputational ComplexityGraph AlgorithmsGraph TheoryClique AlgorithmsCliquesComputational Complexity Of Graph AlgorithmsConditional Lower BoundsEdge-density ProblemsErdős - Rényi GraphsLower BoundsMaximum Clique Approximation
We prove that for k ≪ n1/4 regular resolution requires length nΩ(k) to establish that an Erdos-Renyi graph with appropriately chosen edge density does not contain a k-clique. This lower bound is optimal up to the multiplicative constant in the exponent, and also implies unconditional nΩ(k) lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs.
23
Matthew W. Moskewicz, Conor Madigan, Ying Zhao et al. · 2001 · 2.9K citations
On the Shannon capacity of a graph
László Lovász · IEEE Transactions on Information Theory · 1979 · 1.7K citations
Clique is hard to approximate within n1−ε
Johan Håstad · Acta Mathematica · 1999 · 1.4K citations · Full text
Russell Impagliazzo, Ramamohan Paturi · Journal of Computer and System Sciences · 2001 · 1K citations