Finding the minimum number of tours to cover all nodes

Question

I am facing the below problem.

Statement:

1. A number of nodes with their locations are given
2. There is a central node in the middle which its location is also provided.
3. A route is defined as a path that starts from the central node and visits at least one node and ends up again in the central node.
4. Routes length must be shorter than a given number.

How do I cover all nodes with minimum number of routes?

I would appreciate any help that can provide a solution for this or a similar and famous problem that looks like this if there is anything.

Answer 1

This problem is NP-Hard with a simple reduction from TSP.

First, define the language that is accepted by this problem

L = { (G,x,i) | graph G, maximum length per path x, minimal number of travels required i }

It is easy to see that your problem is basically the optimization problem for the existence problem as defined above.

TSP:
Given an instance of TSP in the form of (G,x), we need to determine if there is a cyclic path that goes through all points of length shorter/equals x.

The reduction:
The reduction is as follows. Given an instance of TSP (G,x), provide the instance for your problem (G,x,1).

Correctness:

• If there is a cyclic path that goes through all points of length x or less in the solution of TSP, there is also a solution to your problem with 1 travel required.
• If there is 1 travel required in the problem with length x or less, this is the route found by TSP.

The reduction we proposed is trivially polynomial.

From this we can conclude that your problem is NP-Hard, since TSP is NP-Hard.