2024/05/29 by Bentert, Matthias, Kellerhals, Leon, Niedermeier, Rolf
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2405.18866
We study the parameterized complexity of finding shortest s-t-paths with an additional fairness requirement. The task is to compute a shortest path in a vertex-colored graph where each color appears (roughly) equally often in the solution. We provide a complete picture of the parameterized complexity landscape of the problem with respect to structural parameters by showing a tetrachotomy including polynomial kernels, fixed-parameter tractability, XP-time algorithms (and W[1]-hardness), and para-NP-hardness.