Pith. sign in

REVIEW 2 major objections 2 minor 2 cited by

In search of the lost tree: Hardness and relaxation of spanning trees in temporal graphs

T0 review · 2 major / 2 minor · reviewed 2026-05-24 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Deciding if a temporal graph admits a temporally connected spanning tree is NP-complete.

desk verdict NP-completeness of TC spanning tree existence and poly-time test for bidirectional spanners are the concrete new pieces; hardness may not transfer under succinct label encodings. read the letter →

arxiv 2312.06260 v2 submitted 2023-12-11 cs.DM cs.DC

Arnaud Casteigts , Timothée Corsini , Nils Morawietz This is my paper · ORCID
classification cs.DMcs.DC
keywords temporalgraphsspanningtreesNP-completenessbidirectionalspannersconnectivityfeedbackedgesetpivotvertex
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper shows that determining whether a temporal graph admits a spanning tree preserving temporal connectivity is NP-complete. A sympathetic reader would care because many real-world networks such as scheduled transportation or communication systems depend on time-ordered reachability for connectivity without redundant edges. The authors also identify a relaxation to bidirectional spanners, which can be verified in polynomial time even though finding minimal ones remains NP-hard. They further prove that every TC tree contains a pivot vertex or pivot edge reachable by all others up to a certain time and able to reach all others afterward.

What carries the argument

The pivot vertex or pivot edge of a TC tree, which all vertices can reach by some deadline and which can reach all vertices after that time.

What would settle it

A polynomial-time algorithm that decides TC spanning tree existence for arbitrary explicitly given temporal graphs would falsify the NP-completeness claim.

Watch

Extended reading notes

Core claim

The authors prove that deciding the existence of a TC spanning tree is NP-complete. They establish that the bidirectional reachability property along the same paths is more general than TC spanning trees and can be tested in polynomial time, yet minimizing the size of a bidirectional spanner is NP-hard even on simple temporal graphs. The problems admit FPT algorithms when parameterized by the feedback edge set number of the underlying graph (plus the maximum labels per edge for the spanner case). Every TC tree is shown to admit a pivot vertex or a pivot edge.

Load-bearing premise

The NP-completeness reductions rely on the standard definition of temporal paths with strictly increasing times and on the temporal graph being presented explicitly with every time label.

Editorial extensions

If this is right

  • No polynomial-time algorithm for TC spanning tree existence exists unless P equals NP.
  • Minimizing bidirectional spanners requires exponential time even when each edge has only one time label.
  • Both problems become fixed-parameter tractable when the underlying graph has bounded feedback edge set number.
  • The pivot vertex or edge property holds for every TC tree and can be used for structural characterization.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Designers of time-dependent networks could use the fast bidirectional check as a practical surrogate when full TC trees are too hard to compute.
  • Graphs whose underlying structure is close to a tree remain tractable for these temporal problems via the FPT results.
  • The pivot concept may extend to other questions about reachability deadlines in temporal graphs beyond spanning trees.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 2 minor

Summary. The paper proves that deciding whether a given temporal graph admits a temporally connected (TC) spanning tree is NP-complete. It introduces bidirectional spanners as a relaxation of TC spanning trees (a property testable in polynomial time but whose minimum size is NP-hard even on simple temporal graphs). It gives FPT algorithms for TC-tree existence parameterized by feedback edge set number (fes) and for bidirectional spanner size parameterized by fes + ℓ (max labels per edge), and shows that every TC tree has a pivot vertex or pivot edge.

Significance. The hardness results delineate the computational limits of exact spanning structures in temporal graphs, while the FPT algorithms and pivot property supply positive structural and algorithmic contributions. The bidirectional relaxation is a natural and efficiently recognizable weakening of TC trees.

major comments (2)
  1. [NP-completeness reduction] The NP-completeness reduction for TC spanning tree existence (abstract and § on complexity results) presupposes an explicit encoding of all time labels. The manuscript should explicitly confirm that the constructed instances remain polynomial in size under the standard temporal-graph input model; otherwise the hardness claim does not transfer.
  2. [Bidirectional spanner hardness] The NP-hardness proof for minimum bidirectional spanners on simple temporal graphs inherits the same input-model assumption. The paper should state whether the reduction for this result (distinct from the TC-tree result) uses only polynomially many labels and the standard chronological-path semantics.
