Complexity of action path finding with small precondition sets

DOI10.1016/J.DAM.2025.12.009MaRDI QIDQ6866643zbMATH OpenFDO

Authors Peter Damaschke, Karinne Ramirez-Amaro

Publication date 28 January 2026

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2025.12.009

zbMATH Keywords

reachabilityperfect matchingtopological orderingfeedback vertex setstate spacetoken sliding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Artificial intelligence for robotics (68T40)

Cites work

• Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard
• Galactic token sliding
• Gap amplification for reconfiguration problems
• On the complexity of reconfiguration problems
• On the parameterized complexity of reconfiguration problems
• Routing Permutations on Graphs via Matchings
• Sequentially swapping tokens: further on graph classes
• Shunting for Dummies: An Introductory Algorithmic Survey
• Solution discovery via reconfiguration for problems in P
• Swapping labeled tokens on graphs

This page was built for publication: Complexity of action path finding with small precondition sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6866643)