I've been trying for a while to develop an algorithm that counts the maximum number of disjoint vertex paths in a graph, but with an addition of "forced paths". Forced paths are here marked with bold lines. Paths that enter a vertex with a forced path is forced to enter it and flow along.
I've omitted the adaption for running max flow on vertex disjoint graphs. The graph is undirected and all edges have flow=1.
For example if we have the path 6->3 the forced path will force 6->3->2->1->9->10->7->8->5. When a vertex is visited with a forced edge that is not part of the path that forced edge is chosen.
The same goes for 6->5 which will result in 6->5->8->7->10->9->1->2->3
When I run maxFlow(6,4) (Ford Fulkeson implementation) it will result in the paths 6->5->4, 6->4 and 6->3->4 and therefor maxFlow(6,4)=3.
Can anybody point me in the right direction? Could I modify Ford Fulkeson, or maybe use another max flow algorithm to account for the forced paths?
Thanks in advance
Best Answer
One way you could solve this is by modifying the graph instead - each forced path can be replaced by a single edge that has the minimum capacity of all the edges in the original forced path (which is always 1 in this case). So any graph with forced paths reduces down to a graph without forced paths.