<p>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.</p>

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

CC BY-SA 3.0
2012-08-30T05:28:57.193Z
I think we cannot reduce it directly to the HAMILTON-PATH problem since in this problem, a vertex can be visited multiple times?
derekhh
CC BY-SA 3.0
2012-08-30T07:28:49.927Z
Oops, you're right. So that part of my answer is incorrect. I'll have to think about this some more.
David Eppstein
CC BY-SA 3.0
2012-08-29T18:22:52.393Z
2012-08-30T00:52:55.380Z
2012-08-30T00:52:55.380Z
David Eppstein
<p>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. </p>

<p>We define the <strong>valid point of partition $p_i$</strong> 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 <strong>valid point of $p_i$</strong> is $z$. </p>

<p>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 <strong>valid points</strong> of their respective partitions.</p>

<p>Can we find a polynomial-time algorithm?</p>

<ds.algorithms><graph-algorithms>
Finding a path with certain properties in a directed graph
derekhh
# Finding a path with certain properties in a directed graph

(Asked by: username_0 on 2012-08-29)

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?

**Tags:** ds.algorithms, graph-algorithms


---

## 1 answers

### Answer by username_1 on 2012-08-29. Score: 5

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

> **Comments:**
> **username_0**: I think we cannot reduce it directly to the HAMILTON-PATH problem since in this problem, a vertex can be visited multiple times?  
> **username_1**: Oops, you're right. So that part of my answer is incorrect. I'll have to think about this some more.  

---

