Skip to main content
retag
Link
Emil Jeřábek
  • 47.1k
  • 4
  • 147
  • 208
Source Link

Hamiltonian paths in subgraphs of rectangular lattice graphs

Is following decision problem NP-hard / NP-complete:

  1. Having vertex-induced subgraph of rectangular lattice graph determine if any Hamiltonian path exists
  2. Having vertex-induced subgraph of rectangular lattice graph determine if exists Hamiltonian path starting at given point (path end can be anywhere)

Please give me some references.