Ex.8.14 Prove that the following problem is NP-complete: given an undirected graph G = (V,E) and an integer k, return a clique of size k as well as an independent set of size k, provided both exist.

答：可以將最大團(tuán)問(wèn)題歸約到此問(wèn)題。假設(shè)要求任意圖G(V,E)中大小為k的團(tuán)，可以在圖G中添加k個(gè)相互獨(dú)立的頂點(diǎn)，得到新圖G'。這新加的k個(gè)頂點(diǎn)保證了圖G'存在大小為k的獨(dú)立集，同時(shí)又不影響到原圖的團(tuán)。