patternMinor
Simple paths with halt in between in directed graphs
Viewed 0 times
simplewithpathsdirectedgraphsbetweenhalt
Problem
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?
-
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.
Solution
As Tsuyoshi Ito notes, the first problem can be solved using network flow. This was described in detail in cstheory.
Context
StackExchange Computer Science Q#1516, answer score: 3
Revisions (0)
No revisions yet.