Re:NP-Complete isn't (always) Hard
by JohnKemeny on Thursday February 23, 2023 @05:12PM
(#34917332)
SAT is NP-complete even when the variable-clause graph is planar.
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...
I remember in one lecture where the dude drew an unweighted graph on the board, claiming it to be in NP.
But he'd already proven it to be planar (by construction), which (and correct me if I'm wrong) simplifies the problem to P.