Time-varying edge cost Minimum Spaning Tree

I am having a hard time wrapping my head around the time-varying edge cost of this question :

Suppose we have a connected graph $$G = (V, E)$$. Each edge e now has a time-varying edge cost given by a function $$f_e$$. Thus, at time t, it has cost $$f_e(t)$$. We’ll assume that all these functions are positive over their entire range. Observe that the set of edges constituting the minimum spanning tree of $$G$$ may change over time. Also, of course, the cost of the minimum spanning tree of $$G$$ becomes a function of the time $$t$$; we’ll denote this function $$c_G(t)$$. A natural problem then becomes: find a value of $$t$$ at which $$c_G(t)$$ is minimized. Suppose each function $$f_e$$ is a polynomial of degree 2: $$f_e(t) = a_et^2 + b_et + c_e$$ , where $$a_e$$ is positive for each edge $$e$$. Give an algorithm that takes the graph $$G$$ and the values $$\{(a_e , b_e , c_e) : e ∈ E\}$$ and returns a value of the time $$t$$ at which the minimum spanning tree has minimum cost. Your algorithm should run in time polynomial in the number of nodes and edges of the graph $$G$$. You may assume that arithmetic operations on the numbers $$\{(a_e , b_e , c_e)\}$$ can be done in constant time per operation.

My first idea was, because $$a_e$$ is positive, to find out the maximum value of $$t$$ that minimizes the cost of an edge $$e$$ (in other words looping through every edge once and find their minima). Intuitively, the maximum of these minima could be an upper-bound for the value that minimizes $$c_G(t)$$. Then I could run a MST algorithm for every time step from 0 to t and return the t that answers the question. However, this looks like a very brute-forcey method and thus not time-efficient at all.

Any help would be greatly appreciated!

Note that this question was part of the Greedy Algorithm chapter.

• We require you to attribute the original source of all copied material: cs.stackexchange.com/help/referencing. Saying it came from "the Greedy Algorithm chapter" is not adequate. Please see the link for our expectations about providing a proper reference: e.g., we'd expect you to provide a full reference, including the textbook name and authors.
– D.W.
Sep 27, 2021 at 4:11

1 Answer

Consider the edges sorted by $$f_e(t)$$ for some $$t$$.

Two quadratic polynomials can intersect at most two times. When the cost function of two edges $$e_1$$ and $$e_2$$ cross at time $$t$$, it means that

• $$f_{e_1}(t-\epsilon) < f_{e_2}(t-\epsilon)$$ and
• $$f_{e_1}(t+\epsilon) > f_{e_2}(t+\epsilon)$$.

Since there are $$m$$ edges and each pair of edges crosses at most twice, we have at most $$2 \cdot {m \choose 2} \leq m^2$$ many crossings, and therefore at most $$m^2$$ many times two edges can swap order in the sorted list.

Now you try all possible time intervals that don't contain crossings, $$(t_a, t_b)$$ and pick the $$n-1$$ cheapest edges. What remains is to minimize a sum over $$n-1$$ quadratic functions which is indeed a quadratic function.