1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ I added the condition that every edge weight must remain non-negative since the problem isn't well-formed without it. $\endgroup$ – David Richerby May 19 '15 at 22:05
  • $\begingroup$ 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. $\endgroup$ – D.W.♦ May 19 '15 at 22:49
  • $\begingroup$ @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. $\endgroup$ – Martin May 20 '15 at 15:12
1
$\begingroup$

The second objective is just a simple circulation problem http://en.wikipedia.org/wiki/Circulation_problem as the maximum circulation gives the highest reduction in weight. This problem is basically equivalent to max flow for which efficient algorithms are well known.

Not so sure about trading of the first and second objective. You might achieve something like this by modelling it as a min concave-cost network flow problem with capacities, e.g. by some cost function that is nearly flat at arc saturation, such that it favours saturating arcs once they are close, but this is NP-hard: http://link.springer.com/article/10.1007/BF02283688

Maybe there is a more efficient way depending on what you are trying to achieve, but the constraint that net edge weights remain the same indicate that you are looking for some network flow type algorithm.

Do you have an application for this in mind?

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks Thomas. Although after having looked at the circulation problem, I would say it doesn't really represent what I'm after. My understanding of the circulation problem is that the algorithm finds a flow given some constraints. In my case, the flow is given but should be optimized according some goals and constraints. And in the circulation problem, all nodes, bar the source and sink, have a net flow (outgoing - incoming) of 0. That is not the case in my situation. $\endgroup$ – Martin May 21 '15 at 6:53
  • $\begingroup$ I came to think of this problem during a trip with friends where a lot of common expenses were paid by one person (could be different each time). So at the end of the trip, you would have payment obligations between lots of people. So I started thinking about if there was an algorithm that could in effect net out as many of the obligations as possible for an arbitrary set of payment obligations between a group of people. $\endgroup$ – Martin May 21 '15 at 6:56

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.