Minimum Temporal Spanners in Happy Graphs

Arnaud Casteigts; Hendrik Molter; Meirav Zehavi

arxiv: 2604.24227 · v1 · submitted 2026-04-27 · 💻 cs.DS

Minimum Temporal Spanners in Happy Graphs

Arnaud Casteigts , Hendrik Molter , Meirav Zehavi This is my paper

Pith reviewed 2026-05-08 02:02 UTC · model grok-4.3

classification 💻 cs.DS

keywords temporal graphstemporal spannersNP-hardnesshappy graphsparameterized complexityvertex coverfeedback vertex set

0 comments

The pith

Finding a minimum temporal spanner is NP-hard even on happy temporal graphs where each edge appears once and no vertex has simultaneous incidents.

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

The paper proves that computing the smallest subgraph preserving temporal connectivity is NP-hard even when restricted to happy temporal graphs. Happy graphs require that every edge appears at exactly one time step and that no vertex is incident to more than one edge at any time. This restricted case was previously open, and hardness here immediately implies hardness for all earlier, less restricted versions of the problem, resolving the open question. The authors further show a polynomial-time algorithm when the underlying graph has constant-size vertex cover, which is the first positive result of its kind for temporal spanners.

Core claim

The minimum temporal spanner problem is NP-hard on happy temporal graphs. A happy temporal graph is one in which every edge appears at most once and no two edges incident to the same vertex appear at the same time step. The hardness holds while preserving temporal connectivity, which means the result applies simultaneously to every previously studied setting of the problem.

What carries the argument

A polynomial-time reduction from a known NP-hard problem that outputs a happy temporal graph while keeping temporal connectivity intact.

If this is right

Hardness holds for every earlier, incomparable setting studied in prior work on temporal spanners.
The problem can be solved in polynomial time on happy graphs whose underlying graph has constant-size vertex cover.
In the general non-happy case the problem is W[1]-hard when parameterized by feedback vertex number of the underlying graph.

Where Pith is reading between the lines

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

Applications in dynamic networks with strict timing constraints cannot rely on small subgraphs to maintain reachability in the simplest cases.
Further parameterized algorithms for other structural parameters of the underlying graph may be worth exploring in the happy setting.
The result suggests that temporal connectivity is fundamentally harder to sparsify than static connectivity even under severe restrictions on timing.

Load-bearing premise

The reduction produces an instance that is truly happy, with each edge appearing once and no simultaneous incidents, while still being temporally connected.

What would settle it

A polynomial-time algorithm that correctly computes a minimum temporal spanner for every happy temporal graph would disprove the NP-hardness claim.

Figures

Figures reproduced from arXiv: 2604.24227 by Arnaud Casteigts, Hendrik Molter, Meirav Zehavi.

**Figure 5.** Figure 5: Illustration of the strict temporal spanner for the edge selection gadget Ci,j for Ei,j = {e1, e2, e3, e4} constructed in the proof of Lemma 5.2, where c = 3 2m + 4kn + 5. Here, the edge e = {v (i,j) 1,i , v (i,j) 1,j } is selected to start the construction of the spanner. underlying graph in the temporal spanner that uses only high labels (that are larger than 3 2m + 4kn + 5) and this creates a temporal p… view at source ↗

read the original abstract

Temporal graphs have edge sets that change over discrete time steps. Such graphs are temporally connected (TC) if all pairs of vertices can reach each other using paths that traverse the edges in a time-respecting way (temporal paths). Given a TC temporal graph it, a natural question is to find a minimum spanning subgraph of it that preserves temporal connectivity. These structures, known as temporal spanners, are fundamental and their properties (especially size) have been studied thoroughly in the past decade. In particular, the problem of minimizing the size of a temporal spanner is known to be hard. However, the existing results establish hardness for several incomparable settings and versions of the problem. In this article, we unify and strengthen these results by showing that this problem is NP-hard even on temporal graphs that are simple and proper (also known as "happy"), i.e., where every edge appears only one time, and a vertex cannot be incident to several edges simultaneously. Proving hardness in this extremely restricted setting implies, at once, that the problem is NP-hard for all the previously considered settings and versions of the problem, resolving Open Question 4 in [Casteigts et al. TCS, 2024]. We also initiate the parameterized study of this problem, showing that in the happy setting, the problem can be solved in polynomial time if the underlying graph has a constant-size vertex cover, this result being actually the first positive result on temporal spanners in general. We also show that in the non-happy setting, the problem is W[1]-hard when parameterized by the feedback vertex number of the underlying graph.

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

