Fdtxjr

Suppose you have a directed graph with vertices colored A, B, C, and D. One node is $s$, the start node, and another $t$, the terminal node. You want to determine two things: First, find a path from $s$ to $t$ which contain at least one vertex of colors A, B, and C, and minimize the number of vertices of color D. Paths need not be simple.

Second, for any given $k>0$ determine whether a path exists which visits $k$-many vertices of color A, and $k$-many of color B, and $k$-many of color C. Again paths need not be simple.

Solution to the first part:

For the first question, I used the following solution: If the color at $s$ is A then we look for paths that go to a vertex colored B and then C minimizing the number of vertices colored D. Then we look for paths that go C then B minimizing the vertices colored at D. Then take the minimum of these two results. As long as we can find the minimum path for some specific color ordering in linear time, then doing it twice will still take linear time.

So to do that, first give every edge of the graph which enters a D vertex weight 1 and all others weight 0. Next make three copies of the graph, so that you have G, G', and G''. In G reassign every edge coming from an A vertex to a B to map into the corresponding vertex of G'. Then do likewise mapping B to C edges into the corresponding vertex of G''.

On this new graph run Dijkstra's. Since edges are not negative and bounded by a small constant, the algorithm runs in linear time.

To reiterate, since we can do it in some particular order of colors, we can do it then on all permutations of colors and this only multiplies linear time by a constant, so the algorithm continues to run in constant time.

I think I got the first part right but am a little more hung up on the second. I've imagined trying to leverage the solution to the first part. Perhaps make $k$ copies of the graph, on each copy run the algorithm ... but that doesn't make sense, you couldn't just stitch together two such paths and be ensured that such a path exists in the original graph. I thought maybe I should make $3k$ copies of the graph but I'm not sure how I would bind them together.

Hints or advice would be welcome.

I don't think I understood your solution, but I can provide an easy one for the first.

Let's build a new graph $G'=(V', E')$ where $V' = v in V$

In other words, vertexes of $G'$ are pairs of an original vertex and bitmask of visited colors. For instance, $(3, 011)$ means vertex $3$ of $G$ and $A$ has not been visited, $B$ and $C$ has been visited).

$E'$ contains an edge $(v, mask1) rightarrow(u, mask2)$ iff the original graph has the edge $u rightarrow v$ and $mask2$ is $mask1$ with the bit corresponding to color of $u$ set to $1$.

Clearly, all you left to do is to find the shortest path (in terms of number of $D$'s) from $(s, 100)$ (if $s$ has color $A$, if $s$ has color $B$ it will be $010$ and so on) to $(t, 111)$.

Clearly, this new graph has $8|V|$ vertexes and $8|E|$ edges, so it linearly depends on the size of the original one.

On minimization the number of $D$'s: it is a good idea to set edge's weight $0$ or $1$ but it is kind of overkill to run Dijkstra on this graph. In order to find the shortest path on $0,1$ graph you just need to slightly modify breadth-first search. If you explore $1$-weighted edge you add the vertex in the end of the queue (as usual in breadth-first search), but to the beginning of queue if you explore $0$-weighted edge. This algorithm will give us the shortest path.

Unfortunately, this algorithm can not be generalized for an arbitrary $k$ with linear complexity as $G'$ will have $k^3|V|$ vertexes.