Question 5: Show that the following problems are NPC. Assume that The Hamilto- n

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 N P C . 1. Can a graph be colored by 4 colors? Hint add a new vertex that is connected to all of V . 2. Given an undirected graph G , does it has a path of length k or more so that all the vertices are different? 3. 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 ) Hint: Choose b wisely. 4. The k -coloring problem. Given a graph and an input k

Explanation / Answer

i)It is true

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),

i) Check that c includes <=colors.

ii) Color each node of G as specified by c.

iii) For each node, check that it has a unique color from each of its neighbors.

iv) If all checks pass, accept; otherwise, reject.”

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.

From the above equation 4-COLOR is in NP and NP-hard

therefore NP-complete.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.