pith. sign in

arxiv: 2604.25589 · v1 · submitted 2026-04-28 · 💻 cs.DS

Testing Robustness of Temporal Transportation Networks via Interval Separators

Riccardo Dondi , Mohammad Mehdi Hosseinzadeh This is my paper

Pith reviewed 2026-05-07 15:23 UTC · model grok-4.3

classification 💻 cs.DS
keywords temporal networksinterval separatorsNP-hardnessinteger linear programmingtransportation networksrobustnesstemporal pathsdeadline
0
0 comments X

The pith

The deadline-constrained minimum interval separator problem in temporal networks is NP-hard yet solvable by integer linear programming.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper defines a new problem called d-MinIntSep that asks for the smallest collection of vertices, each assigned one contiguous time interval, such that every source-to-target temporal path whose total duration stays within a given deadline d is cut. It proves the problem is NP-hard and cannot be approximated to within a logarithmic factor of the number of vertices unless P equals NP. The authors supply an integer linear programming formulation that finds exact minimum separators and run it on both synthetic graphs and real transportation networks. The experiments show that running time grows mainly with the number of time steps, the size of the deadline, and the density of available temporal paths. Readers should care because the formulation turns robustness testing in scheduled systems into a concrete optimization task where failures are limited to time windows rather than permanent removals.

Core claim

We introduce the d-MinIntSep problem of finding a minimum-size interval separator that blocks all s-t temporal paths completable within deadline d. The problem is proven NP-hard and inapproximable to within a logarithmic factor of the vertex set size. We formulate it as an integer linear program and evaluate the approach on synthetic instances and real-world temporal networks from transportation data, where the solver's performance is governed by the temporal dimension, deadline, and path density.

What carries the argument

d-MinIntSep: the deadline-constrained minimum interval separator problem on temporal graphs, which selects the fewest vertex-interval pairs that eliminate every timely path between two given terminals.

If this is right

  • Exact minimum interval separators can be computed for moderate-sized transportation networks using standard ILP solvers.
  • No polynomial-time exact algorithm exists for the problem unless P equals NP.
  • Robustness of a temporal transportation network can be quantified by the size of the smallest interval-based failure set that disconnects all timely routes.
  • Running time of the ILP grows with the temporal dimension, the deadline value, and the density of temporal paths.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The interval-failure model could be validated by comparing computed separators against logs of actual disruptions in transit systems.
  • The same separator idea might apply directly to other scheduled domains such as packet networks or supply chains.
  • For very large instances, the ILP could serve as a base for developing fast heuristics or approximation algorithms.

Load-bearing premise

That real-world failures can be represented as single contiguous time intervals on vertices and that blocking every deadline-respecting path is enough to guarantee the desired level of robustness.

What would settle it

A small temporal graph instance with a known optimum separator size k where the integer linear program returns a value strictly larger than k.

Figures

Figures reproduced from arXiv: 2604.25589 by Mohammad Mehdi Hosseinzadeh, Riccardo Dondi.

Figure 1
Figure 1. Figure 1: An example of a temporal graph D. Consider the case that the deadline d = 4, then there exists two s-z temporal paths in D that are within the deadline: s, (sb, 4), b, (bf, 5), f, (fz, 6), z and s, (sa, 2), a, (ac, 3), c, (cf, 4), f, (fz, 5), z. Note that other s-z temporal paths have traveling time not within the deadline, for example, s, (sa, 1), a, (ab, 2), b, (bf, 5), f, (fz, 6), z has traveling time 6… view at source ↗
Figure 2
Figure 2. Figure 2: An example of temporal graph built by the reduction, w view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces the d-MinIntSep problem, a variant of the temporal separator problem in which failures are modeled as contiguous time intervals on vertices; the goal is to select a minimum-cost collection of such intervals that blocks every s-t temporal path whose total travel time respects a given deadline d. It proves that d-MinIntSep is NP-hard and inapproximable within a logarithmic factor of the vertex set (unless P=NP), supplies an integer-linear-programming formulation that encodes candidate intervals per vertex together with flow-style constraints to enforce path blocking, and reports computational experiments on synthetic instances and real transportation networks that examine the dependence of running time on the temporal dimension, the deadline, and path density.

Significance. If the hardness proofs and ILP are correct, the work supplies a clean theoretical characterization of interval-based robustness in temporal networks together with an exact solver that can be applied to moderate-sized transportation instances. The experimental section usefully quantifies how the temporal granularity and deadline affect tractability, which is directly relevant to practical network-design questions. The use of standard reduction techniques and a conventional ILP encoding is a strength; no machine-checked proofs or fully reproducible artifact are claimed.

