When does FTP become FPT?
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912442902118400 |
|---|---|
| author | Bentert, Matthias Fomin, Fedor V. Golovach, Petr A. Morelle, Laure |
| author_facet | Bentert, Matthias Fomin, Fedor V. Golovach, Petr A. Morelle, Laure |
| contents | In the problem Fault-Tolerant Path (FTP), we are given an edge-weighted directed graph G = (V, E), a subset U \subseteq E of vulnerable edges, two vertices s, t \in V, and integers k and \ell. The task is to decide whether there exists a subgraph H of G with total cost at most \ell such that, after the removal of any k vulnerable edges, H still contains an s-t-path. We study whether Fault-Tolerant Path is fixed-parameter tractable (FPT) and whether it admits a polynomial kernel under various parameterizations. Our choices of parameters include: the number of vulnerable edges in the input graph, the number of safe (i.e, invulnerable) edges in the input graph, the budget \ell, the minimum number of safe edges in any optimal solution, the minimum number of vulnerable edges in any optimal solution, the required redundancy k, and natural above- and below-guarantee parameterizations. We provide an almost complete description of the complexity landscape of FTP for these parameters. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_17008 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | When does FTP become FPT? Bentert, Matthias Fomin, Fedor V. Golovach, Petr A. Morelle, Laure Data Structures and Algorithms Discrete Mathematics In the problem Fault-Tolerant Path (FTP), we are given an edge-weighted directed graph G = (V, E), a subset U \subseteq E of vulnerable edges, two vertices s, t \in V, and integers k and \ell. The task is to decide whether there exists a subgraph H of G with total cost at most \ell such that, after the removal of any k vulnerable edges, H still contains an s-t-path. We study whether Fault-Tolerant Path is fixed-parameter tractable (FPT) and whether it admits a polynomial kernel under various parameterizations. Our choices of parameters include: the number of vulnerable edges in the input graph, the number of safe (i.e, invulnerable) edges in the input graph, the budget \ell, the minimum number of safe edges in any optimal solution, the minimum number of vulnerable edges in any optimal solution, the required redundancy k, and natural above- and below-guarantee parameterizations. We provide an almost complete description of the complexity landscape of FTP for these parameters. |
| title | When does FTP become FPT? |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2506.17008 |