Routing Multiple Agents Below the Sum of Distances

1 Introduction

• Sequentially routing agents along shortest paths gives an upper bound L = 1 + the sum of their shortest-path distances; ζ = L − λ measures the gap to target makespan λ.The bound can be tight, while a schedule may improve on it by using waits, detours, or interleaved movements.Source: §1 · pp. 2–3
• Agents move on a graph without sharing vertices or traversing the same edge at the same time, then disappear upon reaching their destinations.The standard objective is to minimize makespan, the arrival time of the last agent.Source: §1 · pp. 2–3
• The problem is fixed-parameter tractable for the combined parameter k + ζ, where ζ measures improvement over the upper bound L.Theorem 1 gives a 2^O(k^2ζ) · n^O(1) algorithm.Source: §1 · p. 4
• The proof uses shortest-path structure, handling long terminal distances through infeasibility checks or by constructing a schedule within the target makespan.For two faraway terminal pairs, the proof routes those agents in a special way while routing the others concurrently.Source: §1 · pp. 4–5
• The combined result is tight in parameter choice: k alone and ζ alone are W[1]-hard, and k + ζ admits no polynomial kernel.The paper describes these results as an almost complete characterization.Source: §1 · p. 5
• With pairwise distinct terminals, the problem is also fixed-parameter tractable when parameterized solely by ζ.The stated running time is 2^O(ζ^3) · n^O(1).Source: §1 · p. 6

2 Preliminaries

• Each agent has a start and destination in an undirected graph and may enter, move, wait, or disappear upon reaching its destination.A schedule consists of pairwise non-conflicting routes; its makespan is the latest agent’s arrival time.Source: §2 · p. 7
• A parameterized problem is FPT if solvable in f(k)·|x|^O(1) time and belongs to XP if solvable in |x|^g(k) time.W[1]-hardness is used to rule out FPT under standard complexity assumptions.Source: §2 · p. 7
• A kernelization reduces an instance in polynomial time to an equivalent instance whose size is bounded by a function of the parameter.A polynomial kernel has a polynomial size bound; its nonexistence is commonly ruled out assuming coNP ⊄ NP/poly.Source: §2 · p. 7

3 Basic observations

• 1 + Σ_i dist(si, ti) is an upper bound on makespan, achieved by routing agents sequentially along shortest paths with at most one extra round.A tight instance on a path requires the sum of distances plus one; ζ is defined as this bound minus target makespan λ.Source: §3 · p. 8
• A time-expanded graph has λ + 1 copies of the input graph’s vertices, with arcs between consecutive layers for waiting or moving along an edge.The construction is a DAG and supports the reduction to disjoint paths.Source: §3 · pp. 8–9
• (kn)^O(k) time suffices by reducing the problem to vertex-disjoint paths in a directed acyclic time-expanded graph.The construction modifies arcs and adds artificial terminals so vertex-disjoint paths encode valid schedules.Source: §3 · p. 9
• 2^O(kλ)·n^O(1) time suffices for Transient Multiagent Pathfinding when parameterized by the number of agents k and makespan λ.The approach reduces the problem to prescribed-length disjoint paths on a time-expanded graph and applies color coding.Source: §3 · p. 10

Theorem 1

• Transient Multiagent Pathfinding is fixed-parameter tractable when parameterized by k + ζ, where ζ = L_R,G − λ.The section assumes λ ≤ L_R,G; otherwise, the instance is trivially a yes-instance.Source: §4 · p. 10

Codirectional paths

• Two codirectional laminar shortest paths, each of length at least ζ + 2, guarantee a yes-instance.The paths may be disjoint or share a path; in the shared case, one agent starts one step later so it enters shared vertices after the other leaves them.Source: §4 · pp. 11–12

Opposite paths

• Two opposite laminar shortest paths of length at least ζ + 2 guarantee a yes-instance if one specified terminal-to-intersection distance is at least ζ + 2.The condition is max{dist_G(si, x), dist_G(ti, y), dist_G(sj, y), dist_G(tj, x)} ≥ ζ + 2.Source: §4 · p. 12

Branch-vertex detour

• A shortest path of length at least 2ζ + 4 with an internal vertex at distance at least ζ + 2 from both ends and degree at least three, paired with a path of length at least ζ + 3, guarantees a yes-instance.The proof uses the extra neighbor to detour one agent while timing the other agent through the shared path.Source: §4 · p. 13

