3 ms·

There was a discussion here the other day about the Seven Bridges of Königsberg, which is today known as a Eulerian path. [1] Unlike Eulerian paths, which are

There was a discussion here the other day about the Seven Bridges of Königsberg, which is today known as a Eulerian path. [1] Unlike Eulerian paths, which are detectable in linear time [2], detecting Hamiltonian paths is NP-complete [3]. Does anyone have an intuitive explanation for why this is the case? [1]: https://news.ycombinator.com/item?id=23123754 https://news.ycombinator.com/item?id=23123754 [2]: https://en.wikipedia.org/wiki/Eulerian_path#Hierholzer's_algorithm https://en.wikipedia.org/wiki/Eulerian_path#Hierholzer's_alg... [3]: https://en.wikipedia.org/wiki/Hamiltonian_path https://en.wikipedia.org/wiki/Hamiltonian_path

jcranmer 6y ago
> Does anyone have an intuitive explanation for why this is the case? Imagine building a Eulerian path. You're standing at a node, trying to figure out which edge to go down next. Eventually, because it's a Eulerian path, you'll have to go down all the edges eventually. This means it doesn't matter which edge you go down--even if your path hits a dead end, you can magically go back in time and patch in a cycle to your original path. Put another way, if you establish that a graph has a Eulerian path, every maximal set of edge-disjoint cycles in the graph constitutes that path. Just by looking and making decisions at a very localized context (every node), you can formulate a correct answer. By contrast, Hamiltonian paths are rarer. Only some maximal sets of node-disjoint cycles can be combined to construct a Hamiltonian path. You don't have the property that you can trivially patch the cycles together if you make a mistake. Looking at a node and trying to decide which next node to pick, you'd have to understand the structure of the entire graph very well to understand if traversing to A will screw you up, and the ramifications are not local.
bssrdf 6y ago
This book <<The Nature of Computation>>[0] has the best explanation I have ever seen. [0]: https://www.amazon.com/Nature-Computation-Cristopher-Moore-dp-0199233217/dp/0199233217/ref=mt_hardcover?_encoding=UTF8&me=&qid=1589226680 https://www.amazon.com/Nature-Computation-Cristopher-Moore-d...

jcranmer 6y ago

> Does anyone have an intuitive explanation for why this is the case? Imagine building a Eulerian path. You're standing at a node, trying to figure out which edge to go down next. Eventually, because it's a Eulerian path, you'll have to go down all the edges eventually. This means it doesn't matter which edge you go down--even if your path hits a dead end, you can magically go back in time and patch in a cycle to your original path. Put another way, if you establish that a graph has a Eulerian path, every maximal set of edge-disjoint cycles in the graph constitutes that path. Just by looking and making decisions at a very localized context (every node), you can formulate a correct answer. By contrast, Hamiltonian paths are rarer. Only some maximal sets of node-disjoint cycles can be combined to construct a Hamiltonian path. You don't have the property that you can trivially patch the cycles together if you make a mistake. Looking at a node and trying to decide which next node to pick, you'd have to understand the structure of the entire graph very well to understand if traversing to A will screw you up, and the ramifications are not local.

bssrdf 6y ago

This book <<The Nature of Computation>>[0] has the best explanation I have ever seen. [0]: https://www.amazon.com/Nature-Computation-Cristopher-Moore-dp-0199233217/dp/0199233217/ref=mt_hardcover?_encoding=UTF8&me=&qid=1589226680 https://www.amazon.com/Nature-Computation-Cristopher-Moore-d...