Research map / Graph learning / Graph algorithms and clustering
Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Parameterized complexity study of Multiagent Path Finding, giving W[1]-hardness, NP-hardness on planar/tree graphs with bounded makespan/degree, and FPT algorithms for parameters such as k+makespan, k+diameter, treewidth+makespan, and vertex cover.
Problem
Multiagent Path Finding (MAPF): find non-colliding paths for k agents on a graph to their targets while minimizing makespan; the classical and parameterized complexity of exact solving under various structural and natural parameters.
Approach
Systematic parameterized complexity map of MAPF: hardness with respect to the number of agents (even with max degree), planar/tree hardness with constant makespan, FPT algorithms via time-expanded graphs and disjoint-paths results, and a kernel for vertex cover plus agents; the diameter result uses a high-degree hub to bound makespan by O(d·k).
Key results
- MAPF is W[1]-hard parameterized by number of agents k plus maximum degree, and NP-complete on planar graphs with makespan 3 and max degree 4.
- MAPF is FPT parameterized by k plus makespan l, running in O(2^{O(k·l)} · m · log n) time.
- MAPF is FPT parameterized by k plus graph diameter, and FPT for treewidth plus makespan, but W[1]-hard for cliquewidth plus makespan.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add makespan ℓ to the number-of-agents parameter k | MAPF · MAPF | parameterized complexity: O(2^{O(k\cdot \ell)} \cdot m \cdot \log n) | Helped |
| add treewidth to the makespan parameter | MAPF · MAPF | parameterized complexity: (\ell \cdot w)^{O(\ell \cdot w)} \cdot n | Helped |
| add vertex cover number to the number-of-agents parameter | MAPF · MAPF | kernel size: O(2^{\vc}k) | Helped |
| add graph diameter to the number-of-agents parameter | MAPF · MAPF | parameterized complexity: 2^{O(k^2 \cdot d \cdot \log d)} \cdot m \cdot \log n | Helped |
| use the number of agents k alone as the parameter | MAPF · MAPF | parameterized complexity | Hurt |
| add maximum degree Δ(G) to the number-of-agents parameter | MAPF · MAPF | parameterized complexity | Hurt |
| use treewidth alone as a structural parameter | MAPF · MAPF | parameterized complexity | Hurt |
| add makespan ℓ to treewidth | MAPF · MAPF | parameterized complexity: (\ell \cdot w)^{O(\ell \cdot w)} \cdot n | Helped |
| add makespan ℓ to cliquewidth cw(G) | MAPF · MAPF | parameterized complexity | Hurt |
| restrict the graph to bounded treedepth, modularwidth, shrubdepth, or MIM-width | MAPF · MAPF, parameterized by k | parameterized complexity | Helped |
Surprising findings
- Without swaps, MAPF is NP-hard already for makespan 2 on planar graphs with max degree 5.
- MAPF without swaps is NP-complete even on trees of maximum degree 5.
Limitations
- Hardness results and algorithms are purely theoretical; no experiments on practical MAPF instances.
- Several FPT results depend on parameters (e.g., makespan) that may be large in practice.
- Cliquewidth plus makespan remains W[1]-hard, so some structural classes stay intractable.
Experimental setup
Builds on: k-disjoint shortest paths W[1]-hardness Parallel Token Swapping NP-hardness on trees Planar 3-SAT
Closest papers by meaning
- Solving Multiagent Path Finding on Highly Centralized Networks (AAAI 2025 · similarity 0.95)
- Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures (AAAI 2025 · similarity 0.92)
- Decentralized Monte Carlo Tree Search for Partially Observable Multi-Agent Pathfinding (AAAI 2024 · similarity 0.90)
- Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions (AAAI 2025 · similarity 0.89)
- Inapproximability of Optimal Multi-Agent Pathfinding Problems (AAAI 2025 · similarity 0.88)
- Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (AAAI 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.