Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > STANISLAV BUSYGIN:
All reports by Author Stanislav Busygin:

TR03-052 | 13th May 2003
Stanislav Busygin, Dmitrii V. Pasechnik

On ~chi(G)-alpha(G)>0 gap recognition and alpha(G)-upper bounds

We show that for a graph G it is NP-hard to decide whether its independence number alpha(G) equals its clique partition number ~chi(G) even when some minimum clique partition of G is given. This implies that any alpha(G)-upper bound provably better than ~chi(G) is NP-hard to compute.

To establish this ... more >>>




ISSN 1433-8092 | Imprint