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?
