Pathfinding in Self-Deleting Graphs

In this paper, we study the problem of pathfinding on traversal-dependent graphs, i.e., graphs whose edges change depending on the previously visited vertices. In particular, we study self-deleting graphs, introduced by Carmesin et al. (Sarah Carmesin, David Woller, David Parker, Miroslav Kulich, and Masoumeh Mansouri. The Hamiltonian cycle and travelling salesperson problems with traversal-dependent edge deletion. J. Comput. Sci.), which consist of a graph $G=(V, E)$ and a function f V→ 2E, where $f(v)$ is the set of edges that will be deleted after visiting the vertex v. In the {(Shortest) Self-Deleting s-t-path} problem we are given a self-deleting graph and its vertices s and t, and we are asked to find a (shortest) path from s to t, such that it does not traverse an edge in $f(v)$ after visiting v for any vertex v. We prove that {Self-Deleting s-t-path} is NP-hard even if the given graph is outerplanar, bipartite, has maximum degree $3$, bandwidth $2$ and |f(v)|≤ 1 for each vertex v. We show that {Shortest Self-Deleting s-t-path} is W[1]-complete parameterized by the length of the sought path and that {Self-Deleting s-t-path} is {1}-complete parameterized by the vertex cover number, feedback vertex set number and treedepth. We also show that the problem becomes FPT when we parameterize by the maximum size of $f(v)$ and several structural parameters. Lastly, we show that the problem does not admit a polynomial kernel even for parameterization by the vertex cover number and the maximum size of $f(v)$ combined already on 2-outerplanar graphs.