reduction - Prove NP-completeness of CLIQUE-OR-INDEPENDENT-SET -
first of all, want mention homework . however, solve problem can use literature want. even though think problem clear name, give description: "for given undirected graph g , given integer k, g contain totally connected (clique) subgraph of size k or totally disconnected subgraph (independent set) of size k." i know polynomial reductions 3-sat clique , 3-sat independent-set . ( http://mlnotes.com/2013/04/29/npc.html ) however, have problem 1 because cannot combine 2 reductions. tried reduction clique clique-or-independent-set without success. so appreciate hints! thanks in advance. i found out reduction problem independent-set clique-or-independent-set . need add n isolated vertices graph g (which instance of independent-set , has n vertices). let call newly created graph g' (instance of clique-or-independent-set ). not hard prove g has k independent-set iff g' has n+k independent-set of clique (since, construction, cannot have n+k c...