[Solved]: Modification of Hamilton Path

Perhaps the problem is still NP-complete; this reduction should work: given a planar graph $G$ and two nodes $s$ and $t$ (start and end), expand it to a new graph $G’$ in this way: for every node $u$ of $G$ add two nodes $u_1,u_2$ and two edges: $(u,u_1),(u_1,u_2)$ (informally add a tail made with two new nodes). There are only two ways to traverse the three node gadget with a valid Hamiltonian path (i.e. cover the three nodes): a) $out rightarrow u rightarrow u_2 rightarrow u_1 rightarrow out$ and its reverse
b) $out rightarrow u_1 rightarrow u_2 rightarrow u rightarrow out$ In both cases the node $u$ must be traversed and cannot be reused in another part of the path. Now, in order to force one of the two traversals in every node, add two tails to $s$: $(s,s_1), (s_1,s_2)$ and $(s,s_3), (s_3,s_4)$ and pick as starting node of $G’$ the node $s_1$. The only way to traverse and leave $s$ is $s_1 rightarrow s_2 rightarrow s rightarrow s4 rightarrow s3 rightarrow out$. This forces traversal (a) on all remaining nodes (gadgets) of $G’$. Pick $t_2$ as the ending node in $G’$. So the original graph $G$ has an Hamiltonian path from $s$ to $t$ if and only if $G’$ has a “modified” (one node jumps allowed) Hamiltonian path from $s_2$ to $t_2$. EDIT:

• If $deg(v_i) leq 4$ the above reduction still works because Hamiltonian path is NP-complete even in planar cubic graphs. In a planr cubic graph $deg(v_i) = 3$, so nodes can be extended with the tails as described above. If the starting node has degree 3, just add another node $s’$, an edge $(s,s’)$ and add two tails to $s’$.
• But, if $deg(v_i) leq 3$ then the problem falls in $mathsf{P}$, the following algorithm should work (but I didn’t think about it too much):

calculate the shortest path from $s$ to $t$: $s rightarrow u_1 rightarrow … rightarrow u_m rightarrow t$, then expand the path using a depth first search from every node; this will lead to a spanning tree having the shortest path as a “backbone”. For each $u_i$ of the shortest path there is only one branch $u_i,b_1,b_2,…,b_k$(because the degree of $v_i$ is $leq 3$) and it can be covered using jumps: $u_i > b_2 > b_4 > … > b_k > b_{k-1} > … > b_3 > b_1 > u_{i+1}$ if $k$ is even
$u_i > b_2 > b_4 > … > b_{k-1} > b_k > b_{k-2}… > b_3 > b_1 > u_{i+1}$ if $k$ is odd The only problem is if $s$ and/or $t$ have degree 3. In that case the above procedure must be repeated several times using only one incident edge of $s$ (and eventually only one incident edge of $t$). In order to formally prove that the algorithm is correct one must prove that every Hamiltonian path (with jumps) from $s$ to $t$ in a $deg(v_i) leq 3, deg(s)=1, deg(t)=1$ graph can be transformed to an Hamiltonian path (with jumps) of the above form (a spanning tree from the shortest path). It is not immediate but it seems intuitive (but perhaps I’m just wandering :).