Homework 4: Reduction

Please start by reading Dennis Sasha, Dr. Dobb's Journal 1998

Here's my formalization of the "Tentmates" problem. You may want to modify it.

    TENTMATES

    Given: Set T of tents. Capacity function s: T →
    N+. Set C of campers, with |C| = sum(ran
    s). Preference function p: C × C → -10..10 where
    p(c1, c2) is the preference of c1 for c2 and

    forall c in C . p(c, c) = 0.

    Find: Assignment function a: C → T satisfying

    forall t in T . |{c | a(c) = t}| = s(t)

    and maximizing

    sum[c1, c2 in C, a(c1) = a(c2)] p(c1, c2)

We'd like to show that Tentmates is NP Complete.

  1. Transform the Tentmates description into a description of a decision problem. The general idea is to remove the maximization by just asking "is there an arrangement of people for this instance with at least k happiness?" Let's call this problem "k-Tentmates".

  2. We need a problem to reduce from. Find a description of the Max Clique problem, online or in the textbook (sec 16.1 pps 525-). The k-Clique problem is the decision version of the Max Clique problem.

  3. Reduce k-Clique to k'-Tentmates. To do this, you'll have to show a construction that, for any possible k-Clique instance I, produces (in polytime) a corresponding k'-Tentmates instance I' such that the answer to I' is yes if and only if the answer to I is yes. Note that in general k' will not be equal to k: that is, the happiness required by the k'-Tentmates instance will not be the same as the k in the k-Clique instance.

  4. Explain how you would infer the vertices involved in the specific k-Clique in the original instance from the solution to k'-Tentmates, when one exists.

Hints

  • What feature of a k'-Tentmates instance should correspond to vertices in the k-Clique instance?

  • What feature of a k'-Tentmates instance might be used to encode the edges of a k-Clique instance?

  • Once you've got those figured out, how do you constrain the k'-Tentmates instance so that it answers yes exactly when the k-Clique answer is yes?