skip to content

Why is finding a clique of size k not expected to admit a cost of f(k) times a polynomial in n?

level: seniorimportance: nice to knowfreq 24%

answer

  1. brute force over all k-subsets
  2. polynomial degree grows with k
  3. no forced local choice anywhere
  4. hardness under parameter-preserving reductions
  5. W[1] against FPT, still open

basics

~20 s

Brute force over all k-subsets gives n^k, which is XP, and nothing better in shape is known. Finding a k-clique is hard for the class W[1], so an f(k) times polynomial algorithm would collapse W[1] into FPT - widely disbelieved.

solid answer

~40 s

Checking every `k`-subset finds a `k`-clique in roughly `n^k` steps, so the problem sits in **XP**: for each fixed `k` it is polynomial, but the degree grows with `k`. What is missing is the FPT shape, `f(k) * n^c` with a constant `c`. Finding a `k`-clique is **W[1]-hard**, and W[1] is the parameterized analogue of NP-hardness: hardness is transferred by reductions that keep the parameter bounded by a function of the original, so an FPT algorithm for any W[1]-hard problem would put all of W[1] inside FPT. Nobody believes that, just as nobody expects P to equal NP. Structurally, the reason is that a clique offers no forced local branch and no known small kernel: seeing an edge tells you nothing that *must* be in the answer.

go deeper

for a junior

The takeaway is that two problems can be equally hard in the classical sense and still behave very differently once you fix a small limit in the requirements.

for a middle

Be able to say why brute force over subsets is only XP, and what shape would be needed instead: a function of the parameter multiplying a polynomial whose degree never moves.

for a senior

Explain the structural reason rather than the class name - no forced local choice and no sound reduction rule - and what you would do instead, which is to parameterize by a structural measure the data actually bounds.

for a principal

Use it to set expectations before a team spends a quarter optimising: the evidence says the shape is unreachable, so the decision is which parameter or which weaker question the product can live with.

## The gap this question is about Two classical graph problems, both hard in the classical sense, behave completely differently once a parameter is declared: | parameterized by the answer size `k` | vertex cover | clique | |---|---|---| | brute force | `n^k` | `n^k` | | better shape known | `2^k * n`, i.e. FPT | none known | | forced local rule | yes: an edge forces one of two vertices | no | | small kernel | yes, quadratic | none known | | parameterized classification | in FPT | hard for W[1] | Both are NP-complete in the classical setting, so classical hardness cannot explain the difference. Parameterized complexity exists precisely to make this distinction sayable. ## What W[1]-hardness asserts Parameterized reductions are stricter than classical ones. A reduction from problem `A` to problem `B` must run in FPT time **and** produce a new parameter bounded by a function of the old one. That second condition is what makes the reduction preserve fixed-parameter tractability: compose an FPT algorithm for `B` with such a reduction and you get an FPT algorithm for `A`. `W[1]` is a class of parameterized problems defined by bounded-depth circuit satisfiability with a weight constraint; finding a `k`-clique is **complete** for it. The classes line up as `FPT` inside `W[1]` inside `W[2]` and so on, all inside `XP`. Two facts are worth keeping straight, because candidates routinely merge them: - `FPT` is **strictly** inside `XP`. That separation is proven. - Whether `FPT` equals `W[1]` is **open**, and the working assumption is that it does not. So "clique is W[1]-hard" says: an `f(k) * n^c` algorithm for it would drag the entire class down into FPT. It is evidence of the same character as NP-hardness, not a proof of impossibility. ## Why the two standard tools fail here - **No forced branch.** The vertex cover search works because an uncovered edge presents a constant-size set of candidates, one of which every solution must contain. For clique, no small set of vertices is forced: any vertex may or may not be in some `k`-clique, and local inspection gives no certificate either way. Without a forced branch, the depth of a search tree is governed by the graph, not by `k`. - **No known kernel.** Kernelization needs reduction rules that provably preserve the answer. For vertex cover, a vertex of degree above the budget must be taken; for clique, a vertex of enormous degree tells you nothing - it may be in no clique at all. A small kernel for clique would in fact imply an FPT algorithm, since kernel and FPT coincide for decidable problems. ## How far the pessimism goes Under the standard assumption that satisfiability of formulas in conjunctive normal form has no sub-exponential algorithm, the consequence for clique is sharper than "not FPT": there is no algorithm of the form `n^o(k)` either. In other words, the brute-force exponent is close to the best achievable in that shape, not merely un-improved to date. The engineering translation: you cannot expect to shave the dependency on the graph, only to change the question. ## What you do instead 1. **Change the parameter.** Clique becomes tractable when parameterized by a structural measure rather than by the answer size - the width of a tree decomposition, or a bound on how sparse every subgraph is. The problem did not become easier; a different quantity was declared small, and for many real graphs that quantity genuinely is. 2. **Restrict the inputs.** On graphs guaranteed to be sparse or near-tree-shaped, exhaustive enumeration over a bounded neighbourhood is affordable. 3. **Change the question.** If the requirement is "a large mutually-compatible group" rather than "the largest", the surrounding design may accept a weaker guarantee; a guaranteed-ratio answer and an exact exponential search are separate disciplines with their own trade-offs. ## The sentence an interviewer wants *Both problems are hard classically, but one of them has a local rule that forces a decision and the other does not; parameterized complexity is the vocabulary that makes that difference formal, and W[1]-hardness is the evidence that the missing rule is missing for a reason.* Saying that, rather than reciting the class names, is what marks the answer as understood.

  • What makes a parameterized reduction stricter than a classical polynomial one?
    It must run in fixed-parameter tractable time and produce a new parameter bounded by a function of the old one. Without that second condition, a reduction could inflate the parameter and destroy the property being transferred. The extra condition is exactly what makes tractability flow backward along the reduction.
  • Is there any parameter under which finding cliques becomes tractable?
    Yes. Parameterized by a structural measure - the width of a tree decomposition, or a bound on the sparsity of every subgraph - the problem admits algorithms whose exponential factor depends only on that measure. The hardness is attached to the answer size as the parameter, not to the problem in every possible reading.
  • Does W[1]-hardness mean the problem is undecidable or outside NP?
    Neither. A k-clique is verified in polynomial time by checking all pairs in a candidate set, so the classical problem is squarely in NP, and every instance is decidable by brute force. W[1]-hardness is a statement about the shape of achievable running times once a parameter is declared.

saying these in an interview costs you the question

  • Says a W[1]-hard problem cannot be solved at all
  • Calls n^k fixed-parameter tractable because k is treated as a constant
  • Claims the FPT versus W[1] question has been settled
  • Assumes classical NP-completeness already predicts parameterized behaviour
  • Thinks a high-degree vertex must belong to some maximum clique