/Discuss this assignment. /Solutions.

1. Map coloring

In the MAP 3-COLORABILITY problem, you are given a list of n countries, and a list of pairs of countries that are adjacent to each other, e.g.:

 France
 Germany
 Spain
 Italy
 Denmark

 (France, Germany)
 (France, Spain)
 (France, Italy)
 (Germany, Denmark)
 ...

The problem is to find a way to color each country red, green, or blue, so that no two adjacent countries have the same color. To simplify the problem, you may assume that the countries are named with numerical codes from 1 to n.

1. Suppose you are given a coloring, i.e. an array of n entries that specifies a color red, green, or blue for each country. How long does it take (in worst-case asymptotic terms) to test if this coloring solves the problem, as a function of the number of countries n and the number of adjacency pairs m?
2. Now consider an algorithm that tests all possible colorings using the above algorithm. Assuming each test takes the worst-case time, how long does it take in the worst case to determine if a valid coloring exists?
3. A student suggests the following optimization, which works under the assumption that the countries can be ordered so that every country is adjacent to the preceding country in the list: Always color the first country red. For subsequent countries, consider only colors that are not equal to the color already chosen for their predecessor; for example, with just the two countries France and Germany, instead of consider all nine possible colorings, consider only the colorings (red, green) and (red, blue). Assume that the cost of generating these colorings is dominated by the cost of testing them, and that the cost of testing a coloring is the same worst-case cost assumed above. Compute the best upper bound you can on the worst-case asymptotic running time of the improved algorithm. Does this give more than a constant factor improvement on the previous algorithm?

2. Surveillance

The Department of Homeland Suspicion has a list of n suspicious persons it wishes to keep under surveillance. Each of these suspicious persons communicates regularly by telephone with other suspicious persons, and the DHS has a list of which pairs of suspicious persons talk to each other. The DHS suspects that among the n suspicious persons is a hidden conspiracy of k suspicious persons that can be identified by the fact that every member of the conspiracy regularly talks to every other member of the conspiracy. They have asked you to find this conspiracy, so that its members can be flagged for increased suspicion.

1. Give the best algorithm you can that either finds a conspiracy of k suspicious persons, or declares (correctly) that none exists. Compute the asymptotic worst-case running time of your algorithm as a function of n and k.
2. If the suspicious persons are talkative enough, there may be more than one such conspiracy. Give the best algorithm you can that finds all conspiracies of exactly k suspicious persons that all talk to each other, and compute its worst-case asymptotic running time as a function of n and k.

   Clarification: Assume that k is a constant.