minor comments (2)
  1. Define 'simple temporal graph' at first use and state whether it restricts the number of labels per edge.
  2. [FPT results] The FPT statements should include explicit running-time bounds or at least the precise parameterization (fes versus fes + ℓ) in the theorem statements.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and for highlighting the need to clarify the input model in our reductions. We address both major comments below and will incorporate explicit statements confirming polynomial instance sizes.

read point-by-point responses

  1. Referee: [NP-completeness reduction] The NP-completeness reduction for TC spanning tree existence (abstract and § on complexity results) presupposes an explicit encoding of all time labels. The manuscript should explicitly confirm that the constructed instances remain polynomial in size under the standard temporal-graph input model; otherwise the hardness claim does not transfer.

    Authors: Our reduction for TC spanning tree existence is a standard polynomial-time many-one reduction from 3-SAT that produces temporal graphs whose total number of time labels across all edges is linear in the size of the SAT instance. Under the standard model (edge list with per-edge time-label lists), the constructed instance size is therefore polynomial. We will add an explicit paragraph in the complexity section confirming this and that the chronological-path semantics are preserved. revision: yes

  2. Referee: [Bidirectional spanner hardness] The NP-hardness proof for minimum bidirectional spanners on simple temporal graphs inherits the same input-model assumption. The paper should state whether the reduction for this result (distinct from the TC-tree result) uses only polynomially many labels and the standard chronological-path semantics.

    Authors: The separate reduction establishing NP-hardness of minimum bidirectional spanners on simple temporal graphs likewise produces only polynomially many labels per edge (in fact, a constant number in the construction) while respecting standard chronological-path semantics. We will add a clarifying sentence in the relevant theorem statement and proof sketch. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity; results rest on explicit reductions and independent structural arguments

full rationale

The paper proves NP-completeness of TC spanning tree existence and bidirectional spanner minimization via standard polynomial reductions from known problems, using the explicit temporal graph encoding and chronological path semantics as given. FPT results are obtained by dynamic programming over feedback edge sets, and the pivot vertex/edge property is shown by direct reachability arguments. None of these steps reduce to self-definitions, fitted parameters renamed as predictions, or load-bearing self-citations; all derivations are self-contained against the input definitions.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

The paper relies on standard definitions from temporal graph theory and complexity theory; no free parameters, invented entities, or ad-hoc axioms are introduced beyond the problem statements.

assumptions (2)
  • standard math Standard definition of temporal paths requiring strictly increasing timestamps.
    Invoked in the definition of TC and spanning trees.
  • standard math NP-completeness framework via polynomial-time reductions from known hard problems.
    Used to establish the main hardness results.

how reviews work

0 comments
Cite this review

Pith. "Pith review of In search of the lost tree: Hardness and relaxation of spanning trees in temporal graphs." pith.science (2026). https://pith.science/paper/2312.06260

@misc{pith2026231206260,
  author       = {Pith},
  title        = {Pith review of: In search of the lost tree: Hardness and relaxation of spanning trees in temporal graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2312.06260}},
  note         = {Machine review of arXiv:2312.06260}
}
abstract

A temporal graph is a graph whose edges appear at certain points in time. These graphs are temporally connected (in class TC) if all vertices can reach each other by temporal paths (traversing the edges in chronological order). Reachability based on temporal paths is not transitive, with important consequences. For instance, TC graphs do not always admit TC spanning trees. In this paper, we show that deciding if a given temporal graph admits a TC spanning tree is actually NP-complete. Then, we explore possible relaxations. A key feature of TC spanning trees is to support reachability along the same paths in both directions. We show that this property is not equivalent to TC spanning trees, it is more general and it can be tested in polynomial time. Still, minimizing the size of a spanner preserving this property -- a bidirectional spanner -- is \textsf{NP}-hard even more generally than TC spanning tree, including the setting of simple temporal graphs. Along the way, we show that deciding the existence of TC spanning tree is FPT when parameterized by the feedback edge set number (fes) of the underlying graph, and deciding bidirectional spanners of size $k$ is FPT when parameterized by fes + $\ell$ (the maximum number of labels per edge). On the structural side, we show that TC trees always admit a pivot vertex or a pivot edge -- reachable by all vertices by a certain time and able to reach all vertices afterward -- a fact that may be of independent interest.

