Charging Station Placement for Anonymous Mobile Agents: A Parameterized Complexity Perspective

摘要

We study the problem of optimally placing charging stations for a set of k anonymous mobile agents, each of which must reach a distinct terminal. The agents are identical and can travel only up to a given distance r on a single charge. The objective is to find a placement of charging stations so that every terminal can be assigned a unique agent capable of reaching it, and the number of charging stations is minimized. The problem is known to be NP-hard in general and solvable in polynomial time only on paths and cycles. In this work, we comprehensively investigate the classical and parameterized complexity of the problem. We first design a polynomial-time algorithm that, given a set of candidate charging stations, decides whether a feasible assignment of agents to terminals exists. This result also establishes the membership of the problem in NP, which was not previously known. We then analyze the parameterized complexity of the problem. Our results show that the problem remains hard even when we consider different combinations of natural parameters and structural parameters of the given network, such as the distance r plus the tree-depth, or the number of charging stations plus feedback vertex set number. On the positive side, we present three fixed-parameter tractable (FPT) algorithms: one parameterized by the number of agents k, a second by modular-width, and a third by vertex cover number. Finally, we give a polynomial-time k-approximation algorithm, as well as a polynomial-time algorithm for trees, by solving a generalized version of the problem that allows for some charging stations to be pre-placed.