Every story and comment from the Hacker News API, in a layout borrowed from 2001.
A comment on NP-Complete isn't (always) Hard. Parent comment
Vertex cover is NP-complete on planar graphs even if each vertex has at most three neighbors.
Travelling Salesman is NP-complete on planar graphs.
So is independent set, dominating set, 3-coloring...
This reduces the problem from finding the shortest hamiltonian cycle to finding any such cycle.
Vertex cover is NP-complete on planar graphs even if each vertex has at most three neighbors.
Travelling Salesman is NP-complete on planar graphs.
So is independent set, dominating set, 3-coloring...