Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.25589 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913069108559872 |
|---|---|
| author | Dondi, Riccardo Hosseinzadeh, Mohammad Mehdi |
| author_facet | Dondi, Riccardo Hosseinzadeh, Mohammad Mehdi |
| contents | This paper addresses the problem of identifying time interval separators in temporal networks. We introduce d-MinIntSep, a new variant of the temporal separator problem, which models failures as time intervals assigned to vertices and aims to block all temporal paths between a source and a target that can be completed within a given deadline d. We prove that the d-MinIntSep problem is NP-hard and hard to approximate within a logarithmic function of the size of the vertex set, assuming P is not equal to NP, and we propose an Integer Linear Programming (ILP) formulation to compute minimum interval separators. This latter method is evaluated on synthetic and real-world temporal networks derived from transportation datasets. The experimental results show that the running time is strongly influenced by the temporal dimension, the imposed deadline, and the density of temporal paths. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_25589 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Testing Robustness of Temporal Transportation Networks via Interval Separators Dondi, Riccardo Hosseinzadeh, Mohammad Mehdi Data Structures and Algorithms This paper addresses the problem of identifying time interval separators in temporal networks. We introduce d-MinIntSep, a new variant of the temporal separator problem, which models failures as time intervals assigned to vertices and aims to block all temporal paths between a source and a target that can be completed within a given deadline d. We prove that the d-MinIntSep problem is NP-hard and hard to approximate within a logarithmic function of the size of the vertex set, assuming P is not equal to NP, and we propose an Integer Linear Programming (ILP) formulation to compute minimum interval separators. This latter method is evaluated on synthetic and real-world temporal networks derived from transportation datasets. The experimental results show that the running time is strongly influenced by the temporal dimension, the imposed deadline, and the density of temporal paths. |
| title | Testing Robustness of Temporal Transportation Networks via Interval Separators |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2604.25589 |