. Question 5: Show that the following problems are NPC. Assume that The Hamilto-
ID: 3704475 • Letter: #
Question
. 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? 2. Given an undirected graph G, does it has a path of length k or more so that all 3. Given a graph G(V, E), a number k and a number t. Is there a subset U of V of Hint add a new vertex that is connected to all of V the vertices are different? size U k so that the number of edges with both endpoints in U is at least t? (k can depend on n) Hint: Choose b wisely. 4. The k-coloring problem. Given a graph and an input kExplanation / Answer
1. Yes
Part 1. 4-COLOR is in NP. The coloring is (a list of nodes and colors).
The following is a verifier g for 4-COLOR.
V=On input (G,c),
1. Check that c includes <=colors.
2. Color each node of G as specified by c.
3. For each node, check that it has a unique color from each of its neighbors.
4. If all checks pass, accept; otherwise, reject.”
Part 2. 4-COLOR is NP-hard.
We give a polynomial-time reduction from 3-COLOR to 4-COLOR.
The reduction maps a graph G into a new graph G, such that G e 3-COLOR if and only if G' 4-COLOR.
We do so by setting G' to G and then adding a new node y and connecting y to each node in G' .
If G is 3-colorable, then G' can be 4-colored exactly as G with y being the only node colored with the additional color. Similarly, if G' is 4-colorable, then we know that node y must be the only node of its color – this is because it is connected to every other node in G'. Thus, we know that G must be 3-colorable.
This reduction takes linear time to add a single node and G edges.
Since 4-COLOR is in NP and NP-hard, we know it is NP-complete
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.