{"id":"102fb0e6-708f-42a1-b9b6-3b62f795b931","arxiv_id":"2502.06477","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"An algorithm solves ARRIVAL in time 2^{O(k log^2 n)} on n-vertex graphs of treewidth k, and G-ARRIVAL reduces to finding approximate fixed points of l1-contractions.","lead":"This paper gives a quasi-polynomial algorithm for the ARRIVAL problem on graphs of bounded treewidth, and reduces ARRIVAL to finding fixed points of l1-contracting functions. Both results connect ARRIVAL to simple stochastic games and could inform future attempts at a polynomial algorithm.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2's bound x(e)<2|V|t+ is not what its proof establishes: the halving argument only supports 2^{|V|}t+, so the binary-search range r=2|V|t+ in Algorithms 1 and 2 is unsupported.","rationale":"The reader's weakest_assumption correctly identifies Lemma 2 as the load-bearing point: the binary-search ranges in both algorithms, and hence the correctness proofs of Lemma 5, Lemma 8, and Theorem 10, depend on the bound x(e)<2|V|t+. The proof sketch in the manuscript does not establish that bound; its own halving argument yields only an exponential bound, and the paper elsewhere relies on the exponential bound (n2^n t+ in Theorem 19). For t+=1 this is not a minor gap: ARRIVAL's run profile can have edge counts larger than 2|V| when the process takes exponentially many steps, so the range [0,2|V|t+] can exclude the true pivot flow. I agree with the reader that replacing r by 2^{O(|V|)}t+ is the natural repair, and that this repair does not change the stated asymptotic runtime, since the per-recursion cost becomes O(|V|+log t+), whose logarithm is O(log(|V|+log t+)) as already used in the claimed bounds. Because the defect is real but plausibly repairable with a straightforward change, the CONDITIONAL verdict is appropriate; I would not move to reject or accept without revision. I also checked the other candidate concern, the rounding step from a fixed point to the terminal counts in Theorem 19; it is secondary to the main treewidth theorem and would not alter this verdict. No formal verification or code is provided, so independent checking of the corrected range is especially warranted.","tokens_in":16221,"tokens_out":21810,"duration_ms":207633,"concrete_test":"Re-derive Lemma 2 from its own path argument with explicit halving counts: verify that the premise x(e)>=2^{|V|}t+ is what forces a terminal inflow above t+, while x(e)>=2|V|t+ does not for |V|>2. Then simulate ARRIVAL (t+=1) on the smallest known exponential-step switch graph from the literature, or on a brute-force search over all switch graphs up to n=6, and record the maximum edge count in the run profile; if any edge count exceeds 2|V|, Lemma 2's linear bound is false. Finally, rerun Algorithm 1 with r=2^{|V|}t+ on that instance and check both that it returns a valid integral switching flow and that the observed number of recursive calls matches the claimed 2^{O(|V\\T| log(|V|+log t+))} bound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim Theorem 10 depends on Algorithm 2's binary-search case finding a fixed point of the pivot-inflow map f in the interval [0,2|V|t+]. The only justification for that interval is Lemma 2's assertion that every integral switching flow has x(e)<2|V|t+, together with Lemma 5's analogous upper-bound argument for f(2|V|t+). Both rest on the same path-halving calculation, and that calculation does not produce the claimed linear bound. Starting with A=2|V|t+ tokens at the pivot and following a simple path of length at most |V|-1 to an original terminal, repeated halving gives a terminal inflow of at most about A/2^{|V|} = 2|V|t+/2^{|V|}, which is below t+ for |V|>2. To force an arrival of at least t+, the proof needs A=2^{|V|}t+, not A=2|V|t+. The paper itself uses the exponential bound ||x*||<=n2^n t+ in Theorem 19, confirming that the natural bound is exponential. Moreover, for t+=1 the run profile of an ARRIVAL instance can use an edge more than 2|V| times when the deterministic process takes exponential time, so the linear bound is not merely unproved but false. Consequently, the true pivot flow x^-(p) can lie outside [0,2|V|t+], and the binary search in Algorithm 1 and Algorithm 2 may never encounter a correct guess; the correctness proofs of Lemma 5, Lemma 8, and Theorem 10 fail as written. The fix is concrete: take r=2^{O(|V|)}t+ (e.g., 2^{|V|}t+). Then each binary search costs O(|V|+log t+) evaluations, and the recurrences in Lemma 5 and Theorem 10 still give 2^{O(k log|V| log(|V|+log t+))}, so the advertised runtime is preserved. This is a load-bearing but repairable defect, not a refutation of the theorem's plausibility.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies ARRIVAL and its generalization G-ARRIVAL. It proposes a recursive algorithm that guesses the outflow of a pivot vertex and verifies the guess by binary search; choosing pivots from balanced separators yields a 2^{O(k log^2 n)}-time algorithm on n-vertex graphs of treewidth k. The paper also constructs an ℓ1-contracting function whose unique fixed point encodes the answer to a G-ARRIVAL instance, yielding a reduction to approximate fixed-point computation. The recursive framework is used to rederive the subexponential algorithm of Gärtner et al. [16] and to point out parallels with Simple Stochastic Games.","tokens_in":16662,"tokens_out":29961,"duration_ms":252656,"significance":"If the proofs are repaired, the treewidth bound would be a genuine advance: prior work gave a 2^{O(sqrt(n) log n)} algorithm and polynomial-time algorithms only on very restricted graph classes, while no quasi-polynomial bound for bounded-treewidth ARRIVAL was known. The ℓ1-contraction reduction is also novel and, combined with query-efficient algorithms for ℓ1-contractions or future time-efficient versions, could lead to new algorithms for ARRIVAL. The paper is clearly organized and provides useful context linking ARRIVAL to SSG. However, the written proofs contain load-bearing gaps, mainly around Lemma 2 and the separator invariant in Algorithm 2, that must be fixed before the main claims can be accepted.","major_comments":[{"comment":"The stated bound x(e) < 2|V|t+ is not what the proof establishes. The halving argument along a simple path of length at most |V|-1 starting from x(e) ≥ A gives x^-(v_k) ≥ A/2^k, so to force x^-(v_k) > t+ one needs A = 2^{|V|}t+, not A = 2|V|t+. The claimed linear bound is also false as a mathematical statement: for t+ = 1 the run profile of an ARRIVAL instance can traverse an edge more than 2|V| times, since the deterministic process may take exponentially many steps. This bound is load-bearing: the binary search ranges r = 2|V|t+ in Algorithm 1 (line 10) and Algorithm 2 (line 13), and the correctness arguments in Lemma 5 and Lemma 8, rely on it. The paper itself uses the exponential bound ||x*|| ≤ n 2^n t+ in Theorem 19, showing an internal inconsistency. The results are likely repairable by setting r = 2^{O(|V|)} t+; the logarithms in the runtime analyses then remain O(log(|V| + log t+)), but the statements and proofs must be corrected.","section":"Section 2, Lemma 2; Algorithms 1 and 2"},{"comment":"The runtime analysis assumes that after at most k+1 binary-search steps the splitting case halves the number of non-terminals. However, Algorithm 2 does not recompute a balanced separator when a pivot is added to T; it only removes the pivot from S. At the splitting case S = ∅, the remaining graph G−T is the graph obtained from the call's initial instance by deleting all of the initial separator, so a connected component may have size up to half of the initial non-terminal count, not half of the current non-terminal count. Hence Lemma 9's second sentence, as written, is false, and the recurrence T(|V\\T|,0) ≤ ... T(|V\\T|/2, k+1) in Theorem 10 is unsupported. A correct analysis can probably be given by measuring progress in blocks, where each block deletes at most k+1 separator vertices and then reduces the non-terminal count by a factor of two relative to the block's start, but the proof needs to be rewritten.","section":"Section 3.3, Lemma 9 and Theorem 10"}],"minor_comments":[{"comment":"The notation '2|V|−i' should be typeset as 2^{|V|-i}; the current rendering is ambiguous and should be fixed.","section":"Section 2, Lemma 2 proof"},{"comment":"If the binary search range is corrected to r = 2^{O(|V|)} t+, the comments and variable names in the pseudocode should be updated to match the corrected bound.","section":"Algorithms 1 and 2"},{"comment":"The notation g(x̂)_v for v ∈ T is used without a formal definition; the projection g was defined only on non-terminal coordinates, so the intended meaning should be made explicit.","section":"Section 4, near Lemma 18"},{"comment":"The sentence ending with 'using Lemma 2' when deriving x^-(p) ≤ t+_p should cite the total-arrivals equation from Theorem 1 rather than the edge bound from Lemma 2, since the edge bound is not needed there.","section":"Lemma 5 proof"},{"comment":"The text says the reduction is 'to finding a fixed point', but Theorem 19 is a reduction to finding an approximate fixed point; the terminology should be made consistent.","section":"Abstract and Section 1"}],"recommendation":"major_revision","confidential_remarks":"The central ideas are sound and the gaps appear fixable without changing the claimed results, so I recommend major revision rather than rejection. The reliance on Gärtner et al. [16] for Lemmas 4 and 6-7 is legitimate prerequisite use, and the paper should make clear which specific bounds are new. The authors should also double-check the separator invariant in Algorithm 2, as the current recurrence in Theorem 10 is not justified by the pseudocode as written."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper is worth reading and worth refereeing. The bounded-treewidth algorithm for ARRIVAL is a real new result, and the recursive framework around it is clean. The reduction to ell_1-contraction fixed points is also a new and interesting connection. But the written proof has a genuine gap, and the stress-test note correctly identifies it: Lemma 2's halving argument only establishes an exponential bound, and the stated linear bound 2|V|t+ is actually false for t+=1 when run profiles get long. Since Algorithms 1 and 2 set their binary search range to exactly 2|V|t+, the correctness proofs of Lemma 5, Lemma 8, and Theorem 10 fail as written. The fix is straightforward: take r=2^{O(|V|)}t+ instead, and the advertised runtime 2^{O(k log n log(n+log t+))} should survive, because log r only adds O(|V|) to the token-count bound and the recursion-depth factor already absorbs that. The ell_1-contraction reduction is a nice novel angle: discount the one-step update, get a Banach fixed point, and use it to read off the answer. But the step from the fixed point to individual terminal counts in Theorem 19 is under-specified. Lemma 18 proves only a total lower bound on terminal inflow, and the rounding argument that yields each t^-_v is sketched rather than proved. It is probably repairable, but a referee should ask for the full argument. What the paper does well: the algorithm is a genuine contribution that matches the SSG treewidth result, the framework rederives the known subexponential and feedback-vertex-set bounds, and the exposition is mostly clear. The citation of [16] is self-citation, but it points to a published prerequisite and the dependency is honest. No code or formal verification accompanies the paper, so the proof carries the weight—which makes the Lemma 2 gap matter. Who it is for: researchers in ARRIVAL, TFNP, or parameterized algorithms for zero-player games. It deserves a serious referee. I would not desk-reject it; the main idea is plausible and likely correct after repairs. The right outcome is a conditional accept that requires the Lemma 2 fix and a more detailed fixed-point-to-answer proof.","headline":"The treewidth algorithm is genuinely new and worth refereeing, but the written proof has a load-bearing gap—Lemma 2 gives a false linear bound—which has a clean exponential fix that preserves the stated runtime.","tokens_in":693,"tokens_out":1146,"would_cite":true,"duration_ms":76587,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves a treewidth-parameterized quasi-polynomial algorithm for the ARRIVAL game and reduces its generalization to ℓ1-contraction fixed points.","keywords":["ARRIVAL","G-ARRIVAL","switching flow","treewidth","balanced separator","ell1-contraction","fixed point","zero-player game"],"falsifier":"Search exhaustively over small switch graphs and token counts for an integral switching flow with $x(e) \\ge 2|V|t_+$ on some edge $e$. Finding one would refute the stated Lemma 2 and break the binary-search range in Algorithm 1 and Algorithm 2; finding none on modest sizes would support the lemma but would not prove it.","tokens_in":16037,"feed_emoji":"🎲","tokens_out":7693,"duration_ms":60596,"temperature":0.7,"pith_summary":"ARRIVAL is a deterministic zero-player token game whose decision problem lies in NP∩coNP but is not known to be in P. This paper establishes that on n-vertex instances of treewidth k, ARRIVAL can be solved in time $2^{O(k\\log^2 n)}$, which is quasi-polynomial for every fixed k. The algorithm works on a multi-token generalization, G-ARRIVAL, by recursively guessing the outflow of a pivot vertex and verifying the guess with a binary search; balanced separators drive the recursion to split the instance. The same recursive framework also reproduces the best-known subexponential bound. A second result reduces G-ARRIVAL to finding an approximate fixed point of an $\\ell_1$-contracting function, so any polynomial fixed-point finder for such maps would put G-ARRIVAL in P.","feed_headline":"ARRIVAL gets a quasi-polynomial solver for bounded treewidth","feed_subtitle":"Treewidth controls a recursive switching-flow search, and a fixed-point reduction links ARRIVAL to ℓ1 contractions.","key_machinery":"The load-bearing object is the switching flow: a nonnegative assignment to the edges that obeys alternating behavior at each vertex, flow conservation at non-terminals, and prescribed outflow at terminals. Theorem 1 makes any integral switching flow a certificate for the terminal counts. Around it, the paper builds two mechanisms: a pivot binary-search recursion that converts one non-terminal into a terminal and guesses its outflow, and the one-step update function $f(x)_v = \\sum_{u:s_0(u)=v} h_0(x_u) + \\sum_{u:s_1(u)=v} h_1(x_u)$, where $h_0,h_1$ split each vertex's token mass between its two outgoing edges. Projected to non-terminals and multiplied by a discount factor $\\lambda<1$, this map becomes an $\\ell_1$-contraction whose unique fixed point sits below every fixed point of the undiscounted map, and a sufficiently accurate approximation of that fixed point determines the G-ARRIVAL answer.","core_discovery":"The central claim is that G-ARRIVAL—and therefore ARRIVAL—admits algorithms whose running time is controlled by the treewidth k of the underlying undirected graph. Concretely, the paper proves Theorem 10: given a smallest balanced separator of G−T, Algorithm 2 computes an integral switching flow in time $2^{O(k\\log(|V\\setminus T|)\\log(|V|+\\log t_+))}$, which for ARRIVAL is $2^{O(k\\log^2 n)}$. An integral switching flow is the key certificate: by a theorem of Dohrau et al., any integral switching flow determines exactly how many tokens arrive at each terminal, so solving G-ARRIVAL reduces to finding one. The algorithm's correctness rests on a binary search over one vertex's outflow using the monotonicity of the terminal-count map, and its efficiency rests on balanced separators of size at most k+1 that exist in every subgraph of a treewidth-k graph. The paper also claims a reduction from G-ARRIVAL to the approximate fixed-point problem for $\\ell_1$-contractions, showing the fixed point of the appropriately discounted one-step update reveals the terminal counts.","pith_inferences":["The paper does not pursue time-efficient fixed-point algorithms itself; if such algorithms for monotone $\\ell_1$-contractions appear, this reduction could turn into a polynomial ARRIVAL algorithm.","The stated linear edge-flow bound is used only to set the binary-search range; replacing it by the proven exponential bound would change only logarithmic factors in the stated runtime, so the main treewidth result should survive a repair of that lemma.","The balanced-separator framework looks portable: any parameter that guarantees small separators in subgraphs of the input could plug into Algorithm 2 and yield an analogous quasi-polynomial bound."],"forward_implications":["For every fixed treewidth k, ARRIVAL can be decided in quasi-polynomial time $2^{O(k\\log^2 n)}$, improving the previous $2^{O(\\sqrt{n}\\log n)}$ bound on bounded-treewidth graphs.","The recursive framework yields the prior subexponential bound and a polynomial bound on graphs with bounded feedback vertex set as special instantiations.","A polynomial algorithm for finding approximate fixed points of $\\ell_1$-contractions would immediately give a polynomial algorithm for G-ARRIVAL and hence for ARRIVAL.","The reduction supplies the first natural application of the $\\ell_1$-contraction fixed-point problem, whose query complexity has recently been shown to be polynomial.","ARRIVAL now matches known treewidth-parameterized results for Simple Stochastic Games, reinforcing the long-suspected parallel between the two problems."],"supporting_citations":[{"why":"Proves that ARRIVAL lies in NP∩coNP and that any integral switching flow certifies the terminal counts, which is the basis for solving G-ARRIVAL by finding such a flow.","marker":"[11]"},{"why":"Supplies the previous subexponential algorithm, the monotonicity lemma used in the binary search, and the decomposition lemmas that are rederived inside the recursive framework.","marker":"[16]"},{"why":"Provides the balanced-separator lemma for graphs of treewidth k that guarantees separators of size at most k+1 in every subgraph, which Algorithm 2 relies on.","marker":"[10]"},{"why":"Banach's fixed point theorem gives the unique fixed point of the discounted one-step update, the core of the reduction to $\\ell_1$-contraction.","marker":"[4]"},{"why":"Gives the analogous treewidth-parameterized algorithm for Simple Stochastic Games that the paper compares its ARRIVAL bound to.","marker":"[7]"},{"why":"Introduces G-ARRIVAL and the multi-token formulation used throughout the paper, including the well-definedness of terminal counts.","marker":"[19]"},{"why":"Provides the recent polynomial query upper bound for $\\ell_1$-contractions, which motivates the reduction and is cited as the reason a polynomial ARRIVAL algorithm could follow.","marker":"[18]"}],"fun_headline_variants":["Treewidth parameter speeds up ARRIVAL solving","ARRIVAL solved fast on low-treewidth graphs","Quasi-polynomial time for ARRIVAL on small treewidth","ℓ1-contraction reduction deepens ARRIVAL insight","New ARRIVAL algorithm: treewidth controls runtime"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The search range assumes that no edge is ever used more than $2|V|t_+$ times in any valid flow of tokens, but the supplied proof only shows a far weaker exponential bound; if the stronger bound is false, the termination argument for the binary search as written fails.","fun_headline_variants_meta":{"raw":{"variants":["Treewidth parameter speeds up ARRIVAL solving","ARRIVAL solved fast on low-treewidth graphs","Quasi-polynomial time for ARRIVAL on small treewidth","ℓ1-contraction reduction deepens ARRIVAL insight","New ARRIVAL algorithm: treewidth controls runtime"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000322,"raw_usage":{"total_tokens":1908,"prompt_tokens":1142,"completion_tokens":766,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":758,"completion_tokens_details":{"reasoning_tokens":683}},"tokens_in":758,"tokens_out":766,"duration_ms":6443,"temperature":1.0,"reasoning_tokens":683,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T15:22:26.919312+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search exhaustively over small switch graphs and token counts for an integral switching flow with $x(e) \\ge 2|V|t_+$ on some edge $e$. Finding one would refute the stated Lemma 2 and break the binary-search range in Algorithm 1 and Algorithm 2; finding none on modest sizes would support the lemma but would not prove it.","supporting_citations":[{"cited_title":"Query-Efficient Fixpoints of $\\ell_p$-Contractions","cited_arxiv_id":"2503.16089","evidence_quote":"Proves that ARRIVAL lies in NP∩coNP and that any integral switching flow certifies the terminal counts, which is the basis for solving G-ARRIVAL by finding such a flow."}],"review_version":1}