Multiple identical agents must travel from a shared start to a common target through an environment containing hazards. Each hazard temporarily disables any agent that encounters it, then reactivates after a cooldown period. The question is how to schedule the agents' paths to get everyone through.
This paper proves two structural results. First, optimal solutions require only polynomial-length schedules despite the exponentially many feasible plans — the problem is in NP. The compactness of optimal solutions is not obvious: with cooldown periods and multiple agents sharing paths, long wait-and-retry strategies could in principle be optimal. They aren't.
Second, the problem is NP-hard even on trees — environments with no cycles. Trees are the simplest non-trivial graph structure, and many path planning problems become tractable on them. Not this one. The hazard cooldowns create temporal dependencies that tree structure cannot simplify. However, the special case of vertex-disjoint paths connecting start and target admits a polynomial-time algorithm. The tractability boundary runs through the graph structure: when paths share no vertices, the agents don't interact through cooldowns and the problem decomposes. When they share vertices, even on trees, the problem is hard.