major comments (2)
  1. [§3] §3 (Hardness proof): the reduction establishing logarithmic inapproximability must be checked to confirm that the constructed deadline d remains polynomially bounded and that every deadline-respecting path in the original instance maps to a deadline-respecting path in the new instance; without the explicit construction and the argument that the reduction preserves the deadline constraint, the inapproximability claim cannot be verified from the high-level description alone.
  2. [§4] §4 (ILP formulation): the objective and the flow-style constraints that enforce blocking of all deadline-respecting paths are only sketched; the precise definition of the binary variables (one per candidate interval per vertex) and the way the deadline is encoded in the flow network must be stated explicitly, because any mismatch between the interval variables and the temporal-path constraints would invalidate the exactness claim.
minor comments (2)
  1. [Abstract / §1] The abstract and introduction should include one or two concrete equations or a small example that illustrates how an interval separator blocks a deadline-respecting path; the current high-level description leaves the model opaque to readers unfamiliar with temporal networks.
  2. [§5] Table 1 and the experimental plots report only aggregate running times; adding columns or curves that break down the number of generated intervals, the LP relaxation gap, and the number of paths enumerated would make the influence of the temporal dimension and deadline more transparent.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major comment below and indicate the revisions we will make to strengthen the presentation.

read point-by-point responses

  1. Referee: [§3] §3 (Hardness proof): the reduction establishing logarithmic inapproximability must be checked to confirm that the constructed deadline d remains polynomially bounded and that every deadline-respecting path in the original instance maps to a deadline-respecting path in the new instance; without the explicit construction and the argument that the reduction preserves the deadline constraint, the inapproximability claim cannot be verified from the high-level description alone.

    Authors: Section 3 contains the complete reduction, including the explicit construction of the temporal network and the choice of deadline d, which is set to a value linear in the size of the original instance and hence polynomially bounded. The proof argues that the mapping preserves deadline-respecting paths: every s-t temporal path whose total travel time is at most d in the source instance corresponds to a path with identical total travel time in the constructed instance, and the interval selections block exactly the same set of paths. To make verification immediate, we will add a short paragraph that restates the polynomial bound on d and the path-preservation argument in one place. revision: yes

  2. Referee: [§4] §4 (ILP formulation): the objective and the flow-style constraints that enforce blocking of all deadline-respecting paths are only sketched; the precise definition of the binary variables (one per candidate interval per vertex) and the way the deadline is encoded in the flow network must be stated explicitly, because any mismatch between the interval variables and the temporal-path constraints would invalidate the exactness claim.

    Authors: Section 4 defines binary variables x_{v,I} for each vertex v and each candidate contiguous time interval I on its temporal domain, with the objective minimizing the sum of selection costs. The flow-style constraints are written on a time-expanded graph whose arcs are only present when the corresponding vertex-interval is not selected; flow conservation together with a sink inflow of 1 enforces that every s-t temporal path whose total travel time is at most d is cut. The deadline d is encoded by restricting the time-expanded network to time steps and edges whose cumulative travel time never exceeds d. While the current text already states these elements, we will revise the section to present the full mathematical program (variables, objective, and every family of constraints) in a single displayed block for immediate readability. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper defines the d-MinIntSep problem, establishes NP-hardness and logarithmic inapproximability via a standard reduction from a known problem under the external assumption P ≠ NP, and presents an ILP formulation as an independent modeling tool with binary variables and path-blocking constraints. Neither the hardness proof nor the ILP reduces to self-definition, fitted inputs renamed as predictions, or load-bearing self-citations; both rest on first-principles constructions and external benchmarks. Evaluation uses synthetic and real transportation datasets without circular parameter fitting or renaming of known results.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on the newly introduced problem definition together with the standard assumption that P is not equal to NP; no free parameters or invented physical entities are introduced.

axioms (1)
  • standard math P is not equal to NP
    Invoked to establish NP-hardness and logarithmic inapproximability.
invented entities (1)
  • d-MinIntSep problem no independent evidence
    purpose: Models minimum vertex interval separators that block all temporal paths completable within deadline d
    Newly defined modeling framework introduced by the paper.

