1
$\begingroup$

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.

initial graph

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

initial graph

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

Improve this question
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks for the reply. I've had similar thoughts but, imagine we have several forced paths in the graph the result could differ based on what direction one choose for the different paths. For example if we add 4,6 as a forced path, and represent those paths as directed 5->3 and 6->4, then MF(4,5) would be 1. If we direct the forced paths in another way, for example 3->5 and 4->6 MF(4,5) is 3. $\endgroup$ – rasmushaglund Feb 11 '20 at 12:58
  • $\begingroup$ I think I misunderstood your answer. So with the given graph it would mean that we first remove the edges 5-6,5-4,3-4,3-6 and then add directed edges 5->4, 5->6, 3->4, 3->6 (endpoint to adjacent) and 4->3, 6->3, 4->5, 6->5 (from adjacent to other endpoint). Did I understand this correctly? Could you elaborate which edges would be changed/added in this given graph? $\endgroup$ – rasmushaglund Feb 14 '20 at 12:09
  • $\begingroup$ Should, additional to the above comment, an undirected edge be added between the endpoints? $\endgroup$ – rasmushaglund Feb 14 '20 at 13:04
  • $\begingroup$ The idea behind the transformation is that the new graph has the same reachability properties as the original one. However I forgot that in order to make it work for flow you have to add a dummy node which represents the forced path. Now instead of redirecting edges from one endpoint to the opposite one directly, redirect them to the dummy node, which connects to the opposite endpoint with an edge with the capacity of the forced path. I will add this modification to my original answer. $\endgroup$ – Nothing Feb 16 '20 at 13:44
  • $\begingroup$ Thanks again for the answer, I still don't understand. Could you provide the transformed version of the original (undirectetd) graph, maybe that would help me understand the algorihtm for transforming the graph. $\endgroup$ – rasmushaglund Feb 18 '20 at 10:52
0
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks for the answer. So in this special graph, let's take the simpler undirected graph as an example, MF(4,6) would transform to MF(5,3) or MF(3,5) and thus = 2? $\endgroup$ – rasmushaglund Feb 14 '20 at 12:36
  • $\begingroup$ You wrote "So under my proposed transformation the resulting graph will have the following directed edges: 6->5, 6->5", do you mean that there should be two edges 6->5? $\endgroup$ – rasmushaglund Feb 14 '20 at 13:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.