7
$\begingroup$

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.
$\endgroup$
  • 6
    $\begingroup$ For problem 1, see this post on cstheory.stackexchange.com. $\endgroup$ – Tsuyoshi Ito Apr 26 '12 at 21:48
3
$\begingroup$

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

$\endgroup$

Your Answer

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