Finding a path with certain properties in a directed graph

Question

Define a directed graph $G(V,E)$. We divide its vertex set $V$ into $t$ partitions: $p_1, p_2, \ldots, p_t$. Suppose we have a path $v_1 \to v_2 \to v_3 \to \ldots \to v_n$ where the same vertex can be visited multiple times.

We define the valid point of partition $p_i$ as the last point $\in p_i$ appearing in the abovementioned path. For example, if the path goes through $y, x, z$ and $y, x, z \in p_i$ holds, the valid point of $p_i$ is $z$.

Given $k$ vertices as input (we guarantee that these $k$ vertices belong to different partitions), if there exists an $s-t$ path, such that all these $k$ vertices are all valid points of their respective partitions.

Can we find a polynomial-time algorithm?

Answer 1

If all partitions contain only a single vertex and you're given all of them as your initial set of $k$ vertices then the path you seek must be a Hamiltonian path. So it's NP-complete.

However, it's fixed-parameter tractable when parametrized by $t$ — it can be turned into a reachability problem on a larger graph where each vertex is a pair $(S,v)$ of a set $S$ of the partition sets whose valid point has already been passed and a vertex $v$ of the original graph. So the time is $O(\binom{t}{\le k}(m+n))=O(2^t(m+n))$.