{"id":"ed731788-1499-4c6a-9446-505c2fa875c1","arxiv_id":"2509.00448","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Graphic Multi-Path TSP has a 2-approximation and LP integrality gap at most 2; Graphic Ordered TSP has a 1.791-approximation.","lead":"This paper finds multiple least-total-length paths covering a graph, one per start-end pair, within twice the optimum cost. It also improves the ordered version of the problem on unweighted graphs to a 1.791 approximation.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: Theorem 1.1's proof is internally consistent and the graphic reconnection bound is valid.","rationale":"The reader's ACCEPT is appropriate. I checked Lemma 3.2 equation-by-equation, including the cases zP_v≤1 and zP_v>1, the treatment of terminals S∪T, and the derandomization induction. The algorithm's only graph-specific step is the reconnection cost of 2 per uncovered vertex; this is exactly where the graphic assumption is used and it is internally justified by strong connectivity of the bidirected graph. The Theorem 1.3 n-k issue is cosmetic and was already noted by the reader as an imprecise intermediate bound. No step in the central proof relies on unproven consensus; the probability calculations are elementary and the cost accounting is exact. I therefore recommend UNCHANGED.","tokens_in":13029,"tokens_out":45744,"duration_ms":576608,"concrete_test":"As a worth-running verification: independently derive x(δ(S))≥2 for the Ordered-TSP specialization from constraints (2)-(6). For cuts with terminals on both sides, at least two boundary commodities cross; for cuts with no terminals on one side, sum constraint (4) over commodities and use (6). If this derivation fails, Theorem 1.2's parity step would need a different argument, but Theorem 1.1 would not be affected.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After a good-faith pass over the argument, I find no load-bearing concern for the central claim (Theorem 1.1). The randomized rounding is sound: for each vertex v, expected sampling cost is exactly zP_v, the probability v is left uncovered is at most exp(-zP_v) (exactly 0 for S∪T), and each uncovered vertex is reconnected at cost 2 using an arc (v,w) from Y to V\\Y, whose existence follows from strong connectivity of the bidirected graph. The per-vertex bound zP_v+2exp(-zP_v) ≤ max(2,2zP_v), combined with zP_v ≤ z_v and z_v ≥ 1 for v∉S∪T, gives total cost ≤ 2Σ_v z_v = 2LP. Derandomization by conditional expectations is valid because choosing the path minimizing expression (11) preserves the stated invariant. The only qualifications are secondary: Theorem 1.3 uses n-k where n-|S∪T| is the correct bound, but the conclusion still follows since each component of an optimal solution contains a terminal and |U|≤OPT; Theorem 1.2 cites rather than proves the cut condition x(δ(S))≥2, but this follows from constraints (4)-(6) plus the terminal cycle. Neither threatens the 2-approximation.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Graphic Multi-Path TSP and Graphic Ordered TSP. For Graphic Multi-Path TSP it gives a 2-approximation algorithm based on solving a flow LP, decomposing the flow into paths, sampling one path per commodity, and reconnecting uncovered vertices by doubled edges; the analysis is derandomized by conditional expectations. For Graphic Ordered TSP it gives a (1 + e/(2e-2))-approximation algorithm, using a single-edge reconnection followed by an Odd-join parity correction. The paper also proves a reduction showing that any below-2 approximation for Graphic Uncapacitated Multi-Depot VRP (the case s_i = t_i) would yield a below-2 approximation for Graphic Multi-Path TSP. A corollary of the main result is an integrality-gap upper bound of 2 for the proposed LP.","tokens_in":13291,"tokens_out":43693,"duration_ms":501822,"significance":"If the results hold, they improve the best known approximation ratios for two TSP variants in graphic metrics: from 2.214 to 2 for Graphic Multi-Path TSP and from 1.868 to 1.791 for Graphic Ordered TSP. The main algorithm is simple and the analysis is transparent, with an explicit derandomization argument. The paper also contains a conceptually interesting reduction connecting the general problem to the depot version. The central derivation for Theorem 1.1 is self-contained and appears sound, and the work gives a clean integrality-gap result for the LP.","major_comments":[],"minor_comments":[{"comment":"The step 'g(z)=z+(1+alpha)e^{-z} is convex and thus g(z) <= max{g(0), g(1)z}' is not a consequence of convexity alone; convexity does not imply that inequality for all z>=0. The inequality is true for this particular g, but a short proof should be supplied, for example by splitting into z<=1 and z>1 and using e^{-z} <= z/e for z>=1.","section":"Section 4, proof of Theorem 1.2"},{"comment":"The inequality |V \\ (S ∪ T ∪ V_P)| <= n - k is not valid when k > |S ∪ T|, e.g., for six distinct ordered pairs on three terminals. The correct bound is |V \\ (S ∪ T)|, and the proof should use the fact |V \\ (S ∪ T)| <= OPT(I), since every non-terminal vertex has degree at least 2 in the union of walks of any feasible solution. The argument goes through with this replacement.","section":"Section 5, proof of Theorem 1.3, Case 3.2"},{"comment":"In the reconnection phase, adding only a single arc (v,w) to a walk F_i containing w does not by itself preserve the property that F_i is a walk from o_i to o_{i+1}. The correctness proof should explain why the final multigraph (∪_i F_i) ∪ J is a feasible Ordered TSP solution, e.g., by inserting the Eulerian components of the extra edges as closed detours into the cycle formed by the sampled paths, which preserves the prescribed terminal order.","section":"Section 4, Algorithm 2, correctness"}],"recommendation":"minor_revision","confidential_remarks":"The main theorem (Theorem 1.1) is correct and the paper is a good fit for the journal. The secondary theorems contain small proof gaps that are local and easily repairable; I would be happy to recommend acceptance once they are addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis is a good paper. The headline result is a 2-approximation for Graphic Multi-Path TSP, down from the general-metric 2.214, and a 1.791-approximation for Graphic Ordered TSP in graphic metrics. The arguments are self-contained, the LP rounding is elegant, and I checked the main expectation bound, the derandomization, and the parity correction in the Ordered TSP section. They go through. The reconnection bound of cost 2 per uncovered vertex is genuinely where the graphic assumption does the work; that's clearly stated and correct.\n\nWhat's new: sampling paths directly from the flow decomposition rather than sampling arborescences via the Bang-Jensen lemma. That's a real twist. It lets them avoid the parity correction that the general algorithm needs, and the unit edge costs let them afford the doubled-edge reconnection. The Ordered TSP improvement comes from balancing two Odd-joins, the fractional one from Wolsey's analysis and the one from the reconnection edges. The convex combination is standard but the application is clean. The conditional reduction to the single-depot case (Theorem 1.3) is a nice bonus.\n\nSoft spots, in proportion: these are minor. The claim that y = x/2 is in the Odd-join polytope is cited rather than proved; it's true, but a reader has to take the citation on faith. In Theorem 1.3's proof, the bound uses n-k where the correct intermediate is n - |S∪T|; the conclusion still holds because |S∪T| ≤ 2k and the slack absorbs it, but the written inequality is imprecise. Neither issue threatens the main theorems.\n\nOne more thing: the paper's own conclusion is honest about the limit of the approach. The worst case is when the sum of terminal distances is near zero, and they explicitly say the 2 barrier is robust unless the VRP special case improves. I appreciate that.\n\nBottom line: this deserves a serious referee. The results are real, the proofs are reproducible, and the exposition is readable. I'd bring it to a reading group and I'd cite it for the new approximation ratios. Send it out.\n\nBest,\n[Your name]","headline":"Solid paper: a clean 2-approximation for Graphic Multi-Path TSP and a nice extension to Ordered TSP, with proofs that check out.","tokens_in":13840,"tokens_out":2342,"would_cite":true,"duration_ms":23851,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","90C27","90C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"Graphic Multi-Path TSP has a deterministic 2-approximation algorithm; Ordered TSP in graphic metrics reaches 1.791.","keywords":["Graphic Multi-Path TSP","approximation algorithm","LP integrality gap","flow decomposition","Graphic Ordered TSP","Odd-join","randomized rounding","vehicle routing"],"falsifier":"Run an exact solver on small connected unweighted graphs and terminal pairs, comparing the integer optimum with the LP optimum; any instance with ratio strictly greater than 2 would refute the claimed integrality gap and hence Theorem 1.1.","tokens_in":12908,"feed_emoji":"🛣️","tokens_out":10284,"duration_ms":109000,"temperature":0.7,"pith_summary":"The paper proves that two path-constrained versions of the Traveling Salesman Problem (TSP) get much better approximation guarantees when the input is a graphic metric—that is, shortest-path distances in a connected unweighted graph. Its main result is a deterministic 2-approximation for Graphic Multi-Path TSP, improving the previous 2.214-approximation known for general metrics, and as a corollary the LP relaxation has integrality gap at most 2. The algorithm solves a flow LP, decomposes each commodity's flow into paths, samples one path per source-sink pair with probability equal to its flow value, then attaches every vertex missed by the sampled paths at cost two. The analysis reduces to a per-vertex inequality: the expected sampling cost plus twice the probability of being left out never exceeds the LP contribution of that vertex. The same sampling framework, combined with a parity-correction step using an Odd-join, gives a 1.791-approximation for Graphic Ordered TSP, improving the previous 1.868 general-metric bound.","feed_headline":"Sampled LP paths give factor-2 Graphic Multi-Path TSP","feed_subtitle":"Ordered TSP in graphic metrics drops to 1.791, beating the 1.868 general-metric bound.","key_machinery":"The engine is the flow LP (constraints (1)–(7)) on the bidirected unit-edge graph, whose optimal solution decomposes into per-commodity paths and cycles. Sampling paths according to their flow weights, then covering leftover vertices with doubled arcs, is carried by the identity z + 2e^{-z} ≤ 2 max{1, z}: the first term is the expected sampled cost of a vertex, the second is twice its probability of being left uncovered, and the LP gives the non-terminal coverage constraint used to compare with the optimum. For Ordered TSP the second ingredient is the Odd-join (an edge set correcting vertex-degree parity): both the reconnection edges and half the LP flow are Odd-joins, and the algorithm take","core_discovery":"Central claim: Theorem 1.1 gives a 2-approximation for Graphic Multi-Path TSP. The algorithm solves a flow LP, decomposes each commodity's flow into paths, samples one path per commodity with probability equal to its flow value, and reconnects every missed vertex at cost two using doubled arcs—possible in a strongly connected bidirected unit-edge graph. The per-vertex analysis bounds expected sampling cost z_v plus expected reconnection cost 2e^{-z_v} by 2z_v using the LP constraint z_v ≥ 1, so the expected total is at most 2 LP; derandomization makes it deterministic. The same sampling framework with a parity-correction step gives a (1+e/(2e−2))-approximation for Graphic Ordered TSP, and a","pith_inferences":["The per-vertex bound z + 2e^{-z} ≤ 2 max{1,z} is a template: for any routing-cover problem where a missed vertex can be attached for a constant C, the same sampling argument yields a factor of max{C, 1 + C/e}, suggesting where to look for improvements in other TSP variants.","Theorem 1.3 isolates the hard regime for the factor 2: the close-terminal case, where total source-sink distance is small, is exactly where the depot version must be improved to push Graphic Multi-Path TSP below 2.","The balancing of two Odd-joins suggests that other precedence-constrained routing problems might be attacked by identifying two cheap parity-correcting structures and optimizing their convex combination, rather than committing to one."],"forward_implications":["Graphic Multi-Path TSP has a deterministic polynomial-time 2-approximation, and the LP relaxation for the problem has integrality gap at most 2.","The previous best general-metric factor of 2.214 is improved to 2 for graphic metrics without using arborescence sampling or a separate parity-correction phase.","Graphic Ordered TSP admits a 1 + e/(2e−2) < 1.791 approximation, improving the 1.868 general-metric bound.","Any (2−δ)-approximation for Graphic Uncapacitated Multi-Depot VRP (the special case si = ti) automatically gives a (2−f(δ))-approximation for Graphic Multi-Path TSP.","The algorithm is structurally simple: one LP solve, a flow decomposition, sampling, and a greedy reconnection, all polynomial-time."],"supporting_citations":[{"why":"defines the same LP relaxation and gives the 2.214 general-metric Multi-Path TSP approximation that the new graphic factor-2 result improves on.","marker":"[6]"},{"why":"supplies the polynomial path/cycle decomposition theorem for flows and the integrality of the Odd-join polytope, both used as black boxes in the algorithms.","marker":"[14]"},{"why":"proves that half the LP solution is in the Odd-join polytope, giving the LP/2 parity-correction bound used in the Ordered TSP analysis.","marker":"[19]"},{"why":"is the previous best Ordered TSP approximation in general metrics (1.868) that the paper's graphic 1.791 bound improves on.","marker":"[2]"}],"fun_headline_variants":["Sampled LP paths hit factor-2 for Graphic Multi-Path TSP","Graphic Multi-Path TSP gets 2-approximation via LP sampling","Factor-2 for Graphic Multi-Path TSP, 1.791 for Ordered","LP sampling gives factor-2 Graphic Multi-Path and 1.791 Ordered"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The argument assumes that every vertex missed by the sampled paths can be attached to an already-covered vertex by adding exactly two directed edges (one in, one out); this exact cost-two attachment is true for unweighted bidirected graphs but breaks for general metric costs, which is why the result is graphic rather than metric.","fun_headline_variants_meta":{"raw":{"variants":["Sampled LP paths hit factor-2 for Graphic Multi-Path TSP","Graphic Multi-Path TSP gets 2-approximation via LP sampling","Factor-2 for Graphic Multi-Path TSP, 1.791 for Ordered","LP sampling gives factor-2 Graphic Multi-Path and 1.791 Ordered"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000676,"raw_usage":{"total_tokens":2968,"prompt_tokens":854,"completion_tokens":2114,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":598,"completion_tokens_details":{"reasoning_tokens":2027}},"tokens_in":598,"tokens_out":2114,"duration_ms":16602,"temperature":1.0,"reasoning_tokens":2027,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T13:41:34.881023+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an exact solver on small connected unweighted graphs and terminal pairs, comparing the integer optimum with the LP optimum; any instance with ratio strictly greater than 2 would refute the claimed integrality gap and hence Theorem 1.1.","supporting_citations":[{"cited_title":"Approximating traveling salesman problems using a bridge lemma","cited_arxiv_id":null,"evidence_quote":"defines the same LP relaxation and gives the 2.214 general-metric Multi-Path TSP approximation that the new graphic factor-2 result improves on."},{"cited_title":"Combinatorial Optimization: Polyhedra and Efficiency , volume 24 of Algorithms and Combinatorics","cited_arxiv_id":null,"evidence_quote":"supplies the polynomial path/cycle decomposition theorem for flows and the integrality of the Odd-join polytope, both used as black boxes in the algorithms."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"proves that half the LP solution is in the Odd-join polytope, giving the LP/2 parity-correction bound used in the Ordered TSP analysis."},{"cited_title":"A (3/2 + 1/ e)-approximation algorithm for ordered TSP","cited_arxiv_id":null,"evidence_quote":"is the previous best Ordered TSP approximation in general metrics (1.868) that the paper's graphic 1.791 bound improves on."}],"review_version":1}