# Minimum cost max flow network problem with an alternative flow cost

Is there a standard name or a reference for the network flow problem that looks very similar to the minimum cost maximum flow problem, only the flow cost that I wish to minimize isn't sum of edge.flow * edge.weight over edges, but rather sum of [edge.flow > 0] * edge.weight over edges, where [edge.flow > 0] equals one if the flow is greater than zero, and zero otherwise? Is it intractable, as I suspect?

I'll tell you about the original problem that I believe reduces to this problem. A bunch of friends have a dinner, and agree to split the bill evenly. But not everyone has enough money to cover their share at that moment, so some pay more than their share, some less, with the intent to settle later. Later on, they want to settle with a minimum number of transactions, where one transaction is money changing hands between a pair of friends.

This clearly maps to a bipartite network with edges of unlimited capacity from all the ones who underpaid going to all of those who overpaid, and edges of capacity equal to the amount underpaid going from source to the underpaid nodes, and edges of capacity equal to the amount overpaid going from overpaid nodes to the sink. To minimize the number of transactions we need to minimize the number of nonzero flow edges between the under- and overpaid.

• It looks like the descriptions are contradicting to each other. Can you add a simple non-trivial example in the question? – Apass.Jack Jul 4 at 3:46
• @Apass.Jack sorry, can you be more specific as to what exactly contradicts what? – Mio Jul 4 at 14:54
• The "minimum number of transactions" is not "sum of [edge.flow > 0] * edge.weight over edges". – Apass.Jack Jul 4 at 15:11
• @Apass.Jack you're right, one is more general than the other. I believe when we set all edge weights to be equal we get the dinner problem that I described. – Mio Jul 4 at 15:18
• Anyway, you may want to check this question and answer. – Apass.Jack Jul 4 at 15:24

The idea is to solve a standard linear-cost flow problem in which edge capacities are unchanged, but the cost of one unit of flow along edge $$e$$ is defined to be the edge weight divided by the edge capacity. This will give a solution that may weigh up to $$F$$ times the weight of the optimal solution, where $$F$$ is the flow value; but it will not weigh more than that.