---
title: "Charging Station Placement for Anonymous Mobile Agents: A Parameterized Complexity Perspective"
authors:
  - "Arun Kumar Das"
  - "Tesshu Hanaka"
  - "Nikolaos Melissinos"
  - "Hirotaka Ono"
doi: "10.24963/ijcai.2026/9"
url: "https://ijcai.org/proceedings/2026/9"
pdf: "https://ijcai.org/proceedings/2026/0009.pdf"
venue: "Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence"
year: 2026
pages: "72-80"
track: "Main Track"
keywords:
  - "Planning and Scheduling: Theoretical foundations of planning"
  - "Agent-based and Multi-agent Systems: Multi-agent planning"
  - "Agent-based and Multi-agent Systems: Resource allocation"
  - "Search: Combinatorial search and optimisation"
  - "Planning and Scheduling: Routing"
---

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

Arun Kumar Das, Tesshu Hanaka, Nikolaos Melissinos, Hirotaka Ono

*Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence*, pages 72-80. DOI: [10.24963/ijcai.2026/9](https://doi.org/10.24963/ijcai.2026/9)

## Abstract

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.