Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
1  
Since it is NP-complete to find a Hamiltonian path in a cubic planar graph (Garey and Johnson, 1970s, www2.research.att.com/~dsj/pub.html), 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
2  
1. NP-complete, answer is here: research.cs.queensu.ca/home/daver/Pubs/MyPDF/superThin.pdf 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

 
discard

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

Browse other questions tagged or ask your own question.