I chanced upon the following question online:
A company has two trucks, and must deliver a number of parcels to a number of addresses. They want both drivers to be home at the end of the day. This gives the following decision problem.
Instance: Set V of locations, with for each pair of locations v, w ∈ V , a distance d(v, w) ∈ N, a starting location s ∈ V , and an integer K.Question: Are there two cycles, that both start in s, such that every location in V is on at least one of the two cycles, and both cycles have length at most K?
The solution provided uses Hamiltonian Cycle to prove the parcel problem is NP-Complete.
Given any instance of Hamiltonian Cycle with n vertices, construct the following special instance of the above problem.
- Copy the graph and make the distance d(v, w) equal to 2 if there is an edge in the graph, and 4, otherwise.
- Label one of these vertices as s. Add one vertex 0 such that d(s, 0) = d(0, s) = n and d(v, 0) = d(0, v) = 2n + 1 for all v != s. The threshold K is equal to 2n.
The explanation provided is as follows:
The only thing we have to do is to keep the other driver busy, which is easily taken care of by including an additional vertex with distance K/2 from s and distance K + 1 to all other addresses.
I tried constructing a simple graph of N = 3 whereby each vertex is connected by an edge of distance 2. Then I introduced a new node which is distance 4 away from the source vertex(i.e. starting point), and distance 7 from every other vertex.
But I am unable to understand how this construction fits into the original decisional problem. What exactly does the solution mean by "keeping the other driver busy?"
