ECCC-Report TR03-052https://eccc.weizmann.ac.il/report/2003/052Comments and Revisions published for TR03-052en-usMon, 30 Jun 2003 18:16:03 +0300
Paper TR03-052
| On ~chi(G)-alpha(G)>0 gap recognition and alpha(G)-upper bounds |
Stanislav Busygin,
Dmitrii V. Pasechnik
https://eccc.weizmann.ac.il/report/2003/052We 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 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 alpha(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 ~chi(G)&lt;=h always holds. Thus, QCP is satisfiable if and only if alpha(G)=~chi(G)=h. Computing the Lovasz number theta(G) we can detect QCP unsatisfiability at least when ~chi(G)&lt;h. In the other cases QCP reduces to ~chi(G)-alpha(G)&gt;0 gap recognition, with one minimum clique partition of G known.
Mon, 30 Jun 2003 18:16:03 +0300https://eccc.weizmann.ac.il/report/2003/052