{"id":"a5cfabd8-b1bb-41ec-98b9-0769fa423d67","arxiv_id":"2504.14258","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper defines Stretched Temporal Graph Realization (STGR), proves it is NP-hard to approximate within sublinear factors in the period, and provides approximation, fixed-parameter, and local-search algorithms.","lead":"This paper introduces a new problem in periodic temporal graph design: assign each edge a repeating time label so that the fastest temporal path between any two vertices is at most a constant factor (the stretch) longer than the static distance. It proves the problem is NP-hard to approximate, gives a simple polynomial-time labeling algorithm, and studies fixed-parameter and local-search variants.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 7's binary search can miss a feasible interval for a modified edge, leaving Theorem 7.1's XP algorithm unproven as written.","rationale":"The reader's weakest assumption identifies exactly the same load-bearing gap that I find: Theorem 7.1's XP algorithm depends on an unproven binary-search step. The feasible set for a single modified edge is not shown to be monotone in the label; although it is an interval, an interval predicate is not searchable by ordinary binary search without additional information. The manuscript text in Section 7 merely states 'we perform binary search ... until we find a time-labeling (if it exists)' and gives no argument that the midpoint test reveals which half to keep. The additional independence assumption across edges is also unsupported. I therefore agree with the conditional verdict: the local-search contribution needs a corrected or explicit feasibility argument before the theorem can be accepted. I do not see a comparably serious flaw in the approximation-hardness proof, the radius algorithm, or the MSO-based FPT results; my reading of those parts is that they are plausible and do not move the verdict further.","tokens_in":37514,"tokens_out":24348,"duration_ms":237899,"concrete_test":"Build a Fixed Edges Relabel instance with F = {e=(a,b)}, Delta = 100, and two vertex pairs whose only sub-alpha paths force lambda(e) >= 30 (a path from a to c using e first) and lambda(e) <= 40 (a path from d to b using e last), so the feasible labels are exactly the interval [30,40]. Run the algorithm's binary search on the zone [1,100] as described: test the midpoint 50, receive 'stretch > alpha_0', and discard one half according to the implementation's tie-break. If the search returns 'no solution' instead of a label in [30,40], the claimed binary-search step is invalid. Equivalently, implement the oracle P(x) = (30 <= x <= 40) and show that a standard midpoint binary search can fail to find a true point.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Theorem 7.1, the algorithm fixes a time-label profile and then performs binary search on the label of each modified edge, claiming this finds a feasible labeling when one exists. This step is not justified. Fix all other edge labels and consider the label x of one edge e_i. For a fixed ordered pair (s,t), any simple temporal path using e_i has e_i either first (if s is an endpoint), last (if t is the opposite endpoint), or internal; its duration is respectively C - x, C + x, or constant. Hence the set of x satisfying that pair's stretch bound is a prefix, suffix, all, or empty, and the global feasible set for x is an interval [L,U]. An interval is not a monotone predicate: a midpoint test can be negative while feasible labels lie on one side, on the other, or both, so standard binary search that discards one half can miss a nonempty [L,U]. The paper neither computes L and U nor provides a search procedure for interval predicates; it merely asserts that binary search succeeds. The further claim that edges are searched independently is also unsupported: moving e_i changes the constants in the duration expressions for e_j, so coordinate-wise binary searches need not converge to a feasible joint labeling. Since the XP bound of Theorem 7.1 rests entirely on this step, the local-search result is unproven as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Stretched Temporal Graph Realization (STGR): given an undirected graph G, a period Delta, and a rational alpha >= 1, decide whether each edge can receive one label in {1,...,Delta} so that in the resulting Delta-periodic temporal graph, the duration of a fastest temporal path between every ordered pair (u,v) is at most alpha times the static distance in G. The contributions are: (1) inapproximability results ruling out polynomial-time Delta^{1-epsilon}- and 2^{n^c}-approximations under P != NP; (2) a polynomial-time 'radius algorithm' with stretch at most Delta - (Delta-1)/min(rad+1,diam), plus improved guarantees on trees and a 2-approximation for general trees; (3) NP-hardness for Delta=3 and alpha in [1,1.5) on diameter-2 graphs (answering an open question), for Delta=3 and alpha in [1.5,2), and for all constant Delta >= 3 and all constant alpha >= 1; (4) fixed-parameter tractability via MSO_lin and CMSO encodings parameterized by neighborhood diversity plus Delta, and by treewidth plus diameter plus Delta; and (5) a local-search variant LS STGR claimed to admit an XP algorithm for the parameter k and to be W[2]-hard. The XP algorithm for Fixed Edges Relabel STGR is the part I cannot verify as written.","tokens_in":37773,"tokens_out":30609,"duration_ms":277727,"significance":"The problem is natural and well motivated, and the paper is largely self-contained: the reductions use 3-Coloring, the gossip problem, and Hitting Set, while the authors' earlier arbitrary-bound problem [38] appears only as motivation, so there is no evident circularity. The MSO encodings in Section 6 are explicit and checkable, and the radius algorithm gives a clean, falsifiable approximation guarantee. The hardness results for small Delta and constant alpha, if correct, are valuable and answer a posed open question. The main weakness is that one central algorithmic claim, the XP algorithm for LS STGR in Theorem 7.1, rests on an unjustified binary-search step, and there is also an inconsistency in the construction used in Lemma 5.1. If these two technical points are repaired, the paper would be a solid contribution to temporal graph realization; in its current form, it requires major revision.","major_comments":[{"comment":"The binary-search step is not justified. After fixing a zone allocation and a time-label profile, the algorithm claims to search each edge e_i in F independently and to find a feasible label whenever one exists. For a single edge with all other labels fixed, the set of labels satisfying a fixed pair (s,t) is a union of sets of the form {x : x <= a}, {x : x >= b}, or the whole interval, because a path using e_i either has it first, last, or internal. Since the condition for a pair is existential over temporal paths, the feasible set for that pair is a union of such prefix/suffix sets, and the intersection over all pairs can be two separated intervals. A midpoint binary search that discards one half can therefore miss a nonempty feasible set. The text neither computes interval endpoints nor proves any monotonicity property of the feasibility predicate. Furthermore, the independence of the searches is unsupported: changing the label of e_i changes the constants in the duration expressions for paths that also use e_j, so coordinate-wise binary searches need not converge to a joint feasible labeling. Since the XP bound of Theorem 7.1 rests entirely on this step, the local-search result is unproven as written.","section":"Section 7, Theorem 7.1 (paragraph beginning 'Our algorithm proceeds as follows')"},{"comment":"The construction adds a vertex c* and makes {c*} union (V'\\V) into a clique. Since V'\\V consists of the center c and the added x-vertices (plus c* itself), this does not make c* adjacent to any vertex of the original set V. Nevertheless, the proof repeatedly uses (u,c*,v) as a length-2 path for u,v in V: the forward direction uses (b,c*,a) when {a,b} is an edge of G, and the reverse direction asserts that (u,c,v) and (u,c*,v) are the only u-v paths of length less than 3. These claims are false under the stated construction. The accompanying sentence that 'both vertices c and c* are adjacent to all vertices' is inconsistent with the formal construction. If the intended construction is to make c* universal (in particular adjacent to all vertices of V), the proof may go through, but the text must be corrected explicitly; as written, the reduction and hence the claimed NP-hardness for Delta=3 and alpha in [1,1.5) are invalid.","section":"Section 5.1, Lemma 5.1 (construction of G' and proof)"}],"minor_comments":[{"comment":"The clause 'if l1 != l2 then the durations ... are both Delta+1, while both these durations are strictly less than Delta+1 if l1 != l2' is contradictory; the first condition should be l1 = l2. Also, for odd Delta the minimized maximum duration is (Delta+3)/2 rather than (Delta+2)/2; the stated lower bound remains valid, but the algebra should be corrected.","section":"Section 4, Lemma 4.5"},{"comment":"In the line 'alpha_rad = Delta - (Delta-1)/rad >= max{alpha_l = Delta - (Delta-1)/rad | l in [2,rad]}', the expression on the right should be Delta - (Delta-1)/l.","section":"Section 4, Lemma 4.2"},{"comment":"The definition says 'Let Delta be an odd integer with Delta >= 4', but Definition 5.8 is for even Delta; this should read 'even integer'.","section":"Section 5.2, Definition 5.8"},{"comment":"In the paragraph explaining how the partition X_1,...,X_Delta is chosen, the text says 'If the waiting time at vertex x is i, we put x in X_{i+1}'; this should be X_i, since the formula uses X_i for waiting time i.","section":"Section 6, proof of Lemma 6.5"},{"comment":"The phrase 'consecutive lime labels' should be 'consecutive time labels'.","section":"Section 5.1, Lemma 5.1 proof"}],"recommendation":"major_revision","confidential_remarks":"The two substantive problems are (i) the unproven binary-search step in the XP algorithm of Section 7 and (ii) the inconsistent c* construction in Lemma 5.1. Both appear fixable, and the rest of the paper contains careful, checkable arguments. If the authors provide a correct XP proof and correct the construction, I would support acceptance; in the current form, the central local-search claim and one of the key NP-hardness claims are not established."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nQuick take: this is a genuine contribution to temporal graph realization. The STGR problem—multiplicative stretch between fastest temporal-path duration and static distance—is natural, the inapproximability results look sound, the radius algorithm is clean, and the MSO/FPT results are competent. The soft spot is Section 7: the XP algorithm for local search does not prove that the binary search over edge labels converges to a feasible labeling. The stress-test's specific counterexample gets the sign wrong—if an edge is first on a path, its label is the departure time, so the duration is independent of that label, and for a single edge with the other labels fixed the feasible region is a prefix, not an arbitrary interval—so plain binary search on a monotone predicate does work for one edge. But the paper never addresses the interaction between edges. Within a fixed time-label profile, the stretch is non-decreasing in each coordinate, so the feasible set is a down-set; a coordinate-wise greedy search can find a feasible point if one exists, but that's not what is written. The text says the searches are \"independent,\" which is false, and the proof of convergence is absent. This is fixable, not fatal, but Theorem 7.1 is unproven as stated.\n\nThe rest holds up. Lemma 4.5 has a contradictory clause (\"if ℓ1≠ℓ2 then durations are both ∆+1, while ... strictly less if ℓ1≠ℓ2\")—clearly a typo for ℓ1=ℓ2 in the second spot—and the inapproximability reduction from gossip is terse but the gap argument is sound. Citation pattern is fine: the earlier arbitrary-bound problem is only motivation, and the new reductions are self-contained.\n\nRecommendation: send it to referees. The core results deserve scrutiny, and the local-search gap is likely repairable. Just flag Section 7 for the referee.","headline":"Solid new problem and hardness results; Section 7's XP local-search proof has a fixable but real gap.","tokens_in":38313,"tokens_out":13771,"would_cite":true,"duration_ms":127881,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q25","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Assigning periodic time-labels so that fastest temporal paths respect static distances is NP-hard to approximate, but a simple radial labeling keeps the stretch below $\\Delta$.","keywords":["periodic temporal graphs","temporal labeling","stretch","fastest temporal path","graph realization","NP-hardness","approximation algorithm","local search"],"falsifier":"The most directly checkable point is the local-search XP proof: exhaustively enumerate all Fixed Edges Relabel STGR instances with one changed edge and compare the Section 7 midpoint binary search against brute force. A single instance with a feasible labeling that the binary search misses would invalidate the algorithm as written; if no such instance exists, the missing proof can likely be supplied.","tokens_in":37333,"feed_emoji":"⏱️","tokens_out":10985,"duration_ms":91523,"temperature":0.7,"pith_summary":"This paper introduces and analyzes the problem of assigning one periodic time-label from $\\{1,\\dots,\\Delta\\}$ to every edge of a static graph so that, in the resulting $\\Delta$-periodic temporal graph, the duration of the fastest temporal path between any two vertices is at most $\\alpha$ times their distance in the static graph. The paper establishes that this task, called Stretched Temporal Graph Realization (STGR), is NP-hard to approximate within a factor of $\\Delta^{1-\\varepsilon}$ for any $0<\\varepsilon<1$ and within a factor of $2^{n^c}$ for any $c>1$, unless P equals NP. On the positive side, it gives a polynomial-time radius algorithm that labels any graph with stretch at most $\\Delta - \\frac{\\Delta-1}{\\min(\\mathrm{rad}+1,\\mathrm{diam})}$, which is strictly below the trivial bound $\\Delta$, and it shows this guarantee is tight on some NP-hard instances. The paper also proves NP-hardness for constant period length and constant stretch, including $\\Delta=3$, $\\alpha=1$, diameter 2, gives fixed-parameter algorithms via monadic second-order logic, and analyzes a local-search variant that is W[2]-hard but in XP when parameterized by the number of labels changed.","feed_headline":"Periodic schedules that respect distances are NP-hard to approximate","feed_subtitle":"Even period 3 and diameter 2 are intractable; a radial labeling still beats the trivial Δ bound.","key_machinery":"The load-bearing object is the periodic labeling $\\lambda:E\\to\\{1,\\dots,\\Delta\\}$ together with the induced waiting time: when a temporal path uses two consecutive edges with labels $a$ and $b$, the wait at the shared vertex is $b-a$ if $b>a$, $\\Delta+b-a$ if $b<a$, and $\\Delta$ if $b=a$; the stretch is the maximum over vertex pairs of the ratio of fastest-path duration to static distance. The main constructive mechanism is the radius algorithm, which fixes a vertex whose eccentricity equals the graph's radius and labels every edge between layer $i-1$ and layer $i$ with $\\lceil \\Delta/2\\rceil$ for odd $i$ and with $\\Delta$ for even $i$; alternating these two labels controls the worst-case wait at the center and yields the bound $\\Delta - \\frac{\\Delta-1}{\\min(\\mathrm{rad}+1,\\mathrm{diam})}$. On the hardness side, the mechanisms are gap reductions from the gossip problem and from 3-coloring, using sunglasses gadgets that force certain edge pairs to carry distinct labels. For the fixed-parameter results, the mechanism is a monadic second-order formulation of the stretch condition, with cardinality extensions that make the problem expressible in the fragments covered by the relevant model-checking meta-theorems.","core_discovery":"The central claim is that keeping the multiplicative stretch of a periodic temporal labeling close to the static distances is computationally hard, yet a simple constructive labeling can always beat the trivial worst case. For every $0<\\varepsilon<1$ and every $c>1$, STGR has no polynomial-time $\\Delta^{1-\\varepsilon}$-approximation and no polynomial-time $2^{n^c}$-approximation unless P equals NP; the proof is a gap reduction from the gossip problem, where a yes-instance admits a labeling whose stretch is independent of $\\Delta$, while a no-instance forces some fastest temporal path to cross a period boundary, making the stretch grow with $\\Delta$. Complementing this, the radius algorithm picks a vertex of minimum eccentricity and labels edges between consecutive distance layers alternately with $\\lceil \\Delta/2\\rceil$ and $\\Delta$; the paper proves this produces stretch at most $\\Delta - \\frac{\\Delta-1}{\\min(\\mathrm{rad}+1,\\mathrm{diam})}$, and on trees it gives stretch at most $\\frac{\\Delta+1}{2}$, which is optimal when the maximum degree is at least $\\Delta+1$ and a 2-approximation on general trees. The decision version is NP-hard even for $\\Delta=3$, $\\alpha=1$, and diameter 2, resolving an open question from earlier work, and remains NP-hard for every constant $\\Delta\\ge 3$ and every constant $\\alpha\\ge 1$.","pith_inferences":["Beyond the paper: the radius algorithm's two-label alternation suggests a testable design heuristic—layered periodic schedules that interleave $\\lceil \\Delta/2\\rceil$ and $\\Delta$ along BFS layers—which could be extended to directed graphs, weighted graphs, or aperiodic schedules and checked for analogous worst-case wait bounds.","Beyond the paper: the hardness cluster around $\\alpha=\\Delta/2$ indicates a possible phase transition in the stretch parameter; for $\\alpha$ just below $\\Delta/2$ the problem is NP-hard for every $\\Delta$, and deciding what happens for larger $\\alpha$ is a natural next step.","Beyond the paper: if the binary-search gap in the local-search XP algorithm is repaired, the algorithm would provide a practical improvement heuristic—start from any labeling and reduce stretch by changing a constant number of labels in polynomial time—since the W[2]-hardness only rules out FPT-style exact local improvement."],"forward_implications":["Unless P equals NP, no polynomial-time algorithm can guarantee stretch below $\\Delta^{1-\\varepsilon}$ or $2^{n^c}$, so the trivial $\\Delta$ bound is qualitatively hard to improve in the worst case.","The radius algorithm runs in polynomial time and always returns a labeling with stretch at most $\\Delta - \\frac{\\Delta-1}{\\min(\\mathrm{rad}+1,\\mathrm{diam})}$, which is strictly better than $\\Delta$ whenever the radius and diameter are small.","On trees the radius algorithm achieves stretch at most $\\frac{\\Delta+1}{2}$; on trees with maximum degree at least $\\Delta+1$ this is exactly optimal, and on general trees it is a 2-approximation.","STGR is NP-hard even for $\\Delta=3$, $\\alpha=1$, and diameter 2, so the easy-looking small cases are already intractable; hardness also holds for every constant $\\Delta\\ge 3$ and every constant $\\alpha\\ge 1$.","The problem is fixed-parameter tractable with respect to neighborhood diversity plus $\\Delta$ and with respect to treewidth plus diameter plus $\\Delta$, while the local-search variant that changes at most $k$ labels is in XP and W[2]-hard with respect to $k$."],"supporting_citations":[{"why":"Supplies the gossip problem used as the source of the gap reduction proving the $\\Delta^{1-\\varepsilon}$ and $2^{n^c}$ inapproximability bounds.","marker":"[25]"},{"why":"Supplies 3-Coloring, the NP-hard problem from which the constant-$\\Delta$ and constant-$\\alpha$ hardness reductions are built.","marker":"[29]"},{"why":"Defines the earlier multi-label periodic realization problem whose open question about diameter-2 graphs is answered by the $\\Delta=3$, $\\alpha=1$ hardness result.","marker":"[22]"},{"why":"Defines the preceding arbitrary-upper-bound realization problem that STGR specializes, motivating the stretch objective and providing the earlier star NP-hardness context.","marker":"[38]"},{"why":"Provides the monadic second-order logic with linear cardinality constraints whose model-checking fixed-parameter result underlies the neighborhood-diversity tractability.","marker":"[33]"},{"why":"Provides the cardinality-extended monadic second-order model-checking theorem used for the treewidth-plus-diameter-plus-$\\Delta$ fixed-parameter tractability.","marker":"[8]"},{"why":"Extends the monadic second-order framework to graph structure and serves as the standard reference for the model-checking theorems used in the fixed-parameter results.","marker":"[9]"},{"why":"Supplies the Hitting Set problem and the parameterized complexity definitions used in the W[2]-hardness proof for the local-search variant.","marker":"[10]"}],"fun_headline_variants":["Period 3 already makes stretch NP-hard","Radius algorithm beats trivial bound on periodic stretch","Stretch minimization in periodic graphs is NP-hard","Period-3 stretch NP-hard even with diameter 2","Optimal periodic stretch is NP-hard; simple bound exists"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The claim that the local-search variant can be solved in polynomial time for any constant number of changed labels depends on the unproven assumption that, after fixing the other labels and the relative order of labels, a simple midpoint binary search over one changed edge's allowed label range finds a feasible label whenever one exists; the paper does not show the feasible label set has the interval structure this search would need.","fun_headline_variants_meta":{"raw":{"variants":["Period 3 already makes stretch NP-hard","Radius algorithm beats trivial bound on periodic stretch","Stretch minimization in periodic graphs is NP-hard","Period-3 stretch NP-hard even with diameter 2","Optimal periodic stretch is NP-hard; simple bound exists"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001491,"raw_usage":{"total_tokens":6120,"prompt_tokens":1213,"completion_tokens":4907,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":829,"completion_tokens_details":{"reasoning_tokens":4834}},"tokens_in":829,"tokens_out":4907,"duration_ms":35304,"temperature":1.0,"reasoning_tokens":4834,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:56:03.617245+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"The most directly checkable point is the local-search XP proof: exhaustively enumerate all Fixed Edges Relabel STGR instances with one changed edge and compare the Section 7 midpoint binary search against brute force. A single instance with a feasible labeling that the binary search misses would invalidate the algorithm as written; if no such instance exists, the missing proof can likely be supplied.","supporting_citations":[{"cited_title":"Label-connected graphs and the gossip problem","cited_arxiv_id":null,"evidence_quote":"Supplies the gossip problem used as the source of the gap reduction proving the $\\Delta^{1-\\varepsilon}$ and $2^{n^c}$ inapproximability bounds."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies 3-Coloring, the NP-hard problem from which the constant-$\\Delta$ and constant-$\\alpha$ hardness reductions are built."},{"cited_title":"Parameterized algorithms for multi-label periodic temporal graph realization","cited_arxiv_id":null,"evidence_quote":"Defines the earlier multi-label periodic realization problem whose open question about diameter-2 graphs is answered by the $\\Delta=3$, $\\alpha=1$ hardness result."},{"cited_title":"Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity","cited_arxiv_id":null,"evidence_quote":"Provides the monadic second-order logic with linear cardinality constraints whose model-checking fixed-parameter result underlies the neighborhood-diversity tractability."},{"cited_title":"The monadic second-order logic of graphs","cited_arxiv_id":null,"evidence_quote":"Provides the cardinality-extended monadic second-order model-checking theorem used for the treewidth-plus-diameter-plus-$\\Delta$ fixed-parameter tractability."},{"cited_title":"Graph structure and monadic second-order logic: a language-theoretic approach , volume 138","cited_arxiv_id":null,"evidence_quote":"Extends the monadic second-order framework to graph structure and serves as the standard reference for the model-checking theorems used in the fixed-parameter results."}],"review_version":1}