2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Why $m$ necessarily belongs to cycle formed by adding $e_1$ and $e_2$ ? $\endgroup$ – Vladislav Bezhentsev May 12 at 21:11
  • $\begingroup$ Ah thanks for that catch, I fixed my answer. Adding edges $e_1$ and $e_2$ definitely creates a cycle, and we just need to remove the largest edge on that cycle, but making sure that $v$ stays degree 2. $\endgroup$ – Sam Westrick May 12 at 21:25
  • 1
    $\begingroup$ Consider graph with edges (1, 2; weight = 4) (1, 3; weight = 3) (1, 4; weight = 1) (2, 3; weight = 100) (3, 4; weight = 2) And consider that we should find MST in which vertex 1 should have degree = 2. If I understand your algorithm correctly, it will fail to find such MST. However it does exist. $\endgroup$ – Vladislav Bezhentsev May 12 at 21:40
  • $\begingroup$ Ah hmm you're right. My algorithm would claim to have found an MST on your example when actually no solution exists (the MST of your example uses three edges on vertex 1). I think this is fixable by comparing the cost of the spanning tree returned by this algorithm against the true minimum cost, and discarding it if it is not actually minimum. So all we would have to do is additionally compute MST(G). $\endgroup$ – Sam Westrick May 12 at 21:51
  • 1
    $\begingroup$ @VladislavBezhentsev I believe this works, thanks. I've updated the answer above. $\endgroup$ – Sam Westrick May 13 at 14:03
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Switching priorities in the middle of the algorithm is unacceptable by this professor's standard as it changes the input to Kruskal's algorithm as it runs, requiring a re-proof of the algorithm. $\endgroup$ – Or Bairey-Sehayek May 14 at 12:29
  • $\begingroup$ @OrBairey-Sehayek Thanks for your feedback. IMHO, your professor, as depicted, has a peculiar way that risks instilling the wrong kind of the knowledge into student. Let me check whether there is some misunderstanding. Could you answer this simple question, is the first run of Kruskal's algorithm in this answer acceptable by your professor? (To be extra clear, "the same weight" in my answer always means "the minimum weight of remaining edges") $\endgroup$ – John L. May 14 at 14:25
  • $\begingroup$ The professor has a bit of an odd approach... Yes, the first run of Kruskal is fine because it is simply a bluest MST where the edges incident on $v$ are painted blue, or put another way, those edges have had some $\epsilon$ removed from their weight that is sufficiently small to prioritize them over edges of the same original weight without making them lighter than actually lighter edges. The problem arises in the third run when you change priorities in the middle of Kruskal's algorithm; she claims that the minimality of the resultant spanning tree must be re-proved. $\endgroup$ – Or Bairey-Sehayek May 15 at 15:26
  • $\begingroup$ @OrBairey-Sehayek Thanks for your feedback. Please check my updated answer, in which my algorithm applies Prim's algorithm like a black box. $\endgroup$ – John L. May 15 at 18:48
  • $\begingroup$ Working on a formal proof ... $\endgroup$ – John L. May 16 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.