The computation of short paths in graphs with edge lengths is a pillar of graph algorithmics and network science. In a more diverse world, however, not every short path is equally valuable. We contribute to a broader view on path finding by injecting a natural fairness aspect. Our fairness notion relates to vertex-colored graphs. Herein, we seek to find short paths in which all colors should appear with roughly the same frequency. Among other results, we prove the introduced problems to be computationally intractable (NP-hard and parameterized hard with respect to the number of colors), while also presenting an encouraging algorithmic result ("fixed-parameter tractability") related to the length of the sought solution path.

翻译：边长图形中的短路径的计算是图表算法和网络科学的一个支柱。 但是, 在更多样化的世界中, 并不是每一个短路都具有同等价值。 我们通过输入自然公平方面, 有助于在路径查找上形成更广阔的视角。 我们的公正性概念与顶点颜色的图形有关。 在这里, 我们寻求找到所有颜色应该以大致相同频率出现的短路。 除其他结果外, 我们证明引入的问题在计算上是难以解决的( 在颜色数量方面硬化和参数化), 同时呈现出与所寻求的解决方案路径长度有关的令人鼓舞的算法结果( “ 固定参数可移动性 ” )。