Guarantee about edge not being part of a minimum spanning tree

Question

I was solving exercises from the Algorithm Design book by Kleinberg and Tardos and came across this not-so-easy (to me) problem on finding a guarantee that an edge will never belong to the MST of a graph. The question goes like this:

You are given a graph G = (V, E) with cost c_e on each edge e. Given error parameters epsilon and k (both > 0), you would like to ascertain whether the following property (*) holds for a particular edge e' = (u, v) in polynomial time.

(*) Even if the cost of each edge were to be changed by at most epsilon (either increased or decreased), and the costs of k edges other than e' were further changed to some arbitrary different values, the edge e' would still not belong to any MST of G.

I know the cut property for MST's but cannot see how that can be applied to this problem. Thanks for your ideas in advance!

Answer 1

Eventually reached an answer thanks to j_random_hacker's comments.

The answer basically uses the cycle properties of an MST - if an edge is the most expensive edge in a cycle in G, it cannot belong to any MST of G.

The provision for changing the costs of k edges to arbitrary values implies that we must show that e' is the most expensive edge in at least k+1 cycles which are all edge-disjoint except for e' itself. This way, even if the arbitrary change of k edges causes e' to not be the most expensive in k cycles, it will still be the most expensive in the last cycle.

Given a graph G, edge e' and parameters k and epsilon (both > 0):

1. Temporarily delete all edges in G more expensive than e' (this ensures that e' is the most expensive in whichever cycles we find)

2. Now, set one end of e' to be a source (s) and the other end to be a sink (t). Set capacities of all edges to be 1. Flow integrality ensures that since all capacities are integers, we will get an integral flow.

3. See if you get a flow of value at least k+1. If yes, flow decomposition will give you as many edge-disjoint paths from s to t as the value of flow. Convert all these paths to cycles by adding e' to them - this way you have k+1 (or more) cycles in which e' is the most expensive edge and which are all edge-disjoint except for e'. You can now safely say that property (*) holds for e'.

I have a way to deal with epsilon if it is an integer. In step 1, delete all edges that are more expensive than cost(e) + 2*epsilon.