Question

A teacher needs to take n naughty children across a river during a trip. Certain pairs of these children don’t like each other at all and cannot be left together on one side of the river unless the teacher is also present, or they will harm each other. The ferry can hold at most k passengers at a time, including the teacher, and the kids are too small to pilot the ferry.

Prove that it is NP-hard to decide whether the teacher can ferry all n children across the river unharmed by reducing from the Independent Set problem. The input consists of the integers k and n and an n-vertex graph G describing the pairs of children who don’t like each other. The output is either True or False. (Hint: Start with a graph G on which you want to solve the independent ′ set problem with parameter k . Create two copies of G. Add some edges. Choose an appropriate k.)

Answer 1

Now, suppose that a Hamiltonian cycle h exists in G. It is clear that the cost of each edge in h is 0 in G^' as each edge belongs to E. Therefore, h has a cost of 0 in G^'. Thus, if graph G has a Hamiltonian cycle, then graph G^' has a tour of 0 cost.

Conversely, we assume that G^' has a tour h^' of cost at most 0. The cost of edges in E^' are 0 and 1 by definition. Hence, each edge must have a cost of 0 as the cost of h^' is 0. We therefore conclude that h^' contains only edges in E.