Smooth Routing in Decaying Trees

arXiv:2603.23504v1 Announce Type: new
Abstract: Motivated by evacuation scenarios arising in extreme events such as flooding or forest fires, we study the problem of smoothly scheduling a set of paths in graphs where connections become impassable at some point in time. A schedule is smooth if no two paths meet on an edge and the number of paths simultaneously located at a vertex does not exceed its given capacity. We study the computational complexity of the problem when the underlying graph is a tree, in particular a star or a path. We prove that already in these settings, the problem is NP-hard even with further restrictions on the capacities or on the time when all connections ceased. We provide an integer linear program (ILP) to compute the latest possible time to evacuate. Using the ILP and its relaxation, we solve sets of artificial (where each underlying graph forms either a path or star) and semi-artificial instances (where the graphs are obtained from German cities along rivers), study the runtimes, and compare the results of the ILP with those of its relaxation.