Parameterized Restless Temporal Path
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_ | 1866915377049501696 |
|---|---|
| author | Cauvi, Justine Viennot, Laurent |
| author_facet | Cauvi, Justine Viennot, Laurent |
| contents | Recently, Bumpus and Meeks introduced a purely temporal parameter, called vertex-interval-membership-width, which is promising for the design of fixed-parameter tractable (FPT) algorithms for vertex reachability problems in temporal graphs. We study this newly introduced parameter for the problem of restless temporal paths, in which the waiting time at each node is restricted. In this article, we prove that, in the interval model, where arcs are present for entire time intervals, finding a restless temporal path is NP-hard even if the vertex-interval-membership-width is equal to three. We exhibit FPT algorithms for the point model, where arcs are present at specific points in time, both with uniform delay one and arbitrary positive delays. In the latter case, this comes with a slight additional computational cost. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_05760 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Parameterized Restless Temporal Path Cauvi, Justine Viennot, Laurent Computational Complexity Data Structures and Algorithms Recently, Bumpus and Meeks introduced a purely temporal parameter, called vertex-interval-membership-width, which is promising for the design of fixed-parameter tractable (FPT) algorithms for vertex reachability problems in temporal graphs. We study this newly introduced parameter for the problem of restless temporal paths, in which the waiting time at each node is restricted. In this article, we prove that, in the interval model, where arcs are present for entire time intervals, finding a restless temporal path is NP-hard even if the vertex-interval-membership-width is equal to three. We exhibit FPT algorithms for the point model, where arcs are present at specific points in time, both with uniform delay one and arbitrary positive delays. In the latter case, this comes with a slight additional computational cost. |
| title | Parameterized Restless Temporal Path |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.05760 |