2
$\begingroup$

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.

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ 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. $\endgroup$
    – Douglas Zare
    Commented Sep 15, 2011 at 11:35
  • $\begingroup$ Is it obvious that cublic planar graph is a vertex-induced subgraph of rectangular lattice graph? $\endgroup$
    – Grzegorz Jaśkiewicz
    Commented Sep 15, 2011 at 12:24
  • 2
    $\begingroup$ 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 $\endgroup$
    – Grzegorz Jaśkiewicz
    Commented Sep 15, 2011 at 12:41
  • $\begingroup$ 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. $\endgroup$
    – Douglas Zare
    Commented Sep 15, 2011 at 14:16
  • $\begingroup$ 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 ;) $\endgroup$
    – Grzegorz Jaśkiewicz
    Commented Sep 15, 2011 at 20:59

0

Reset to default

You must log in to answer this question.