  The computation of short paths in graphs with arc lengths is a pillar of
graph algorithmics and network science. In a more diverse world, however, not
every short path is equally valuable. For the setting where each vertex is
assigned to a group (color), we provide a framework to model multiple natural
fairness aspects. We seek to find short paths in which the number of
occurrences of each color is within some given lower and upper bounds. Among
other results, we prove the introduced problems to be computationally
intractable (NP-hard and parameterized hard with respect to the number of
colors) even in very restricted settings (such as each color should appear with
exactly the same frequency), while also presenting an encouraging algorithmic
result ("fixed-parameter tractability") related to the length of the sought
solution path for the general problem.

Data Structures and Algorithms;Computational Complexity