Three distant terminal pairs

• Three terminal pairs with distances at least 2ζ + 3, ζ + 2, and ζ + 2 guarantee a yes-instance.The proof uses laminar shortest paths and reduces to earlier sufficient conditions for codirectional or opposite paths.Source: §4 · p. 14

Long path and short pairs

• A terminal pair of length between 5ζ + 4 and L_R,G − ζ guarantees a yes-instance if the sum of distances for pairs of length at most ζ + 1 is at least ζ.The proof routes a selected group of short-path agents in two nonconflicting time intervals around a long-path agent.Source: §4 · pp. 15–16

• When both main routes traverse the long shared subpath, an optimal schedule can start one agent on its shortest path and delay the other by at least dist_G(s1, y′) − ζ − 2.The remaining agents are partitioned and routed in separate time intervals, yielding a schedule with makespan at most r ≤ L_R,G − ζ.Source: §4 · pp. 18–19
• If either main route avoids an edge of the shared subpath, the two agents can use shortest paths with one path in the graph after deleting that subpath’s internal vertices.The other agents are scheduled in late time intervals using a partition that avoids conflicts, yielding makespan r ≤ L_R,G − ζ.Source: §4 · pp. 19–20
• The problem is solvable in 2^O(k^2ζ) · n^O(1) time when λ = L_R,G − ζ.The proof uses distance-based case analysis, applying a bounded-distance algorithm in the remaining cases.Source: §4 · p. 21

5 The case of distinct terminals

• The distinct-terminal result makes the gap ζ alone sufficient for fixed-parameter tractability.The section combines the routing bound with Theorem 1 to obtain the algorithmic result.Source: §5 · pp. 21, 23
• Among three agents with distinct terminals, some pair can be routed without conflicts in makespan at most the sum of their two shortest-path distances minus one.The proof selects shortest paths and considers codirectional and opposite path orientations.Source: §5 · pp. 21–22
• For distinct terminals, any instance with λ at least the sum of shortest-path distances minus one is a yes-instance.The proof routes disjoint pairs with a one-step saving, then concatenates those routes and the remaining shortest paths.Source: §5 · pp. 22–23
• 2^O(ζ^3) · n^O(1) time suffices when terminals are pairwise distinct and λ = L*R,G − ζ.The proof handles the case λ ≥ L*R,G using Lemma 22; otherwise k ≤ 2ζ and Theorem 1 applies.Source: §5 · p. 23

6 Computational lower bounds

• Transient Multiagent Pathfinding is W[1]-hard when parameterized by k, even on subcubic input graphs.The hardness reduction is from Layered Vertex-Disjoint Shortest Paths; the subcubic result is stated as a corollary.Source: §6 · pp. 23–24
• Transient Multiagent Pathfinding is W[1]-hard when parameterized by ζ.The paper reduces from the problem parameterized by k, which is W[1]-hard.Source: §6 · p. 24
• Transient Multiagent Pathfinding parameterized by k + ζ has no polynomial kernel unless coNP ⊆ NP/poly.The proof uses a polynomial parameter transformation from Layered Vertex-Disjoint Shortest Paths parameterized by k + λ.Source: §6 · p. 24
• The kernel lower-bound construction adds a universal vertex and λ − 1 agents, keeping ζ at most 1 + 2k.The added agents force the original agents to avoid the universal vertex during the schedule.Source: §6 · p. 25

7 Conclusion and open questions

• The results delineate a near-complete boundary: the combined parameterization is fixed-parameter tractable, neither parameter alone is likely to yield an FPT algorithm, and no polynomial kernel exists for the combined parameter.The authors describe their characterization as near-complete with respect to k and ζ.Source: §7 · p. 25
• The authors could neither establish nor refute the proposed alternative upper-bound inequality for the minimum makespan in general.A positive answer would prompt new algorithmic questions in the above-and-below-guarantee framework.Source: §7 · p. 25
• The complexity for parameterization by ζ alone remains unresolved, with XP membership versus para-NP-hardness posed as the open question.Resolving this would complete the single-parameter landscape.Source: §7 · p. 25
• Whether the problem is FPT when parameterized by k on planar graphs or planar grids remains open.The authors also identify restricted graph classes, including bounded-degree graphs, as a direction for further study.Source: §7 · pp. 25–26