pith-pipeline@v0.9.0 · 5430 in / 1281 out tokens · 65433 ms · 2026-05-07T15:23:52.347405+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [1]

    3 Kyriakos Axiotis and Dimitris Fotakis

    Akrida, E. C., Mertzios, G. B., Spirakis, P. G., and Rapto poulos, C. L., The temporal explorer who returns to the base, J. Comput. Syst. Sci. 120 (2021) 179–193, doi: 10.1016/j.jcss.2021.04.001

    work page doi:10.1016/j.jcss.2021.04.001 2021

  2. [2]

    Algorithms 2 (2006) 153–177, doi:10.1145/1150334.1150336, https://doi.org/10.1145/1150334.1150336

    Alon, N., Moshkovitz, D., and Safra, S., Algorithmic con struction of sets for k - restrictions, ACM Trans. Algorithms 2 (2006) 153–177, doi:10.1145/1150334.1150336, https://doi.org/10.1145/1150334.1150336

    work page doi:10.1145/1150334.1150336 2006

  3. [3]

    Bumpus, B. M. and Meeks, K., Edge exploration of temporal graphs, Algorithmica 85 (2023) 688–716, doi:10.1007/s00453-022-01018-7

    work page doi:10.1007/s00453-022-01018-7 2023

  4. [4]

    L., Lopes, R., Marino, A., and Silva, A., On comp uting large temporal (unilateral) connected components, J

    Costa, I. L., Lopes, R., Marino, A., and Silva, A., On comp uting large temporal (unilateral) connected components, J. Comput. Syst. Sci. 144 (2024) 103548, doi: 10.1016/J.JCSS.2024.103548

    work page doi:10.1016/j.jcss.2024.103548 2024

  5. [5]

    and Steurer, D., Analytical approach to parall el repetition, in Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - J une 03, 2014, ed

    Dinur, I. and Steurer, D., Analytical approach to parall el repetition, in Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - J une 03, 2014, ed. Shmoys, D. B. (ACM, 2014), pp. 624–633, doi:10.1145/25 91796.2591884, https://doi.org/10.1145/2591796.2591884

    work page doi:10.1145/25 2014

  6. [6]

    and Hosseinzadeh, M

    Dondi, R. and Hosseinzadeh, M. M., Dense sub-networks di scovery in temporal net- works, SN Comput. Sci. 2 (2021) 158, doi:10.1007/s42979-021-00593-w

    work page doi:10.1007/s42979-021-00593-w 2021

  7. [7]

    and Hosseinzadeh, M

    Dondi, R. and Hosseinzadeh, M. M., Colorful path detecti on in vertex-colored tem- poral, Network Science 11 (2023) 615–631

    work page 2023

  8. [8]

    and Hosseinzadeh, M

    Dondi, R. and Hosseinzadeh, M. M., Interval separators i n temporal graphs, in Pro- ceedings of Complex Networks 2025 , SCI 1265 , Vol. 3 (Springer, 2025), to appear

    work page 2025

  9. [9]

    and Lafond, M., An FPT algorithm for timeline cover, J

    Dondi, R. and Lafond, M., An FPT algorithm for timeline cover, J. Comput. Syst. Sci. 154 (2025) 103679, doi:10.1016/J.JCSS.2025.103679, https://doi.org/10.1016/j.jcss.2025.103679

    work page doi:10.1016/j.jcss.2025.103679 2025

  10. [10]

    and Lafond, M., Novel complexity results for t emporal separators with deadlines, in 19th International Symposium on Algorithms and Data Struct ures, April 29, 2026 0:57 main 14 R

    Dondi, R. and Lafond, M., Novel complexity results for t emporal separators with deadlines, in 19th International Symposium on Algorithms and Data Struct ures, April 29, 2026 0:57 main 14 R. Dondi and M. M. Hosseinzadeh WADS 2025, August 11-15, 2025, York University, Toronto, Ca nada, eds. Morin, P. and Oh, E., LIPIcs, Vol. 349 (Schloss Dagstuhl - Leibniz...

    work page doi:10.4230/lipics.w 2026

  11. [11]

    Erlebach, T., Hoffmann, M., and Kammer, F., On temporal g raph exploration, J. Comput. Syst. Sci. 119 (2021) 1–18, doi:10.1016/j.jcss.2021.01.005

    work page doi:10.1016/j.jcss.2021.01.005 2021

  12. [12]

    , and Zschoche, P., Temporal graph classes: A view through temporal separators, Theor

    Fluschnik, T., Molter, H., Niedermeier, R., Renken, M. , and Zschoche, P., Temporal graph classes: A view through temporal separators, Theor. Comput. Sci. 806 (2020) 197–218, doi:10.1016/j.tcs.2019.03.031

    work page doi:10.1016/j.tcs.2019.03.031 2020

  13. [13]

    B., and Spirakis, P

    Hamm, T., Klobas, N., Mertzios, G. B., and Spirakis, P. G ., The complexity of tem- poral vertex cover in small-degree graphs, in Proceedings of the AAAI Conference on Artificial Intelligence , Vol. 36 (2022), pp. 10193–10201, doi:10.1609/aaai.v36i9 .21259

    work page doi:10.1609/aaai.v36i9 2022

  14. [14]

    Harutyunyan, H. A., Koupayi, K., and Pankratov, D., Tem poral separators with deadlines, in 34th International Symposium on Algorithms and Computatio n, ISAAC 2023, December 3-6, 2023, Kyoto, Japan , eds. Iwata, S. and Kakimura, N., LIPIcs, Vol. 283 (Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informat ik, 2023), pp. 38:1–38:19, doi:10.4230/LIPICS.ISAAC.2023.38

    work page doi:10.4230/lipics.isaac.2023.38 2023

  15. [15]

    Holme, P., Modern temporal network theory: a colloquiu m, The European Physical Journal B 88 (2015) 234, doi:10.1140/epjb/e2015-60657-4

    work page doi:10.1140/epjb/e2015-60657-4 2015

  16. [16]

    and Saram¨ aki, J., A map of approaches to tempo ral networks, Temporal Network Theory (2019) 1–24, doi:10.1007/978-3-030-23495-9 \ 1

    Holme, P. and Saram¨ aki, J., A map of approaches to tempo ral networks, Temporal Network Theory (2019) 1–24, doi:10.1007/978-3-030-23495-9 \ 1

    work page doi:10.1007/978-3-030-23495-9 2019

  17. [17]

    M., Cannataro, M., Guzzi, P

    Hosseinzadeh, M. M., Cannataro, M., Guzzi, P. H., and Do ndi, R., Temporal networks in biology and medicine: a survey on models, algorithms, and tools, Netw. Model. Anal. Health Informatics Bioinform. 12 (2023) 10, doi:10.1007/S13721-022-00406-X

    work page doi:10.1007/s13721-022-00406-x 2023

  18. [18]

    M., and Kumar, A., Connectivit y and inference problems for temporal networks, J

    Kempe, D., Kleinberg, J. M., and Kumar, A., Connectivit y and inference problems for temporal networks, J. Comput. Syst. Sci. 64 (2002) 820–842, doi:10.1006/jcss. 2002.1829

    work page doi:10.1006/jcss 2002

  19. [19]

    K., Mladenovi´ c, M

    Kujala, R., Weckstr¨ om, C., Darst, R. K., Mladenovi´ c, M. N., and Saram¨ aki, J., A collection of public transport network data sets for 25 citi es, Scientific data 5 (2018) 1–14

    work page 2018

  20. [20]

    and Silva, A., Eulerian walks in temporal gra phs, Algorithmica 85 (2023) 805–830, doi:10.1007/S00453-022-01021-Y

    Marino, A. and Silva, A., Eulerian walks in temporal gra phs, Algorithmica 85 (2023) 805–830, doi:10.1007/S00453-022-01021-Y

    work page doi:10.1007/s00453-022-01021-y 2023

  21. [21]

    12 (2016) 239–280, doi:10.1080/15427951.2016.1177801

    Michail, O., An introduction to temporal graphs: An alg orithmic perspective, Internet Math. 12 (2016) 239–280, doi:10.1080/15427951.2016.1177801

    work page doi:10.1080/15427951.2016.1177801 2016

  22. [22]

    Colloquium Comput

    Nelson, J., A note on set cover inapproximability independent of universe size, Electron. Colloquium Comput. Complex. TR07-105 (2007), https://eccc.weizmann.ac.il/eccc-reports/200 7/TR07-105/index.html

    work page 2007

  23. [23]

    Rozenshtein, P., Bonchi, F., Gionis, A., Sozio, M., and Tatti, N., Finding events in temporal networks: segmentation meets densest subgraph di scovery, Knowl. Inf. Syst. 62 (2020) 1611–1639, doi:10.1007/s10115-019-01403-9

    work page doi:10.1007/s10115-019-01403-9 2020

  24. [24]

    Rozenshtein, P., Tatti, N., and Gionis, A., The network -untangling problem: from interactions to activity timelines, Data Min. Knowl. Discov. 35 (2021) 213–247, doi: 10.1007/s10618-020-00717-5

    work page doi:10.1007/s10618-020-00717-5 2021

  25. [25]

    VLDB Endow

    Wu, H., Cheng, J., Huang, S., Ke, Y., Lu, Y., and Xu, Y., Pa th problems in temporal graphs, Proc. VLDB Endow. 7 (2014) 721–732, doi:10.14778/2732939.2732945

    work page doi:10.14778/2732939.2732945 2014

  26. [26]

    , Efficient algorithms for temporal path computation, IEEE Trans

    Wu, H., Cheng, J., Ke, Y., Huang, S., Huang, Y., and Wu, H. , Efficient algorithms for temporal path computation, IEEE Trans. Knowl. Data Eng. 28 (2016) 2927–2942, doi:10.1109/TKDE.2016.2594065

    work page doi:10.1109/tkde.2016.2594065 2016

  27. [27]

    Zschoche, P., Fluschnik, T., Molter, H., and Niedermei er, R., The complexity of finding small separators in temporal graphs, J. Comput. Syst. Sci. 107 (2020) 72–92, doi:10.1016/j.jcss.2019.07.006

    work page doi:10.1016/j.jcss.2019.07.006 2020