1

Suppose you have a directed graph G, with V vertices and E edges. There are L special edges that contain a medal, and the objective is to collect N medals in the least time. Note that vertices and edges (except special edges) can be visited any number of times. You are also given a starting vertex, but no end vertex.

I have looked at similar problems, namely this: find shortest path in a graph that compulsorily visits certain Edges while others are not compulsory to visit. Unfortunately, L is around 600, and N is around 100. I have also considered some modified version of Dijkstra's algorithm, but that only allows vertices to be visited once. Is there some solution that can run this in a reasonable amount of time?

needarubberduck
  • 596
  • 3
  • 17
  • 3
    Sounds like traveling salesman. – G. Bach Jul 19 '17 at 17:32
  • 1
    @G.Bach The difference between traversing edges and traversing vertices is huge (Eular path VS Hamilton path), so I am unsure if it's indeed TSP – amit Jul 19 '17 at 18:47
  • 1
    @amit Reduction from TSP would go something like, split every node into two, connect them with an edge, make those edges the ones you want to visit. – G. Bach Jul 19 '17 at 19:01
  • Similar: https://stackoverflow.com/questions/18549965/most-rewarding-path-in-a-graph – Lior Kogan Jul 20 '17 at 04:22

2 Answers2

2

Tracking the references mcdowella suggested, we end up at this paper (direct link to PDF, may require a Wiley online subscription). The described problem is the Rural Postman Problem and is indeed NP-hard; the paper mentions TSP (NP-hard), the Chinese Postman Problem (polytime), and the Rural Postman Problem (NP-hard). They reduce from Hamilton Circuit to RPP, and the reduction is pretty much what I suggested in a comment: split every node into two, connect them with an edge, assign suitable weights, make those edges the ones you want to visit.

They mention that the difference between CPP (where you have to visit all edges) and RPP is similar to the difference between finding an MST, where you have to find a minimum-weight tree that spans all nodes, and a Steiner tree, where you have to find a minimum-weight tree that spans a subset of the nodes.

G. Bach
  • 3,869
  • 2
  • 25
  • 46
1

There is something called the Chinese Postman problem, which Wikipedia calls https://en.wikipedia.org/wiki/Route_inspection_problem. This covers the case when you want to visit all edges, but if you at the end of the Wikipedia account you will see "Minimize the "Rural Postman Problem": solve the problem with some edges not required." which gives you at least a reference and perhaps a search term.

mcdowella
  • 19,301
  • 2
  • 19
  • 25