Max flow on undirected graph with constrained edges

Question

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

Answer 1

You can transform the graph by taking each pair of endpoints of a forced path.

For each forced path all the vertices, except ones on the forced path, adjacent to an endpoint will have an ingoing edge from that endpoint and an outgoing edge to the other endpoint, and no outgoing edges to the endpoint they are connected to in the original graph. The two endpoints will be connected by an undirected edge with the minimum capacity of an edge along the forced path and the remainder of the forced path will be deleted.

By now it might be clear that if you run Ford-Fulkerson on the transformed graph that it will find the max flow which obeys the constraints you laid out. If not you can ask me to clarify.

Answer 2

I respond to your comment in another answer because all this can’t fit in a comment, but it’s just a clarification.

To start I was left with the impression that you’re asking about an undirected graph where forced paths are bidirectional.

Even so, when the graph is directed, of course assuming that all forced paths don’t overlap and all edges along a forced path point in the same direction, my proposed solution can be slightly modified to work. The modification is that all ingoing edges to one endpoint of a forced path will be redirected towards the other endpoint of the path only if the path is in that direction.

Also a note when a flow has to start from a vertex u which is an endpoint of a path will start instead from the other endpoint of the path v if the forced path points from u to v.

First of all about the example you provided where 4->6 and 3->5 are the directed forced paths, there are 2 units of flow that can go from 4 to 5. One unit of flow goes along the path 4->3->5 and the other one along the path 4->6–>5. So under my proposed transformation the resulting graph will have the following directed edges: 6->5, 6->5 And when you run MF(4,5) the flow will start from 6 because 4->6 is a forced path and will find 2 units of flow from 6 to 5 along the 2 edges between them.

To give another example to make it more clear let’s use the graph in your question where the forced paths are bidirectional and the graph is undirected. Under the transformation the result will be a graph with the following directed edges: 4->3, 6->3, 4->5, 6->5, 3->6, 3->4, 5->6, 5->4, 4->6, 6->4

Even that example might not be clear as it is a special case where all the vertices that are connected to one of the endpoints of the forced path are connected to both endpoints of the path. But the idea is that edges that point to an endpoint of a forced path that will force you to go along it will be redirected as shortcuts to the other endpoint of the path. And edges that point away from an endpoint will be preserved. So that way if the endpoints of the path are u and v and the forced path is u<->v you can’t go to u and then to one of its neighbours unless you went along the forced path and the same for v. So in the transformed graph there are no edges that point to u except the ones that used to point to v, and there are no edges that point to v except the ones that used to point to u.

Answer 3

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.