Research map / Learning theory and algorithms / Combinatorial and search optimization

Solving Multiagent Path Finding on Highly Centralized Networks

AAAI 2025 · Learning theory and algorithms › Combinatorial and search optimization · approach: Structure and complexity of constraint reasoning · 2 citations (OpenAlex)

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.

Theoretical paper showing MAPF is NP-hard on trees with bounded vertex cover (or 11 leaves) and gives an FPT algorithm parameterized by distance to clique.

Problem

Multiagent Path Finding (MAPF) asks for collision-free, makespan-optimal agent trajectories on a graph; the paper studies its parameterized complexity with respect to structural parameters (vertex cover, max leaf number, distance to clique).

Approach

Proves NP-hardness for trees with bounded vertex cover number and for trees with 11 leaves via reductions from 3-Partition and Pancake Flipping, and gives an FPT algorithm for graphs with bounded distance to clique, the first positive result not parameterized by number of agents or makespan.

Key results

• MAPF is NP-hard on trees with nine internal vertices and vertex cover number 7.
• MAPF is NP-hard on trees with 11 leaves, and Colored MAPF is NP-hard with 6 agent groups on trees with 11 leaves.
• MAPF is FPT parameterized by distance to clique, the main algorithmic contribution.

Surprising findings

• Bounded vertex cover does not give tractability for MAPF; NP-hard even on trees with vertex cover number 7.

Limitations

• No experimental evaluation of the FPT algorithm.
• Results restricted to the restrictive version disallowing edge swaps.

Experimental setup

Builds on: Fioravantes et al. AAAI'24 MAPF treelike topology results 3-Partition Pancake Flipping

Closest papers by meaning

• Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology (AAAI 2024 · 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.89)
• Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (AAAI 2024 · similarity 0.88)
• Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions (AAAI 2025 · similarity 0.88)
• Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning (AAAI 2024 · similarity 0.87)