<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2013-12-21T11:42:33.593Z
2013-12-21T11:42:33.593Z
David Richerby
<p>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. </p>

<p>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. </p>

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

<ul>
<li>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.]</li>
<li>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.]</li>
<li>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.]</li>
</ul>

<p>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). </p>

<p>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. </p>

<p>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. </p>

<p>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).</p>

<p>The output (for all graphs) is <em>some</em> (but not all) of its MSTs. </p>

<p><strong>EDIT</strong>: 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. </p>

CC BY-SA 3.0
2013-12-20T07:31:07.993Z
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.
David Richerby
CC BY-SA 3.0
2013-12-20T13:48:59.963Z
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.
Jeffε
CC BY-SA 3.0
2013-12-20T14:55:44.840Z
How about some encouragement for enterprising students rather than downvotes?
Yuval Filmus
CC BY-SA 3.0
2013-12-20T23:59:01.553Z
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](http://en.wikipedia.org/wiki/Cayley%27s_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?
David Richerby
CC BY-SA 3.0
2013-12-21T00:00:04.827Z
It is not clear what problem you are taking about. Please be more specific and define what is the input to your algorithm and what is the output. Are you talking about second best MST problem (CLRS Ex. 23-1)?
Kaveh
CC BY-SA 3.0
2013-12-21T00:03:54.707Z
@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.
Kaveh
CC BY-SA 3.0
2013-12-21T00:03:55.330Z
Also, what does "it only finds some of the MSTs in O(E/V)$" mean? On all graphs, it runs in time O(E/V) and finds some, but not necessarily all, additional MSTs? On some, but not necessarily all, graphs, it finds all additional MSTs, but it always runs in time O(E/V)? On all graphs, it finds some additional MSTs within time O(E/V) but it might take longer than that to find all of them? Something else?
David Richerby
CC BY-SA 3.0
2013-12-21T03:47:35.630Z
@DavidRicherby on all graphs, it finds some additional MSTs within time O(E/V), and I'm not sure how to find all possible MSTs.
curtissv
CC BY-SA 3.0
2013-12-21T07:08:15.117Z
This is still confusing. You seem to be claiming you can output an MST (which would have n-1 edges) in time O(1) for sparse graphs? How is that done? Do you just list the symmetric difference with the MST already computed? Also according to the rest of the question body, it seems your $O(m/n)$ time algorithm actually takes the graph, an MST, and a priority queue of edges (which itself might take $O(m)$ time to construct, no?)
Sasho Nikolov
CC BY-SA 3.0
2013-12-22T10:31:11.593Z
"Sorry for getting excited about this." Don't worry. Everyone who's done research has had the experience of doing something they think is neat but turns out to be mistaken.
David Richerby
<graph-algorithms>
I found an algorithm for computing multiple MSTs in O(E/V). Is this publishable?
curtissv
# I found an algorithm for computing multiple MSTs in O(E/V). Is this publishable?

(Asked by: username_0 on 2013-12-20)

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.

**Tags:** graph-algorithms
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_3**: How about some encouragement for enterprising students rather than downvotes?  
> **username_1**: 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](http://en.wikipedia.org/wiki/Cayley%27s_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?  
> **username_4**: It is not clear what problem you are taking about. Please be more specific and define what is the input to your algorithm and what is the output. Are you talking about second best MST problem (CLRS Ex. 23-1)?  
> **username_4**: @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.  
> **username_1**: Also, what does "it only finds some of the MSTs in O(E/V)$" mean? On all graphs, it runs in time O(E/V) and finds some, but not necessarily all, additional MSTs? On some, but not necessarily all, graphs, it finds all additional MSTs, but it always runs in time O(E/V)? On all graphs, it finds some additional MSTs within time O(E/V) but it might take longer than that to find all of them? Something else?  
> **username_0**: @DavidRicherby on all graphs, it finds some additional MSTs within time O(E/V), and I'm not sure how to find all possible MSTs.  
> **username_5**: This is still confusing. You seem to be claiming you can output an MST (which would have n-1 edges) in time O(1) for sparse graphs? How is that done? Do you just list the symmetric difference with the MST already computed? Also according to the rest of the question body, it seems your $O(m/n)$ time algorithm actually takes the graph, an MST, and a priority queue of edges (which itself might take $O(m)$ time to construct, no?)  
> **username_1**: "Sorry for getting excited about this." Don't worry. Everyone who's done research has had the experience of doing something they think is neat but turns out to be mistaken.  

---

## 1 answers

### Answer by username_1 on 2013-12-21. Score: 4

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.


---

