Which of the following problems are in P? Which of the following problems are in

Question

Which of the following problems are in P? Which of the following problems are in NP? Justify your answers. For parts (a) and (b) we reference the problem of graph colorings. A graph coloring is a way of assigning a color to each vertex such that no two adjacent vertices have the same color. A graph is said to be k-colorable if there is a valid graph coloring which uses no more than k colors. As an example, all bipartite graphs are 2-colorable. Using these definitions we define the following class of languages k-COLORING {G | G is a graph G is k-colorable} (a) 2-COLORING (b) 3-COLORING (c) 5-SAT-{(d) | is a satisfiable 5-CNF formula}

Explanation / Answer

Graph Coloring which is defined as the labelling the graph components such as vertices, edges or region with constraints as no two adjacent vertices, adjacent edges, or adjacent regions are coloured with minimum number of colors. The smallest number of colors needed to colour a graph G is called its chromatic number

Option 1: 2 Coloring:

We can write a simple algorithm for determining whether a graph is 2-colorable and assigning colors to its vertices, using breadth first search, assigning blue to first layer and res to second layer. This algorithm complexity is O(|V| + |E|).

Therefore it is in P.

Option 2: 3 Coloring:

For k > 2 however, the problem is much more difficult and this is a different case here. You can use brute force search by considering every possible combinations but, it can be shown that deciding whether a given graph is k-colorable for k > 2 is an NP-complete problem.
Hence it is not in P

Option3: 5-SAT

According to Cook's theorem If a Boolean formula is in CNF and every clause consists of exactly k literals, we say the Boolean formula is an instance of k-SAT. Because not every Boolean formula has a k-SAT equivalent. So, 2SAT is in P; 3SAT is NP-complete and 5-SAT is NP-complete as well.
Hence it is not in P

Answer:

Only Option 1 (i.e 2 coloring) is in P.

Option 2 and 3 are NP-Complete problem. (which is in NP)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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