I have two problems related to paths in a directed graph. Let $G=(V,E)$ be a directed graph with source $s \in V$ and target $t \in V$. Let $v \in V \setminus \{s,t\}$ be another vertex in $G$.

  1. Find a simple directed path¹ from $s$ to $t$ through $v$.

  2. Find a simple directed path from $s$ to $t$ that goes through two fixed edges in $G$.

I do not know if there are polynomial time algorithms for them. Does anyone have solutions or references for them?

  1. A simple directed path does not allow any vertex to appear more than once.
  • 6
    $\begingroup$ For problem 1, see this post on cstheory.stackexchange.com. $\endgroup$ Apr 26, 2012 at 21:48

1 Answer 1


As Tsuyoshi Ito notes, the first problem can be solved using network flow. This was described in detail in cstheory.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.