Realization of Temporally Connected Graphs Based on Degree Sequences
Arnaud Casteigts, Michelle Döring, Nils Morawietz · 2025
Read Realization of Temporally Connected Graphs Based on Degree Sequences by Arnaud Casteigts, Michelle Döring, Nils Morawietz (2025) 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-2504-17743.txt.
Introduction
Arnaud Casteigts, Michelle Doring, and Nils Morawietz asked in 2025 which degree sequences can be realized as temporally connected graphs. In a temporal graph, edges carry time labels, and a path must respect the order of time. Deciding whether a given graph can be labeled to be temporally connected is known to be hard, so the authors relax the question to degree sequences alone.
Their main result fully characterizes the feasible cases. Recognition runs in linear time for ordinary degree sequences and near-linear time for multigraph ones, and the checks can be made constructive at little cost: an algorithm builds the graph itself. The catalog title appends a conference note; the clean title governs. Readers get a complete answer where the original problem was intractable, by changing what is asked.
Catalog record
| CREATOR | Arnaud Casteigts, Michelle Döring, Nils Morawietz |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 98 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-17743
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Realization of Temporally Connected Graphs Based on Degree Sequences Thanks: A preliminary version of this work appeared in the Proceedings of the 36th International Symposium on Algorithms and Computation (ISAAC’25), Schloss Dagstuhl – Leibniz-Zentrum für Informatik. This full version contains all missing proofs. Arnaud Casteigts, Michelle Döring, Nils Morawietz Abstract Given an undirected graph G G , the problem of deciding whether G G admits a simple and proper time-labeling that makes it temporally connected is known to be NP-hard (Göbel et al., 1991). In this article, we relax this problem and ask whether a given degree sequence can be realized as a temporally connected graph. Our main results are a complete characterization of the feasible cases, and a recognition algorithm that runs in 𝒪 ( n ) \mathcal{O}(n) time for graphical degree sequences (realized as simple temporal graphs) and in 𝒪 ( n + m ) \mathcal{O}(n+m) time for multigraphical degree sequences (realized as non-simple temporal graphs, where the number of time labels on an edge corresponds to the multiplicity of the edge in the multigraph). In fact, these algorithms can be made constructive at essentially no cost, we present a 𝒪 ( n + m ) \mathcal{O}(n+m) time algorithm that outputs, for a given (multi)graphical degree sequence 𝐝 \mathbf{d} , a temporally connected graph whose underlying (multi)graph is a realization of 𝐝 \mathbf{d} , if one exists. Department of Computer Science, University of Geneva, Switzerland LaBRI, Université de Bordeaux, [email protected]://orcid.org/0000-0002-7819-7013Supported by the French ANR, project ANR-22-CE48-0001 (TEMPOGRAL). Hasso Plattner Institute, University of Potsdam, Germany and https://hpi.de/friedrich/people/michelle-doering.html [email protected]://orcid.org/0000-0001-7737-3903German Federal Ministry for Education and Research (BMBF) through the project “KI Servicezentrum Berlin Brandenburg” (01IS22092) Institute of Computer Science, Friedrich Schiller University Jena, Germany LaBRI, Université de Bordeaux, [email protected]://orcid.org/0000-0002-7283-4982Supported by the French ANR, project ANR-22-CE48-0001 (TEMPOGRAL). keywords temporal paths, gossiping, (multi)graphical degree sequences, edge-disjoint spanning trees, linear time algorithms ccs Theory of computation Graph algorithms analysis ccs Mathematics of computing Discrete mathematics ccs Networks Network design and planning algorithms keywords temporal graphs, temporal paths and connectivity, gossiping, (multi)graphical degree sequences, edge-disjoint spanning trees, linear time algorithms † † runningauthor: A. Casteigts, M. Döring, and N. Morawietz † † copyright: Arnaud Casteigts, Michelle Döring, Nils Morawietz 1 Introduction The problem of assigning time labels to the edges of a graph in such a way that every vertex can reach every other vertex by a non-decreasing path (temporal path) is known as the gossiping problem. Problems of this type were extensively studied in the late 70s - early 90s (see, e.g. [ 23 , 24 ] ), initially motivated by optimal scheduling of phone calls, where the agents are represented by vertices and the calls by time-labeled edges (e.g. [ 19 , 6 ] ). Most of the research in this line considers interactions that are mutually exclusive (an agent cannot have multiple phone calls at the same time) and non-repetitive (two agents cannot call each other twice). One of the landmark results in this area was obtained in 1991 by Göbel et al. [ 17 ] , who showed that deciding whether a given graph admits such a labeling is NP -complete. The past decade has seen a renewed interest in this type of problems, motivated by the modeling of various types of dynamic networks, such as wireless networks, social networks, autonomous vehicles, and transportation scheduling. In today’s terminology, the gossip problem can naturally be rephrased in terms of temporal graphs. Formally, a temporal graph is a pair \mathcal{G}=(G,\lambda) where G=(V,E) is the underlying graph (in this work, undirected) and \lambda is a mapping that assigns time labels to the edges. Such a labeling is simple if every edge of G has a single time label, and it is proper if adjacent edges do not share any time label. The graph \mathcal{G} is temporally connected (i.e. in class TC ) if there exists a path traversing edges with non-decreasing times (temporal path) between each ordered pair of nodes. In this terminology, the gossip problem corresponds to deciding, given a graph G , if there exists a simple and proper labeling \lambda such that \mathcal{G}=(G,\lambda)\in TC (and/or to find such a labeling). A number of similar realizability questions have been considered recently in the temporal graph literature, focusing on labelings that satisfy additional prescribed properties. For example, several works investigate whether the labeling can ensure that the fastest temporal paths between vertices match (or are upper-bounded by) a given matrix of pairwise durations [ 26 , 14 , 29 , 28 , 30 ] . Another problem asks that the temporal paths realize a target reachability relation [ 13 ] , under various restrictions of the labeling function (see [ 7 , 10 ] for discussions on the resulting expressivity). Further studies consider minimizing the number of labels [ 1 ] , minimizing reachability times [ 12 ] , maximizing overall reachability sets [ 5 ] , or avoiding temporal cycles [ 2 ] , to name a few. Broadly speaking, all these problems, and their non-temporal versions before them, are part of a long series of realizability questions in graph theory, having their root in the seminal work of Erdős and Gallai [ 16 ] and Havel and Hakimi [ 22 , 20 ] on whether (and how, respectively) a given degree sequence can be realized as a (static) graph. In this work, we return to the roots of realizability questions, studying the temporal analog of Erdős and Gallai’s problem, namely, whether (and how) a given degree sequence can be realized as a temporal graph in TC , for both the simple and non-simple cases. This question is partly motivated by the hardness results of Göbel et al. [ 17 ] , a natural question being how to relax the input specification in a way that offers more flexibility (and tractability) for realization. Another motivation is to investigate whether this format allows for an elegant and concise characterization of all the feasible cases, a situation that is pretty rare in the literature on temporal graphs. 1.1 Main results Before stating the results, we recall that a degree sequence \mathbf{d} is a non-increasing list of integers. A degree sequence of length n is graphical if there exist an n -vertex (static) graph whose vertices have exactly these values as their degrees. Moreover, \mathbf{d} is multigraphical if a multigraph with this degree distribution exists. Our main result is a complete characterization of the graphical sequences that admit a realization as a simple and proper temporal graph in TC . We refer to these sequences as TC -realizable graphical sequences . The characterization, obtained in Section 5 , is the following: Theorem 1 . A graphical sequence \mathbf{d}=(d_{1},\dots,d_{n}) with m:=\frac{1}{2}\cdot\sum_{i=1}^{n}d_{i} edges is TC -realizable if and only if one of the following holds: • m=2n-4 , d_{1}<n-1 , and d_{n}\geq 2 • m\geq 2n-3 and either (i) n\leq 2 or (ii) n>2 , d_{n-1}\geq 2 , and d_{n}\geq 1 . We also characterize the degree sequences that can be realized as a non-simple and proper temporal graph in TC , where non-simple means that a same edge can receive multiple time labels. Conveniently, non-simple temporal graphs are equivalent to simple temporal graphs