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

1 Introduction

Coordinating multiple agents in a shared working environment via routing and path planning has become a central problem in optimization and robotics [Wurman et al., 2008]. The agents are typically autonomous mobile robots tasked with performing specific operations within designated domains such as warehouses, hospitals, libraries, restaurants, military installations, and transportation systems. In practical settings, these agents are often identical with respect to key attributes, including speed, battery capacity, and computational capability. Depending on the nature of their tasks and the operational costs incurred by system operators, a variety of models have been proposed, with the most wellknown being the VEHICLE ROUTING PROBLEM (VRP) and the MULTI-AGENT PATHFINDING (MAPF) problem. Naturally, many of these problems are computationally intractable. In particular, MAPF is known to be notoriously hard when multiple agents are required to reach agent-specific goals without collisions. Indeed, it remains NP-hard even on structurally simple networks, such as trees with a small number of internal vertices [Fioravantes et al., 2025a].

In most cases, the agents operate under limited energy capacities and must periodically recharge their batteries to sustain continuous operation [Kundu and Saha, 2018; Kundu and Saha, 2021]. In practical environments such as warehouses, hospitals, road networks [Zhang et al., 2022], and airborne delivery systems, the efficient placement of charging stations is crucial for ensuring cost-effective and reliable operations. Recent studies [Falchetta and Noussan, 2021] show a significant gap in the placement of charging infrastructure that leaves agents stranded due to depleted batteries. Nowadays, in the US [David Shepardson, 2025] and the EU [European Automobile Manufacturers' Association, 2024], the problem of green energy adoption has become crucial, and consequently, both the placement of charging stations and the scheduling of recharging cycles have a significant impact on overall system performance by substantially reducing idle time and improving operational efficiency [Zhu et al., 2025; Xiong et al., 2015].

1.1 Our Model

In this work, we are interested in scenarios where we have multiple identical agents placed in a network together with a set of terminal positions. The movement of the agents is energy-dependent, and each agent requires recharging at least once every specific number of steps. The goal is to identify the minimum number of charging stations and their placement in the network such that each terminal is reachable by a unique agent. We call this problem CHARGING STATION PLACEMENT.

In order to give a formal definition we need some graphtheoretical notation. Let G = (V, E) be an undirected graph where |V | = n, C be a subset of V and r be a positive integer. A sequence of vertices v1, . . . , vℓ, ℓ ∈ N, where vivi+i ∈ E, for all i ∈ [ℓ-1], is called a walk between v1 and vℓ. A walk W connecting s and t is a (C, r)-walk if it can be decomposed into a set of sub-walks P1, P2, . . . , Pm such that:

1. for every 1 ≤ i < m, the last vertex of Pi is the first vertex of Pi+1,
2. for every 1 ≤ i < m, the shared vertex of Pi and Pi+1 belongs to C, and
3. the length of each sub-walk Pi, i ∈ [m] is at most r.

In CHARGING STATION PLACEMENT, we are given an undirected graph G = (V, E) with |V | = n along with two sets of vertices S and T with |S| = |T | = k, together with a capacity r. We need to compute a minimum cardinality subset C of charging stations such that each target position in T can be occupied with exactly one robot using the chargers in C. We call C a charger placement, or simply, placement. Further, we say that a charger placement C is feasible if there exists a bijection f : S → T and for any pair s, f(s) there exists (C, r)-walk in G that connects s and f(s). Then CHARGING STATION PLACEMENT is formally defined as follows.

CHARGING STATION PLACEMENT

Input: Graph G = (V, E), two sets of vertices S ⊆ V and T ⊆ V , where |S| = |T | = k, and two positive integers r and c.

Question: Is there a feasible charger placement C ⊆ V of size at most c in G?

We denote by (G, S, T, r, c) an instance of CHARGING STATION PLACEMENT. Any feasible charger placement C of minimum size is called a minimum charger placement.

CHARGING STATION PLACEMENT has applications in scenarios where we have identical energy-dependent robots that need to reach specific places to perform some tasks. Other scenarios may assume fully electrical communities where everyone moves with electric vehicles, and some companies try to provide charging stations in order to allow their employees to reach their workplaces. In such scenarios, it is not unnatural to assume that the employees have received the same training and thus can be considered identical.

1.2 Our Assumptions and Limitations

The primary motivation behind our model is to minimize the number of charging stations. This is a rational objective, since in many cases, deploying additional charging stations is the primary challenge. This challenge may arise from various factors, such as budgetary constraints or regulations imposed by third parties. Therefore, our model is tailored with this obstacle in mind.

Motivated by this, we adopted the following assumptions. First, we do not consider the travel distance, focusing solely on reachability. Second, we consider the anonymous version of the problem, i.e., the final agent-terminal matching is not restricted. We do not consider any timing limitations; i.e., we do not consider charging times or any restrictions imposed by the positions of the agents in the network.

Notably, these are some of the most common restrictions appearing in many path-finding problems. However, as previously noted, the current model is highly applicable even without incorporating any of these constraints.

1.3 Our Contribution

We provide a detailed study of the computational complexity of CHARGING STATION PLACEMENT, with an emphasis on its parameterized complexity. Table 1 summarizes our results. In section 3, we prove that the problem belongs to the class NP. To this end, we present a polynomial-time algorithm that, given a subset C, verifies whether it is a feasible solution of CHARGING STATION PLACEMENT.

In Section 4, we provide several hardness results, including NP-hardness on planar bipartite graphs of maximum degree 3, W[2]-hardness when parameterized by the number of chargers c, W[1]-hardness when parameterized by the feedback vertex set number fvs together with the number of charging stations c, and W[1]-hardness when parameterized by distance to stars dts of G or distance to clusters dtc, even for instances with r = 1. For the inapproximability, the problem admits no (1 - ϵ) ln k-approximation algorithm even on split or bipartite graphs unless P=NP.

We then turn to algorithmic results. In Section 5, we present three FPT algorithms: one parameterized by the number of agents, a second by modular-width, and a third by vertex cover number. The first is obtained via a reduction to the well-studied STEINER TREE problem, while the second and third exploit structural properties of graphs with bounded modular-width and vertex cover number, respectively. Finally, we provide a polynomial-time algorithm for trees, as well as a polynomial-time k-approximation algorithm.

Due to space limitations, we omit several proofs or provide only proof sketches.

1.4 RelatedWork

Robot motion planning [Cesati and Wareham, 1995] is central to artificial intelligence and multi-agent systems, with a vast body of literature on path planning for mobile agents [Guo et al., 2023]. Prior works address diverse optimization objectives, including minimizing total traveled distance [Liu et al., 2019], ensuring collision avoidance [Fioravantes et al., 2025b], and obstacle removal [Erickson and LaValle, 2013]. However, accommodating agents with limited energy introduces fundamentally different constraints, necessitating a distinct algorithmic perspective.

CHARGING STATION PLACEMENT is first introduced in [Das, 2025], proving it NP-hard in general networks and polynomial-time solvable on simple paths or cycles. To our knowledge, CHARGING STATION PLACEMENT is not studied elsewhere. However, since charging station placement is a central challenge in electric vehicle (EV) E-mobility, Storandt and Funke [Storandt and Funke, 2013] address related problems. They study the hardness of minimizing

Table 1: Overview of the results for CHARGING STATION PLACEMENT.

charging stations in a directed graph where each pair of vertices needs to be reachable subject to recharge constraints. Strimel and Veloso [Strimel and Veloso, 2014] study finding a location minimizing charging stations when a single agent needs to reach a given set of targets following a predetermined path. Kundu and Saha introduce an INDOOR CHARGING STATION PLACEMENT problem: given a workspace graph and battery threshold, place the minimum number of stations so that any robot from any starting point can reach a station before running out of power [Kundu and Saha, 2018]. They formulate two variants (minimize stations given threshold, or find maximum threshold given station count), develop SMT-based algorithms, and later prove both variants NP-hard with polynomial-time approximation algorithms [Kundu and Saha, 2023; Kundu and Saha, 2021]. Kumar et al. formulate the persistent robot charging problem, which optimizes recharging schedules to minimize station utilization during extended missions [Kumar et al., 2025].

While identical agents often simplify models, this is not always the case. MAPF is one example where, considering identical agents (i.e., goals are not agent-specific), we can efficiently compute coalition-free schedules [Yu and LaValle, 2012]. However, the VRP, seeking optimal routes for a fleet of vehicles, is originally introduced as a "truck dispatching" problem for a homogeneous fleet [Dantzig and Ramser, 1959], yet remains computationally hard.

Our problem diverges significantly from both VRP and MAPF. Unlike VRP and MAPF, CHARGING STATION PLACEMENT minimizes charging stations rather than primarily bounding travel time. This aspect distinguishes our work from previous routing problems. Notably, beyond [Das, 2025], other works consider similar settings. Agarwal et al. [Agarwal et al., 2016] define a SHORTEST-PATH HITTING SET problem to place minimum charging stations so that every shortest path remains "EV-feasible" (traversable on a full charge). A key distinction lies in our focus on traveling between specific starting and terminal positions, while SHORTEST-PATH HITTING SET guarantees feasibility between any pair via a shortest path. In some sense, our setting generalizes their model. Furthermore, we note that in practice, connecting all possible pairs is often unnecessary.

2 Preliminaries

Throughout this paper, we use standard graph theory notation and terminology. Let G = (V (G),E(G)) be an undirected graph with |V (G)| = n vertices and |E(G)| = m edges. When the context is clear, we omit the argument G (e.g., writing V and E). A directed arc from u to v is denoted by -→ uv, and an undirected edge between u and v is denoted by uv. We denote the distance between u and v by dist(u, v).

For a vertex v ∈ V , the neighborhood of v is denoted by N(v) = {u ∈ V | uv ∈ E}. The degree of v is denoted by deg(v) = |N(v)|. The maximum degree of G is denoted by ∆(G) = maxv∈V deg(v). For a positive integer r, the r-neighborhood of v is denoted by Nr(v) = {u ∈ V | dist(u, v) ≤ r}. For a graph G = (V,E), the r-th power of G, denoted by Gr = (V,Er ), is a graph with vertex set V where uv ∈ Er if and only if the distance between u and v in G is at most r. Note that G1 = G.

2.1 Natural and Structural Parameters

One of the main goals of this work is to study the parameterized complexity of CHARGING STATION PLACEMENT. In the parameterized complexity framework, in addition to an input instance, one is given a parameter x, and the objective is to design algorithms whose running time is efficient when x is small. A problem is fixed-parameter tractable (FPT) if there exists an algorithm that runs in time f(x) · nO(1) , where f is a computable function depending only on x, and n is the input size. Such an algorithm is called an FPT algorithm.

Some problems are believed not to admit FPT algorithms under standard complexity assumptions; such problems are called W[1]-hard.

We consider both natural parameters, such as the number c of charging stations or the number k of agents, and structural parameters of the underlying graph. The structural parameters used in this paper are the following:

• Feedback vertex set number, fvs: the size of a smallest set S such that G- S is a forest.
• Distance to stars, dts: the size of a smallest set S such that G- S is a disjoint union of stars.
• Distance to clusters, dtc: the size of a smallest set S such that G- S is a disjoint union of cliques.

We also consider the modular-width mw of a graph. While the formal definition is rather technical, intuitively mw measures how well the vertex set can be recursively partitioned into modules where vertices of the same module have identical neighbors outside of the module. Finally, the set S of vertices is called a vertex cover if u ∈ S or v ∈ S for every edge uv ∈ E. The vertex cover number vc of G is defined by the size of a minimum vertex cover.

We note that these parameters are closely related to treewidth tw and cliquewidth cw. In particular, for any graph G, the inequalities mw ≤ 2vc + vc, cw ≤ dtc ≤ vc, and tw - 1 ≤ fvs ≤ dts ≤ vc hold. Consequently, the hardness results for fvs, dtc, and dts imply corresponding hardness results for tw and cw. Conversely, the FPT result for mw implies FPT results for other parameters, e.g., the vertex cover vc.

2.2 General Observations

Throughout this paper, we assume that the input graph is connected, as the global solution can be computed by solving the problem for each connected component of the input graph.

Then, we give several useful observations for CHARGING STATION PLACEMENT.

Observation 1. Let G = (V,E) be a graph, C ⊆ V and r a positive integer. Additionally, let (si, ti), i ∈ [k] be k pairs of vertices. If si+1 = ti ∈ C for all i ∈ [k - 1] and there exists a path Pi of length at most r between si and ti, for all i ∈ [k], then there exists a (C, r)-walk between s1 and tk.

Observation 2. Let G = (V,E) be a graph, C ⊆ V and r a positive integer. Additionally, let Ws,v and Wt,v be two (C, r)-walks between s and v, and between t and v respectively. If v ∈ C, then we can combine the two walks into a (C, r)-walk between s and t.

Proposition 1. An instance (G, S, T, r, c) of CHARGING STATION PLACEMENT is a yes-instance if and only if the instance (Gr , S, T, 1, c) is a yes-instance.

3 NP-Membership

Let (G, S, T, r, c) be an instance of CHARGING STATION PLACEMENT and let C ⊆ V (G) be a vertex set of order at most c. We prove that one can decide if C is a feasible solution of (G, S, T, r, c) in polynomial time. This implies that CHARGING STATION PLACEMENT belongs to the class NP.

We construct an intermediate directed graph D from G in the following way. The vertex set of D is S ∪ T ∪ C. Now, we construct the set of arcs in A(D) as follows. For any vertex u ∈ S ∪ C we add the arcs -→ uv in A(D) if and only if v ∈ Nr(u) ∩ (T ∪ C). Now, the following lemma is true for D.

Lemma 1. For any pair (s, t) ∈ S ×T , there exists a (C, r)- walk in G if and only if there exists a directed s-t path in D.

Then we consider an auxiliary bipartite graph H that is constructed as follows: For each vertex s ∈ S, we create a vertex us in H. For every vertex t ∈ T we create a vertex vt in H. Note that if a vertex w is both a starting and a terminal vertex, i.e., w ∈ S ∩ T , then we create two vertices related to w: uw representing that it is a starting vertex and vw representing that it is a terminal vertex. We construct both vertices because we may have optimal solutions that do not match s with t, even if s = t. Then we introduce an edge between two vertices us and vt in H if and only if there exists a directed path from s to t in D. We conclude the following lemma.

Lemma 2. The set C with |C| ≤ c is a feasible solution of (G, S, T, r, c) if and only if there exists a perfect matching in H.

Observe that the construction of both D and H can be performed in polynomial time. Indeed, the edges in A(D) depend on Nr(v) of v, which can be computed by a BreadthFirst Search (BFS), and the edges of H can be computed using an algorithm for s-t paths in D. Both BFS and s-t paths can be computed in polynomial time [Cormen et al., 2009]. Finally, computing a maximum matching can be done in polynomial time [Cormen et al., 2009].

Theorem 1. Given an instance I = (G, S, T, r, c) and a set C ⊆ V (G), we can decide in polynomial time whether C is a feasible solution of I. Additionally, we can return a bijection f : S → T and a set of (C, r)-walks between s and f(s) for s ∈ S.

Corollary 1. CHARGING STATION PLACEMENT belongs to NP.

We conclude by observing that given the number of chargers c, there are at most nO(c) possible placements of charging stations in any graph of order n. Therefore, by enumerating all potential solutions and checking their feasibility, we have the following corollary.

Corollary 2. CHARGING STATION PLACEMENT can be solved in time nO(c) .

4 Hardness Results

We start by establishing NP-hardness even for instances where both r and ∆(G) are constants and G is bipartite.

Theorem 2. CHARGING STATION PLACEMENT is NP-hard even when:

• r = 1 andG is a planar bipartite graph with∆(G) = 6,
• r = 1 and G is a bipartite graph with ∆(G) = 4,
• r = 3 andG is a planar bipartite graph with∆(G) = 3.

The proofs of all the statements appearing in Theorem 2 are based on reductions from VERTEX COVER.

In the following theorems, we show the parameterized hardness of CHARGING STATION PLACEMENT even on restricted graph classes. To do so, we give a parameterized reduction from SET COVER: Given a universe U = {u1, . . . , un}, a family F = {F1, . . . , Fm} of subsets of U, and an integer ℓ, the problem asks whether there exists a subfamily F ′ ⊆ F such that ⋃F∈F ′ F = U and |F ′ | ≤ ℓ. SET COVER is a well-known NP-complete problem [Garey and Johnson, 1979] and is W[2]-hard when parameterized by the solution size [Cygan et al., 2015].

Theorem 3. CHARGING STATION PLACEMENT is W[2]- hard when parameterized by the number of charging stations c, even when r = 1 and the input graph is split or bipartite.

Proof sketch. We reduce from SET COVER, which is W[2]- hard parameterized by the solution size [Downey and Fellows, 1999]. Given (U, F, ℓ), where U = {u1, . . . , un} and F = {F1, . . . , Fm}, we construct a split graph G as follows. Create a clique W with vertex set {wF | F ∈ F} and, for each u ∈ U, two independent vertices su, tu. Add edges wFsu if u ∈ F, and wF tu for all (F, u) ∈ F × U. Set S = {su | u ∈ U}, T = {tu | u ∈ U}, r = 1, and c = ℓ.

Finally, we can observe that a subfamily F ′ ⊆ F with |F ′ | ≤ ℓ covers U if and only if C = {wF | F ∈ F ′ } is a feasible charger placement with |C| ≤ ℓ: for each u ∈ U, the path su, wF , tu gives a (C, 1)-walk whenever u ∈ F . Thus, this parameterized reduction shows the W[2]-hardness parameterized by c even when r = 1 and the input graph is split.

Observe that this reduction works even if we delete edges within W and the resulting graph is a bipartite graph. Therefore, the W[2]-hardness on bipartite graphs can also be shown by a similar argument.

Observe that our reduction in Theorem 3 preserves the objective value exactly. It is known that SET COVER cannot be approximated within (1 - ϵ) ln |U| unless P=NP [Dinur and Steurer, 2014]. As |U| = |S| = |T| = k, the following corollary holds.

Corollary 3. Unless P=NP, CHARGING STATION PLACEMENT cannot be approximated within (1 - ϵ) lnk for any ϵ > 0, even on split or bipartite graphs.

The next theorems consider structural parameters of the graph G. In particular, we consider the distance to clusters (dtc) and the distance to stars (dts) as parameters.

Theorem 4. CHARGING STATION PLACEMENT is W[1]- hard when parameterized by distance to stars dts or distance to clusters dtc, even when r = 1.

Proof sketch. We give a parameterized reduction from UNARY BIN PACKING. Given a multiset E = {e1, . . . , en} of integers in unary and an integer m ∈ N, the problem asks whether there is a partition of E into multisets E1, . . . , Em, such that, for all j ∈ [m], ∑e∈Ej e = (∑e∈E e)/m. It is known that UNARY BIN PACKING is W[1]-hard when parameterized by the number of bins m [Jansen et al., 2013].

We start with an instance (E,m) of UNARY BIN PACKING. Let B = (∑e∈E e)/m. We define a graph G together with the sets S and T as follows. First, we create m vertices v1, . . . , vm. For all j ∈ [m], we attach B leaves to vj. Let Tj be the set of all leaves incident to vj for j ∈ [m], and let T = ⋃j∈[m] Tj. For each integer ei ∈ E, we create a vertex ui and attach ei +m leaves to it. Let Si be the set of leaves {lip | p ≤ ei} for i ∈ [n], and set S = ⋃i∈[n] Si. Then, for each j ∈ [m] and i ∈ [n], we add the edge liei+j vj; that is, we connect each vj with the (ei + j)-th leaf of the star centered at ui. This completes the construction of G and the sets of terminals. Notice that deleting {v1, . . . , vm} leaves a disjoint union of stars, so G has distance to stars at most m.

Now, we claim that the constructed instance I = (G, S, T, 1, 2n + m) of CHARGING STATION PLACEMENT is a yes-instance if and only if (E,m) is a yes-instance of UNARY BIN PACKING. First, we observe that a bin packing {E1, . . . , Em} with ∑e∈Ej e = B yields a feasible charging set C = {ui | i ∈ [n]} ∪ {vj | j ∈ [m]} ∪ {liei+j | ei ∈ Ej} of size 2n + m, which ensures that each agent starting at a vertex in Si can reach some Tj. Conversely, we show that any feasible C of size 2n + m induces a partition of E into m multisets, each of total weight B. As r = 1, the construction forces any feasible C to include the vertices {ui | i ∈ [n]} ∪ {vj | j ∈ [m]}, and exactly one vertex from {liei+1 , . . . , liei+m} for each ei, indicating the bin to which ei is assigned. Since G has distance to stars at most m, the problem is W[1]-hard parameterized by dts even when r = 1.

By replacing stars with cliques for each connected component of G - {v1, . . . , vm}, we can construct a graph with distance to clusters at most m. The remaining argument is the same as the distance to stars.

We finally show the W[1]-hardness of CHARGING STATION PLACEMENT parameterized by fvs + c via a reduction from the (k, r)-CENTER problem, defined as follows. Given a graph G = (V,E) and two integers k, r, a set S ⊆ V is called a (k, r)-center if |S| ≤ k and the distance from any vertex v ∈ V to the set S is at most r. The (k, r)- CENTER problem asks whether there exists a (k, r)-center in G. This problem is W[1]-hard when parameterized by fvs+k and admits no algorithm running in time no(fvs+k) under the ETH [Katsikarelis et al., 2019].

Theorem 5. CHARGING STATION PLACEMENT is W[1]- hard when parameterized by fvs + c. Furthermore, no algorithm for CHARGING STATION PLACEMENT runs in time no(fvs+c) assuming the ETH.

Proof sketch. We give a parameterized reduction from (k, r)- CENTER. Let (G0 = (V0, E0), k, r) be an instance of (k, r)- CENTER, and let n = |V0|. We construct an instance of CHARGING STATION PLACEMENT as follows. First, we create a graph G′ starting from G0. For each vertex v ∈ V0, we attach a new pendant vertex, and let S be the set of these n new pendant vertices (i.e., vertices of degree 1). Next, we construct a star-like structure: we introduce a new center vertex p and create 2n paths of length r + 1, each starting at p. We identify the other endpoints of n of these paths with the vertices in V0 one to one. Let T be the set of the n remaining endpoints of the other paths. The resulting graph is G′ . Note that |S| = |T| = n. This construction ensures that the feedback vertex set number of G′ is bounded by a linear function of the feedback vertex set number of the original graph G0. Indeed, fvs(G′ ) ≤ fvs(G0) + 1 holds.

We complete the proof by showing that there exists a (k, r)-center in G0 if and only if there exists a feasible charger placement for the instance (G′ , S, T, r+1, k+1) of CHARGING STATION PLACEMENT.

5 Algorithmic Results

5.1 Parameterized by Terminal Pairs

In this section, we give an FPT algorithm parameterized by k = |S| = |T |.

Theorem 6. CHARGING STATION PLACEMENT can be solved in time kO(k)nO(1) .

By Proposition 1, it suffices to assume r = 1. A set F = {H1, . . . ,Hℓ}, ℓ ≤ k, of trees in G will be called a connecting forest 1 of S and T if there exist partitions S1, . . . , Sℓ of S and T1, . . . , Tℓ of T such that, for each i ∈ [ℓ], |Si| = |Ti|, Si∪Ti ⊆ V (Hi), and all leaves of Hi belong to Si∪Ti. Each Hi ∈ F will be called a connecting tree. Let Ii be the set of vertices u ∈ V (Hi) with dHi (u) ≥ 2, i.e., u ∈ Ii if u is not a leaf of Hi. Also, let IF = ⋃i∈[ℓ] Ii. We show the following key lemma.

Lemma 3. There exists a feasible placement C of size at most c in G if and only if there exists a connecting forest F for S and T with |IF | ≤ c.

Based on Lemma 3, we determine whether G has a connecting forest F for S and T with |IF | ≤ c. Towards this, we guess partitions S1, . . . , Sℓ and Ti, . . . , Tℓ of the terminals. For each guessed partition, we can compute a connecting tree Hi of Si and Ti with the minimum number of inner vertices in time 2O(k)nO(1) by reducing it to WEIGHTED STEINER TREE [Lokshtanov and Nederlof, 2010] after guessing the set of inner terminals Xin ⊆ Si ∩ Ti and leaf terminals Xout = Si ∩ Ti \ Xin. If the sum of inner vertices across all connecting trees is at most c, we conclude that there exists a connecting forest F for S and T with |IF | ≤ c in G. Since the number of guesses is bounded by kO(k) , the total running time is kO(k)nO(1) , which proves Theorem 6.

5.2 FPT Algorithm byModular-width

Theorem 7. There exists a 2mw nO(1) -time algorithm for CHARGING STATION PLACEMENT where mw is the modular-width of the input graph.

Let Q be a graph with vertices q1, . . . , qt, and let H1, . . . ,Ht be t vertex-disjoint graphs. The substitution Q(H1, . . . ,Ht) is the graph obtained by replacing each qi with Hi, and adding all edges between V (Hi) and V (Hj) whenever {qi, qj} ∈ E(Q). A modular decomposition represents a way to construct G by recursively applying substitutions starting from singletons. The width of a modular decomposition is the maximum number of vertices in any graph Q appearing in the decomposition. The modular-width mw(G) is the minimum width over all decompositions. A modular decomposition of width mw(G) can be computed in polynomial time [Cournier and Habib, 1994; Tedder et al., 2008; Habib and Paul, 2010]. Since mw(Gr ) ≤ mw(G) for r ≥ 2 [Hanaka et al., 2024], by Proposition 1, it suffices to solve the case where r = 1. Let G = Q(V1, . . . , Vt) be the top-level decomposition where t ≤ mw(G).

1 Note that F is not necessarily an actual forest as we have no requirement that the trees in F do not share vertices or edges.

Lemma 4. If r = 1 and G is connected, any yes-instance admits a feasible charger placement of size at most c where each module contains at most one charger.

Based on Lemma 4, we guess which modules contain exactly one charger. As t ≤ mw(G), there are at most 2mw(G) guesses. Let M′ ⊆ {V1, . . . , Vt} be a guessed set of modules, and let Q[M′ ] be the induced subgraph of the quotient graph. For any component in Q[M′ ] of size at least two, the placement of a charger within each module does not affect inter-module connectivity due to the complete adjacency between connected modules. Thus, we can place a charger on an arbitrary vertex in each such module.

We then consider the placement of a charger for each isolated module in Q[M′ ] (i.e., a module with no neighbors in M′ ). For an isolated module M ∈ M′ , the placement only affects terminal pairs {s, t} ⊆ M, as every vertex in M has the same neighbors outside of M. Thus, for each isolated module, we select a vertex v ∈ M maximizing the number of connected pairs {s, t} ⊆ M when a charger is placed on v. Such a vertex v ∈ M can be found by computing a maximum matching in a bipartite graph constructed based on the connectivity between the vertices in M assuming a charger is placed at v. The running time is dominated by the 2mw guesses, yielding 2mw nO(1) .

5.3 FPT Algorithm by Vertex Cover Number

Theorem 7 implies an algorithm with runtime 22O(vc) nO(1) . We improve this to single-exponential in vc2 .

Theorem 8. Given an instance I of CHARGING STATION PLACEMENT, a minimum charger placement can be computed in time 22vc2+vcnO(1) .

Proof sketch. We first compute a minimum vertex cover X ⊆ V (G) of G in time 2vcnO(1) [Downey and Fellows, 1999]. Then, I = V (G) \X is an independent set of G. We guess at most 2vc possible intersections X∗ = X∩C with a minimum charger placement C. We also guess at most 2vc2 subsets W ⊆ X × X that represent pairs of vertices in X that are connected by a charger in I.

For a fixed guess (X∗ ,W), we construct an instance of SET COVER to find a minimum charger placement in I. Define the universe U = W and Fv = {(x, x′ ) ∈ W | x, x′ ∈ N(v)} for each v ∈ I. The set Fv represents the pairs in W that can be connected by a charger on v. Let F = {Fv | v ∈ I}. Then (U,F) is an instance of SET COVER introduced in Section 4 corresponding to finding a minimum subset of I in which chargers are placed. Since |U| ≤ vc2 , |F| ≤ n, and SET COVER can be solved in time

2|U| (|U| + |F|)O(1) [Cygan et al., 2015], we can find an optimal solution F ′ ⊆ F of (U, F) in time 2vc2 nO(1) . Then we construct a candidate solution C = X∗ ∪ {v | Fv ∈ F ′ } and verify whether it is a feasible solution of CHARGING STATION PLACEMENT by Theorem 1. After examining all guesses, we return the smallest solution. Since there are 2vc2+vc guesses, the total running time is 22vc2+vcnO(1) .

5.4 Polynomial-Time Algorithm for Trees

In this subsection, we provide a polynomial-time algorithm for trees. In particular, we solve a more general problem called EXT-CHARGING STATION PLACEMENT. In this problem, given an instance I = (G, S, T, r, c) and a partial solution P ⊆ V , the goal is to find a set C ⊇ P such that |C \ P| ≤ c and C is a feasible solution. Note that, for P = ∅, the problem is equivalent to CHARGING STATION PLACEMENT.

Theorem9. EXT-CHARGING STATION PLACEMENT can be solved in polynomial time when G is a tree.

To show this, we first root G at an arbitrary vertex w. For any h ∈ V , let Gh be the subtree rooted at h, ph be the parent of h, and Ph = P ∩ V (Gh), Sh = S ∩ V (Gh), Th = T ∩ V (Gh). We say that Gh is covered by P if there exist partitions (S1h , S2h ) of Sh and (T 1 h , T 2 h ) of Th such that: (1) |S1h | = |T 1 h |, (2) there exists a bijection f : S1h → T 1 h such that a (Ph, r)-walk between s and f(s) exists in Gh for each s ∈ S1h , and (3) for each x ∈ S2h ∪ T 2 h , there exists a (Ph, r)-walk W ′ in Gh + ph between x and ph (to be consistent, if h = w, we assume a dummy parent pw for w). For any h ∈ V , we can verify, in polynomial time, whether Gh is covered by P by applying Theorem 1 to an auxiliary graph obtained from Gh by attaching a clique of size |Sh| + |Th|, which consists of |Th| terminals on S and |Sh| terminals on T , to h. Based on this, we define the following reduction rule.

Reduction Rule: Given an instance (G, S, T, r, c, P) with c ≥ 1, if there exists h ∈ V such that Gh is not covered by P, and Gv is covered by P for all v ∈ V (Gh) \ {h}, create the new instance (G, S, T, r, c - 1, P ∪ {h}).

This rule is safe because such an uncovered Gh forces any feasible solution to add at least one charger in Gh. Moreover, since the subtrees of Gh are covered, placing a charger at h enables all unmatched terminals in Gh to connect via h. We exhaustively apply this reduction rule as long as c > 0 and there exists such a vertex h in G.

After thoroughly applying the rule, if c = 0, we simply check if P is a feasible solution by using Theorem 1. If c > 0, then we can show that P ∪ {w} is a feasible solution because G = Gw is covered by P . The algorithm runs in polynomial time, as the reduction rule decreases c by 1, and checking whether Gh is covered by P as well as testing the feasibility of P can both be done in polynomial time by Theorem 1.

6 k-Approximation Algorithm

Theorem 10. Let I = (G, S, T, r, c) be an instance of CHARGING STATION PLACEMENT. Then, a kapproximation solution of I can be computed in time O(√kk4 + k3n + km).

Proof sketch. Let C ∗ be a minimum charger placement and f : S → T be a bijection such that for each s ∈ S, there exists a (C ∗ , r)-walk between s and f(s). Let (s∗ , f(s∗ )) be a pair maximizing the distance between its terminals i.e., dist(s∗ , f(s∗ )) ≥ dist(s, f(s)) for all s ∈ S. Since the length of any (C ∗ , r)-walk between s∗ and f(s∗ ) is at most dist(s∗ , f(s∗ )), at least ⌈ dist(s∗ ,f(s∗ )) r ⌉ - 1 vertices must belong to C ∗ .

Assume that (s∗ , f(s∗ )) is known. We construct a bijection h : S → T such that h(s∗ ) = f(s∗ ) and dist(s, h(s)) ≤ dist(s∗ , f(s∗ )) for all s ∈ S by defining a bipartite graph H where V (H) = (S ∪ T) \ {s∗ , f(s∗ )}, and an edge st is added if and only if dist(s, t) ≤ dist(s∗ , f(s∗ )). Then a perfect matching in H defines the required bijection h.

We now construct an approximate solution C as follows. For each pair (s, h(s)), we take a shortest s-h(s) path and place a charging station on every r-th vertex. Since each path contributes at most ⌈dist(s∗ , t∗ )/r⌉-1 vertices, we have |C| ≤ k(⌈dist(s∗ , t∗ )/r⌉ - 1) ≤ k|C ∗ |.

Therefore, we compute such a set for each of the O(k2 ) possible pairs (s∗ , t∗ ) and take the smallest feasible solution, which is an approximate solution C.

7 Conclusions

In this work, we consider a natural model of the chargingstation placement problem. We present a theoretical study dedicated to the general and parameterized complexity of the problem, picturing the details of the time complexity with respect to both natural and structural parameters.

From a practical perspective, the model is highly pragmatic, yet the existing literature on this topic remains relatively limited. Additionally, the hardness results indicate that, in many cases, alternative approaches are necessary and justify interest in developing heuristics to tackle the problem. Furthermore, our algorithms can be utilized to improve the accuracy of such heuristics.

Additionally, our study gives rise to several theoretical directions, both within the same model and beyond. With respect to parameterized complexity, a particularly interesting question is the parameterization by the combination of the number of charging stations, the distance parameter r, and the maximum degree of the network. The reason is that the closely related (k, r)-CENTER problem becomes FPT under this parameterization, and it would be surprising if this were not the case for CHARGING STATION PLACEMENT.

Further research could explore the relaxation of certain assumptions adopted in this work. The most natural extensions would be to drop the anonymity assumption or to consider restrictions on traveling distance, since these were the main limitations of our model. Most of our results should be easily adaptable to the non-anonymous case; however, this is not true for all of them. For example, Theorem 4 heavily depends on the anonymity assumption. We believe that it would be intriguing to investigate which results can and cannot be generalized depending on the exact models we consider. Moreover, in such comparisons, it is essential to assess how the number of charging stations differs across the considered models.

Acknowledgements

Tesshu Hanaka is partially supported by JSPS KAKENHI Grant Numbers JP22H00513, JP25K03077, and JST, CRONOS, Japan Grant Number JPMJCS24K2.

Nikolaos Melissinos is partially supported by Charles University projects UNCE 24/SCI/008 and PRIMUS 24/SCI/012, and by the project 25-17221S of GA ˇCR.

Hirotaka Ono is partially supported by JSPS KAKENHI Grant Numbers JP22H00513, JP24K02898, JP25K03077, and JST, CRONOS, Japan Grant Number JPMJCS24K2.