The paper proves NP-hardness for min temporal spanners even on happy graphs and gives the first FPT result when the underlying graph has small vertex cover.

read the letter

This paper settles that minimum temporal spanners are NP-hard even on happy graphs, where each edge appears at a single time and no vertex sees two edges at once. That single result tightens all earlier hardness statements and answers the open question about whether the problem stays hard under these tight restrictions. They also give the first positive algorithmic result: an FPT algorithm for happy instances whose underlying graph has constant-size vertex cover. That part is useful because it identifies a concrete tractable case and stands as the first algorithmic handle on temporal spanners at all. The W[1]-hardness by feedback vertex set in the non-happy setting rounds out the picture but is less surprising. The reduction itself is the part that needs the closest look. It must map the source problem to a happy instance while keeping the optimum spanner size exactly the same, without creating extra temporal paths or breaking the per-time matching condition. If the gadgets hold, the claim goes through cleanly; any slip on simultaneous incidents or shortcut edges would weaken the equivalence. The abstract indicates they constructed it carefully, and the parameterized vertex-cover result looks clean on its face. This work is for people who track complexity results in temporal graphs and spanner problems. A reader who cares about how restrictions on edge timing affect hardness will get direct value from the unified proof, and anyone working on FPT algorithms for graphs with small covers will note the new tractable case. It deserves a serious referee because it resolves an explicit open question with a strengthening reduction and adds the first algorithmic positive result. I would send it out for review.

Referee Report

2 major / 2 minor

Summary. The paper proves that Minimum Temporal Spanner is NP-hard even when restricted to happy temporal graphs (each edge appears at a unique time and edges at any fixed time form a matching). This unifies and strengthens prior hardness results for various settings, resolving an open question. It also gives the first positive algorithmic result: the problem is solvable in polynomial time on happy graphs whose underlying graph has constant-size vertex cover. In the non-happy case it is W[1]-hard parameterized by feedback vertex set of the underlying graph.

Significance. If the reduction is correct, the result is significant because hardness on happy graphs immediately implies hardness for all previously studied relaxations of the model. The constant-vertex-cover algorithm is the first explicit positive result for any variant of temporal spanners. The W[1]-hardness result further delineates the boundary between tractable and intractable parameterizations.

major comments (2)

[§3.2] §3.2 (Reduction construction): the proof that the constructed instance remains happy must explicitly verify that the auxiliary edges and time labels assigned to each gadget never place two edges incident to the same vertex at the same time step. The current argument shows distinct times globally but does not enumerate the per-time matching condition for the combined original-plus-gadget edges; a single counter-example time step would invalidate the equivalence.
[§3.3] §3.3 (Correctness of the reduction): the argument that any temporal spanner of size k in the happy instance corresponds to a solution of size k in the source problem relies on the absence of temporal shortcuts created by the gadget edges. The manuscript claims that the chosen times prevent such shortcuts, but the case analysis does not cover all possible interleavings of gadget times with original-edge times; an omitted interleaving could allow a strictly smaller spanner and collapse the hardness.

minor comments (2)

[Introduction and §2] The definition of 'happy' in the introduction and preliminaries is repeated almost verbatim; a single consolidated definition with a forward reference would improve readability.
[Figure 1] Figure 1 (example happy graph) uses the same line style for original and gadget edges; distinguishing them by color or dashing would make the reduction illustration clearer.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and for identifying points where the reduction proof can be made more explicit. The comments concern the completeness of the happy-graph verification and the coverage of the correctness argument. We address each below and will incorporate the suggested clarifications in the revised manuscript.

read point-by-point responses

Referee: [§3.2] §3.2 (Reduction construction): the proof that the constructed instance remains happy must explicitly verify that the auxiliary edges and time labels assigned to each gadget never place two edges incident to the same vertex at the same time step. The current argument shows distinct times globally but does not enumerate the per-time matching condition for the combined original-plus-gadget edges; a single counter-example time step would invalidate the equivalence.

