Untestable though the algorithm might be, the validity of its result in any given case is trivial to check. This means an option would be to use the O(N2) algorithm and if it broke fall back to the O(eN) one, giving the option to e-mail the author.
…except that I just bet the constants in the O(N2) are so huge you need to be colouring a much larger map than the ones in your puzzle before they're amortised.
For the avoidance of doubt, when you say that each step has to construct a reduced version of its input graph, I assume the previous version must be retained in its entirety?
I assume the previous version must be retained in its entirety?
As I said in the post, "as best I could tell". I didn't see any way to avoid having to do so, although it's possible that a way might have existed and I failed to spot it.
I noted your saying that a graph couldn't be reduced in situ; I was just wanting confirmation that you can't delete graphn once you've made graphn+1, i.e. that you have to retain the entire sequence of graphs in order to reconstruct the colouring once all the reductions have been done.
Incidentally, if — as I suspect — the algorithm works by creating a reducing sequence of graphs then reconstructing a colouring back up the sequence towards the original, you can probably transform the algorithm from O(N2) time O(N2) space into one that's O(N3) time and O(N) space, simply by making sure the reduction sequence is deterministic then replaying it at each step in the reconstruction instead of using retained copies of the graphs.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
…except that I just bet the constants in the O(N2) are so huge you need to be colouring a much larger map than the ones in your puzzle before they're amortised.
For the avoidance of doubt, when you say that each step has to construct a reduced version of its input graph, I assume the previous version must be retained in its entirety?
As I said in the post, "as best I could tell". I didn't see any way to avoid having to do so, although it's possible that a way might have existed and I failed to spot it.
I noted your saying that a graph couldn't be reduced in situ; I was just wanting confirmation that you can't delete graphn once you've made graphn+1, i.e. that you have to retain the entire sequence of graphs in order to reconstruct the colouring once all the reductions have been done.
Incidentally, if — as I suspect — the algorithm works by creating a reducing sequence of graphs then reconstructing a colouring back up the sequence towards the original, you can probably transform the algorithm from O(N2) time O(N2) space into one that's O(N3) time and O(N) space, simply by making sure the reduction sequence is deterministic then replaying it at each step in the reconstruction instead of using retained copies of the graphs.