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 W1-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.