# The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths

Preprint · Matthias Bentert, Leon Kellerhals, Rolf Niedermeier

- Archive id: arxiv:2405.18866
- Published: 2024-05-29
- arXiv: https://arxiv.org/abs/2405.18866
- Source URL: https://arxiv.org/abs/2405.18866
- PDF: https://arxiv.org/pdf/2405.18866
- Provenance: arxiv

## Abstract

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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.