News for hackers. Stuff that matters.
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...

Re:NP-Complete isn't (always) Hard by yarg on Friday February 24, 2023 @03:04PM (#34929362)
It's not the travelling salesman - as per the description it's an unweighted graph.

This reduces the problem from finding the shortest hamiltonian cycle to finding any such cycle.