# Is this problem just an application of traveling salesman? If not is it some other already "solved" problem?

Description of the problem in question:

Say I have a complete graph with positive weighted edges. 1 vertex is specified as the "end". A subset of the other vertices are designated as "start" vertices.

I want to find paths from each start vertex to the end vertex with the following conditions:

• As input, each path is given a maximum number of vertices it can visit. ie a path with a max of 5 vertices can only visit 5 other vertices before going straight to the end.

• Each vertex can only be visited by one path

• Each path must visit its max number of vertices, as long as there are unvisited vertices still available.
• The total combined cost of the paths should be minimized

Basically, I want to find a path from each start vertex to end vertex that hits as many other vertices as possible, limited by each paths max and that each vertex can only be visited once. So it's possible that not all vertices will be hit or that a path won't visit its max number of vertices.

I want to know if and how this problem breaks down into TSP, or some other problem. In general, I want to figure out how to solve this problem but I'm just looking for a place to start.

Any insight would be greatly appreciated.

Thanks a lot

• The third condition is not clear. Are you given a set of integers $\{m_1, m_2,\dots, m_k \}$ indicating that path $1$ may visit at most $m_1$ vertices, path $2$ at most $m_2$ vertices and so on? What is your input? Oct 9, 2017 at 23:07
• Sorry about that. You got it right though. Each start vertex has its own max associated with it independent of the other start vertices. You're given the graph itself, the start vertices, their respective m values, and the end vertex. Oct 10, 2017 at 3:49
• Points 2 and 4 seem to contradict each other: the graph is complete so, assuming the weights are positive, a minimum-weight path necessarily visits the minimum number of vertices. If you sort that out, your problem is most likely a generalization of TSP: you can probably reduce TSP to the case where there's a single start vertex that wants a path of length $n$. Oct 10, 2017 at 8:40
• I'm voting to close as unclear, but I'll happily retract that or vote to reopen if the problem statement is made clear. Oct 10, 2017 at 8:41
• It still seems contradictory. You want to maximize the number of vertices visited by the collection of paths as a whole, but visiting more vertices means traversing more edges, means incurring more costs, yet you're also trying to minimize costs. Which takes priority? Oct 11, 2017 at 10:33