# How to balance the inflow and outflow of each vertex in a bipartite graph?

I have a situation where in a group of people, every person is trading with multiple people and giving them some money. It can be visualised as a directed bipartite graph with L and R as the total set of people. A directed edge from l to r means l gave r some money with weight w which is the weight of the edge. Now I'm an auditing firm and want to make sure that the total amount given out by a person should be as close as possible to the amount received by him. I can limit each such transaction (implying I can reduce the weight of any edge in the graph). What is the best way to solve this approximately with the minimum restrictions required (in terms of actual amount)?

Ex. if

a -> 10 -> b
b -> 10 -> c
c -> 5  -> a


can be limited to

a -> 5 -> b
b -> 5 -> c
c -> 5 -> a


by reducing 10 units of transactions

## 1 Answer

You can write a linear program. For each edge you have a restriction variable. You want to minimize the sum of the restriction variables. For constraints you want to have the sums of the differences between outgoing edges and the incoming edges (minus their restriction variables) to be smaller than a threshold that you choose.