pith. sign in

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

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

Arnaud Casteigts , Timoth\'ee Corsini , Nils Morawietz This is my paper

Pith reviewed 2026-05-24 05:34 UTC · model grok-4.3

classification 💻 cs.DM cs.DC
keywords temporal graphsspanning treesNP-completenessbidirectional spannerstemporal connectivityfeedback edge setpivot vertex
0
0 comments X

The pith

Deciding if a temporal graph admits a temporally connected spanning tree is NP-complete.

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

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.

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.

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.

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.

Where Pith is reading between the lines

These are 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.

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.

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.

Figures

Figures reproduced from arXiv: 2312.06260 by Arnaud Casteigts, Nils Morawietz, Timoth\'ee Corsini.

Figure 1
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 qu… view at source ↗
Figure 2
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 restr… view at source ↗
Figure 3
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 redu… view at source ↗
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] view at source ↗
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 that a clause cannot be connected to B through a variable if its valuation does not satisfy the clause. This is shown through the following… view at source ↗
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 between s and w. Proof. The existing triplet at v implies that a bi-path exists from s to v arriving at v before time ai (included). If a ′ i 6=… view at source ↗
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, then a bi-spanner of size 3n+ 2m+k + 3 can be built as follows: for each si selected in the solution, keep the edge vsi (remove the others). F… view at source ↗
read the original 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.

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.

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

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.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 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.

axioms (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.

pith-pipeline@v0.9.0 · 5815 in / 1385 out tokens · 19969 ms · 2026-05-24T05:34:22.816402+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

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

  1. Maximizing Reachability via Shifting of Temporal Paths

    cs.DS 2026-05 unverdicted novelty 6.0

    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 1 Pith paper

  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

  9. [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

    work page 2015

  10. [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

    work page 2022

  11. [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

    work page doi:10.1016/j.ipl.2020.106086 2021

  12. [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

    work page 2023

  13. [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

    work page 2003

  14. [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

    work page 2022

  15. [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

    work page 2012

  16. [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

    work page 2021

  17. [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

    work page 2019

  18. [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

    work page 2021

  19. [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 Dagstuhl-Leibniz-Zentrum für Informatik, 2020

    work page 2020

  20. [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

    work page 2020

  21. [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 Informatik, 2019

    work page 2019

  22. [22]

    Count ing temporal paths

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

    work page arXiv 2022

  23. [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

    work page 2022

  24. [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

    work page 2013

  25. [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

    work page 2020

  26. [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

    work page 2015

  27. [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

    work page 2014

  28. [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

    work page 2000

  29. [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

    work page 2020

  30. [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

    work page 2021

  31. [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

    work page 2012