2026-07-20T11:27:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24936 2026-02-09T08:02:17Z ddc:004 open_access

Pathfinding in Self-Deleting Graphs Dvořák, Michal Knop, Dušan Opler, Michal Pokorný, Jan Suchý, Ondřej Szilágyi, Krisztina Parameterized complexity self-deleting graphs pathfinding 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 et al., 2023], which consist of a graph G = (V, E) and a function f: V → 2^E, 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 W[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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michal Dvořák and Dušan Knop and Michal Opler and Jan Pokorný and Ondřej Suchý and Krisztina Szilágyi 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.28 urn:nbn:de:0030-drops-249365 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.28 eng https://creativecommons.org/licenses/by/4.0/legalcode