MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Since it is NP-complete to find a Hamiltonian path in a cubic planar graph (Garey and Johnson, 1970s,, I think this is NP-complete. – Douglas Zare Sep 15 '11 at 11:35
Is it obvious that cublic planar graph is a vertex-induced subgraph of rectangular lattice graph? – Grzegorz Jaśkiewicz Sep 15 '11 at 12:24
1. NP-complete, answer is here: 2. NP-complete by polyminal reduction to problem 1 - just check Hamiltonian path for every vertex – Grzegorz Jaśkiewicz Sep 15 '11 at 12:41
The idea I had was that you should be able to lengthen the edges and embed any cubic graph into the lattice in a way which preserves Hamiltonian paths and only expands the graph a polynomial amount. It's not obvious to me that this is possible, and I haven't filled in the details, but this is not the type of problem where I think you need a super-polynomial expansion. By the way, it's fine to post an answer to your own question. – Douglas Zare Sep 15 '11 at 14:16
I have some funny idea: 1. Draw cubic planar graph on white piece of paper with black pen, so that there are no edge intersections. 2. Take a photo with digital camera. Now all pixels in photo form square lattice, black pixels are verteices of lattice subgraph. With correct lens scaling this would produce good embedding ;) – Grzegorz Jaśkiewicz Sep 15 '11 at 20:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.