Assume we have a weighted, directed Graph $G$ with vertices $V$.
There are vertices named START and END in the graph.
Among all possible paths from START to END, I want to select paths that, together, cover all vertices in a designated subgraph $S$ (such collection of paths is guaranteed to exist). I want to minimize the total weight of all selected edges.
Would there be a suitable algorithm for this problem?
The closest parallel I can find for this problem is submodular maximization of paths. I was wondering if there was any other way.
Thank you.
In the case where edges are counted each time we pass through if $S$ is the whole graph, then your problem is equivalent to the traveling salesman problem (TSP), which is NP-hard, so it is not tractable. In this case, I would compute the matrix of the shortest paths in $G$ for all pairs of vertices in $S\cup \{START, END\}$. This can be solved efficiently (for example using Floyd Warshall). Your problem is reduced to a TSP on this matrix, which if $S$ is small, is a big win.
In the directed case, there is no advantage whatsoever in using an edge multiple times. Every walk using an edge multiple times can be re-routed to get a shorter one where this edge is used at most once :
If the edge taken multiples times is $uv$, then the walk goes to $u$, then through $uv$, do one or multiple loops then goes from $v$ to the end. We arrived at $u$, we can take the loops, alternating backward and forward, but without going through the edge $uv$. After that, depending on the parity of the number of loops, we can go through $uv$ to reach the vertex $v$. Then we go to the end.
In the undirected case, in the case where edges are counted only once, then you need to find a tree spanning all the vertices in $S\cup \{START, END\}$, where the total weight is minimal. With this tree, we are able to move on it while visiting all the needed vertices. If $S$ is the whole graph, this is known as the Minimum Spanning Tree problem (MST) and is much easier to solve than the TSP. There exist very efficient algorithms to solve it (Prim's, Kruskal's algorithm).
If $S$ is only a subset of the vertices, this is known as the Steiner tree problem in graphs and is NP-hard, so it is not tractable in general. There are good libraries to solve these problems, or you may need to browse the literature.