Search Results

Documents authored by Cauvi, Justine

Document
DOI: 10.4230/LIPIcs.SAND.2026.15
Designing Sparse Temporal Graphs Satisfying Connectivity Requirements

Authors: Thomas Bellitto, Jules Bouton Popper, Justine Cauvi, Bruno Escoffier, and Raphaëlle Maistre-Matus

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

Abstract
Connectivity of temporal graphs has been widely studied both as graph theory and as gossip theory. In particular, it is well known that in order to connect every vertex to every other, a temporal graph needs to have at least 2n-4 edges where n is the number of vertices. This paper investigates the optimal number of edges required to satisfy partial connectivity requirements. We introduce the problem of Connectivity Request Satisfaction where we are given a directed graph that we call the request graph, where an arc from u to v means that we need to be able to go from u to v. Our goal is to build a temporal graph on the same vertex set with as few temporal edges as possible that would satisfy all the requests. When the graph we build is directed, we prove that the number of temporal arcs required is n-cc+dfvs where cc is the number of connected component of the request graph and dfvs is the size of its smallest directed feedback vertex set. It follows that the problem is NP-complete but inherits fixed parameter tractability properties of Directed Feedback Vertex Set. When the graph we build is undirected, we establish a characterization of strongly connected request graphs that admit a solution with n-1 edges: it is possible if and only if any set of pairwise non-vertex-disjoint closed walks all share a common vertex. We prove that this criteria can be tested in polynomial time.
Cite as

Thomas Bellitto, Jules Bouton Popper, Justine Cauvi, Bruno Escoffier, and Raphaëlle Maistre-Matus. Designing Sparse Temporal Graphs Satisfying Connectivity Requirements. In 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 373, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bellitto_et_al:LIPIcs.SAND.2026.15,
  author =	{Bellitto, Thomas and Popper, Jules Bouton and Cauvi, Justine and Escoffier, Bruno and Maistre-Matus, Rapha\"{e}lle},
  title =	{{Designing Sparse Temporal Graphs Satisfying Connectivity Requirements}},
  booktitle =	{5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)},
  pages =	{15:1--15:17},
  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.15},
  URN =		{urn:nbn:de:0030-drops-262499},
  doi =		{10.4230/LIPIcs.SAND.2026.15},
  annote =	{Keywords: Temporal Graphs, Connectivity, Gossiping, Network Design}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.24
Foremost, Fastest, Shortest: Temporal Graph Realization Under Various Path Metrics

Authors: Justine Cauvi, Nils Morawietz, and Laurent Viennot

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
In this work, we follow the current trend on temporal graph realization, where one is given a property P and the goal is to determine whether there is a temporal graph, that is, a graph where the edge set changes over time, with property P. We consider the problems where the given property P is a prescribed matrix for the duration, length, or earliest arrival time of pairwise temporal paths. This means that we are given a matrix D and ask whether there is a temporal graph such that for any ordered pair of vertices (s,t), D_{s,t} equals the duration (length, or earliest arrival time, respectively) of any temporal path from s to t minimizing that specific temporal path metric. For shortest and earliest arrival temporal paths, we are the first to consider these problems as far as we know. We analyze these problems for many settings such as: strict and non-strict paths, periodic and non-periodic temporal graphs, and limited number of labels per edge (limited number of occurrences per edge over time). In contrast to all other path metrics, we show that for the earliest arrival times, we can achieve polynomial-time algorithms in periodic and non-periodic temporal graphs and for strict and and non-strict paths. However, the problem becomes NP-hard when the matrix does not contain a single integer but a set or range of possible allowed values. As we show, the problem can still be solved efficiently in this scenario, when the number of entries with more than one value is small, that is, we develop an FPT-algorithm for the number of such entries. For the setting of fastest paths, we achieve new hardness results that answers an open question by Klobas, Mertzios, Molter, and Spirakis [Theor. Comput. Sci. '25] about the parameterized complexity of the problem with respect to the vertex cover number and significantly improves over a previous hardness result for the feedback vertex set number. When considering shortest paths, we show that the periodic versions are polynomial-time solvable whereas the non-periodic versions become NP-hard.
Cite as

Justine Cauvi, Nils Morawietz, and Laurent Viennot. Foremost, Fastest, Shortest: Temporal Graph Realization Under Various Path Metrics. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 24:1-24:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cauvi_et_al:LIPIcs.STACS.2026.24,
  author =	{Cauvi, Justine and Morawietz, Nils and Viennot, Laurent},
  title =	{{Foremost, Fastest, Shortest: Temporal Graph Realization Under Various Path Metrics}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{24:1--24:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.24},
  URN =		{urn:nbn:de:0030-drops-255139},
  doi =		{10.4230/LIPIcs.STACS.2026.24},
  annote =	{Keywords: network design, temporal paths, foremost paths, fastest paths, shortest paths, non-strict paths, periodic temporal graphs}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2024.1
Landmark Hub Labeling: Improved Bounds and Faster Query Answering

Authors: Justine Cauvi, Ruoying Li, and Sabine Storandt

Published in: OASIcs, Volume 123, 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)

Abstract
Hub Labeling (HL) is a state-of-the-art method for answering shortest-distance queries between node pairs in weighted graphs. It provides very fast query times but also requires considerable additional space to store the label information. Recently, a generalization of HL, called Landmark Hub Labeling (LHL), has been proposed, that conceptionally allows a storage of fewer label information without compromising the optimality of the query result. However, query answering with LHL was shown to be slower than with HL, both in theory and practice. Furthermore, it was not clear whether there are graphs with a substantial space reduction when using LHL instead of HL. In this paper, we describe a new way of storing label information of an LHL such that query times are significantly reduced and then asymptotically match those of HL. Thus, we alleviate the so far greatest shortcoming of LHL compared to HL. Moreover, we show that for the practically relevant hierarchical versions (HHL and HLHL), there are graphs in which the label size of an optimal HLHL is a factor of Θ(√ n) smaller than that of an optimal HHL. We establish further novel bounds between different labeling variants. Additionally, we provide a comparative experimental study between approximation algorithms for HL and LHL. We demonstrate that label sizes in an LHL are consistently smaller than those of HL across diverse benchmark graphs, including road networks.
Cite as

Justine Cauvi, Ruoying Li, and Sabine Storandt. Landmark Hub Labeling: Improved Bounds and Faster Query Answering. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 1:1-1:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cauvi_et_al:OASIcs.ATMOS.2024.1,
  author =	{Cauvi, Justine and Li, Ruoying and Storandt, Sabine},
  title =	{{Landmark Hub Labeling: Improved Bounds and Faster Query Answering}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{1:1--1:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-350-8},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{123},
  editor =	{Bouman, Paul C. and Kontogiannis, Spyros C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2024.1},
  URN =		{urn:nbn:de:0030-drops-211892},
  doi =		{10.4230/OASIcs.ATMOS.2024.1},
  annote =	{Keywords: Route Planning, Shortest Path, Hub Labeling}
}
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