The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
<|reference_start|>The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths: 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.<|reference_end|>
@article{bentert2024the,
    title={The Structural Complexity Landscape of Finding Balance-Fair Shortest
  Paths},
    author={Matthias Bentert and Leon Kellerhals and Rolf Niedermeier},
    journal={arXiv preprint arXiv:2405.18866},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.18866},
    primaryClass={cs.DS cs.CC}
}