2
$\begingroup$

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:

Examples

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.

$\endgroup$
9
  • $\begingroup$ From S to F, do you want to cover every vertex? $\endgroup$
    – Shashwat
    Commented Nov 2, 2012 at 10:52
  • 1
    $\begingroup$ I dont get your "Last condition". Also you should know that Hamiltonian Path is NP-complete for planar graphs. $\endgroup$
    – A.Schulz
    Commented Nov 2, 2012 at 11:26
  • $\begingroup$ @A.Schulz: I think that John means that one node jumps are allowed i.e. an Hamiltonian path in the augmented graph having edges $(u,v)$ such that $(u,w),(w,v)$ are edges of the original graph. But this is my interpretation (and gave a quick answer according to it :-). $\endgroup$
    – Vor
    Commented Nov 2, 2012 at 11:53
  • $\begingroup$ I mean that we can add new edge beetwen two vertex which distance is 2. Example in 1st picture : $(1,8), (1,11), (1,2)$ etc. $\endgroup$
    – John
    Commented Nov 2, 2012 at 15:07
  • $\begingroup$ I'm sure that must exist polynomial time algorithm solving this problem. $\endgroup$
    – John
    Commented Nov 2, 2012 at 15:08

1 Answer 1

2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ If you use $out \rightarrow u \rightarrow u_2 \rightarrow u_1 \rightarrow out$, you could still jump a node before you enter $u$. You can fix this by using two tails. $\endgroup$
    – Peter Shor
    Commented Nov 2, 2012 at 19:22
  • $\begingroup$ @PeterShor: you're right ... but a pair of two nodes tails makes it impossible to leave the gadget after entering it from $u$ (and you are forced to enter it from $u$ after traversing the previous one). Perhaps to fix my answer it is sufficient to use two tails on the starting node $(s,s_1),(s_1,s_2)$ and $(s,s_3),(s_3,s_4)$ and pick $s_1$ as the starting node. This forces a $s_1,s_2,s,s_4,s_3$ traversal of the first node. And this forces the $out \rightarrow u \rightarrow u_2 \rightarrow u_1 \rightarrow out$ traversal on all the following single tailed nodes. ... I'll try to fix it tomorrow. $\endgroup$
    – Vor
    Commented Nov 3, 2012 at 0:44
  • $\begingroup$ You're right. My attempted fix doesn't work. But your suggestion of modifying the starting node should work. $\endgroup$
    – Peter Shor
    Commented Nov 3, 2012 at 0:59
  • $\begingroup$ @PeterShor: I modified the answer but I'm still thinking if there are counterexamples; also take a look to the $deg(v_i) \leq 3$ case ... if it can have a meaning. $\endgroup$
    – Vor
    Commented Nov 3, 2012 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.