Einfache Pfade mit Zwischenstopp in gerichteten Graphen

Ich habe zwei Probleme im Zusammenhang mit Pfaden in einem gerichteten Graphen. Let mit der Quelle ein gerichteter Graph und das Ziel . Lassen in einen anderen Eckpunkt sein .$G=(V,E)$$s \in V$$t \in V$$v \in V \setminus \{s,t\}$$G$

1. Finden Sie einen einfachen gerichteten Pfad¹ von nach durch .$s$$t$$v$

2. Finden Sie einen einfachen gerichteten Pfad von nach , der durch zwei feste Kanten in .$s$$t$$G$

Ich weiß nicht, ob es für sie polynomielle Zeitalgorithmen gibt. Hat jemand Lösungen oder Referenzen für sie?

1. Bei einem einfachen gerichteten Pfad kann kein Scheitelpunkt mehr als einmal angezeigt werden.

Wie Tsuyoshi Ito bemerkt, kann das erste Problem mithilfe des Netzwerkflusses gelöst werden. Dies wurde in der Theorie ausführlich beschrieben .