Design a polynomial time algorithm for the problem 2-coloring defined below as D

Question

Design a polynomial time algorithm for the problem 2-coloring defined below as Definition 10.2. (Hint: Color the first vertex white, all adjacent vertices black, etc).

Definition 10.2: The class of decision problems P consists of those deci- sion problems whose yes/no solution can be obtained using a deterministic algorithm that runs in polynomial number of steps, i.e., in O(nk) steps, for some nonnegative integer k, where n is the input size.

We have encountered numerous such problems in the previous chap- ters. Since in this chapter we are dealing with decision problems, we list here some of the decision problems in the class P. The solutions to these problems should be fairly easy.
sorting: Given a list of n integers, are they sorted in nondecreasing order? set disjointness: Given two sets of integers, is their intersection empty? shortest path: Given a directed graph G = (V, E) with positive weights on its edges, two distinguished vertices s, t V and a positive integer k, is there a path from s to t whose length is at most k?
2-coloring: Given an undirected graph G, is it 2-colorable?, i.e., can its vertices be colored using only 2 colors such that no two adjacent vertices are assigned the same color? Note that G is 2-colorable if and only if it is bipartite, that is, if and only if it does not contain cycles of odd length.
2-sat: Given a boolean expression f in conjunctive normal form (CNF), where each clause consists of exactly two literals, is f satisfiable?

We say that a class of problems C is closed under complementation if for any problem C the complement of is also in C. For instance, the complement of the 2-coloring problem can be stated as follows. Given a graph G, is it not 2-colorable? Let us call this problem not-2-color. We can show that it is in P as follows. Since 2-coloring is in P, there is a deterministic algorithm A which when presented with a 2-colorable graph halts and answers yes, and when presented with a graph that is not 2-colorable halts and answers no. We can simply design a deterministic algorithm for the problem not-2-color by simply interchanging the yes and no answers in Algorithm A. This, informally, proves the following fundamental theorem:

Explanation / Answer

2-coloring determining whether a graph is bipartite which can be solved in polynomial time.

A polynomial time algorithm for 2-coloring can assign an arbitrary color to an arbitrary vertex, thereafter iteratively pick a uncolored vertex that has a colored neighbor and color it with the color not assigned to its neighbor.

This algorithm must produce a 2-coloring if it exists, and must run into a monochromatic edge otherwise.

An optimization problem associated with 2-coloring is to find a 2-labeling with fewest monochromatic edges, or equivalently, with the largest number of properly colored edges.

This last problem is known as max-cut and is NP-hard.

Once one color class is given, the remaining graph needs to be 2-colored, which can be done in polynomial time.

The smallest color class has size at most n/3.

Finding it by exhaustive search involves checking n/3 i=1 ( n i ) sets.

As we ignore polynomial factors, this last term can be replaced by ( n n/3 ) = n! (n/3)!(2n/3)! 3 n/3 (3/2)2n/3 = (27/4)n/3 .

Running time O ( (27/4)n/3 ) O (1.89n ). Take home message.

To design exponential time algorithms, one needs to know polynomial time algorithms.

Input: H from Forb(n, F)

Output: Proper coloring of H 1

Choose > 0 appropriately ;

2 (X, Y ) Partition (H, );

3 if e(X) + e(Y ) = 0 then

4 output 2-coloring corresponding to (X, Y );

5 else

6 try all n n = 2n log2 n possible colorings and output the one that minimizes the number of colors used;

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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