PACT · Parameterized Analysis of Constrained Transitions

Pathfinding in graphs is one of the most fundamental problems in graph theory. Dijkstra’s algorithm for finding shortest paths between nodes has been a part of standard computer science curriculum for decades. However, in several applications in logistics and operations research, the desired path should satisfy some additional constraints, and thus cannot be found by a straightforward application of Dijkstra’s algorithm. For example, on some crossroads turning right is not permitted, i.e. certain edges of the graph cannot appear as consecutive edges on the path. Another example occurs in pickup and delivery route planning, where each pick-up location needs to be visited beforethe corresponding destination. In other words, the ordering of the vertices on the path needs to respect a given partial order. The above scenarios might seem very different, but they share one key property that makes pathfinding difficult. Namely, Dijkstra’s algorithm relies on triangle inequality, which does not hold in the above cases. The aim of this project is to design novel algorithms that overcome this obstacle and to conduct a systematic study on different variants of the pathfinding problem with traversal constraints. To achieve this, we will employ parameterized complexity tools, which enable us to study the complexity of problems with respect to multiple parameters describing the input and output data.