1. JE12-5a (TSP)

Set weight of each edge to infinity and check if there is a TSP. When such an edge is found, contract the edge and recurse. Show that a tour in the contracted graph can be used to be find a tour in the original graph.

2. You’re consulting for a small high-tech company that maintains a high-security computer system for some sensitive work that it’s doing. To make sure this
system is not being used for any illicit purposes, they’ve set up some logging
software that records the IP addresses that all their users are accessing over
time. We’ll assume that each user accesses at most one IP address in any given
minute; the software writes a log file that records, for each user u and each
minute m, a value I(u, m) that is equal to the IP address (if any) accessed by
user u during minute m. It sets I(u, m) to NULL if u did not access
any IP address during minute m.
The company management just learned that yesterday the system was
used to lannch a complex attack on some remote sites. The attack was carried
out by accessing t distinct IP addresses over t consecutive minutes: In minute 
1, the attack accessed address i1; in minute 2, it accessed address i2; and so
on, up to address it in minute t.

Who could have been responsible for carrying out this attack? The company checks the logs and finds to its surprise that there’s no single user u who
accessed each of the IP addresses involved at the appropriate time; in other
words, there’s no u so that I(u, m) = im for each minute m from 1 to t.
So the question becomes: What if there were a small coalition of users
that collectively might have carried out the attack using the set of t IP addresses? We will say a subset S of
users is a suspicious coalition if, for each minute m from 1 to t, there is at least
one user u in S for which I(u, m) = im. (In other words, each IP address was
accessed at the appropriate time by at least one user in the coalition.)

The Suspicious Coalition Problem asks: Given the collection of all values
I(u, m) for n users and t minutes, and a set J of t distinct IP addresses, what is the smallest size of a suspicious coalition that access all the IP addresses in J?

(a) Design a decision version of this problem (name it SUSP).

(b) Show that SUSP is in NP.

(c) Show that SUSP is NP-hard.

See Kleinberg-Tardos Ch8 solved exercise 1 that shows a reduction from VertexCover. Also show a reduction from Set Cover: for each set Si, create a user Ui and for each element xj in Si, add to log that Ui accessed IP address Ij in the j-th minute. Finally set J as {I1 ... It} where t is the cardinality of the universe.

*3. JE12.16(a-f).