Authors: We agree that an explicit per-time-step verification strengthens the presentation. The construction assigns globally distinct times to all gadget edges and ensures that gadget times are disjoint from the original-edge times; within each gadget the local matching property is immediate by design. Nevertheless, to eliminate any ambiguity about the union, we will insert a dedicated lemma that enumerates the possible time steps (original times, gadget-internal times, and cross-gadget times) and confirms that no vertex is incident to more than one edge at any single time. This lemma will be placed immediately after the construction and before the correctness argument. revision: yes
Referee: [§3.3] §3.3 (Correctness of the reduction): the argument that any temporal spanner of size k in the happy instance corresponds to a solution of size k in the source problem relies on the absence of temporal shortcuts created by the gadget edges. The manuscript claims that the chosen times prevent such shortcuts, but the case analysis does not cover all possible interleavings of gadget times with original-edge times; an omitted interleaving could allow a strictly smaller spanner and collapse the hardness.

Authors: The referee correctly notes that a fully exhaustive case analysis on time interleavings would be desirable. Our existing argument proceeds by showing that any temporal path using a gadget edge must traverse a corresponding original edge at a later time, and that the chosen time ordering forces the gadget edges to act only as “detours” that cannot bypass the original structure. To address the concern directly, we will expand the case analysis into a complete enumeration of the relative ordering between gadget times and original-edge times. For each possible ordering we will prove that either (i) the path still requires the original edges counted in the solution or (ii) the path length exceeds the budget k. This expanded analysis will be added as a new subsection or appendix. revision: yes

Circularity Check

0 steps flagged

No circularity: hardness via explicit reduction from known NP-complete problem

full rationale

The paper's central claim is NP-hardness of minimum temporal spanners on happy graphs, established by a polynomial reduction from a known NP-complete problem that is asserted to preserve the happy properties (unique edge times and per-time matchings) along with temporal connectivity. This reduction is presented as new work in the current manuscript and does not reduce by construction to any fitted parameter, self-definition, or prior result by the same authors. The citation to Casteigts et al. TCS 2024 is used only to identify the open question being resolved and carries no load-bearing justification for the new proof. The parameterized results (FPT for constant vertex cover in happy graphs; W[1]-hardness for feedback vertex set in the general case) are likewise direct algorithmic and hardness arguments with no self-referential collapse. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard NP-completeness of a base problem and on the definition of temporal paths; no new entities or fitted constants are introduced.

axioms (2)

standard math NP-completeness of the base problem used in the reduction (standard complexity assumption)
Invoked to transfer hardness to the happy temporal spanner problem
domain assumption Temporal connectivity is preserved under the constructed happy instance
Central to the reduction correctness

pith-pipeline@v0.9.0 · 5591 in / 1354 out tokens · 65159 ms · 2026-05-08T02:02:21.208422+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

[1]

E. C. Akrida, L. Gasieniec, G. B. Mertzios, and P. G. Spirakis. The complexity of optimal design of temporally connected graphs. Theory Comput. Syst., 61 0 (3): 0 907--944, 2017

work page 2017
[2]

Angrick, B

S. Angrick, B. Bals, T. Friedrich, H. Gawendowicz, N. Hastrich, N. Klodt, P. Lenzner, J. Schmidt, G. Skretas, and A. Wells. How to reduce temporal cliques to find sparse spanners. In Proc.\ of 32nd ESA , volume 308 of LIPIcs, pages 11:1--11:15. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2024

work page 2024
[3]

Axiotis and D

K. Axiotis and D. Fotakis. On the size and the approximability of minimum temporally connected subgraphs. In Proc.\ of the 43rd ICALP , pages 149:1--149:14, 2016

work page 2016
[4]

Balev, E

S. Balev, E. Sanlaville, and J. Schoeters. Temporally connected components. Theor. Comput. Sci., 1013: 0 114757, 2024

work page 2024
[5]

Bellitto, J

T. Bellitto, J. B. Popper, and B. Escoffier. Temporal connectivity augmentation. In 4th Symposium on Algorithmic Foundations of Dynamic Networks, 2025

work page 2025
[6]

