most recent 30 from http://mathoverflow.net 2013-05-20T19:45:34Z http://mathoverflow.net/feeds/question/75501 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/75501/hamiltonian-paths-in-subgraphs-of-rectangular-lattice-graphs Grzegorz Jaśkiewicz 2011-09-15T10:52:57Z 2011-09-15T14:20:47Z

<p>Is following decision problem NP-hard / NP-complete:</p> <ol> <li>Having vertex-induced subgraph of rectangular lattice graph determine if any Hamiltonian path exists</li> <li>Having vertex-induced subgraph of rectangular lattice graph determine if exists Hamiltonian path starting at given point (path end can be anywhere)</li> </ol> <p>Please give me some references.</p>