Skip to interview prep
Apexed

395. Checking for a clique of size 3 is polynomial, so why is CLIQUE NP-complete?

MediumComplexity classes

Technical
Show model answer

For a fixed constant k, trying every k-subset of vertices takes O(n^k · k²) time, which is polynomial because k does not grow with the input (triangles take O(n³), or faster with matrix multiplication). In the CLIQUE problem, k is part of the input and can be as large as n/2, and C(n, n/2) is exponential.

So 'polynomial for every fixed k' is not the same as polynomial. Parameterized complexity makes the distinction precise: k-vertex cover is fixed-parameter tractable (O(2^k · n)), while k-clique is believed not to be, since no algorithm of the form f(k) · n^c is known.

Checking for a clique of size 3 is polynomial, so why is CLIQUE NP-complete — Data structures & algorithms interview question — Apexed