No code please, just explain. Thank you! Question 3: Show that the following pro

Question

No code please, just explain. Thank you!

Question 3: Show that the following problems are in NP (this does not contains the harder part of showing that the problem is NPC. You only need to show that given a candidate solution, it is possible to check in polynomial time if the solution is valid) 1. The 3 coloring problem: Given a graph G can we give the numbers 1 or 2 or 3 to 2. The k-coloring problem. Given a graph and an input k (k can depend on n) is 3. Given an undirected graph G, does it has a path of length k or more so that all the vertices of the graph, so that neighbors get different numbers? the graph k-colorable? the vertices are different? 4. 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? 5. Given a universe U, a collection of subsets s1, S2, . . . , Sm of U and a number k, is there a subcollection Sin . . . , Sik whose union s U? Namely U = -Si,

Explanation / Answer

We need to show that the given problems are NP i.e solution of the given problem is verifiable in polynomial time. let us start one by one:

1) In a 3 coloring problem, the solution is the number assigned to each of the vertex. Suppose that we are provide d with a solution, to esure wether given solution is valid or not, we can verify the solution by following method:

for every edge E between the vertices i and j in graph G, check wether vertices i and j have different number, if true for every edge, it is a valid solution. Maximum number of eges present in a graph is of the order N2, so we can verify the solution in O(N2) time, which in polynomial. Hence 3 coloring problem is NP.

2) Here also, we can use the approach same as the above, just check each and every edge to ensure every vertex connected to same edge gets a different number and the number is less than k, so, it can also be verified in O(N2) time. So, it is also in NP.

3)In the given problem, solution is the path of length k or more . it is very easy to verify wether the given path belongs to the graph and the path contains unique vertices. We can simply check wether every edge in path belongs to graph and no of unique vertices in path are more then r equal to k. It can be done in O(k) time, hence it is also in NP

4) In this problem, we will be provides a set of vertices U as the solution. To verify the solution, we will check how many edeges are ther whose both end points belongs to the given set U. if the number of edges turn out to be more re than or equal to t, the solution is verified. This method takes the time equal to the umber f edges present in the graph. In worst case the number of edges that can be present in the graph are of the order N2, so, the solution can be verified in O(N2). Hence, It also belongs to NP.

5) In this problem, we will be provided a collection of subsets of size k. To verify the solution, we ned to perform the union of the given subset and check wether the resulting union equals the universe U. Performing union will take time equal to sum of the number of elements in each subset and checking wether the result equals to the universe will take time of the order of no. of elements present in the universe. So, time complexity of verification method if of the order of the size of the U say N. Hence it can be verified in O(N) i.e in polynomial time. hence, it is also in NP.

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

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