# Decreasing a digraph's edge-weights while keeping net weights of edges at each vertex constant

Given a directed weighted graph, is there an algorithm that does the following:

• Removes as many edges possible.
• Reduces as many weights as possible.

Given the constraint that the net weight of all edges connected to the vertex (sum of incoming edge weights minus sum of outgoing edge weights) remains the same and every edge weight remains non-negative.

Examples:

The graph "A -10-> B -10-> C" could be reduced to "A-10->C" since vertex B has net zero weights (10 incoming and 10 outgoing)

The graph "A -10-> B -3-> A" could be reduced to "A-7->B".

Thanks.

• I added the condition that every edge weight must remain non-negative since the problem isn't well-formed without it. – David Richerby May 19 '15 at 22:05
• 1. When you say "the vertex", do you mean "each vertex"? (If not, what vertex are you talking about? There is no distinguished vertex provided as input.) 2. This is a multi-objective optimization problem: maximize number of edges removed, maximize number of weights reduced. How do you want these two objectives to be traded off? Optimization problems are only well-defined if there is a single objective to optimize; otherwise there might be no unique optimal solution. – D.W. May 19 '15 at 22:49
• @D.W. 1. I mean all vertices in the graph. 2. Primarily I'm most interested in the first objective, removing as many edges as possible, but I'ld love to know if there is any algorithm that achieves any of the objectives, or both with some parameter being used for weighing the different objectives. – Martin May 20 '15 at 15:12