Search Results

Documents authored by Brunelli, Filippo

Document
DOI: 10.4230/LIPIcs.SAND.2026.5
Complexity Gaps Between Point and Interval Temporal Graphs for Some Reachability Problems

Authors: Guillaume Aubian, Filippo Brunelli, Feodor F. Dragan, Guillaume Ducoffe, Michel Habib, Allen Ibiapina, and Laurent Viennot

Published in: LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)

Abstract
Temporal graphs arise when modeling interactions that evolve over time. They usually come in several flavors, depending on the number of parameters used to describe the temporal aspects of the interactions: time of appearance, duration, delay of transmission. In the point model, edges appear at specific points in time, whereas in the more general interval model, edges can be present over specific time intervals. In both models, the delay for traversing an edge can change with each edge appearance. When time is discrete, the two models are equivalent in the sense that the presence of an edge during an interval is equivalent to a sequence of point-in-time occurrences of the edge. However, this transformation can drastically change the size of the input and has implications for complexity. Indeed, we show a gap between the two models with respect to the complexity of the classical problem of computing a fastest temporal path from a source vertex to a target vertex, i.e., a path where edges can be traversed one after another in time and such that the total duration from source to target is minimized. It can be solved in near-linear time in the point model, while we show that the interval model requires quadratic time under classical assumptions of fine-grained complexity. With respect to linear time, our lower bound implies a factor of the number of vertices, while the best known algorithm has a factor of the number of underlying edges. We also show a similar complexity gap for computing a shortest temporal path, i.e., a temporal path with a minimum number of edges. Here our lower bound matches known upper bounds up to a logarithmic factor. Interestingly, we show that near-linear time for fastest temporal path computation is possible in the interval model when it is restricted to uniform delay zero, i.e., when traversing an edge is instantaneous. However, this special case is not exempt from our lower bound for shortest temporal path computation. These two results should be contrasted with the computation of a foremost temporal path, i.e., a temporal path that arrives as early as possible. It is well known that this computation can be solved in near-linear time in both models. We also show that there is no gap in testing the all-to-all temporal connectivity of a temporal graph. We demonstrate a quadratic lower bound that applies to both the interval and point models and aligns with the existing upper bounds.
Cite as

Guillaume Aubian, Filippo Brunelli, Feodor F. Dragan, Guillaume Ducoffe, Michel Habib, Allen Ibiapina, and Laurent Viennot. Complexity Gaps Between Point and Interval Temporal Graphs for Some Reachability Problems. In 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 373, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{aubian_et_al:LIPIcs.SAND.2026.5,
  author =	{Aubian, Guillaume and Brunelli, Filippo and Dragan, Feodor F. and Ducoffe, Guillaume and Habib, Michel and Ibiapina, Allen and Viennot, Laurent},
  title =	{{Complexity Gaps Between Point and Interval Temporal Graphs for Some Reachability Problems}},
  booktitle =	{5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)},
  pages =	{5:1--5:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-427-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{373},
  editor =	{Mertzios, George B. and Richa, Andr\'{e}a W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.5},
  URN =		{urn:nbn:de:0030-drops-262395},
  doi =		{10.4230/LIPIcs.SAND.2026.5},
  annote =	{Keywords: Temporal graphs, Dynamic networks, Time-dependent networks, Temporal connectivity, Foremost, Fastest or Shortest temporal path, Fine-grained complexity}
}
Document
DOI: 10.4230/LIPIcs.SAND.2023.4
Computing Temporal Reachability Under Waiting-Time Constraints in Linear Time

Authors: Filippo Brunelli and Laurent Viennot

Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)

Abstract
This paper proposes a simple algorithm for computing single-source reachability in a temporal graph under waiting-time constraints, that is when waiting at each node is bounded by some time constraints. Given a space-time representation of a temporal graph, and a source node, the algorithm computes in linear-time which nodes and temporal edges are reachable through a constrained temporal walk from the source.
Cite as

Filippo Brunelli and Laurent Viennot. Computing Temporal Reachability Under Waiting-Time Constraints in Linear Time. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 4:1-4:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{brunelli_et_al:LIPIcs.SAND.2023.4,
  author =	{Brunelli, Filippo and Viennot, Laurent},
  title =	{{Computing Temporal Reachability Under Waiting-Time Constraints in Linear Time}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{4:1--4:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-275-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{257},
  editor =	{Doty, David and Spirakis, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.4},
  URN =		{urn:nbn:de:0030-drops-179402},
  doi =		{10.4230/LIPIcs.SAND.2023.4},
  annote =	{Keywords: temporal reachability, temporal graph, temporal path, temporal walk, waiting-time constraints, restless temporal walk, linear time}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact