MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This problem is analogous to fast removal of the minimum number of edges in a weighted graph such that if the graph were to be drawn on paper with edge lengths linear in proportion to their weights, it could be drawn with only line segments (and perhaps dots for vertices or some other aesthetically pleasing touch)
I have come up with a simple and naive solution of using the previous research on fast apsp algorithms to my advantage (all pairs shortest paths). This runs in n^2 expected time with high probability as shown by B. Sudakov (in the most prominent and recent paper I could find while browsing google scholar) Once the edges that exist in the shortest paths are found, the others can be ignored.
But this problem is not that hard! I don't need to actually know the paths, I just need to know every edge that isn't or equivalently is present. Or is it? I'll take anything from a full blown algorithm to a proof detailing a better time bound. Note that the paper I'm referencing above delivers an expected time bound and worst-case is what I care most about right now.

share|cite|improve this question
I don't know exactly what you mean by $n^2$ expected time, what is the random model? But it seems you want to keep only the edges that are in themselves the shortest path between their two endpoints, because those are precisely the ones that occur in some shortest path, right? One idea is to find a spanning tree (for instance consisting of all shortest paths from one particular vertex) and start by discarding all edges that are longer than the diameter of that tree. Then look more carefully at what's left. – Johan Wästlund Jun 14 '11 at 11:36
So is this equivalent to computing all-pairs shortest path, then deleting all edges not contained in some shortest path? And I don't really understand the question... use the Floyd-Warshall algorithm if you want it to be simple, and use this Sudakov result you mention if you want it to be fast. I highly doubt that you would easily be able to construct the edge set faster than that, but I may be wrong. – Andrew D. King Jun 15 '11 at 11:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.