The Hamiltonian Cycle and Travelling Salesperson problems with traversal-dependent edge deletion.

Variants of the well-known Hamiltonian Cycle and Travelling Salesperson problems have been studied for decades. Existing formulations assume either a static graph or a temporal graph in which edges are available based on some function of time. In this paper, we introduce a new variant of these problems inspired by applications such as open-pit mining, harvesting and painting, in which some edges become deleted or untraversable depending on the vertices that are visited. We formally define these problems and provide both a theoretical and experimental analysis of them in comparison with the conventional versions. We also propose two solvers, based on an exact backward search and a meta-heuristic solver, and provide an extensive experimental evaluation. • This paper concerns with dynamic graphs where some edges become deleted or untraversable depending on the vertices that are already visited. • Existing formulations of TSPs do not cover dynamic graphs. • To model a graph that changes due to the path of already visited vertices, we introduce a new class of graphs, called Self-Deleting. • We formally define the Hamiltonian Cycle Problem with Self-Deleting graphs (HCP-SD), and the Travelling Salesperson Problem with Self-Deleting graphs (TSP-SD). [ABSTRACT FROM AUTHOR]