Result: Routing Few Robots in a Crowded Network
Title:
Routing Few Robots in a Crowded Network
Authors:
Contributors:
Argyrios Deligkas and Eduard Eiben and Robert Ganian and Iyad Kanj and Dominik Leko and M. S. Ramanujan
Publisher Information:
Schloss Dagstuhl β Leibniz-Zentrum fΓΌr Informatik, 2025.
Publication Year:
2025
Subject Terms:
Document Type:
Conference
Conference object
File Description:
application/pdf
Language:
English
DOI:
10.4230/lipics.wads.2025.20
Rights:
CC BY
Accession Number:
edsair.od......1814..6755245f3cde43fdc4bec976fef0a2bc
Database:
OpenAIRE
Further Information
In Graph Coordinated Motion Planning, we are given a graph G some of whose vertices are occupied by robots, and we are asked to route k marked robots to their destinations while avoiding collisions and without exceeding a given budget π on the number of robot moves. We continue the recent investigation of the problem [ICALP 2024], focusing on the parameter k that captures the task of routing a small number of robots in a possibly crowded graph. We prove that the problem is W[1]-hard parameterized by π even for k = 1, but fixed-parameter tractable parameterized by k plus the treedepth of G. We complement the latter algorithm with an NP-hardness reduction which shows that both parameters are necessary to achieve tractability.