# 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? – fade2black Oct 9 '17 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. – cwolf08 Oct 10 '17 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$. – David Richerby Oct 10 '17 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. – David Richerby Oct 10 '17 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? – David Richerby Oct 11 '17 at 10:33