5
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ NetworkX is a popular graph/network library for Python that contains an implementation of MinCostMaxFlow. It should support MultiDiGraphs as well. However with $n \approx 100,000$ it may still take a good bit of time and memory. $\endgroup$ – Nicholas Mancuso Oct 23 '12 at 15:37
  • $\begingroup$ There's lots of work on the network flow problem. What research have you done? Have you done a literature review of the known algorithms? Have you tried implementing any of them? $\endgroup$ – D.W. Mar 18 '14 at 22:14
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What algorithm would one use to solve this in $O(n^{1.5})$? $\endgroup$ – Niklas B. Mar 18 '14 at 22:08
  • $\begingroup$ The Hungarian algorithm solves the problem in O(k^3) for a kxk matrix. Here, we have k = |V| and n := |E| = O(k^2). I guess this could be a bit confusing since in this question n means something different than normally in graph problems. $\endgroup$ – Falk Hüffner Mar 19 '14 at 4:09
  • $\begingroup$ Oh I see. I thought OP was saying $n = |V| = |E|$ or something :) Pardon my lack of reading comprehension $\endgroup$ – Niklas B. Mar 19 '14 at 4:20
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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, msand@seaber.io */
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));
```
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you explain why your algorithm works and analyze its running time? $\endgroup$ – Yuval Filmus May 20 '19 at 12:44
  • $\begingroup$ Actually, I've found some problem instances where this algorithm fails. Currently looking to see if I can find a way to resolve it while preserving the time complexity to be bounded by the fastest comparison sort i.e. O(|E[ log |E|) in the number of edges. I've found some variations to solve the problematic cases, but I keep finding other problematic ones for now. $\endgroup$ – msand May 27 '19 at 22:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.