3
$\begingroup$

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

Improve this question
$\endgroup$
12
  • $\begingroup$ 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? $\endgroup$
    – fade2black
    Oct 9, 2017 at 23:07
  • $\begingroup$ 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. $\endgroup$
    – cwolf08
    Oct 10, 2017 at 3:49
  • $\begingroup$ 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$. $\endgroup$
    – David Richerby
    Oct 10, 2017 at 8:40
  • $\begingroup$ I'm voting to close as unclear, but I'll happily retract that or vote to reopen if the problem statement is made clear. $\endgroup$
    – David Richerby
    Oct 10, 2017 at 8:41
  • 1
    $\begingroup$ 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? $\endgroup$
    – David Richerby
    Oct 11, 2017 at 10:33

1 Answer 1

Reset to default
1
$\begingroup$

This problem comes down to a transportation problem (actually the Wikipedia article is not very good), although it is not exactly the problem you are stating. As David Richerby stated in the comments, your problem is formulated contradictory, therefore I would suggest a reformulation, where you fix the number of vertices that each path visits. But while reading yourself into the capacitive transport problem, you will find out yourself what changes fit best for your task.
Solving these problems can indeed, as stated by Raphael, be solved via min-cost max-flow algorithms.
When you decided on a new version I am happy to extend my answer to fit your needs.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the help. I updated the post to fix number of vertices that each path visited as you suggested. The fixed number is given as input for each path. I'll also look into min-cost max-flow algorithms to see if they make sense for me and update here again. $\endgroup$
    – cwolf08
    Oct 12, 2017 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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