Avoiding Deadlocks via Weak Deadlock Sets

A deadlock occurs in a network when two or more items prevent each other from moving and are stalled. In a general model, items are stored at vertices and each vertex (Formula presented.) has a buffer with (Formula presented.) slots. Given a route for each item toward its destination, the Deadlock Safety Problem asks whether the current state is safe, that is, it is possible to deliver each item at its destination, or is bound to deadlock, that is, any sequence of moves will end up with a set of items stalled. While when (Formula presented.) the problem is solvable in polynomial time building upon a nice characterization of YES/NO-instances, it is NP-hard on quite simple graphs as grids when (Formula presented.) and on trees when (Formula presented.). We improve on these results by means of two new tools, weak deadlock sets and wise states. We show that for general networks and (Formula presented.) a state that is wise and without weak deadlock sets—this can be recognized in polynomial time—is safe: this is indeed a strengthening of the result for (Formula presented.). We sharpen this result for trees, where we show that a wise state is safe if and only if it has no weak deadlock set. That is interesting in particular in the context of rail transportation where networks are often single-tracked and deadlock detection and avoidance focuses on local sub-networks, mostly with a tree-like structure. We pose some research questions for future investigations.