Let's say you use Kruskal's or Prim's algorithm to compute the first MST, and you want to check to see if there are other MSTs. I can do this in O(E/V) time.

The algorithm uses a priority queue (which can be constructed in O(N) ). Kruskal's and Prim's already use priority queues, but they're slower than the linear time algorithms listed below.

I know there are already algorithms that can find a single MST in linear time:

  • A randomized algorithm can solve it in linear expected time. [Karger, Klein, and Tarjan, "A randomized linear-time algorithm to find minimum spanning trees", J. ACM, vol. 42, 1995, pp. 321-328.]
  • It can be solved in linear worst case time if the weights are small integers. [Fredman and Willard, "Trans-dichotomous algorithms for minimum spanning trees and shortest paths", 31st IEEE Symp. Foundations of Comp. Sci., 1990, pp. 719--725.]
  • Otherwise, the best solution is very close to linear but not exactly linear. The exact bound is O(m log beta(m,n)) where the beta function has a complicated definition: the smallest i such that log(log(log(...log(n)...))) is less than m/n, where the logs are nested i times. [Gabow, Galil, Spencer, and Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica, vol. 6, 1986, pp. 109--122.]

I'm not sure if these algorithms use priority queues. It doesn't really matter since I could just use one of these algorithms to find the first MST in O(N) then construct a priority queue in O(N) then find all the other MSTs in O(E/V). Overall, this would take O(N).

I just came up with this algorithm for a class assignment. The algorithm my TA used to find multiple MSTs took O(N^2) or O(N^3), and so he said I should try to see if this is publishable.

Edit: I realized my algorithm only finds some of the MSTs in O(E/V). To be more specific: on all graphs, it finds some additional MSTs within time O(E/V), and I'm not sure how to find all possible MSTs.

The input to the algorithm is: 1. an MST (a list of Edge objects. Edge.weight, Edge.vertex1 and Edge.vertex2 are fields of the object). 2. A graph (a list of Edges and Verteces).

The output (for all graphs) is some (but not all) of its MSTs.

EDIT: I talked to one of the other TA's about this, and he discovered a flaw in my proof. Sorry for getting excited about this.


closed as off-topic by Kaveh Dec 22 '13 at 17:28

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Kaveh
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 5
    $\begingroup$ What is your exact claim? That, if you're given a graph $G=(V,E)$ and a spanning tree $T$, you can determine in time $O(|E|/|V|)$ whether there is another spanning tree? If so, that can't be correct. If $G$ has constant degree, your algorithm would have to run in constant time, which doesn't even give you enough time to discover that $G$ has constant degree. $\endgroup$ – David Richerby Dec 20 '13 at 7:31
  • 5
    $\begingroup$ I think the OP's claim is that after computing the MST, one can use the internal priority queue of the MST algorithm to determine whether the MST is unique in $O(m/n)$ additional time. But not every MST algorithm uses a priority queue; see Boruvka's algorithm, or the traditional sort+scan formulation of Kruskal's algorithm. $\endgroup$ – Jeffε Dec 20 '13 at 13:48
  • 5
    $\begingroup$ How about some encouragement for enterprising students rather than downvotes? $\endgroup$ – Yuval Filmus Dec 20 '13 at 14:55
  • 3
    $\begingroup$ Does your algorithm find MSTs or just count them? You certainly can't find them all in polynomial time in general because a complete graph on $n$ vertices with unit edge weights has $n^{n-2}$ MSTs, by Cayley's formula. If anyone's going to be able to evaluate the importance of your discovery (it's not my direct area of expertise), you need to give a precise statement of what you've achieved. What exactly is the input to your algorithm? What is its output? What time complexity are you claiming for it? $\endgroup$ – David Richerby Dec 20 '13 at 23:59
  • 3
    $\begingroup$ @Yuval, the post is unclear, and it is not clear if the TA thinks the algorithm is correct or not (i.e. one of incorrect heuristics that students come up with all the time in undergraduate courses where they cannot prove it to be correct but the TA cannot come up with a counter-example). I think this is off-topic if this was an assignment in an undergraduate course and TA/Instructor has not verified the solution. $\endgroup$ – Kaveh Dec 21 '13 at 0:03

I think the best way to proceed is to have a chat with your algorithms professor. Together, you can figure out exactly what you have achieved and then decide if it's something that's worth taking farther. That might mean dropping it, it might mean publishing what you have already, or it might mean extending the results and publishing something more significant.

It's very hard for us to give specific advice here as it's not clear to us exactly what you've achieved. In fact it's not clear to me that you're sure exactly what you've achieved. It's possible that your algorithm can be extended to do more than you realise but, because of the questions above about how it manages to, for example, output a spanning tree in constant time, it's also possible that it does less than you think. I think you need to share your work with somebody who can help you figure out exactly what it does.


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