Min cost max flow in bipartite run time

Question

I have a bipartite graph with $|E|=O(|V|^2)$, a super-source and a super-sink. I am looking for the min-cost max-flow (the max-flow of all possible max-flows that has the minimum cost).

For the sake of my question, denote $n=|E|$.

Are there algorithms that will run in $O(n^2)$, or even $O(n\log(n))$, or for that matter anything less than $O(n^3)$? In my case, $n$ is ~100,000, so $O(n^3)$ is impractical for me.

'Extra' questions (should these go under a separate question?):

1. Do any of these supper multi-graphs (I have 2 edges from my super-source node to each of the "blue" nodes in my bipartite graph, and 2 edges from each of the "red" nodes to my super-sink node)?
2. Are there efficient implementations of such algorithms (that run in less than $O(n^3)$, and support multi-graphs) in C++, C, or Python?
3. If the answer is 'no', what are popular approximation algorithms and their associated run times?

Answer 1

Assuming your edges have unit capacity, but non-unit costs, you can reduce this to a maximum-weight bipartite matching, that is, the assignment problem. For this, just make a copy of each vertex. The assignment problem can be solved in $O(n^{1.5})$ time.

Answer 2

I'm most familiar with the Cost-Scaling Algorithm by Goldberg. I'm pretty sure it behaves like $O( n^2 \log n \log U)$, where $\log U$ is (essentially) the number of bits in the representation of the edge costs.

This link provides a nice review.

Answer 3

You can solve this in $\mathcal{O}(n\log{}n)$

Edit: I've retracted this claim for now, until further notice.

Given amounts of supply and demand, and a cost matrix from supply to demand:

1. Sort the edges by cost
2. For each edge in order of cost:
   • Calculate the minimum of the remaining amount in the supply and demand nodes
   • Subtract from the supply and demand nodes
   • Assign it to the edge

The complexity is dominated by sorting the edges.

You can probably adapt this to almost any language, but javascript seems like the most commonly available vm for now, so here's an implementation:

const compare = (a, b) => a[0] - b[0];
const amount_to_node = amount => [amount];

/* Single commodity, maximum flow, minimum cost optimizer, [email protected] */
function optimize(supplies, demands, costs) {
  const supply_nodes = supplies.map(amount_to_node);
  const demand_nodes = demands.map(amount_to_node);

  const num_supplies = supplies.length;
  const num_demands = demands.length;
  const edges = [];

  for (let from = 0; from < num_supplies; from++) {
    const f = costs[from];
    const supply = supply_nodes[from];
    for (let to = 0; to < num_demands; to++) {
      const demand = demand_nodes[to];
      const cost = f[to];
      edges.push([
        cost,
        supply,
        demand,
        from,
        to,
      ]);
    }
  }

  edges.sort(compare); // Most expensive part of the function

  const num_edges = edges.length; // = num_supplies * num_demands;
  for (let e = 0; e < num_edges; e++) {
    const edge = edges[e];
    const supply = edge[1];
    const demand = edge[2];
    const amount = Math.min(supply[0], demand[0]);
    supply[0] -= amount;
    demand[0] -= amount;
    edge[5] = amount;
  }

  return edges;
}

const supplies = [12, 23];
const demands = [7, 17];
const costs = [[3, 6], [5, 7]];
console.log(optimize(supplies, demands, costs));
```