Search Results

Documents authored by Ibiapina, Allen

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.1
Snapshot Disjointness in Temporal Graphs

Authors: Allen Ibiapina and Ana Silva

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

Abstract
In the study of temporal graphs, only paths respecting the flow of time are relevant. In this context, many concepts of walks disjointness have been proposed over the years, and the validity of Menger’s Theorem, as well as the complexity of related problems, has been investigated. Menger’s Theorem states that the maximum number of disjoint paths between two vertices is equal to the minimum number of vertices required to disconnect them. In this paper, we introduce and investigate a type of disjointness that is only time dependent. Two walks are said to be snapshot disjoint if they are not active in a same snapshot (also called timestep). The related paths and cut problems are then defined and proved to be W[1]-hard and XP-time solvable when parameterized by the size of the solution. Additionally, in the light of the definition of Mengerian graphs given by Kempe, Kleinberg and Kumar in their seminal paper (STOC'2000), we define a Mengerian graph for time as a graph G for which there is no time labeling for its edges where Menger’s Theorem does not hold in the context of snapshot disjointness. We then give a characterization of Mengerian graphs in terms of forbidden structures and provide a polynomial-time recognition algorithm. Finally, we also prove that, given a temporal graph (G,λ) and a pair of vertices s,z ∈ V(G), deciding whether at most h multiedges can separate s from z is NP-complete, where one multiedge uv is the set of all edges with endpoints u and v.
Cite as

Allen Ibiapina and Ana Silva. Snapshot Disjointness in Temporal Graphs. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ibiapina_et_al:LIPIcs.SAND.2023.1,
  author =	{Ibiapina, Allen and Silva, Ana},
  title =	{{Snapshot Disjointness in Temporal Graphs}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{1:1--1:20},
  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.1},
  URN =		{urn:nbn:de:0030-drops-179379},
  doi =		{10.4230/LIPIcs.SAND.2023.1},
  annote =	{Keywords: Temporal graphs, Menger’s Theorem, Snapshot disjointness}
}
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