# Best way for two players to visit a set of graph vertices in a given order

I am struggling with the following dynamic programming problem:

Given a complete $N$ vertex digraph and a list of vertices $List$, find a way for two players who start at vertices 1 and 2 respectively to visit each vertex from $List$ (order matters, i.e. $List_{i + 1}$ should be the vertex visited after $List_i$). Some vertices may appear in $List$ more than once (multiset). It is sufficient for a vertex to be visited by only one of players (i.e. one of them can visit all vertices while the other would remain at his starting position) If one player makes a move, the other stands still (can't make moves in parallel). If the current vertex to be visited is $List_i$, players must move to it directly, i.e. take either $(List_{i - 1}, List_i)$ edge (since the previous move guarantees one of player is in $List_{i - 1}$) or $(List_j, List_i)$, for some $j < i$ ($List_j$ is the position other player stopped at during some previous move). This means the path with $L$ vertices in it consists of exactly $L$ edges. The weight/cost of the path should be minimal. Weight of edge $(i, i)$ is always $0$, all weights are non-negative integers, no multi-edges or loops are allowed. Output the cost of such a path.

This is actually a problem from a Russian online judge. The original problem has three players (starting at $1, 2, 3$) in it and also asks to output what player did visit $List_i$, but I reduced the problem for the case of two players which should just make things easier for perception. I think according to the rules I should provide the link for the source problem even if this is a Russian language only website, so here it is http://informatics.mccme.ru/moodle/mod/statements/view.php?chapterid=3379 . If someone really needs it, the stated constraints (that shouldn't matter since we are talking about a simplified version of a problem) for the original problem are $(3 \leq N \leq 200)$ and the number of vertices to be visited is at most $1000$ (I swapped denoting letters), no memory/time limits are given.

The problem has a 2D dynamic programming tag.

My thoughts would be to denote $dp_{i, j}$ as a shortest path that visits vertices from $List_i$ to $List_j$, i.e. $(List_i, List_{i + 1}, ...,List_{j - 1}, List_j)$. The answer is would be stored in $dp_{1, L}$, provided that indexing goes from $1$ and $L$ stands for the length of the $List$. The problem is that I don't have a clear idea how to compute this dp-table. I thought of doing someting like $dp_{i, j} = \min_{k \in i..j}\{ dp_{i,k - 1} + cost(k - 1, List_k) + cost(List_k, k + 1) + dp_{k+1,j}\}$. Naturally, I'd at first compute all paths of length 2, then 3 and so on. The thing is, I don't understand how to deal with the main 'problem' of this problem, determining when the move is made by player 1 or 2. I thought there would probably have to be different costs of paths for different players, but they actually use the same graph, so all that matters is the position player $x$ ended up at. Filling the DP-table would actually have to consider two cases, the one described above which is guaranteed to exist as in path $dp_{i,k - 1}$ we know that one of players ended up in vertex $k - 1$. The case where the other player goes from 'some previous' vertex should be taken into consideration as well, $\min\{ dp_{i,k - 1} + cost(j, List_k) + cost(List_k, k + 1) + dp_{k+1,j}\}$ , where $j$ stands for 'some previous' vertex. While writing this, I also realized that I'd probably need a little hint how to remember the player that visited vertex $List_i$ which is needed for the original problem.

Could you provide me some help please?

• Try thinking of it this way - one table entry should encode all the information about the current state of the game. This includes both how many vertices from $List$ have been visited and where the players ended up afterwards. With this information you can fill the table by considering all subsequent moves of players. Oct 14, 2017 at 17:34

Here is the naive dynamic programming algorithm, which can probably be improved upon: For every $1 \leq i, j \leq |List|$, compute the minimal weight of a path in which Player 1 is at $List_i$, Player 2 is at $List_j$, and the players have covered all vertices up to $List_{\max(i,j)}$. This should run in $O(|List|^3)$.