DROPS

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.SAND.2025.3

Temporal Connectivity Augmentation

Authors: Thomas Bellitto, Jules Bouton Popper, and Bruno Escoffier

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract

Connectivity in temporal graphs relies on the notion of temporal paths, in which edges follow a chronological order (either strict or non-strict). In this work, we investigate the question of how to make a temporal graph connected. More precisely, we tackle the problem of finding, among a set of proposed temporal edges, the smallest subset such that its addition makes the graph temporally connected (TCA). We study the complexity of this problem and variants, under restricted lifespan of the graph, i.e. the maximum time step in the graph. Our main result on TCA is that for any fixed lifespan at least 2, it is NP-complete in both the strict and non-strict setting. We additionally provide a set of restrictions in the non-strict setting which makes the problem solvable in polynomial time and design an algorithm achieving this complexity. Interestingly, we prove that the source variant (making a given vertex a source in the augmented graph) is as difficult as TCA. On the opposite, we prove that the version where a list of connectivity demands has to be satisfied is solvable in polynomial time, when the size of the list is fixed. Finally, we highlight a variant of the previous case for which even with two pairs the problem is already NP-hard.

Cite as

Thomas Bellitto, Jules Bouton Popper, and Bruno Escoffier. Temporal Connectivity Augmentation. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bellitto_et_al:LIPIcs.SAND.2025.3,
  author =	{Bellitto, Thomas and Popper, Jules Bouton and Escoffier, Bruno},
  title =	{{Temporal Connectivity Augmentation}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.3},
  URN =		{urn:nbn:de:0030-drops-230565},
  doi =		{10.4230/LIPIcs.SAND.2025.3},
  annote =	{Keywords: Temporal graph, temporal connectivity}
}

Search Results

Documents authored by Popper, Jules Bouton

Designing Sparse Temporal Graphs Satisfying Connectivity Requirements

Abstract

Cite as

Temporal Connectivity Augmentation

Abstract

Cite as

Thanks for your feedback!

Could not send message