Is CLIQUE PROBLEM polynomial on a class of graphs $\mathbb{G}$, if $\mathbb{G}$ has one graph.

35 Views Asked by At

By CLIQUE PROBLEM I mean whether $\omega(G) \geq k$ for $k \geq 3$.

If $\mathbb{G}$ has just one graph, is the CLIQUE PROBLEM polynomial when restricted to $\mathbb{G}$?

My Attempt: I can check whether there is a clique of size $k$ for $k=1,2,\ldots,n$. So it should be polynomial.

1

There are 1 best solutions below

0
On BEST ANSWER

[Comment promoted to answer at request of OP]

The question of whether a problem can be solved in polynomial time is only asked when there are infinitely many instances of the problem, not when there's just one (or any finite number). Any single problem can always be solved in time polynomial in the input size by just taking a big enough polynomial!