Designing sparse temporal graphs satisfying connectivity requirements

Thomas Bellitto, Jules Bouton Popper, Justine Cauvi, Bruno Escoffier, Raphaëlle Maistre-Matus · 2026

Read Designing sparse temporal graphs satisfying connectivity requirements by Thomas Bellitto, Jules Bouton Popper, Justine Cauvi, Bruno Escoffier, Raphaëlle Maistre-Matus (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-27227.txt.

Introduction

Bellitto and four colleagues design sparse temporal graphs that satisfy partial connectivity requirements with as few edges as possible. Full connectivity of n vertices needs at least 2n minus 4 edges, a classic result in graph and gossip theory. Their Connectivity Request Satisfaction problem starts from a directed request graph. An arc from u to v demands a route from u to v. The goal is a temporal graph on the same vertices meeting every request. For directed builds they prove bounds on the number of temporal edges needed.

Catalog record

CREATORThomas Bellitto, Jules Bouton Popper, Justine Cauvi, Bruno Escoffier, Raphaëlle Maistre-Matus
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE54582
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.27227

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Designing sparse temporal graphs satisfying connectivity requirements Thomas Bellitto, Jules Bouton Popper, Justine Cauvi, Bruno Escoffier, Raphaëlle Maistre-Matus 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 2 ​ n − 4 2n-4 edges where n 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 u to v v means that we need to be able to go from u u to v 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 n-\mathrm{cc}+\mathrm{dfvs} where cc \mathrm{cc} is the number of connected component of the request graph and dfvs \mathrm{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 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. 1 Introduction A temporal graph is a powerful tool to model and analyse complex real-world networks such as public transit networks, phone call networks, social networks or biological networks. A temporal graph allows for edges to change over time. More precisely, it is defined as a graph with each edge being equipped with a set of appearance times. Connectivity in this context is defined by journeys, that is a walk where edges are traversed one after the other in time. (Shortest) paths, connectivity and exploration problems have been at the core of the study of temporal graphs [ 3 , 4 , 6 , 11 , 23 , 31 , 32 ] . While some notions and algorithms quite easily transfer from static to temporal graphs, some other notions (such as spanning trees) and problems turn out to be much more complex in temporal graphs. Among those, a famous result in temporal graphs concerns the number of edges in a connected temporal graphs. In static graphs, minimal (in term of number of edges) graphs that connect a set of n vertices are trees, which have n-1 edges. In temporal graphs, the question is more complex: how many (temporal) edges do we need to connect a set of n vertices? This problem has been introduced in the literature as the gossip problem in the context of optimal scheduling of phone calls (see e.g. [ 21 ] for a survey on gossiping), and it is known that for n\geq 4 the minimum number of edges is 2n-4 (see Figure 1 for an illustration) [ 5 , 19 ] . Most of the works in that field consider that at most one phone call can be done between two persons. It was shown in [ 18 ] that deciding if a given graph is label-connected, that is every edge can be given an appearance time such that there is a journey between every pair of vertices, is NP-complete and a characterization of label-connected graphs with 2n-4 edges was proposed. 1 n-5 n-4 n-1 n-3 n-2 n n+1 n+2 2n-5 2n-4 Figure 1: A solution to the gossip problem with 2n-4 edges. A label next to an edge corresponds to the appearance time of the edge. Every vertex can reach every other vertex by a path that uses edges with increasing appearance time. However, if we only need to connect some vertices of the graph to some others, we would expect to be able to do it at a smaller cost. Still, while this can be relevant for many practical applications of temporal graphs, very little is known about it. We thus introduce a generalization of the gossip problem where we do not require full connectivity of the graph but instead we are given as input a set of ordered pairs (u,v) that we have to connect. These connectivity requests can be seen as a directed graphs where an arc (u,v) means that we need to be able to go from u to v in the temporal graph \mathcal{G} that we create. Hence, the gossip problem is the case where the input is a complete graph. Contributions As explained above, given a directed graph R=(V,A) called the request graph, we want to design a temporal graph \mathcal{G} on the same set of vertices, such that for every (u,v) in A there is a journey from u to v in \mathcal{G} . We first consider the directed version of the problem, where we want to design a directed temporal graph. We establish a strong link between our problem and the well known feedback vertex set problem. More precisely, we show that the minimal number of temporal edges we need to satisfy all the connectivity requirements is n-cc+f , where n=|V| , cc is the number of connected components of R , and f is the size of a minimum feedback vertex set in R . This characterization shows in particular that the problem is NP-hard. We then tackle the problem in undirected temporal graphs. This is the case of the gossip problem mentioned above, which states that 2n-4 edges is the minimum number of temporal edges when R is a complete graph. On the other hand, it is easy to see that n-cc edges are always necessary (where cc is the number of connected components of R ). We tackle the question to determine when this lower bound is reached, i.e., when the minimum number of temporal edges needed to satisfy the connectivity requirements is equal to n-cc . We provide a characterization when R is strongly connected: in this case, we show that there exists a solution which is a tree if and only if R satisfies a property that we call walk-Helly, which is a Helly-like property on walks in graphs. We also show a polynomial time algorithm that builds such a tree when it exists. This easily extends to the case where every connected components of R are strongly connected. Organization: Section 2 formally introduces the problems we consider in this article. The directed case is dealt with in Section 3 , while the undirected case is studied in Section 4 . Some open questions are given in the conclusion in Section 5 . Related works Graph realization problems have been studied on static graphs since the 1960s and consist of finding a graph that satisfy a given property P or answering no if such a graph does not exist [ 13 , 20 ] . It was recently

Read the complete text