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 NPC 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 k so that the number of edges with both endpoints in U is at least t? size U ( k can depend on n ) Hint: Choose b wisely. 4. The k-coloring problem. Given a graph and an input k

Explanation / Answer

For part 1 and 4, the graph coloring problem is a well known NP complete problem. It is also known as map coloring problem. A coloring of a graph is basically labeling the graph’s vertices with colors such that no two vertices sharing the same edge have the same color. This is known as vertex coloring. A coloring using at most k color is known as k-coloring. The smallest number of colors needed to color a graph is known as its chromatic number.

Lets denife the problem statement:
Given a graph G, an integer k and another integer ?, is there a k-coloring of G with at most ? monochromatic edges?

To show NP-completeness of a problem P, we need to do two things:

1) Show that P is in NP.This means that a commonly accepted solution can be verified.

2) Show that P is NP-hard. This is done by showing that some other NP-hard problem Q is many-one reducible to P. This implies that P itself is NP-hard.

A many-one reduction from Q to P is a function f, computable in polynomial time, which maps an instance x of Q to an instance f(x) of P such that
x?Q if and only if f(x)?P.

Lets say in our case, the NP machine guesses a k-coloring of G, and verifies (in polynomial time) that there are at most "?" monochromatic edges. In order to show that it is NP-hard, we come up with a many-one reduction f from the NP-hard problem K-COLORING to MIN-MONOCHROMATIC.

The reduction f takes a graph G and an integer k, forming an instance of K-COLORING, to the instance (G,k,0) of MIN-MONOCHROMATIC (i.e., with ?=0). The definition of coloring implies that (G,K) is in K-COLORING iff (G,k,0) is in MIN-MONOCHROMATIC. Also, clearly f can be computed in polynomial time. So f is a polytime many-one reduction from an NP-hard problem K-COLORING to MIN-MONOCHROMATIC, so we conclude that the latter is NP-hard. Since it is also in NP, it is NP-complete.

ANS 2 and 3)  Given an undirected graph G = (V, E), a feedback set is a set X ? V with the property that G ? X has no cycles. The undirected feedback set problem asks: given G and k, does G contain a feedback set of size at most k? Prove that the undirected feedback set problem is NP-complete. Solution: Easy to check that the problem is in NP: a solution needs to show a set of vertices S. The verifying algorithm first removes S, and then checks that the resulting graph does not have a cycle (can be done by any graph traversal algorithm). We reduce from vertex cover. Let G, k be an instance of vertex cover. We produce a graph G0 = (V 0 , E0 ) from G = (V, E) as follows: for every vertex v in G, we have a vertex v in G0 as well (G0 will have some more vertices). For an edge e = (u, v) in G, we create a new vertex ve in G0 , and add edges (u, ve),(ve, v),(u, v) in G0 . Now, suppose G have a vertex cover of size k. Let these vertices be S. We claim that S will be a feedback set in G0 . Indeed, any cycle in G0 must contain a pair u, v, where (u, v) is an edge in G. Since S contains at least one of u and v, S must intersect this cycle. Thus after removing S from G0 , we will not have any cycle. Conversely, consider a feedback set S of size k in G0 . First we claim that S need not contain any of the vertices ve – indeed, if e = (x, y), then any cycle containing ve must also contain x. Thus we can replace ve by x. Finally, any feedback set in S 0 must contain a vertex from the cycle x, y, ve in G0 , where e = (x, y) is an edge in E. We just argued that S must contain either x or y. Thus, S is a vertex cover in G.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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