# Simple paths with halt in between in directed graphs

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.

## migrated from cstheory.stackexchange.comApr 26 '12 at 19:54

This question came from our site for theoretical computer scientists and researchers in related fields.

• For problem 1, see this post on cstheory.stackexchange.com. – Tsuyoshi Ito Apr 26 '12 at 21:48