Cycle-cancelling algorithm

In algorithms, many problems have different variations. The maximum flow problem, that you are already familiar with, is no exception. One of them is the minimum cost maximum flow problem. Imagine that you need to choose an optimal route for distributing some goods. You have several routes that allow the transportation of the same amount of produce, which is also the maximal one possible. However, some of the options are not free, so, naturally, you want to minimize the expenses. This is exactly the moment when the minimum cost maximum flow problem arises. So, how can a maximum flow of minimum cost be found? Obviously, this task, just like any other, can be approached in many different ways. Let's discuss one of them, which is the cycle-cancelling algorithm.

Algorithm

First of all, let's remember some definitions, that are crucial for understanding the algorithm.

For starters, a flow network is a directed graph, which has a source and a sink, each edge of which has flow and capacity. Secondly, the flow of the edge is the amount of source that currently goes through it. For example, in a network, representing a pipe system, a flow is the amount of water that goes through the pipe. Additionally, in the algorithm, a residual graph is used. It is a graph, each edge of which has a residual capacity assigned to it. Don't forget, that the residual capacity is the difference between the capacity and the flow of an edge.

Last but not least is a negative cycle. It can be found in weighted graphs. Basically, it is a cycle, formed by the edges, the sum of weights assigned to which is negative. It may sound difficult but becomes much easier after looking at the example.

Imagine, that you have the following weighted graph:

The cycle $ABC$ is negative, as $4 + 5 + (-12)=-3<0$. One more important detail is that a negative cycle and a cycle with a negative edge are different things. For example, in the graph mentioned above, there is a cycle $CDE$, which is not negative, nevertheless, it has a negative edge in it.

Let's define some additional variables:

• $v$ and $u$ are the vertices of the network;

• $f(v, u)$ is the flow of the edge from $v$ to $u$;

• $p(v, u)$ is the cost of going through the edge from $v$ to $u$. In terms of our example about transporting the produce, it is the amount of money you pay for using a road;

• $c(v, u)$ is the capacity of the edge from $v$ to $u$;

Now, we are ready to move on to the algorithm. It is the following:

1. For each backward edge from $u$ to $v$ define capacity $c(u, v) = 0$, flow $f(u, v)=−f(v, u)$ (skew symmetry), cost $p(u, v)=−p(v, u)$.

2. The initial flow for each edge equals 0.

3. Find any maximum flow in a network.

4. Create a weighted graph $G$ in the following way: take the initial network and assign a cost to each edge, which residual capacity is positive. The important thing here is to remember about the backward edges. If the residual capacity of such an edge is positive, you need to assign a negative cost to the corresponding edge of the graph $G$ (just like it was stated in the step 1 of the algorithm). In this graph you don't need flows and capacities, only the newly assigned costs. Keep in mind that you need to know the cost of going through each edge before the start of the algorithm in order to be able to assign it during this step.

5. Look for a negative cycle in a graph $G$. If there is none, the algorithm is finished.

6. If there is a negative cycle, you eliminate it by pushing the maximum flow possible through the cycle. The maximum possible flow in this case equals the minimum residual capacity in the cycle. Pushing the flow here means increasing the flow of each edge of the cycle by a certain amount

7. Go back to step 5 and repeat the process, until no negative cycle is left.

Take a look at the pseudocode, if too many words bother you:

class CycleCancelling is 
  network = initNetwork()
  maximumFlowNetwork = maximumFlow(network) 

  method findMinCost() is 
    costsGraph = buildCostsGraph() 
    cycle = findNegativeCycle(costsGraph) 

      while (cycle is not Empty): 
        flowToPush = min(edge.residualCapacity | edge ∈ cycle) 

        for (edge ∈ cycle):
          edge.flow += flowToPush 
			
        costsGraph = buildCostsGraph() 
        cycle = findNegativeCycle(costsGraph) 

  method initNetwork() is ... // creates the structure, describing the initial flow network 

  method maximumFlow() is ... // finds any combination of paths, that in total give the maximum flow in the network
  
  method buildCostsGraph() is ... // creates a weighted graph, described in step 4 of the algorithm

