Fair Short Paths in Vertex-Colored Graphs

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. * This work was initiated at the 2021 Research Retreat of the Algorithmics and Computational Complexity group, Technische Universität Berlin. † We dedicate this paper to Rolf, who tragically passed away last year. We are deeply affected by this loss of our co-author, colleague, and advisor. Rolf contributed tremendously to computer science and, in particular, to parameterized algorithmics, and should have continued doing so for a long time. The computer science community shall build on the foundations he has laid.