Is it NP-complete to find a sub-maximal clique which is at least max clique size - 1?

Question

It is well-known that it is a NP-complete problem to find a maximal clique in a graph. But I wonder know if it possible to find a sub-maximal clique in a graph in polynomial time. That is, given that we don't know whether P=NP or not, is there a polynomial algorithm that would give me a clique whose size is at least the maximal clique size minus 1?

I guess the answer is "no", because I know that there isn't a polynomial-time algorithm that gives me a clique whose size is exactly maximal clique size minus 1 - otherwise I would know the size of max clique by this algorithm in polynomial time, which is impossible if P!=NP.

But I just don't know how to prove it when we expect the algorithm to return a clique with size at least maximal clique size minus 1 - say, it may randomly return a clique, whose size may be maximal, or may be maximal-1.

Is there any approach to prove its NP-completeness? Or such an algorithm really exists?

Answer 1

I just got the answer by myself. The maximal clique problem can be reduced to this problem.

Given a maximal clique problem with graph G, we can duplicate the graph G to a new graph G'. Then combine the two graphs in the following manner: if there is an edge between two vertices in graph G, connect each pair of the two vertices in G and G'; and for each vertex in G, connect it and its duplication in G'.

Then, each clique in G of size m with its duplication in G' consist of a larger clique of size 2m. So, there is a clique of size m if and only if there is a clique of size 2m in G'.

So, to find the maximum clique in G, we just find the sub-maximum clique in G' and the clique must contains all vertices in the maximum clique of G. Thus, we know the maximum clique in G in polynomial time, which is only possible when P=NP.