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 worstcase is what I care most about right now.
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.