Bil \` o , G

D. Bil \` o , G. D'Angelo, L. Gual \` a , S. Leucci, and M. Rossi. Sparse temporal spanners with low stretch. In Proc.\ of the 30th ESA , volume 244 of LIPIcs, pages 19:1--19:16. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2022

work page 2022
[7]

Bui-Xuan, A

B.-M. Bui-Xuan, A. Ferreira, and A. Jarry. Computing shortest, fastest, and foremost journeys in dynamic networks. Int. J. Found. Comput. Sci., 14 0 (02): 0 267--285, 2003

work page 2003
[8]

Carnevale, A

D. Carnevale, A. Casteigts, and T. Corsini. Dismountability in temporal cliques revisited. In Proceedings of the 4th Symposium on Algorithmic Foundations of Dynamic Networks ( SAND ) , LIPIcs, pages 6:1--6:18. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2025

work page 2025
[9]

Casteigts, J

A. Casteigts, J. G. Peters, and J. Schoeters. Temporal cliques admit sparse spanners. J. Comput. Syst. Sci., 121: 0 1--17, 2021 a

work page 2021
[10]

Casteigts, M

A. Casteigts, M. Raskin, M. Renken, and V. Zamaraev. Sharp thresholds in random simple temporal graphs. In Proc.\ of the 62nd FOCS , pages 319--326. IEEE , 2021 b

work page 2021
[11]

Casteigts, T

A. Casteigts, T. Corsini, and N. Morawietz. In search of the lost tree - hardness and relaxation of spanning trees in temporal graphs. In Proc.\ of 31st SIROCCO , volume 14662 of LNCS, pages 138--155. Springer, 2024 a

work page 2024
[12]

Casteigts, T

A. Casteigts, T. Corsini, and W. Sarkar. Simple, strict, proper, happy: A study of reachability in temporal graphs. Theor. Comput. Sci., 991: 0 114434, 2024 b

work page 2024
[13]

J. O. Cerdeira. Label-connected graphs and the gossip problem. Discrete Mathematics, 87 0 (1): 0 29--40, 1991

work page 1991
[14]

J. Chen, I. A. Kanj, and G. Xia. Improved parameterized upper bounds for vertex cover. In Proceedings of the 31st International symposium on Mathematical Foundations of Computer Science (MFCS), pages 238--249. Springer, 2006

work page 2006
[15]

Christiann, E

E. Christiann, E. Sanlaville, and J. Schoeters. On inefficiently connecting temporal networks. In Proc.\ of the 3rd SAND , volume 292 of LIPIcs, pages 8:1--8:19. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2024

work page 2024
[16]

M. R. Fellows, D. Hermelin, F. Rosamond, and S. Vialette. On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci., 410 0 (1): 0 53--61, 2009

work page 2009
[17]

R. Haag, H. Molter, R. Niedermeier, and M. Renken. Feedback edge sets in temporal graphs. Discret. Appl. Math., 307: 0 65--78, 2022

work page 2022
[18]

Huang, A

S. Huang, A. W. Fu, and R. Liu. Minimum spanning trees in temporal graphs. In Proc.\ of the 36th SIGMOD, pages 419--430, 2015

work page 2015
[19]

R. M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85--103. Springer, 1972

work page 1972
[20]

Kempe, J

D. Kempe, J. Kleinberg, and A. Kumar. Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci., 64 0 (4): 0 820--842, 2002

work page 2002
[21]

Klobas, G

N. Klobas, G. B. Mertzios, H. Molter, and P. G. Spirakis. The complexity of computing optimum labelings for temporal connectivity. J. Comput. Syst. Sci., 146: 0 103564, 2024

work page 2024
[22]

G. B. Mertzios, O. Michail, and P. G. Spirakis. Temporal network optimization subject to connectivity constraints. Algorithmica, 81 0 (4): 0 1416--1449, 2019

work page 2019

[1] [1]

E. C. Akrida, L. Gasieniec, G. B. Mertzios, and P. G. Spirakis. The complexity of optimal design of temporally connected graphs. Theory Comput. Syst., 61 0 (3): 0 907--944, 2017

work page 2017

[2] [2]

Angrick, B

S. Angrick, B. Bals, T. Friedrich, H. Gawendowicz, N. Hastrich, N. Klodt, P. Lenzner, J. Schmidt, G. Skretas, and A. Wells. How to reduce temporal cliques to find sparse spanners. In Proc.\ of 32nd ESA , volume 308 of LIPIcs, pages 11:1--11:15. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2024

work page 2024

[3] [3]

Axiotis and D

K. Axiotis and D. Fotakis. On the size and the approximability of minimum temporally connected subgraphs. In Proc.\ of the 43rd ICALP , pages 149:1--149:14, 2016

work page 2016

[4] [4]

Balev, E

S. Balev, E. Sanlaville, and J. Schoeters. Temporally connected components. Theor. Comput. Sci., 1013: 0 114757, 2024

work page 2024

[5] [5]

Bellitto, J

T. Bellitto, J. B. Popper, and B. Escoffier. Temporal connectivity augmentation. In 4th Symposium on Algorithmic Foundations of Dynamic Networks, 2025

work page 2025

[6] [6]

Bil \` o , G

D. Bil \` o , G. D'Angelo, L. Gual \` a , S. Leucci, and M. Rossi. Sparse temporal spanners with low stretch. In Proc.\ of the 30th ESA , volume 244 of LIPIcs, pages 19:1--19:16. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2022

work page 2022

[7] [7]

Bui-Xuan, A

B.-M. Bui-Xuan, A. Ferreira, and A. Jarry. Computing shortest, fastest, and foremost journeys in dynamic networks. Int. J. Found. Comput. Sci., 14 0 (02): 0 267--285, 2003

work page 2003

[8] [8]

Carnevale, A

D. Carnevale, A. Casteigts, and T. Corsini. Dismountability in temporal cliques revisited. In Proceedings of the 4th Symposium on Algorithmic Foundations of Dynamic Networks ( SAND ) , LIPIcs, pages 6:1--6:18. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2025

work page 2025

[9] [9]

Casteigts, J

A. Casteigts, J. G. Peters, and J. Schoeters. Temporal cliques admit sparse spanners. J. Comput. Syst. Sci., 121: 0 1--17, 2021 a

work page 2021

[10] [10]

Casteigts, M

A. Casteigts, M. Raskin, M. Renken, and V. Zamaraev. Sharp thresholds in random simple temporal graphs. In Proc.\ of the 62nd FOCS , pages 319--326. IEEE , 2021 b

work page 2021

[11] [11]

Casteigts, T

A. Casteigts, T. Corsini, and N. Morawietz. In search of the lost tree - hardness and relaxation of spanning trees in temporal graphs. In Proc.\ of 31st SIROCCO , volume 14662 of LNCS, pages 138--155. Springer, 2024 a

work page 2024

[12] [12]

Casteigts, T

A. Casteigts, T. Corsini, and W. Sarkar. Simple, strict, proper, happy: A study of reachability in temporal graphs. Theor. Comput. Sci., 991: 0 114434, 2024 b

work page 2024

[13] [13]

J. O. Cerdeira. Label-connected graphs and the gossip problem. Discrete Mathematics, 87 0 (1): 0 29--40, 1991

work page 1991

[14] [14]

J. Chen, I. A. Kanj, and G. Xia. Improved parameterized upper bounds for vertex cover. In Proceedings of the 31st International symposium on Mathematical Foundations of Computer Science (MFCS), pages 238--249. Springer, 2006

work page 2006

[15] [15]

Christiann, E

E. Christiann, E. Sanlaville, and J. Schoeters. On inefficiently connecting temporal networks. In Proc.\ of the 3rd SAND , volume 292 of LIPIcs, pages 8:1--8:19. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2024

work page 2024

[16] [16]

M. R. Fellows, D. Hermelin, F. Rosamond, and S. Vialette. On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci., 410 0 (1): 0 53--61, 2009

work page 2009

[17] [17]

R. Haag, H. Molter, R. Niedermeier, and M. Renken. Feedback edge sets in temporal graphs. Discret. Appl. Math., 307: 0 65--78, 2022

work page 2022

[18] [18]

Huang, A

S. Huang, A. W. Fu, and R. Liu. Minimum spanning trees in temporal graphs. In Proc.\ of the 36th SIGMOD, pages 419--430, 2015

work page 2015

[19] [19]

R. M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85--103. Springer, 1972

work page 1972

[20] [20]

Kempe, J

D. Kempe, J. Kleinberg, and A. Kumar. Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci., 64 0 (4): 0 820--842, 2002

work page 2002

[21] [21]

Klobas, G

N. Klobas, G. B. Mertzios, H. Molter, and P. G. Spirakis. The complexity of computing optimum labelings for temporal connectivity. J. Comput. Syst. Sci., 146: 0 103564, 2024

work page 2024

[22] [22]

G. B. Mertzios, O. Michail, and P. G. Spirakis. Temporal network optimization subject to connectivity constraints. Algorithmica, 81 0 (4): 0 1416--1449, 2019

work page 2019