Modification of Hamilton Path

Question

Although I know that the Hamilton Path problem is ${\sf NP}$-complete, I think the following variant can be solved in polynomial time:

Given a planar graph with vertex set $V$, edge set $E$, start node $S$ and target node $F$, our task is to find the Hamiltonian path from $S$ to $F$ or write that the path doesn't exist.

Last condition: In the path, in addition to selecting the directly connected vertices, we can also choose those connected to exactly one neighbor.

Edit: The degree of any vertex is at most four ($\deg(v_i) \le 4$).

Does anyone have any ideas how to prove that this can be solved in polynomial time?

It can be hard to understand, so I will give an example:

In the left example, for $S=1,F=12$, the solution is the path $1, 11, 8, 7, 5, 9, 2, 10, 4, 6, 3, 12$.

In the right example, for $S=1,F=15$, there is no Hamiltonian path.

Answer 1

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 :).