On NP-hardness of the clique partition—Independence number gap recognition and related problems

We show that for a graph G it is NP  -hard to decide whether its independence number α(G)α(G) equals its clique partition number χ¯(G) even when some minimum clique partition of G   is given. This implies that any α(G)α(G)-upper bound provably better than χ¯(G) is NP-hard to compute.To establish this result we use a reduction of the quasigroup completion problem (QCP, known to be NP  -complete) to the maximum independent set problem. A QCP instance is satisfiable if and only if the independence number α(G)α(G) of the graph obtained within the reduction is equal to the number of holes h   in the QCP instance. At the same time, the inequality χ¯(G)⩽h always holds. Thus, QCP is satisfiable if and only if α(G)=χ¯(G)=h. Computing the Lovász number ϑ(G)ϑ(G) we can detect QCP unsatisfiability at least when χ¯(G)0 gap recognition, with one minimum clique partition of G known.