Caminhos simples com parada intermediária em gráficos direcionados

Eu tenho dois problemas relacionados a caminhos em um gráfico direcionado. Deixe que ser um grafo orientado com fonte e alvo . Deixe ser outro vértice em .$G=(V,E)$$s \in V$$t \in V$$v \in V \setminus \{s,t\}$$G$

1. Encontre um caminho direcionado simples¹ de até até .$s$$t$$v$

2. Encontrar um caminho simples dirigido a partir de a que passa por duas arestas fixas em .$s$$t$$G$

Não sei se existem algoritmos de tempo polinomial para eles. Alguém tem soluções ou referências para eles?

1. Um caminho direcionado simples não permite que nenhum vértice apareça mais de uma vez.

Como Tsuyoshi Ito observa, o primeiro problema pode ser resolvido usando o fluxo de rede. Isso foi descrito em detalhes na história .