Realization of Temporally Connected Graphs Based on Degree Sequences

Arnaud Casteigts; Michelle D\"oring; Nils Morawietz

arxiv: 2504.17743 · v3 · submitted 2025-04-24 · 💻 cs.DS

Realization of Temporally Connected Graphs Based on Degree Sequences

Arnaud Casteigts , Michelle D\"oring , Nils Morawietz This is my paper

Pith reviewed 2026-05-22 18:05 UTC · model grok-4.3

classification 💻 cs.DS

keywords temporal graphsdegree sequencestemporal connectivitygraph realizationrecognition algorithmtime-labelingsimple proper labeling

0 comments

The pith

A degree sequence can be realized as a temporally connected graph if and only if it meets conditions that are checkable in linear time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper starts from the known NP-hard problem of deciding whether a fixed undirected graph can be given time labels to become temporally connected. It relaxes the input to a degree sequence and asks whether some realization of that sequence admits a simple proper time-labeling that makes the resulting temporal graph connected. The authors supply a complete characterization of the feasible sequences together with recognition algorithms that run in O(n) time for simple graphs and O(n+m) time for multigraphs. These procedures are also constructive, so they produce both the underlying graph and the time labels when the sequence is feasible. The shift matters because it converts an intractable verification task on fixed structures into an efficient design method whenever only the degrees are prescribed in advance.

Core claim

The paper gives a complete characterization of which graphical and multigraphical degree sequences admit a realization as a temporally connected temporal graph under a simple proper time-labeling. It further supplies O(n)-time and O(n+m)-time recognition algorithms for the two cases that can be made constructive at essentially no extra cost, outputting both a realizing (multi)graph and a valid time-labeling whenever the sequence is feasible.

What carries the argument

The complete characterization of feasible degree sequences that guarantees existence of a proper time-labeling rendering some realization temporally connected.

If this is right

Graphical degree sequences satisfying the characterization can be realized as simple temporally connected temporal graphs.
Multigraphical degree sequences satisfying the characterization can be realized as non-simple temporally connected temporal graphs.
Both recognition tasks are solvable in linear time and the algorithms produce explicit graphs and labelings.
The relaxation from a fixed graph to any realization of the degree sequence makes the problem tractable.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Network designers who control only node degrees could use the characterization to guarantee temporal connectivity without specifying the exact edges.
The constructive algorithms could be embedded in generators that produce synthetic temporal networks for simulation studies in contact tracing or communication systems.
Similar degree-sequence approaches might apply to directed temporal graphs or to variants with minimum or maximum time-label constraints.

Load-bearing premise

The assumption that temporal connectivity can always be achieved by some choice of realization and some proper time-labeling whenever the degree sequence satisfies the stated characterization.

What would settle it

A degree sequence that the algorithm accepts as feasible yet no realization admits any proper time-labeling that makes the graph temporally connected, or a sequence the algorithm rejects that nonetheless possesses such a realization.

read the original abstract

Given an undirected graph $G$, the problem of deciding whether $G$ admits a simple and proper time-labeling that makes it temporally connected is known to be NP-hard (G\"obel 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 $O(n)$ time for graphical degree sequences (realized as simple temporal graphs) and in $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. Namely, we give a constructive $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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives a full characterization of degree sequences that work for temporally connected graphs plus linear-time constructive algorithms.

read the letter

The one thing to know is that this work completely characterizes the degree sequences that can be realized as temporally connected temporal graphs with proper time labels, and it gives linear time algorithms to recognize them and construct the graphs when they exist. This is new because the decision problem for a fixed underlying graph is NP-hard, as cited from 1991. By switching to existence over all possible realizations of the degree sequence, the hardness disappears and they get efficient methods. The constructive aspect means you not only decide but also build the graph and the labeling. The paper does well here by separating the simple graph case from the multigraph case and giving matching time bounds. The O(n) for graphical sequences and O(n+m) for multigraphical ones are good, and keeping the construction at essentially the same cost is a nice touch. The argument builds on standard definitions of temporal connectivity and proper labelings, which keeps it grounded. On the soft spots, the main one is the narrow focus. This solves a specific relaxed version but does not extend to other temporal properties like reachability with delays or robustness. Also, since the full proofs are in the paper, one would want to check the edge cases in the characterization, but the overall structure does not show internal contradictions or unsupported steps. The stress test found no significant issues. This paper is aimed at researchers working on temporal graphs and network design problems where degree sequences are given and temporal connectivity is required. A reader interested in polynomial algorithms for graph realization problems would find it worthwhile. It deserves a serious referee. The result is formally stated and the algorithms are efficient, so it should go through review rather than a desk reject. I recommend sending it to peer review.

Referee Report

0 major / 2 minor

Summary. The paper relaxes the NP-hard problem of deciding whether a fixed undirected graph admits a simple proper time-labeling making it temporally connected (Gobel et al. 1991) to the question of whether a given degree sequence admits some realization as a temporally connected graph. It claims a complete characterization of the feasible degree sequences together with recognition algorithms running in O(n) time for graphical sequences (realized as simple temporal graphs) and O(n+m) time for multigraphical sequences (realized as non-simple temporal graphs), both of which are constructive.

Significance. If the characterization and algorithms are correct, the result is significant because it supplies an efficient, constructive method for generating temporally connected graphs with prescribed degrees, bypassing the source of NP-hardness by relaxing from a fixed graph to any realization. The linear-time bounds and explicit constructiveness are practical strengths that build directly on standard definitions of temporal connectivity and proper labelings from the cited literature.

minor comments (2)

Abstract: the citation 'Gobel et al., 1991' should be expanded to a full bibliographic entry in the references section to allow readers to locate the NP-hardness result without ambiguity.
Introduction: the notation for the degree sequence d is used without an explicit preliminary definition; adding a short sentence recalling the standard definition of a (multi)graphical degree sequence would improve accessibility.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our work, for recognizing its significance in relaxing the NP-hard fixed-graph problem to degree sequences, and for recommending minor revision. The referee accurately describes our complete characterization of feasible degree sequences and the linear-time constructive algorithms for both simple and multigraph cases.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper provides a complete characterization of degree sequences realizable as temporally connected graphs under proper time-labelings, along with linear-time recognition and constructive algorithms. It explicitly builds on the known NP-hardness of the fixed-graph version (Göbel et al. 1991) and relaxes to existence over realizations of a given degree sequence. No self-citations are load-bearing; the argument uses standard definitions of temporal connectivity and proper labelings from prior literature without internal reduction to fitted parameters, self-definitions, or ansatzes. The O(n) and O(n+m) bounds follow from direct algorithmic construction on degree sequences, which is independent of the target result.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard graph-theoretic background and the cited NP-hardness result; no free parameters, new axioms, or invented entities are introduced in the abstract.

axioms (1)

domain assumption Standard definitions of temporal graphs, simple and proper time-labelings, and temporal connectivity as used in Göbel et al. 1991.
These background notions are required to state the relaxed problem and are taken from prior literature.

pith-pipeline@v0.9.0 · 5720 in / 1213 out tokens · 80963 ms · 2026-05-22T18:05:00.211038+00:00 · methodology

Realization of Temporally Connected Graphs Based on Degree Sequences

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)