On NP-hardness of the clique partition : independence number gap recognition and related problems

• Main Authors: Busygin, Stanislav., Pasechnik, Dmitrii V.
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2012
• Subjects: DRNTU::Science::Mathematics::Discrete mathematics::Theory of computation
• Online Access: https://hdl.handle.net/10356/80117; http://hdl.handle.net/10220/8272
• Institution: Nanyang Technological University

We show that for a graph G it is NP-hard to decide whether its independence number α(G) equals its clique partition number ¯χ(G) even when some minimum clique partition of G is given. This implies that any α(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) 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) we can detect QCP unsatisfiability at least when ¯χ (G) <h. In the other cases QCP reduces to ¯χ (G) − α(G) >0 gap recognition, with one minimum clique partition of G known.