# 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?