The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910462197628928 |
|---|---|
| author | Bentert, Matthias Kellerhals, Leon Niedermeier, Rolf |
| author_facet | Bentert, Matthias Kellerhals, Leon Niedermeier, Rolf |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_18866 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths Bentert, Matthias Kellerhals, Leon Niedermeier, Rolf Data Structures and Algorithms Computational Complexity 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. |
| title | The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2405.18866 |