  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.
