The Zoo problem is: Given a set of n animals, {a_1, a_2, ...., a_n}, and a list

Question

The Zoo problem is: Given a set of n animals, {a_1, a_2, ...., a_n}, and a list of pairs of animals who will attack each other, is it possible to split the animals into three enclosures, E_1, E_2 and E_3, so that no animal will attack any other animal in its enclosure? (a) Prove that the Zoo problem is in NP. b) Prove that the 3-coloring problem reduces to the Zoo problem in polynomial time. (Note that proving a) and b) proves that the Zoo Problem is NP-complete, assuming that 3-coloring is NP-complete.)

Explanation / Answer

(1) :

Here n animals and list of pairs of animal who will attack each other is given in problem.

Now lets consider one of the possible splits X, Y and Z. i.e n animals are divided into X, Y and Z three groups.

We need to find if there is some polynomial time algorithm which can check if X, Y and Z is solution to the given problem or not.

i.e if X, Y and Z has animals divided in such a way that no animals attack each other.

This can be done with simple linear check.

If there are E pairs of animals that will attack each other then for each pair check if they are in same group or not.

if for all E pairs, animals are in different groups then we can say that X, Y, Z is solution to the given problem

hence from given three sets, we can find out if given sets are solution of the problem or not. This can be done in polynomial time. Time taken would be O(E). There can be at most n2 pairs. So upper bound would be O(n2).

Hence we can say that zoo problem is NP problem as there is some polynomial time algorithm to check whether given solution is correct or not.

(2) :

For 3 coloring in graph G :

1) consider each node as animal . hence there are n animals (n node in graph G )

2) if there is an edge between two nodes then make a pair of corresponding animals of those two nodes

and add that pair to the list of pairs of animals who will attack each other.

3) now, Solution to the zoo problem will give three groups of animals. Which are X, Y and Z.

4) node corresponing to animals in same group will be colored with similar color. i.e all nodes(animals) in group X will have same color but different than animals in Y and Z.

color X with red, Y with green and Z with blue. i.e color nodes with corresponding animals in X with red, Y with green and Z with blue.

Hence 3 coloring problem can be reduced to the zoo problem in polynomial time.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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