2
$\begingroup$

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

Solution link.

$\endgroup$
1
$\begingroup$

Basically, Hamiltonian Cycle is the parcel problem with just one driver. To reduce Hamiltonian Cycle to the parcel problem with two drivers, you get one of the drivers to solve your Hamiltonian Cycle problem, and you make enough work for the other driver that they can't "cheat" by helping the first driver (but not so much work that the first driver has to help the second one).

$\endgroup$
  • $\begingroup$ Thanks for the reply. May I clarify how the second driver operates? Assuming we have a graph of 3 + 1 vertices (where the + 1 is the new vertex added), I take it that the first driver visits the first 3 vertex/location with a total distance of 6? And the second driver visits the newly added node instead? My confusion lies with how the second driver gets back to the source node as the newly added node is of distance 3 which is > k = 2. $\endgroup$ – Carrein Nov 23 '18 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.