{"id":"fc4dda5c-18f5-44ba-a52a-f18c34e03e3a","arxiv_id":"2501.18987","paper_version":2,"verdict":"REJECT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper defines the DelayBetter problem in temporal graphs, gives polynomial algorithms for fixed-route and tree cases, gives an FPT algorithm parameterized by feedback edge set and passengers, and proves NP-completeness for lifetime-2 and planar cases.","lead":"This paper introduces DelayBetter, a scheduling problem for train networks: can some connections be delayed so that every passenger reaches their destination by their deadline? It proves tractability for fixed-route passengers and network trees, and NP-hardness for even tiny time horizons.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 10's LP constraint (4) has the wrong inequality: it allows equal consecutive edge times, so integral LP solutions need not be strict temporal paths.","rationale":"The reader's weakest_assumption identifies precisely the flaw in Equation (4). The manuscript defines temporal paths as having strictly increasing time-labels (Definition 1) and explicitly states that the paper focuses exclusively on strict temporal paths. Constraint (4) as printed, t'_uv <= t'_vw + 1, is equivalent to t'_uv - t'_vw <= 1, which permits equality (and even a decrease by exactly 1 if integer times are assumed). It does not enforce t'_vw >= t'_uv + 1. The correct constraint is t'_uv <= t'_vw - 1. The theorem's proof asserts that Equation (4) 'enables strict temporal paths along each path specified in D,' which is false. The provided counterexample is a minimal concrete witness: the LP has integral optimal solutions that violate strict temporal connectivity, so the claimed equivalence between LP solutions and feasible delayings does not hold. Since Theorem 10 is the basis for Corollary 12 and Theorem 13, the paper's positive results rest on an invalid derivation as written. The reader's REJECT verdict is therefore appropriate, and no verdict adjustment is needed. The concern is mechanical and precise, not a matter of interpretation or external consensus, and it is fully consistent with the text of the manuscript.","tokens_in":18606,"tokens_out":2758,"duration_ms":27740,"concrete_test":"Construct a Path DB instance: vertices u,v,w; edges uv and vw both with λ=1; one demand (u,w,2,P) where P is the path u-v-w. Solve the LP from Theorem 10 exactly. The optimal solution is t'_uv = t'_vw = 1, an integral LP solution that does not correspond to a strict temporal path from u to w. This directly contradicts the theorem's claim that integral LP solutions exactly correspond to feasible delayings.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 10 relies on Equation (4), t'_uv <= t'_vw + 1, to enforce strict temporal paths. Strictness requires t'_uv + 1 <= t'_vw, equivalently t'_uv <= t'_vw - 1; the printed inequality is the reverse of this and permits t'_uv = t'_vw. Consequently, an integral feasible solution to the LP may assign equal times to consecutive edges, which does not correspond to a valid delaying that realizes the specified temporal path. This breaks the claimed equivalence in the central tractability proof. For example, a single demand on path u-v-w with both original times 1 and arrival time 2 yields LP optimum (t'_uv, t'_vw) = (1,1), which satisfies (4) but is not a strict temporal path, even though a feasible delaying (1,2) exists. The objective of minimizing final arrival times actively selects such non-strict solutions. A correction to (4) might restore the argument, but as written the proof of Theorem 10 is invalid.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces DelayBetter (DB) and two variants, (path-constrained and delay-bounded), in which one may delay time-edges of a temporal graph so that prescribed passenger demands (source, destination, arrival deadline, and optionally a fixed route) are realized by strict temporal paths. The authors claim polynomial-time algorithms for Path DB and δ-Path DB via a linear program, a corollary for trees, an FPT algorithm parameterized by the feedback edge set and the number of passengers, and NP-completeness results for bounded lifetime and planar instances. The hardness reductions are substantial, but the central tractability proof contains a critical error in the LP constraint that is supposed to enforce strict temporal paths, and the stated FPT running time is incorrect.","tokens_in":18781,"tokens_out":6677,"duration_ms":66001,"significance":"If repaired, the paper would describe a natural temporal-graph formalization of delay management with clean tractability results for path-fixed passengers and for trees, complemented by strong NP-hardness results for very small lifetime and for planar graphs. The problem formulation and the planned complexity dichotomy are interesting and would likely be useful to the temporal graphs and delay management communities. However, the main positive results are not established as written because the key LP constraint does not enforce strictness, and the FPT complexity bound is understated; these issues are central to the paper's contribution.","major_comments":[{"comment":"The constraint t'_uv <= t'_vw + 1 does not enforce strict temporal paths. A strict path requires t'_uv + 1 <= t'_vw, i.e., t'_uv <= t'_vw - 1. As printed, the inequality permits consecutive edges to have equal times (or even decreasing times), so an integral LP solution need not correspond to any valid delaying. For example, for a single demand on path u-v-w with initial times 1 and deadline 2, the LP with the printed inequality admits the solution (t'_uv, t'_vw) = (1,1), which satisfies all constraints but gives no strict temporal path, while a feasible delaying (1,2) exists. This invalidates the claimed equivalence in the proof of Theorem 10, and since Corollary 12 and Theorem 13 rely on Theorem 10, the tractability results as stated are unsupported. A corrected inequality would likely restore the approach, but the proof as written is invalid.","section":"Section 3, Theorem 10, Equation (4)"},{"comment":"The claimed running time O(ρ!·2^ρ·|D|·poly(n)) for directed graphs (and O(ρ!·3^ρ·|D|·poly(n)) for undirected graphs) is incorrect. For each ordering of the feedback edge set, each demand independently chooses one of 2^ρ (directed) or 3^ρ (undirected) subsets of E', so the number of Path-DB instances generated is ρ!·(2^ρ)^{|D|} (directed) or ρ!·(3^ρ)^{|D|} (undirected). The correct bounds are O(ρ!·2^{ρ|D|}·poly(n)) and O(ρ!·3^{ρ|D|}·poly(n)), respectively. The algorithm is still FPT in ρ + |D|, but the stated complexity in the theorem and proof is wrong and should be corrected.","section":"Section 3, Theorem 13"},{"comment":"The integrality proof of the LP is not rigorous as written. The iterative rounding argument asserts that rounding down a non-integral variable and then repeating leads to a contradiction, but it does not carefully handle the possibility that rounding down one variable may violate a constraint involving another non-integral variable, and that the chain of violations may cycle or terminate without a clear contradiction. Since the LP (after correcting Equation (4)) is a system of difference constraints with a network matrix, a total unimodularity argument would provide a clean proof; as written, Claim 11, which is essential for Theorem 10, rests on a sketch with a gap.","section":"Appendix A.4, Claim 11"}],"minor_comments":[{"comment":"In the undirected gadget proof, the demands are defined as (uv_i, v', i+1) for i in [t, t+δ], but later the text refers to 'some demand (uv_i, v', t)'; the intended demand index is i+1, and the notation should be made consistent.","section":"Section 2, Lemma 3"},{"comment":"The theorem statement contains typos: 'reps.' should be 'resp.', and 'for forδ-DB' should be 'for δ-DB'.","section":"Section 3, Theorem 13"},{"comment":"The aside that a modification of Kahn's algorithm 'has been omitted' is unnecessary because the paper already cites polynomial-time LP solvability; either provide the algorithm or delete the sentence.","section":"Section 3, Theorem 10"},{"comment":"The caption refers to 'the two leftmost passengers' although the text describes three passengers starting at u, v, and w; the caption should be clarified.","section":"Figure 1"}],"recommendation":"major_revision","confidential_remarks":"The central error in Equation (4) appears to be a sign error that is readily fixable by changing the inequality to t'_uv <= t'_vw - 1, after which the LP becomes a difference-constraint system and integrality should follow from total unimodularity. The FPT running-time error is also easy to correct. The hardness reductions appear more involved and I did not find a comparable flaw in them. I therefore see the paper as salvageable, but not acceptable in its current form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper introduces a genuinely new problem—DelayBetter and its path variant—that connects delay management in train networks to temporal graph theory, and it maps the landscape with a broad set of results. The hardness reductions (NAE-3SAT for Tmax=2, CBP-EPE for planar lifetime 19) look extensive and internally coherent; I did not spot a gap there. The writing is clear and the motivation is solid.\n\nThe trouble is in the main positive result. Theorem 10 relies on LP constraint (4), t'_uv <= t'_vw + 1, to enforce strict temporal paths. That inequality is the wrong direction. Strictness requires t'_vw >= t'_uv + 1, i.e., t'_uv <= t'_vw - 1. As printed, the LP allows consecutive edges at equal times. The stress-test example is decisive: a single demand on path u-v-w with both original times 1 and arrival time 2, the LP optimum is (t'_uv,t'_vw)=(1,1), which satisfies all constraints and maximizes the objective, but is not a valid delaying because no strict temporal path exists. This breaks the claimed equivalence in the center of the tractability argument. A simple correction to (4) might restore the proof, but as written Theorem 10 is invalid.\n\nThe FPT result in Theorem 13 also has a numerical error. For directed graphs, each demand has at most 2^ρ choices of feedback-edge subset, so the total number of combinations across |D| demands is (2^ρ)^|D| = 2^(ρ|D|), not 2^ρ·|D|. The stated time bound is understated. The algorithm would still be FPT with the corrected count (since 2^(ρ|D|) is a function of ρ+|D|), but the paper's advertised running time is wrong.\n\nI want to be fair: the problem is interesting and the hardness half is likely salvageable. The LP error is concrete and fixable, and the FPT bound can be corrected without changing the qualitative result. But the main positive claim is not proven as written.\n\nWho is this for? Researchers in temporal graph modification and delay management. If you fix the LP inequality and the enumeration count, the paper would be a solid contribution. As it stands, it deserves a serious referee—this is not a desk reject—but the referee should be told to check Theorem 10 carefully before trusting the polynomial-time claims.","headline":"A promising new temporal-graph problem with a thorough hardness study, but the main tractability proof has a wrong LP inequality that invalidates Theorem 10 as printed, and the FPT bound is understated.","tokens_in":19295,"tokens_out":3948,"would_cite":false,"duration_ms":33423,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q25","05C85","90C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Selecting delays to help passengers is P when routes are fixed","keywords":["Temporal graphs","Delay management","Computational complexity","NP-completeness","Linear programming","Fixed-parameter tractability","Train networks","Temporal paths"],"falsifier":"Build a Path DelayBetter instance with a single demand whose prescribed path consists of two edges e1 then e2 sharing a vertex, give both edges the same initial time t, and choose a deadline equal to t. The LP with the printed inequality admits the integral solution t'_e1 = t'_e2 = t, which is LP-feasible but does not yield a strict temporal path; observing this for any such instance settles whether the claimed exact correspondence between LP solutions and valid delayings in Theorem 10 holds.","tokens_in":18406,"feed_emoji":"🚆","tokens_out":10447,"duration_ms":96769,"temperature":0.7,"pith_summary":"The paper introduces DelayBetter, a temporal-graph decision problem: given edge availability times and passengers each with a starting vertex, destination, and latest arrival time, can some edges be delayed so that every passenger still arrives on time? Its central positive claim is that fixing the route each passenger takes makes the problem tractable: (δ-)Path DelayBetter is asserted to lie in P via a linear program, with DelayBetter on trees following as a corollary and a fixed-parameter tractable (fpt) algorithm parameterized by the feedback edge set and the number of passengers. The hardness side shows that without fixed routes the problem is NP-complete even when only two time steps are allowed, on undirected diameter-6 graphs and on acyclic digraphs, and remains NP-complete on planar bounded-degree graphs at lifetime 19. A sympathetic reader would see this as a first temporal-graph complexity treatment of the operations-research delay management problem.","feed_headline":"Selecting delays to help passengers is P when routes are fixed","feed_subtitle":"Temporal-graph model: fixed-route delay demands are easy, free routing NP-hard even at lifetime 2.","key_machinery":"The linear program with variables $t'_{uv}$ for every edge. Constraints (2) and (3) keep the delaying within bounds; constraint (4), $t'_{uv} \\leq t'_{vw} + 1$, is the mechanism meant to enforce strict temporal paths along each prescribed route; constraint (5) enforces arrival deadlines. The integrality of the LP, stated as Claim 11, is the load-bearing step: it lets the paper move from feasibility of the relaxed LP to an actual delaying, and the same LP is then reused as a subroutine in the feedback-edge-set enumeration.","core_discovery":"The paper's core discovery is that route information is the complexity switch. Theorem 10 claims that for Path DelayBetter and δ-Path DelayBetter a single linear program decides feasibility and even optimizes total lateness, because an optimal solution can be taken to be integral; the variables are the delayed time labels $t'_{uv}$, with constraints requiring no edge to be moved earlier, bounding the delay per edge in the δ version, capping each arrival edge at its demand's deadline, and (via Equation (4)) prescribing the order of consecutive edges along each demanded path. Corollary 12 lifts tractability to DelayBetter when the footprint is a tree, since each pair of vertices has a unique path. Theorem 13 further lifts this to graphs of bounded feedback edge set by enumerating the possible orderings and edge subsets per passenger, solving a Path DB instance for each combination. For the unrestricted problem, the paper proves NP-completeness with lifetime 2 (Theorems 14 and 15) and on planar bounded-degree graphs with lifetime 19 (Theorem 17).","pith_inferences":["An optimization counterpart of Path DelayBetter that minimizes total lateness is also polynomial, since the LP objective already sums the demand-by-demand lateness margins.","The lifetime-2 hardness indicates that short horizons do not automatically make temporal reachability-modification problems easy; route flexibility is the true source of hardness, a lesson that may transfer to other delay-based modification problems.","The tractability boundary suggested by the tree corollary is that acyclic footprints are easy, while the fpt result suggests a feedback-edge-set bound as a useful structural parameter; testing whether treewidth or feedback vertex number also suffice would be a natural next step."],"forward_implications":["If Theorem 10 is correct, deciding whether delays can realize fixed-route passenger demands, and even optimizing total lateness, costs polynomial time.","Corollary 12 places (δ-)DelayBetter in P for tree-shaped networks, since each pair of vertices has a unique static path.","Theorem 13 gives an fpt algorithm for general DelayBetter parameterized by the feedback edge set size plus the number of passengers, with running time $O(\\rho! \\cdot 2^{\\rho} \\cdot |D| \\cdot \\mathrm{poly}(n))$ on directed graphs and $O(\\rho! \\cdot 3^{\\rho} \\cdot |D| \\cdot \\mathrm{poly}(n))$ on undirected graphs.","The lifetime-2 hardness results show that even two available time steps do not trivialize the general problem, on undirected diameter-6 graphs and on acyclic digraphs.","The planar hardness result shows that δ-DelayBetter remains NP-complete on planar bounded-degree graphs at lifetime 19 for delays up to 10."],"supporting_citations":[{"why":"Supplies the polynomial-time linear programming solver on which Theorem 10's P membership relies.","marker":"[19]"},{"why":"Provides topological sorting, which the paper cites as the basis of a direct alternative algorithm for computing a solution to the LP.","marker":"[18]"},{"why":"Defines the strict temporal path model that the LP constraint (4) is meant to encode.","marker":"[5]"},{"why":"Is the NP-complete positive Not-All-Equal 3SAT problem reduced from in the lifetime-2 hardness theorems.","marker":"[11]"},{"why":"Is the NP-complete cubic bipartite planar edge precoloring extension problem reduced from in the planar hardness theorem.","marker":"[24]"},{"why":"Provides the polynomial-time earliest-arrival computation used in the NP membership proof for DelayBetter.","marker":"[32]"}],"fun_headline_variants":["Fixed routes make delay selection P; free routes NP-hard","Route freedom flips delay selection from P to NP-hard","Passenger delay planning: fixed paths easy, free paths NP-hard even in 2 steps"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of Theorem 10 rests on the assumption that the inequality $t'_{uv} \\leq t'_{vw} + 1$ enforces strict time increase along each passenger's prescribed path, but that inequality allows consecutive equal labels; if it is not corrected, an integral LP solution can fail to describe a valid delaying.","fun_headline_variants_meta":{"raw":{"variants":["Fixed routes make delay selection P; free routes NP-hard","Route freedom flips delay selection from P to NP-hard","Passenger delay planning: fixed paths easy, free paths NP-hard even in 2 steps"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001504,"raw_usage":{"total_tokens":6081,"prompt_tokens":1043,"completion_tokens":5038,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":659,"completion_tokens_details":{"reasoning_tokens":4978}},"tokens_in":659,"tokens_out":5038,"duration_ms":32487,"temperature":1.0,"reasoning_tokens":4978,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T21:44:01.200966+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build a Path DelayBetter instance with a single demand whose prescribed path consists of two edges e1 then e2 sharing a vertex, give both edges the same initial time t, and choose a deadline equal to t. The LP with the printed inequality admits the integral solution t'_e1 = t'_e2 = t, which is LP-feasible but does not yield a strict temporal path; observing this for any such instance settles whether the claimed exact correspondence between LP solutions and valid delayings in Theorem 10 holds.","supporting_citations":[{"cited_title":"Kroon, Rommert Dekker, and Michiel J","cited_arxiv_id":null,"evidence_quote":"Supplies the polynomial-time linear programming solver on which Theorem 10's P membership relies."},{"cited_title":"Karmarkar","cited_arxiv_id":null,"evidence_quote":"Provides topological sorting, which the paper cites as the basis of a direct alternative algorithm for computing a solution to the LP."},{"cited_title":"Delay-Robust Routes in Temporal Graphs","cited_arxiv_id":"2201.05390","evidence_quote":"Is the NP-complete positive Not-All-Equal 3SAT problem reduced from in the lifetime-2 hardness theorems."}],"review_version":1}