{"id":"6915bb31-7ba4-45e7-a366-1efebcc71b0d","arxiv_id":"2312.06260","paper_version":2,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Deciding TC spanning tree existence in temporal graphs is NP-complete; bidirectional spanners are testable in P but their minimization is NP-hard, with FPT algorithms via feedback edge set parameterization.","lead":"The paper proves that deciding whether a temporal graph admits a temporally connected spanning tree is NP-complete. It introduces a polynomial-time testable bidirectional spanner relaxation and shows related FPT results parameterized by feedback edge set.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.3","headline":"NP-completeness of TC spanning tree existence rests on explicit label encoding and standard temporal path semantics","rationale":"The reader's weakest_assumption directly names the modeling assumption that underpins both hardness results. With the full manuscript now accessible, the same assumption remains the least-secured precondition for the complexity claims; the structural results (pivot vertex/edge) and FPT algorithms do not share this dependency. No internal inconsistency or other load-bearing gap was located.","tokens_in":1814,"tokens_out":349,"duration_ms":15560,"concrete_test":"Locate the NP-completeness reduction (likely §3); extract the constructed temporal graph G' from an instance of the source problem and measure |E(G')| versus input size; confirm every edge label is listed explicitly and every temporal path uses only the chronological definition; if any label set is represented implicitly or the size is super-polynomial, recompute the reduction with an explicit enumeration and re-check membership in NP and hardness.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central NP-completeness claim (deciding existence of a TC spanning tree) is established via reduction. This reduction presupposes that the temporal graph is presented explicitly (all time labels listed) and that temporal paths obey the standard chronological-order definition with no compact or implicit encoding of labels. If the input model permits succinct representations of periodic or infinite labels, or if reachability semantics differ, the constructed instances may no longer be polynomial-size or the hardness may fail to transfer. The bidirectional-spanner hardness inherits the same modeling assumption. No other part of the argument (FPT results, pivot property) depends on this encoding detail as critically.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","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.","tokens_in":1925,"tokens_out":427,"duration_ms":19910,"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":[{"comment":"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.","section":"NP-completeness reduction"},{"comment":"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.","section":"Bidirectional spanner hardness"}],"minor_comments":[{"comment":"Define 'simple temporal graph' at first use and state whether it restricts the number of labels per edge.","section":null},{"comment":"The FPT statements should include explicit running-time bounds or at least the precise parameterization (fes versus fes + ℓ) in the theorem statements.","section":"FPT results"}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"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.","responses":[{"response":"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_made":"yes","referee_comment":"[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."},{"response":"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_made":"yes","referee_comment":"[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."}],"tokens_in":1398,"tokens_out":376,"duration_ms":13818,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The paper's main contributions are the NP-completeness proof for existence of a TC spanning tree and the polynomial-time algorithm to test for bidirectional spanners. It also gives FPT results parameterized by feedback edge set (plus number of labels for the spanner case) and notes that every TC tree has a pivot vertex or pivot edge. These are direct complexity classifications that build on standard temporal path definitions and prior work on temporal connectivity. The structural pivot fact is presented cleanly and could stand on its own. The FPT algorithms follow expected lines once the parameterization is chosen but are still useful to have stated explicitly. The bidirectional spanner result is shown to be hard even on simple temporal graphs, which widens the scope a bit. The central concern is the modeling assumption in the reductions: they treat the temporal graph as given with an explicit list of all time-labeled edges. If inputs can use compact or periodic encodings, the polynomial-size reduction may break and the hardness claim would need re-examination. Nothing else in the paper appears to rest on that detail as heavily. The abstract and claims read internally consistent with no obvious circularity or invented parameters. This work sits squarely inside temporal graph algorithms. Readers already working on reachability, spanners, or parameterized complexity in dynamic graphs will find the classifications and the pivot property worth checking. It is not broad enough to interest people outside the subfield. The paper deserves a serious referee because the results are specific, the questions are well-posed, and the FPT and structural parts provide positive evidence that the authors have engaged the material carefully.","headline":"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.","tokens_in":2434,"tokens_out":392,"would_cite":false,"duration_ms":10340,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[],"headline":"Temporal-graph spanning-tree NP-completeness and bi-spanner algorithms lie outside RS forcing chain","alignment":"orthogonal","rationale":"The paper's machinery (reductions from SAT to TST in proper temporal graphs, bi-path extension/elimination rules, FPT by fes, pivot existence) concerns algorithmic complexity of chronological reachability and bidirectional spanners. No reference to J-cost, cosh identities, φ-ladder, 8-tick periodicity, or parameter-free constant derivation appears; the domain (cs.DM temporal graphs) is one on which the RS framework states no opinion.","tokens_in":52497,"confidence":"high","tokens_out":141,"duration_ms":10688,"cache_read_input_tokens":38528,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Deciding if a temporal graph admits a temporally connected spanning tree is NP-complete.","keywords":["temporal graphs","spanning trees","NP-completeness","bidirectional spanners","temporal connectivity","feedback edge set","pivot vertex"],"falsifier":"A polynomial-time algorithm that decides TC spanning tree existence for arbitrary explicitly given temporal graphs would falsify the NP-completeness claim.","tokens_in":2700,"feed_emoji":"","tokens_out":641,"duration_ms":41669,"temperature":0.7,"pith_summary":"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.","feed_headline":"Deciding temporal spanning trees is NP-complete","feed_subtitle":"Temporal graphs may lack connectivity-preserving trees and finding them is hard, though a bidirectional property allows fast verification.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Deciding temporal spanning trees NP-complete","Temporal spanning tree existence NP-complete","NP-complete for TC spanning trees in temporal graphs","Existence of temporal connectivity trees NP-complete","TC spanning tree decisions NP-complete"],"cache_read_input_tokens":64,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Deciding temporal spanning trees NP-complete","Temporal spanning tree existence NP-complete","NP-complete for TC spanning trees in temporal graphs","Existence of temporal connectivity trees NP-complete","TC spanning tree decisions NP-complete"]},"model":"grok-4.3","cost_usd":0.006738,"raw_usage":{"total_tokens":3100,"prompt_tokens":756,"num_sources_used":0,"completion_tokens":60,"cost_in_usd_ticks":67378000,"prompt_tokens_details":{"text_tokens":756,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":2284,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":756,"tokens_out":60,"duration_ms":16250,"temperature":1.0,"reasoning_tokens":2284,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-24T05:34:22.816402+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A polynomial-time algorithm that decides TC spanning tree existence for arbitrary explicitly given temporal graphs would falsify the NP-completeness claim.","supporting_citations":[],"review_version":1}