• Question 5: Show that the following problems are NPC. Assume that The Hamilto- nian path question, The clique of size

[answerhappygod]

Question 5 Show That The Following Problems Are Npc Assume That The Hamilto Nian Path Question The Clique Of Size 1 (20.38 KiB) Viewed 42 times

• Question 5: Show that the following problems are NPC. Assume that The Hamilto- nian path question, The clique of size k question, and the 3 coloring problem are in NPC. 1. Can a graph be colored by 4 colors? Assume that the problem if telling if a graph has a 3 coloring is in NPC. (waste a color). 2. Given a graph G(V, E), a number k and a number t. Is there a subset U of V of size U = k so that the number of edges with both endpoints in U is at least t? (k can depend on n). Choose t wisely. 3. The k-coloring problem. Given a graph and an input k Assume that 3 coloring is in NPC.