Figures

Figures reproduced from arXiv: 2312.06260 by the authors.

Figure 1
Figure 1. A temporal graph that is temporally connected (left), in which all temporal subgraphs whose footprint is a tree are not temporally connected (middle and right, up to isomorphism). underlying spanning trees all induce temporally disconnected graphs. Here, a temporal spanning tree would exist if, for example, the two edges labeled 1 had an additional label of value 3. We consider the following fundamental question: Pr… view at source ↗
Figure 2
Figure 2. A temporally connected graph with pivotable vertex d with bidirectional paths between all vertices, but no temporal spanning tree. bi-paths, but these paths cannot be mutualized in the form of a spanning tree. We will use this graph as a gadget in one of our reductions. Observe that this graph also has a pivot, namely d. 2.3 Simple, strict, proper, happy : generality of results Temporal graphs can be restricted in m… view at source ↗
Figure 3
Figure 3. Outline of the results. (Plain red: both Temporal Spanning Tree and k-Bi-Spanner are hard; Vertical green: both problems are tractable; and Slanting blue: only k-Bi-Spanner is hard. Bi-Spanner of unrestricted size is always tractable.) 3 Temporal spanning trees In this section, we show that Temporal Spanning Tree is NP-complete in temporal graphs, whether the setting is strict or non-strict, through a reduction from… view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Footprint for the reduction from SAT to TST. The time labels are as follows (see [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]
Figure 5
Figure 5. Figure 5: Time labels for the reduction from SAT to TST. if xi is set to true and F xi is kept otherwise. Observe that there might exist some spanning trees without both T xi and F xi which means that the value of xi does not impact the valuation of φ. Next, we want to make sure…
Figure 6
Figure 6. Figure 6: Example of the extension of a bi-path. Lemma 3. If the triplet (ui , ai , di) corresponds to a valid bi-path between s and v, and a triplet (v, a′ i , d′ i ) is added by the extension rule to a neighbor w of v, then (v, a′ i , d′ i ) corresponds to a valid bi-path betw…
Figure 7
Figure 7. Figure 7: The reduction, dotted edges have a distinct label from their neighborhood biconnect all the vertices in U with each other, all the vertices of S with each other, and all the vertices in U with all the vertices in S. (→) If there is a solution of size k to Set Cover, th…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Simple, Strict, Proper, and Directed: Comparing Reachability in Directed and Undirected Temporal Graphs

    cs.DM 2025-01 conditional novelty 7.0 of 10

    The directed temporal graph settings form a single reachability hierarchy topped by strict and simple graphs, while undirected settings split into two incomparable strands.

  2. Maximizing Reachability via Shifting of Temporal Paths

    cs.DS 2026-05 unverdicted novelty 6.0 of 10

    Maximizing reachability in k-path temporal graphs via budgeted shifts is FPT when parameterized by k and b together or by k alone, but intractable in most other parameterizations with matching XP algorithms.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages · cited by 2 Pith papers

  1. [1]

    Temporal flows in temporal networks

    Eleni C Akrida, Jurek Czyzowicz, Leszek Gasieniec, Łukas z Kuszner, and Paul G Spirakis. Temporal flows in temporal networks. Journal of Computer and System Sciences , 103:46–60, 2019

    work page 2019

  2. [2]

    Akrida, Leszek Gasieniec, George B

    Eleni C. Akrida, Leszek Gasieniec, George B. Mertzios, an d Paul G. Spirakis. The complexity of optimal design of temporally connected graphs. Theory of Computing Systems , 61(3):907–944, 2017

    work page 2017

  3. [3]

    On implementing stabilizing leader election with weak assumptions on netwo rk dynamics

    Karine Altisen, Stéphane Devismes, Anaïs Durand, Colett e Johnen, and Franck Petit. On implementing stabilizing leader election with weak assumptions on netwo rk dynamics. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing , pages 21–31, 2021

    work page 2021

  4. [4]

    On the size and the approximability of minimum temporally connected subgraphs

    Kyriakos Axiotis and Dimitris Fotakis. On the size and the approximability of minimum temporally connected subgraphs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pages 149:1–149:14, 2016

    work page 2016

  5. [5]

    Parsimonious flooding in dynamic graphs

    Hervé Baumann, Pierluigi Crescenzi, and Pierre Fraignia ud. Parsimonious flooding in dynamic graphs. Distributed Computing , 24(1):31–44, 2011

    work page 2011

  6. [6]

    Complexity of connec ted components in evolving graphs and the computation of multicast trees in dynamic networks

    Sandeep Bhadra and Afonso Ferreira. Complexity of connec ted components in evolving graphs and the computation of multicast trees in dynamic networks. In International Conference on Ad-Hoc Networks and Wireless , pages 259–270. Springer, 2003

    work page 2003

  7. [7]

    Blackout-tolerant temporal spanners

    Davide Bilò, Gianlorenzo D’Angelo, Luciano Gualà, Stefa no Leucci, and Mirko Rossi. Blackout-tolerant temporal spanners. In International Symposium on Algorithms and Experiments for Wireless Sensor Networks, pages 31–44. Springer, 2022

    work page 2022

  8. [8]

    Sparse tempo- ral spanners with low stretch

    Davide Bilò, Gianlorenzo D’Angelo, Luciano Gualà, Stefa no Leucci, and Mirko Rossi. Sparse tempo- ral spanners with low stretch. In 30th Annual European Symposium on Algorithms (ESA) . Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022

    work page 2022

Show all 31 references
  1. [9]

    The complexity of d ata aggregation in static and dynamic wireless sensor networks

    Quentin Bramas and Sébastien Tixeuil. The complexity of d ata aggregation in static and dynamic wireless sensor networks. In Symposium on Self-Stabilizing Systems , pages 36–50. Springer, 2015

    2015

  2. [10]

    A dynamic data structure for temporal reachability with unsorted contact insertions

    Luiz F A Brito, Marcelo K Albertini, Arnaud Casteigts, an d Bruno AN Travençolo. A dynamic data structure for temporal reachability with unsorted contact insertions. Social Network Analysis and Mining, 12(1):1–12, 2022

    2022

  3. [11]

    On computing pareto opti- mal paths in weighted time-dependent networks

    Filippo Brunelli, Pierluigi Crescenzi, and Laurent Vie nnot. On computing pareto opti- mal paths in weighted time-dependent networks. Inf. Process. Lett. , 168:106086, 2021. doi:10.1016/j.ipl.2020.106086

    2021 doi

  4. [12]

    Maximizing reachability in a temporal graph obtained by assigning starting times to a collection o f walks

    Filippo Brunelli, Pierluigi Crescenzi, and Laurent Vie nnot. Maximizing reachability in a temporal graph obtained by assigning starting times to a collection o f walks. Networks, 81(2):177–203, 2023

    2023

  5. [13]

    Bui-Xuan, Afonso Ferreira, and Aubin Jarry

    B. Bui-Xuan, Afonso Ferreira, and Aubin Jarry. Computin g shortest, fastest, and foremost journeys in dynamic networks. International Journal of Foundations of Computer Science , 14(02):267–285, 2003. 15

    2003

  6. [14]

    Simple, strict, proper, happy: A study of reachability in temporal graphs

    Arnaud Casteigts, Timothée Corsini, and Writika Sarkar . Simple, strict, proper, happy: A study of reachability in temporal graphs. In International Symposium on Stabilizing, Safety, and Secur ity of Distributed Systems (SSS 2022) , pages 3–18. Springer, 2022

    2022

  7. [15]

    Time-varying graphs and dynamic networks

    Arnaud Casteigts, Paola Flocchini, Walter Quattrocioc chi, and Nicola Santoro. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distribut ed Systems , 27(5):387–408, 2012

    2012

  8. [16]

    Finding temporal paths under waiting time constraints

    Arnaud Casteigts, Anne-Sophie Himmel, Hendrik Molter, and Philipp Zschoche. Finding temporal paths under waiting time constraints. Algorithmica, 83(9):2754–2802, 2021

    2021

  9. [17]

    Peters, and Jason Schoeters

    Arnaud Casteigts, Joseph G. Peters, and Jason Schoeters . Temporal cliques admit sparse spanners. In 46th International Colloquium on Automata, Languages, and Programming (ICALP), volume 132 of LIPIcs, pages 129:1–129:14. Schloss Dagstuhl - Leibniz-Zentrum f ür Informatik, 2019

    2019

  10. [18]

    Sharp thresholds in random simple temporal graphs

    Arnaud Casteigts, Michael Raskin, Malte Renken, and Vik tor Zamaraev. Sharp thresholds in random simple temporal graphs. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer S cience (FOCS), pages 319–326. IEEE, 2022

    2021

  11. [19]

    Enumeration of sd separators in dags with application to reliability analysis in temporal g raphs

    Alessio Conte, Pierluigi Crescenzi, Andrea Marino, and Giulia Punzi. Enumeration of sd separators in dags with application to reliability analysis in temporal g raphs. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) . Schloss Dagstuh...

    2020

  12. [20]

    Distributed exploration of dynamic rings

    G Di Luna, Stefan Dobrev, Paola Flocchini, and Nicola San toro. Distributed exploration of dynamic rings. Distributed Computing , 33(1):41–67, 2020

    2020

  13. [21]

    Deleting edges to restrict the size of an epidemic in temporal networks

    Jessica Enright, Kitty Meeks, George B Mertzios, and Vik tor Zamaraev. Deleting edges to restrict the size of an epidemic in temporal networks. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) . Schloss Dagstuhl-Leibniz-Zentrum fuer I...

    2019

  14. [22]

    Count ing temporal paths

    Jessica Enright, Kitty Meeks, and Hendrik Molter. Count ing temporal paths. arXiv preprint arXiv:2202.12055, 2022

    2022

  15. [23]

    Parameterized temp oral exploration problems

    Thomas Erlebach and Jakob T Spooner. Parameterized temp oral exploration problems. In 1st Sym- posium on Algorithmic Foundations of Dynamic Networks (SAN D 2022) . Schloss Dagstuhl-Leibniz- Zentrum für Informatik, 2022

    2022

  16. [24]

    On th e exploration of time-varying networks

    Paola Flocchini, Bernard Mans, and Nicola Santoro. On th e exploration of time-varying networks. Theoretical Computer Science , 469:53–68, 2013

    2013

  17. [25]

    Temporal graph classes: A view through temporal separators

    Till Fluschnik, Hendrik Molter, Rolf Niedermeier, Malt e Renken, and Philipp Zschoche. Temporal graph classes: A view through temporal separators. Theoretical Computer Science, 806:197–218, 2020

    2020

  18. [26]

    A connectivity model for agreement in dynamic systems

    Carlos Gómez-Calzado, Arnaud Casteigts, Alberto Lafue nte, and Mikel Larrea. A connectivity model for agreement in dynamic systems. In European Conference on Parallel Processing , pages 333–345. Springer, 2015

    2015

  19. [27]

    Exploration of constantly connected dynamic graphs based on cactuses

    David Ilcinkas, Ralf Klasing, and Ahmed Mouhamadou Wade . Exploration of constantly connected dynamic graphs based on cactuses. In International Colloquium on Structural Information and Co m- munication Complexity, pages 250–262. Springer, 2014

    2014

  20. [28]

    Kempe, J

    D. Kempe, J. Kleinberg, and A. Kumar. Connectivity and in ference problems for temporal networks. In Proceedings of 32nd ACM Symposium on Theory of Computing (ST OC), pages 504–513, Portland, USA, 2000. ACM

    2000

  21. [29]

    Stro ngly connected components in stream graphs: Computation and experimentations

    Léo Rannou, Clémence Magnien, and Matthieu Latapy. Stro ngly connected components in stream graphs: Computation and experimentations. In International Conference on Complex Networks and Their Applications, pages 568–580. Springer, 2020

    2020

  22. [30]

    A theoretical and experimental study of a new algorithm for minimum cost flow in dynamic graph s

    Mathilde Vernet, Maciej Drozdowski, Yoann Pigné, and Er ic Sanlaville. A theoretical and experimental study of a new algorithm for minimum cost flow in dynamic graph s. Discrete Applied Mathematics , 296:203–216, 2021

    2021

  23. [31]

    Temporal reach- ability graphs

    John Whitbeck, Marcelo Dias de Amorim, Vania Conan, and J ean-Loup Guillaume. Temporal reach- ability graphs. In Proceedings of the 18th annual international conference on Mobile computing and networking, pages 377–388, 2012. 16

    2012

Pith tools

Reviewed May 24, 2026 · model on record in the stance chip above.