Example

In order to understand the work of the algorithm better, let's perform it ourselves. The network is the following, with capacities assigned to each edge:

The costs of going through each edge — you can think of it as paying for using a road — are the following:

First of all, you need to find any combination of paths that in total give the maximum flow in a network. For example, it may look like this:

Now, let's perform the steps of the algorithm. In each picture, you will see a residual graph on the left and a graph with costs on the right. After performing steps 3 (finding the maximum flow) and 4 (creating a weighted graph with costs) of the algorithm, the graphs look like this:

Now, as step 5 states, we need to try to find a negative cycle. If you look at the graph on the right above, you can see it – a cycle $BDEC$. At step 6 we need to get rid of this cycle by pushing the maximum possible flow through it. Look at the residual graph on the left. The maximum flow equals the minimum residual capacity of the edges of this cycle, which is $min(6, 10, 12,5)=5$. After pushing the flow, the graphs look like this:

Now, let's go back to step 5 of the algorithm and find a negative cycle $CDE$. At step 6 you push the maximum flow possible through it. It equals $min(15,5,7)=5$. After pushing the flow, the graphs look like this:

Once again, we need to look for a negative cycle in the graph on the right. Hooray, finally there are none left!

The final flow of a network is the following:

Note that for the maximum flow, that we found in the beginning, the total cost was 171, but right now it is much less — 101. You can think of it as units of money, that we were able to save after redistributing the flow. It is quite pleasant, isn't it?

Correctness of the algorithm

After learning about the algorithm, you may have a question: does it actually find the optimal paths? Let's check it.

First of all, may there be negative cycles in a graph if the cost of the flow is minimal? Imagine, that there may be. Then you can push the flow through the cycle — the total flow in a network will remain the same, but the cost will decrease. It means, that the flow wasn't optimal in terms of cost from the beginning, therefore, if cost is minimal, there may be no negative cycles.

On the other hand, if there are no negative cycles, does it guarantee that the cost of the flow is the minimum one possible? Let $f$ be such a maximum flow, that there are no negative cycles in a graph of costs, and $f_1$ — a maximum flow of minimum cost. It is obvious, that $cost(f_1) \leq cost(f)$. First off, let's find the difference between the flow in $f_1$ and $f$ for each edge of the network. It can be decomposed into cycles, which means that $f_1 = f + cycles$. As we suppose, that there are no cycles of negative cost, then $cost(f_1) \geq cost(f)$. Previously we've already discovered that $cost(f_1) \leq cost(f)$, which means that $cost(f_1) = cost(f)$. Therefore, $f$ is indeed the maximum flow of minimum cost.

Complexity

By now you are probably eager to implement the algorithm and try it out in some real-life problems. However, before doing that, you need to understand its time complexity.

Let $C$ be the maximum capacity of the edges of a network, $P$ — the maximum cost of the edges of a network, and $E$ — the number of edges. Then the total cost of the flow in the beginning of the work of the algorithm is no bigger than $CPE$. In a worst-case scenario, on each iteration, you decrease the total cost by 1 unit after finding a negative cycle. As the cost cannot be negative, this leads us to at most $CPE$ iterations. As for finding a negative cycle, you can use Bellman-Ford algorithm, the complexity of which is $O(VE)$, where $V$ is the number of vertices in a network. Therefore, the total complexity of the cycle-cancelling algorithm is $O(E^2VCP)$.

Conclusion

To sum up, let's go through the main points of the topic:

• The cycle-cancelling algorithm is used for finding the maximum flow of minimum cost.

• A negative cycle is a cycle, formed by the edges, the sum of weights assigned to which is negative.

• On each step the algorithm creates a graph of costs for the edges with positive residual capacities, and checks if it has any negative cycles. If it does, the maximum possible flow is pushed through the cycle in order to get rid of the negative one.

• The complexity of the cycle-cancelling algorithm is $O(E^2VCP)$, where $E$ and $V$ are the number of the edges and the vertices in a network respectively, $C$ — the maximum capacity of the edges and $P$ — the maximum cost of going through the edge.