HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Simple paths with halt in between in directed graphs

Submitted by: @import:stackexchange-cs··
0
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?

  • 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.