Geek Answers Handbook

The maximum flow - through the top - how?

Problem:

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

I believe that this problem should / can be solved using the Max Flow algorithm, but I'm not sure how to do it. This reminds me of the Max Flow algorithm with several sources, where the edges have a capacity of 1. Does anyone know how the problem can be reduced to the maximum flow algorithm?

If I set vertex b as a receiver, I cannot be sure that it will include v. If I set v as a receiver, how can I continue when v is reached?

+8
algorithm graph
source share
2 answers

The following should work:

  • find all minimal paths from a to v that do not contain vertex b . You can get them using (for example) DFS on a chart without vertex b . We say that av -path p is minimal if no other av -path p' contains only vertices from p .

  • for each minimum av -path, try finding a path from v to b , ignoring the vertices that already belong to av -path. If you find such a thing, you're done.

Note. Note that the number of paths can increase exponentially, but, as I noted in my comment, at least the generalized version of this problem seems to boil down to TSP, so it is probably very difficult.

+2
source share

This is equivalent to a query if the graph contains a subgraph homeomorphic to the directed path with three vertices (the pattern is a graph at some vertices from the input graph, and the subgraph is homeomorphic to the pattern if the edges of the pattern can be mapped onto simple, pairwise vertex disjoint subgraph paths). This is confirmed by Fortune, Hopcroft and Wyllie that directed submontane homeomorphism is NP-hard for almost all fixed patterns, including this. Thus, the problem is NP-rigid and cannot be solved by flow methods if P = NP.

The non-oriented version, however, can be reduced to maximum flow, although if a and b are the source and v is the sink.

+1
source share

More articles:


All Articles