2
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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))$.

$\endgroup$
  • 2
    $\begingroup$ I think we cannot reduce it directly to the HAMILTON-PATH problem since in this problem, a vertex can be visited multiple times? $\endgroup$ – derekhh Aug 30 '12 at 5:28
  • $\begingroup$ Oops, you're right. So that part of my answer is incorrect. I'll have to think about this some more. $\endgroup$ – David Eppstein Aug 30 '12 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.