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$.
Find a simple directed path¹ from $s$ to $t$ through $v$.
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?
- A simple directed path does not allow any vertex to appear more than once.