Maximum flow - via vertex - how?

Question

The problem:

Let G = (V, E) be a directed graph on n >= 3 vertices with m edges. The vertex set V includes three special vertices a, v, and b. Find a simple path from a to b via v if it exists. (A simple path is a path without repeated vertices.)

I believe this problem should/can be solved with a Max Flow algorithm but I am not sure how. It reminds me of a Max Flow algorithm with multiple sources where the edges have capacity 1. Anyone know how the problem can be reduced to Maximum flow algorithm?

If I set vertex b as sink I can not be sure it will include v. If I set v as sink how do I continue when v is reached?

Answer 1

The following should work:

• find all minimal paths from a to v, that do not contain vertex b. You can get those by (e.g.) a DFS on the graph without vertex b. We say that an a-v-path p is minimal, if no other a-v-path p' contains only vertices from p.

• for each minimal a-v-path, try to find a path from v to b ignoring vertices already belonging to the a-v-path. If you find such a thing, you're done.

Remark: Note that the number of paths might grow exponential, but as I pointed out in my comment, at least the generalized version of this problem seems to be reducible to the TSP, thus being probably very difficult.

Answer 2

This is equivalent to asking if a graph contains a subgraph homeomorphic to a directed path with three vertices (a pattern is a graph on some of the vertices from the input graph, and a subgraph is homeomorphic to a pattern if edges of the pattern can be mapped to simple, pairwise vertex disjoint paths of the subgraph). It has been proven by Fortune, Hopcroft, and Wyllie that directed subgraph homeomorphism is NP-hard for almost all fixed patterns, including this. So the problem is NP-hard, and cannot be solved by flow techniques unless P = NP.

The undirected version though can be reduced to maximum flow though by having a and b be the source and v the sink.