MST with degree constraints on some node

Question

While preparing for an algorithms exam I came across the following problem in a practice test:

Let $G = (V,E)$ be a connected, undirected graph with weighted edges (all weights are rational numbers but not necessarily all unique) and let $v$ be some node in $G$.

Design an algorithm that finds a minimum spanning tree of $G$ where $\deg(v)=2$ if one exists or indicates if there is no such tree.

Full credit will be given for solutions with the same time complexity as Prim's algorithm ($O(|E| + |V|\log |V|)$). Partial credit will be given for solutions whose time complexity is $|V|\cdot$Prim, and minimal credit will be given for solutions with greater time complexity.

The first step in any solution must be to use Prim or Kruskal's algorithm to find the target weight for such an MST. From there, though, I've tried a number of different methods of approaching this problem but all the successful ones require halting an existing MST algorithm before it's done, i.e. prioritizing all $v$'s edges, running Kruskal until $v$''s degree is two, then deprioritizing them and continuing the algorithm, etc.

The problem is that my professor flat-out refuses to accept answers that involve stopping an algorithm in the middle, insisting that this would require one to re-prove the correctness of the entire algorithm.

Does anyone have a solution? The problem has been eating at me for a few weeks now and I haven't been able to find an answer on the internet anywhere. The professor said she won't tell us the answer and I suspect she intends to put this question on this or future exams.

Thanks very much in advance for your time.

Answer 1

Here's an algorithm that just reduces to MST; no need to modify Prim's or some other algorithm. The idea is simple: remove $v$, compute the MSTs of the resulting components of the graph, and then stitch them together with $v$. The interesting case is when removing $v$ doesn't disconnect the graph.

I'll assume the input graph $G$ is connected, although it would not be difficult to generalize this idea to computing a minimum spanning forest. Also, obviously the degree of $v$ needs to be at least 2.

Algorithm

Start by removing $v$ and all incident edges; call this $G'$. Now compute the number of connected components in $G'$. This can be done with DFS or something similar.

More than 2 components: If $G'$ has more than 2 connected components, no solution is possible.

Exactly 2 components: If $G'$ has exactly two connected components, then we can construct a solution by using $v$ as the "bridge" between the two components: just connect the MSTs of the components with the cheapest edges through $v$.

