4

In a weighted undirected graph I need to find a minimum spanning tree containing a given edge 'e', if it's possible. How can I do it? Kruskal starting from 'e' ?

zeusm
  • 75
  • 2
  • 7

3 Answers3

2

I would not use Kruskal algorithm because if the edge e is part of cycle and e has maximum weight in that cycle, then the algorithm will not include 'e'. I believe with modification it could work. But with Prim's algorithm modification required is minimal.

Prim's algorithm is best suited for this problem, if we recall Prim algorithm goes like this:

STEP 1: Begin with set S containing a vertex picked randomly.

STEP 2: From all the edges with one vertex in set S and other vertex in set V - S,pick the one with minimum weight. Let it be (x,y), x belongs to S and y belongs to V - S.

STEP 3: Add y to set S.

STEP 4: Repeat step 2 and 3 till S contains all vertices.

Modification required:

For your problem just change step 1 to:

STEP 1: Begin with set S containing a vertex u and v where edge 'e' = (u,v).

Sumeet
  • 8,086
  • 3
  • 25
  • 45
  • I agree that Prim's algorithm is the best approach, but I think that Kruskal's algorithm will work too. In Kruskal's algorithm, you never need to remove an edge that has been added already, so you could just start with the given edge and go from there. – Edward Doolittle Nov 18 '18 at 17:51
  • @EdwardDoolittle Guess you are right, but Prim's algorithm required minimum modification, and hence I wrote it. – Sumeet Nov 18 '18 at 18:29
  • But if I use DFS to check if 'e' is contained in some MST like here :https://stackoverflow.com/questions/15049864/check-if-edge-is-included-in-some-mst-in-linear-time-non-distinct-values , I shouldn't be able to get a MST with kruskal, so what I get using kruskal starting from 'e' isn't the right MST? – zeusm Nov 19 '18 at 12:05
  • @zeusm A modified version of kruskal will work for this. You have to set the weight of edge 'e' minimum and then perform the sorting of edges. This will definitely yield correct MST. – Sumeet Nov 19 '18 at 13:28
  • @Sumeet ok but if the DFS test linked above fails,so it doesn't exist a MST containing 'e', with Kruskal/Prim starting from 'e' I get always a MST containing 'e'. How is it possible? – zeusm Nov 19 '18 at 14:21
  • 1
    @zeusm If the edge 'e' is part of a cycle and has maximum weight of all edges inside that cycle, then definitely DFS test will fail and yes then none of Kruskal or Prim can give you the required MST. – Sumeet Nov 19 '18 at 14:37
  • How can I compute the mst containing e, if it exists in O(mlogm) where m is the number of edges? – zeusm Nov 19 '18 at 14:47
  • @zeusm Both Prim and Kruskal run in time O(mlogm). Now to check if 'e' is part of cycle with maximum weight, efficient algorithms exist to list edges in cycle of undirected graph with time O(m+n),yielding total time to be still O(mlogm). Take a look at this https://www.geeksforgeeks.org/print-all-the-cycles-in-an-undirected-graph/ – Sumeet Nov 19 '18 at 15:01
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/183900/discussion-between-zeusm-and-sumeet). – zeusm Nov 19 '18 at 15:18
  • Can someone explain why in this case O(m + n) + O(mlogm) is O(mlogm)? – zeusm Nov 20 '18 at 16:17
2

Here is a possible "lazy solution" that requires no modification of an MST algorithm

  1. Run any MST algorithm.
  • The MST algorithm will output an MST T = (V,E,w)

  1. If edge e is already in T then you're done

  2. If edge e is not in T then add edge e and you will have a cycle σ

  3. Iterate over cycle σ, if there is an edge with the same weight as e then remove that edge and your'e done

  4. If none of the edges have the same weight as e then a MST with e is not possible

Whats good about this approach is that is fairly easy to prove formally hence you have a proof for a MST algorithm and the other steps are based on known theorems.

Micael Illos
  • 467
  • 2
  • 15
  • How would you proove it? – Kavar Rushikesh Aug 06 '22 at 17:25
  • I could think of a proof. If you add the edge in MST and then remove the edge which has highest weight in circle which is created by adding an edge, you will get the best optimum spannig which contains the added edge. Let us call this tree T. Consider a path P on the T, after adding the edge on P, the added edge will be having higher weight than any edge on path P. (Can be proved by contradiction). So, how can you improve weight of T where each addition of edge has no counter edge to remove from created circle, which has higher weight then added edge!! :) Hence T is optimal. Any doubts? – Kavar Rushikesh Aug 15 '22 at 14:28
0

For a lazy solution, make the cost of that edge less than the cost of all other edges and run any MST algorithm on it.

eesiraed
  • 4,626
  • 4
  • 16
  • 34