show/hide this revision's text 2 retag
show/hide this revision's text 1

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.