2 ms·
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.
by JohnKemeny 4y ago
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...
- yarg 4y agoIt'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.