How can I get maximum flow of minimum index?

Question

Denote edge with index i by E[i].

Let S be an array of a solution. If a maximum flow contains E[i], S[i] = 1. Otherwise, S[i] = 0.

I want to get a maximum flow whose solution is alphabetically minimum. I can get maximum flow with Ford-Fulkerson, but I don't know how can I get the solution that is alphabetically minimum.

Answer 1

Algorithm

One approach is to compute the maximum flow and then for each edge in turn try:

1. Remove the edge from the graph
2. Compute the maximum flow (for efficiency start from your previous solution)
3. If the maximum flow has decreased then replace the edge

At the end of this process the edges used will be the lowest in alphabetical order.

Example

For your example of 0010001, 1000000, 0001100 suppose we started with the solution 1000000.

We would first try removing edge 1, the new maximum flow would have the same value, (now using edges 00100001), so we permanently remove edge 1.

Edge 2 is not included so we can permanently remove it.

Edge 3 is included, so we try removing it and computing the new maximum flow. The new flow has the same value and uses edges 0001100 so we remove edge 3 permanently.

We now try removing edge 4. However, in this case the value of maximum flow decreases so we have to keep edge 4.

Similarly we will find we need to keep edge 5, but can remove edges 6 and 7.

Answer 2

You can formulate it as a min cost max flow problem, by assigning smaller costs to edges with smaller indices.