# Hamiltonian path in dynamic graph

Given an undirected Graph. I want to find a hamiltonian path with no restriction to starting or ending vertices. I know there are some smart algorithms for solving that.
Now let's make things interesting: sometimes, when I arrive at a vertex, the edges connected to that vertex change. I.e. some will be removed, others appear. It is only depending on the edge I used before which egdes will change.
That means, if I go from vertex $v_1$ to $v_x$, edges connected to $v_x$ will change in the way $b_{1,x}$. if I arrived $v_x$ via $v_2$, edges will change in the way $b_{2,x}$ and so on.

I am looking for a efficient algorithm telling me if there is a hamiltonian path and output that if so. Has anybody ideas on how to approach that? Or has anyone an idea if this can be transformed into another better known problem?

• Could you name any of the smart algorithms for the Hamiltonian Path problem? – A.Schulz Nov 30 '12 at 13:02
• This page presents some good heuristics. Particularly, I waas pretty impressed by their snakes-and-ladders heuristic, which you can try out via an applet. But don't attach too much importance to that sentence. It's not the point here ;-) – Hebi Nov 30 '12 at 16:03
• Seems to me that you can blow up the graph by a factor of $n$, direct it, and then search for directed $n$-cycles. – Raphael Jul 5 '16 at 8:51