If you want to make money online : Register now

# [Solved]: Ford-Fulkerson algorithm with asymmetric adjacency matrix

, ,
Problem Detail:

Suppose that I have a bipartite graph \$G=(A \cup B, E)\$ and \$A = \{1, 2, \dots, n\}\$, \$B = \{1, 2, \dots, m\}\$. After a virtual sink \$s = 0\$ and a source \$t = n+1\$ is included into the graph, I want to implement Ford-Fulkersen max flow algorithm.

To the algorithm, we need a symmetric adjacency matrix, therefore \$O((n + m)^2)\$ space.

However, in a bipartite graph, it is enough to use an adjacency matrix with \$O(nm)\$ space. But I could not figure out how to modify the algorithm so that it works with an asymmetric adjacency matrix.

Is there any way that Ford-Fulkersen max flow algorithm works in above scenario?

#### Answered By : Yuval Filmus

The algorithm doesn't need a symmetric adjacency matrix. It needs to keep track of a flow and a residual network. Both are supported on the edges of \$G\$ and their inverses. You can store them in roughly the same way you store your graph \$G\$, using the same amount of space (up to a multiplicative constant).