Search Results

Documents authored by Dragan, Feodor F.

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.SoCG.2018.22
Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs

Authors: Jérémie Chalopin, Victor Chepoi, Feodor F. Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, and Yann Vaxès

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
In this paper, we study Gromov hyperbolicity and related parameters, that represent how close (locally) a metric space is to a tree from a metric point of view. The study of Gromov hyperbolicity for geodesic metric spaces can be reduced to the study of graph hyperbolicity. Our main contribution in this note is a new characterization of hyperbolicity for graphs (and for complete geodesic metric spaces). This characterization has algorithmic implications in the field of large-scale network analysis, which was one of our initial motivations. A sharp estimate of graph hyperbolicity is useful, {e.g.}, in embedding an undirected graph into hyperbolic space with minimum distortion [Verbeek and Suri, SoCG'14]. The hyperbolicity of a graph can be computed in polynomial-time, however it is unlikely that it can be done in subcubic time. This makes this parameter difficult to compute or to approximate on large graphs. Using our new characterization of graph hyperbolicity, we provide a simple factor 8 approximation algorithm for computing the hyperbolicity of an n-vertex graph G=(V,E) in optimal time O(n^2) (assuming that the input is the distance matrix of the graph). This algorithm leads to constant factor approximations of other graph-parameters related to hyperbolicity (thinness, slimness, and insize). We also present the first efficient algorithms for exact computation of these parameters. All of our algorithms can be used to approximate the hyperbolicity of a geodesic metric space.
Cite as

Jérémie Chalopin, Victor Chepoi, Feodor F. Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, and Yann Vaxès. Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chalopin_et_al:LIPIcs.SoCG.2018.22,
  author =	{Chalopin, J\'{e}r\'{e}mie and Chepoi, Victor and Dragan, Feodor F. and Ducoffe, Guillaume and Mohammed, Abdulhakeem and Vax\`{e}s, Yann},
  title =	{{Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{22:1--22:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.22},
  URN =		{urn:nbn:de:0030-drops-87356},
  doi =		{10.4230/LIPIcs.SoCG.2018.22},
  annote =	{Keywords: Gromov hyperbolicity, Graphs, Geodesic metric spaces, Approximation algorithms}
}
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