3 ms·
MST is polynomial, so you can't use it as an NP oracle, anyway.
by pmiller2 15y ago
MST is polynomial, so you can't use it as an NP oracle, anyway.
- hythloday 15y agoAnd the fact that the slime molds didn't create the same layout every time implies they don't provide an optimum answer.
- ganley 15y agoNot necessarily true. There could be multiple, equal-valued optima.
- pmiller2 15y agoExactly. Consider the case of all equal weights. In that case, every spanning tree is a MST. For the extreme cases (labeled complete graph, and a tree) of order n, those numbers are $n^{n-2}$ and 1, respectively, so the answer can be far from unique.