Show that the following problems are in NP. Assume that the graph is given by ma

Question

Show that the following problems are in NP. Assume that the graph is given by matrix representation. All you have to do is to show that if you are given a candidate solution you can check if its valid or not. The dominating set problem. We are given a graph G( V, E) and a number k and the question is if there is a subset S V of size at most k so that for every u S there exists a v S so that (v, u) E? The coloring problem. Given a graph G(V, E) and a number k the question is can we decompose V into a union of at most k disjoint sets V = Vi so that for every Vi, the set is an independent set, namely, every pair of vertices inside Vi are not neighbors? The Max-cut problem: The input is a graph G(V, E) and a number k. The question is: can we partition V into V = V1 U V2, V1 V2 = so that the number of edges that have one endpoint in V1 and one in V2 is at least k?

Explanation / Answer

NP-complete (abbreviated NP-C or NPC) is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems and also in the set of NP-hard problems. Although any given solution to such a problem can be verified quickly, there is no known efficient way to locate a solution in the first place; indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. This means that the time required to solve even moderately sized versions of many of these problems can easily reach into the billions or trillions of years, using any amount of computing power available today. As a consequence, determining whether or not it is possible to solve these problems quickly, called the P versus NP problem, is one of the principal unsolved problems in computer science today.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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