Exactly 1 component: If $G'$ has exactly one component, we can compute $T' = \text{MST}(G')$, and then we just need to stitch $v$ into $T'$ using two edges.

1. Find the cheapest edge incident on $v$ and add this to $T'$. Call this $T''$. Now we have a spanning tree, but not necessarily minimum.
2. Iterate over all other edges incident on $v$. For each of these, we will try to construct a MST where $d(v) = 2$. If we don't find one, then no solution is possible.
   • Consider some incident edge $(u,v)$ which is not the lightest edge on $v$.
   • Observe that if we added this edge to $T''$, it would create a cycle.
   • If $(u,v)$ is the heaviest edge on this cycle, then skip this edge, because no solution is possible using $(u,v)$.
   • Otherwise, we can take out the heaviest cycle edge and add $(u,v)$ instead. Now we have a spanning tree where $d(v) = 2$. If this spanning tree is minimum, we're done. (We can determine if a spanning tree is minimum just by computing any $\text{MST}(G)$ and comparing weights. This "reference" MST only needs to be computed once.)

It's not immediately obvious that this is within cost bounds, because for each of $O(|V|)$ edges incident on $v$, we have to compute the heaviest edge in the tree on the path between $v$ and some other vertex $u$. However, these "path queries" are well studied in the literature, and can be computed in $O(\log|V|)$ by preprocessing $T''$ into a balanced lookup structure. Some examples include binary lifting, Miller-Reif rake/compress tree contraction, and Sleator-Tarjan link/cut trees. The link/cut trees are actually far more general: they handle dynamic trees too! But here we only need to preprocess a static tree, i.e. $T''$.

---

Edit: My original idea was to do the following, which doesn't work (thank you @VladislavBezhentsev for pointing this out in the comments!). It doesn't work because, while we know that the cheaper of $e_1$ and $e_2$ is certainly in the MST (by the cut property), it's not necessarily true that the heavier of the two edges is!

(Incorrect idea): Find the two cheapest edges $e_1$ and $e_2$ that are incident on $v$. Add $e_1$ and $e_2$ to $T'$: this creates a cycle. If the largest edge on this cycle is either $e_1$ or $e_2$, no solution is possible. Otherwise, remove the largest edge on the cycle.

Answer 2

This is not a complete solution, but just an idea.

1Choose 2 edges out of $v$ (maybe using a greedy heuristic)

2 Find the MST for G - { $v$, $u$} (where $u$ is the one of the 2 selected neighbors). Then add $v$ with its 2 edges (this way v & the other node are added).

3 Repeat to reach the optimal answer.

Answer 3

Here is an algorithm that runs in about triple Prim's time, which is still $O(|E| + |V|\log |V|)$. The basic idea is to adapt OP's idea so as to determine or approximate the answer from the case of least degree and the case of most degree.

---

Denote the given weight function by $w_\text{orig}$. Let $\epsilon$ be the smallest positive difference between two different edge weight. Let the edges that are incident to $v$ be $\mu_1, \mu_2, \cdots, \mu_k$ for some $1\le k\le |E|$. .

First run of Prim. Define a new weight function $w_{\text{disfavor}}$, which is the same as $w_\text{orig}$ except that $w_\text{disfavor}(\mu_k)=w_\text{orig}(\mu_k) + \frac\epsilon 2$ for all $k$. Run Prim's algorithm on $(V,E, w_\text{disfavor}$). Consider the edges that are incident to $v$ in the returned MST. Call those edges "required edges".

• If there are more than two "required edges", return "there is no such tree". Stop the whole algorithm.
• Otherwise, continue.

Second run of Prim. Define a new weight function $w_{\text{favor}}$, which is the same as $w_\text{orig}$ except that

• $w_\text{favor}(\mu_k)=w_\text{orig}(\mu_k) - \frac\epsilon 2$ for all $k$ such that $\mu_k$ is a "required edge".
• $w_\text{favor}(\mu_k)=w_\text{orig}(\mu_k) - \frac\epsilon 3$ for all other $k$, i.e., such that $\mu_k$ is not a "required edge".

Run Prim's algorithm on $(V,E, w_\text{favor}$). Consider the edges that are incident to $v$ in the returned MST. Call those edges "selectable edges". Note that all "required edges" are "selectable edges".

• If there are less than two "selectable edges", return "there is no such tree". Stop the whole algorithm.
• Otherwise, continue.

Third run of Prim. Select "additional edges", which are "selectable edges" but not "required edges" so that the total number of edges that are either "required" or "additional" is 2. Define a new weight function $w_{\text{final}}$, which is the same as $w_\text{orig}$ except

• $w_\text{final}(\mu_k)=w_\text{orig}(\mu_k) - \frac\epsilon 2$ for all $k$ such that $\mu_k$ is a "required edge".
• $w_\text{final}(\mu_k)=w_\text{orig}(\mu_k) - \frac\epsilon 3$ for all $k$ such that $\mu_k$ is an "additional edge".
• $w_\text{final}(\mu_k)=w_\text{orig}(\mu_k) + \frac\epsilon 2$ for all other $k$, i.e., such that $\mu_k$ is neither a "required edge" nor an "additional edge".

Run Prim's algorithm on $(V,E, w_\text{final}$). Return the Obtained MST.

---

The above algorithm only applies the exact vanilla version of Prim's algorithm as a black box. This peculiar requirement by OP's professor does not seem attractive to me, although it may be interesting.

The above algorithm works still if we replace Prim with Kruskal everywhere.