Reachability in temporal graphs under perturbation
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_ | 1866910962366283776 |
|---|---|
| author | Enright, Jessica Larios-Jones, Laura Meeks, Kitty Pettersson, William |
| author_facet | Enright, Jessica Larios-Jones, Laura Meeks, Kitty Pettersson, William |
| contents | Reachability and other path-based measures on temporal graphs can be used to understand spread of infection, information, and people in modelled systems. Due to delays and errors in reporting, temporal graphs derived from data are unlikely to perfectly reflect reality, especially with respect to the precise times at which edges appear. To reflect this uncertainty, we consider a model in which some number $ζ$ of edge appearances may have their timestamps perturbed by $\pmδ$ for some $δ$. Within this model, we investigate temporal reachability and consider the problem of determining the maximum number of vertices any vertex can reach under these perturbations. We show that this problem is intractable in general but is efficiently solvable when $ζ$ is sufficiently large. We also give algorithms which solve this problem in several restricted settings. We complement this with some contrasting results concerning the complexity of related temporal eccentricity problems under perturbation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_19479 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Reachability in temporal graphs under perturbation Enright, Jessica Larios-Jones, Laura Meeks, Kitty Pettersson, William Discrete Mathematics Combinatorics Reachability and other path-based measures on temporal graphs can be used to understand spread of infection, information, and people in modelled systems. Due to delays and errors in reporting, temporal graphs derived from data are unlikely to perfectly reflect reality, especially with respect to the precise times at which edges appear. To reflect this uncertainty, we consider a model in which some number $ζ$ of edge appearances may have their timestamps perturbed by $\pmδ$ for some $δ$. Within this model, we investigate temporal reachability and consider the problem of determining the maximum number of vertices any vertex can reach under these perturbations. We show that this problem is intractable in general but is efficiently solvable when $ζ$ is sufficiently large. We also give algorithms which solve this problem in several restricted settings. We complement this with some contrasting results concerning the complexity of related temporal eccentricity problems under perturbation. |
| title | Reachability in temporal graphs under perturbation |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2404.19479 |