  We study the maximum-flow/minimum-cut problem on scale-free networks, i.e.,
graphs whose degree distribution follows a power-law. We propose a simple
algorithm that capitalizes on the fact that often only a small fraction of such
a network is relevant for the flow. At its core, our algorithm augments
Dinitz's algorithm with a balanced bidirectional search. Our experiments on a
scale-free random network model indicate sublinear run time. On scale-free
real-world networks, we outperform the commonly used highest-label Push-Relabel
implementation by up to two orders of magnitude. Compared to Dinitz's original
algorithm, our modifications reduce the search space, e.g., by a factor of 275
on an autonomous systems graph.
  Beyond these good run times, our algorithm has an additional advantage
compared to Push-Relabel. The latter computes a preflow, which makes the
extraction of a minimum cut potentially more difficult. This is relevant, for
example, for the computation of Gomory-Hu trees. On a social network with 70000
nodes, our algorithm computes the Gomory-Hu tree in 3 seconds compared to 12
minutes when using Push-Relabel.
