Puzzle: Minimum Spanning Tree with edge weight linear function of time

You're given a directed graph G with N vertices and M edges. Each edge weight *w* is a linear function of time, i.e. *at + b* for some given values of *a* and *b*. You're also given a time interval [t1, t2].

Find the minimum spanning tree in the time interval [t1, t2], i.e. the time instant *t* and the edges that make up the minimum spanning tree.

**Solution below**:

Hint 1:

First observation is that in a standard MST algorithm like Kruskal's, its correctness only depends on the *order* of the edges sorted by weight. If the weights are different but the order of the edges is the same, then you still have the same solution (in terms of the list of edges that are part of the MST).

Hint 2:

Now imagine a line sweep from left to right (time -ve infinity to +ve infinity). Two straight lines (linear functions) intersect at most once. Since we have M lines, and hence M choose 2 = M * (M-1) / 2 intersection points, that is the maximum possible number of times the order of the edges change.

Hint 3:

Moreover, notice that the solution will lie at one of the intersection points (or at the ends of the time intervals). Since the functions above are linear, the cost of the MST as a function of time is a piecewise linear function.

Hint 4:

Combining the above two observations, one possible solution is to solve the MST problem O(M^2) times. Since each run of Kruskal's takes O(M log M) time, we could get a total run time of O(M^3 log M).

**Extended puzzles**:

Extension 1 (better complexity solution possible?):

I think its possible to improve on the above solution runtime. Notice that you are sorting the list of M edges O(M^2) times. But each successive sort only needs us to swap 2 edges. So we in fact need O(1) time for each sort. I don't know if we can take advantage of this property in our disjoint set data structure.

Extension 2 (higher degree polynomials)

If the edge weights are higher degree polynomials (degree d), then the number of intersection points increases by a factor of d. Moreover, for each time interval between two intersection points, the total cost of the MST will also be a polynomial of degree d. Now, we'll have to additionally figure out the points at which this polynomial obtains the minimum values (we can't assume that the minimum value will be at the ends of the interval). Finding the zeros of a polynomial of degree d is not trivial, but has many known strategies. Read more here: Root-finding algorithm.

Hope you enjoyed the puzzle!

Read more…(453 words)

About the author:

Keshav Dhandhania

Loading…

Join the discussion. Add a reply…

Post

About the author

Keshav Dhandhania

Ready to join our community?

Sign up below to automatically get notified of new lists, get **reminders** to finish ones you subscribe to, and **bookmark** articles to read later.

Continue with Facebook

— OR —

Your Full Name

Email address

I have an account. Log in instead

By signing up, you agree to our Terms and our Privacy Policy.