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

• المؤلفون الرئيسيون: Busygin, Stanislav., Pasechnik, Dmitrii V.
• مؤلفون آخرون: School of Physical and Mathematical Sciences
• التنسيق: مقال
• اللغة: English
• منشور في: 2012
• الموضوعات: DRNTU::Science::Mathematics::Discrete mathematics::Theory of computation
• الوصول للمادة أونلاين: https://hdl.handle.net/10356/80117; http://hdl.handle.net/10220/8272

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 w...