{"id":"676ef59b-831c-4d84-a5f8-49f7403c13eb","arxiv_id":"2505.21645","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For dense digraphs with minimum degree above n/2 and independent edge costs, a small modification of Karp's patching algorithm produces an ATSP tour whose cost is (1+o(1)) times the optimal assignment cost, with high probability.","lead":"Karp's classic patching algorithm, with a small modification, is shown to find near-optimal asymmetric traveling salesman tours on any dense digraph with minimum degree above n/2, under independent random edge costs. This brings the known equivalence between assignment and tour costs from complete graphs to a much wider class of networks.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 4.3's Broder-chain bound is not derivable as written: δ_t is treated as both a net change and a positive increment, so the inequality bounding E(σ_t) lacks a valid chain.","rationale":"The paper's main theorem depends on Lemma 3, which bounds the number of cycles in the optimal assignment. Lemma 3 in turn rests entirely on the Broder-chain analysis in Section 4.3. The reader's verdict identifies the alpha=1/2 boundary as the weakest assumption, but that is a scope limitation of the stated theorem (alpha>1/2), not a threat to its proof. The reader's rationale does mention 'the delta_t computation in Section 4.3 has a direction ambiguity,' and that is the concern I find most load-bearing. The displayed inequality leading to E(σ_t)≤2n^{4/5}log^{55}n uses δ_t in two incompatible senses: if δ_t is the net change then E(δ_t)=0 and the upper bound from Lemma 11 is vacuous; if it is the positive increment then E(δ_t)=0 is false. A corrected two-sided argument with creation and destruction terms is likely what was intended, and it may well go through, but it is not what is written. For this reason the proof is not fully verified as written, and the appropriate verdict is CONDITIONAL, matching the reader's verdict. No change to the reader's judgment is needed.","tokens_in":12110,"tokens_out":28120,"duration_ms":269501,"concrete_test":"Rewrite the stationarity argument explicitly with δ_t^+ = number of small cycles created and δ_t^- = number destroyed, so σ_t−σ_{t-1}=δ_t^+−δ_t^-. Then check (i) Lemma 11 gives E(δ_t^+)≤ℓ1 log^{25}n/n, (ii) Lemma 12 gives E(δ_{t+1}^-)≥E(σ_t)/(n log^{30}n), and (iii) stationarity gives E(δ_t^+)=E(δ_t^-). If these three statements combine to E(σ_t)≤2ℓ1 log^{55}n, the Lemma 3 conclusion stands with a corrected derivation; if any one fails, the cycle-count bound and Theorem 1 are unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section 4.3, δ_t is defined as the increase in the number of small cycles from M_{t-1} to M_t, and then 'We must of course have E(δ_t)=0.' This treats δ_t as the net change σ_t−σ_{t-1}. Immediately after, 'It follows from Lemma 11 that E(δ_t) ≤ ℓ1 log^{25}n/n' is used as an upper bound on the positive part of the change; but if δ_t is the net change, this inequality is vacuous (E(δ_t)=0) and cannot feed into the displayed chain 0 = E(δ_t+δ_{t+1}) ≤ 2ℓ1 log^{25}n/n − E(σ_t)·n/(log^{30}n·n^2). If δ_t instead denotes the positive part, the stationarity equality is false. The intended argument presumably separates δ_t^+ (small cycles created) and δ_t^- (small cycles destroyed), uses Lemma 11 to bound E(δ_t^+) by ℓ1 log^{25}n/n, Lemma 12 to lower-bound E(δ_{t+1}^-) by E(σ_t)/(n log^{30}n), and stationarity E(δ_t^+)=E(δ_t^-); but none of this is written. As it stands, the derivation of E(σ_t)≤2n^{4/5}log^{55}n, which is the key to Lemma 3 and hence to Theorem 1, is not a valid chain of inequalities. The alpha=1/2 boundary concern in the reader's report is a scope limitation, not a threat to the stated alpha>1/2 theorem.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the asymmetric TSP on a dense digraph D with minimum in- and out-degree at least alpha n, where alpha=1/2+epsilon, and independent edge costs drawn from an 'acceptable' distribution. The main claim (Theorem 1) is that w.h.p. the optimal assignment value v(AP) is asymptotically equal to the optimal tour value v(ATSP), and that a small modification of Karp's patching algorithm finds a tour of cost (1+o(1))v(AP) in polynomial time. The proof has three ingredients: Lemma 2 bounds the costs in the optimal assignment by gamma_n=log^4 n/n; Lemma 3 bounds the number of cycles in the optimal assignment by n^{5/6}; and Section 2 shows that, given these bounds, patching or direct tour construction adds o(1) cost. Lemma 3 is proved via expansion estimates for the low-cost subgraph, uniform optimality of the assignment given the dual variables, and a Broder-chain analysis of the number of small cycles.","tokens_in":12436,"tokens_out":23276,"duration_ms":228211,"significance":"If correct, the paper establishes that the assignment relaxation is asymptotically tight for ATSP on dense digraphs with independent edge costs, substantially extending Karp's classical result from complete digraphs to digraphs with minimum degree above n/2. The proof is parameter-free and contains no circularity: the ATSP/AP gap is derived from concentration inequalities, LP duality, and Markov-chain arguments rather than assumed. The expander lemmas and the Broder-chain approach are interesting tools that may be useful elsewhere. The alpha=1/2 boundary is explicitly acknowledged as open and is not part of the theorem, so I do not treat the collapse of the constants at alpha=1/2 as a flaw. The main barriers to acceptance are the unfinished Markov-chain argument in Section 4.3, the cryptic proof of Lemma 8, and an incorrect-looking reduction in Section 5.","major_comments":[{"comment":"The treatment of delta_t in the Markov-chain argument is internally inconsistent. It is first defined as 'the increase in the number of small cycles' and then asserted that E(delta_t)=0, which treats delta_t as the net change sigma_t - sigma_{t-1}. Immediately afterwards Lemma 11 is used to assert E(delta_t) <= ell_1 log^25 n/n, which is only meaningful for the positive part. The displayed chain 0 = E(delta_t + delta_{t+1}) <= 2 ell_1 log^25 n/n - E(sigma_t) n/(log^30 n n^2) combines both interpretations. If delta_t is the net change, the upper bound on E(delta_t) is vacuous; if delta_t is the positive increment, the stationarity equality is false. The intended argument must introduce delta_t^+ and delta_t^- separately, bound E(delta_t^+) by Lemma 11, lower-bound E(delta_{t+1}^-) by E(sigma_t)/(n log^30 n) via Lemma 12, and use stationarity E(delta_t^+)=E(delta_t^-). As written, the key bound E(sigma_t) <= 2 n^{4/5} log^55 n, which underpins Lemma 3 and hence Theorem 1, is not derived.","section":"4.3"},{"comment":"The proof of Lemma 8 is only a sketch. The sentence 'Because the costs (and maybe the tree) have changed there will be a non-trivial sum of positive and negative costs that sum to zero or a one that sums to gamma_n' does not identify the algebraic relation among the edge costs, the relevant random variables after conditioning on u and v, or the precise event whose probability is asserted to be zero. Since Lemma 8 is used in Lemma 11 to justify restricting to tree edges of cost at most gamma_n, this gap is load-bearing and the argument must be written out in full.","section":"4.2 (Lemma 8)"},{"comment":"The reduction to general distributions for b != 0 is not valid as stated. After scaling to a=1, the paper writes f(x)=e^{-bx+O(x^2)} and F(x)=P(C>=x)=b^{-1}e^{-bx+O(x^2)} as x -> 0. Since F(0^+)=1 for every continuous cost distribution, this forces b=1. Moreover, for any distribution with f(0)=1, the tail is F(x)=1-x+O(x^2)=e^{-x+O(x^2)}, so the linear coefficient in the exponent is always 1 and cannot serve as an independent parameter. The ratio f/F = b e^{O(gamma_n^2)} used to derive asymptotic uniformity of M^* is therefore not justified. Because the theorem claims all acceptable distributions, this reduction needs to be repaired, for example by applying the quantile transformation uniformly to all acceptable distributions.","section":"5"}],"minor_comments":[{"comment":"In the near-perfect case, the update with x=a_{M_{t-1}} and y != b_{M_{t-1}} deletes the nonexistent edge (x, phi_{M_{t-1}}(x)); it should delete (y, phi^{-1}_{M_{t-1}}(y)).","section":"4.3 (Broder chain)"},{"comment":"The McDiarmid inequality is misstated: the probability should be P(|Z-E(Z)| >= t), and the changed coordinate should be Y_i, not Y_1.","section":"3 (Eq. (4))"},{"comment":"The definition of 'quite surely' uses o(r^{-K}); the variable should be n, and the statement should make clear that the bound holds for every constant K>0.","section":"Footnote 1"},{"comment":"The sentence 'W.h.p. there are at most n^{1/6} large' appears to be a typo: since a large cycle has length at least ell_1=n^{4/5}, the correct bound is n^{1/5}.","section":"4.3 (end)"},{"comment":"Both lemmas state 'for i=1,2,...,r' with r undefined; this should be n.","section":"4.2 (Lemmas 11-12)"},{"comment":"Reference [6] lacks publication data, and reference [5] has a typo in the author name ('nd').","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The overall strategy is plausible and the statistical estimates are detailed, but three load-bearing points need real work before the theorem is established: the Section 4.3 derivation of E(sigma_t) is invalid as written, Lemma 8 is not proved, and Section 5's b!=0 case is mathematically inconsistent. I do not see circularity or parameter-fitting, and the issues appear fixable within the manuscript's scope, so I recommend major revision rather than rejection. The authors should also correct the several notational typos listed in the minor comments."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth reading and the main result is probably true: for digraphs with minimum in/out degree at least (1/2+epsilon)n and acceptable independent edge costs, Karp's patching algorithm gives a tour within (1+o(1))v(AP). That is a genuine extension beyond the complete digraph and beyond the previous dense-plus-random-edge model, and the Broder-chain argument for bounding assignment cycles is a real methodological addition. The expansion proof for Lemma 2 is also clean, and the reduction to general distributions is handled honestly. I would not desk-reject this.\n\nThe trouble is Section 4.3, and the stress-test note is right. The chain that yields E(sigma_t) <= 2 n^{4/5} log^{55} n is not a valid derivation as written. delta_t is first called the increase in the number of small cycles, then we are told E(delta_t)=0, which makes delta_t a net change; but the very next step bounds E(delta_t) from above as if delta_t were a positive increment. Those two uses are incompatible. To get the claimed bound you need to split delta_t into delta_t^+ and delta_t^- and use stationarity, Lemma 11 for the positive part, Lemma 12 for the negative part. That is plausibly the intended argument, but it is not written, and this bound is the core of Lemma 3 and hence of Theorem 1. So the proof, as it stands, has a load-bearing gap. I would not call it fatal---I suspect it can be repaired---but it is not a matter of a typo.\n\nOther soft spots are minor. Lemma 8 is cryptic: \"both of these possibilities have probability 0\" needs a real argument, because it is doing work to bound the cost of tree edges. The McDiarmid inequality statement also has a small typo (P(|E(Z)|) should presumably be P(|Z-E(Z)|)), but the intended inequality is standard. The alpha=1/2 boundary is a scope limitation, not a flaw; the paper says that case is open, which is fair.\n\nWho is this for? Probabilistic combinatorics and ATSP heuristic people. It deserves a serious referee, but the referee should insist on a rewritten Section 4.3 before publication. I would send it to review, not because the current proof is solid, but because the result is important enough and the intended method is clear enough that fixing this gap is a tractable revision.","headline":"A real extension of Karp's theorem to dense digraphs, with a nice Broder-chain idea, but the proof as written has a hole in the key cycle-count bound.","tokens_in":12969,"tokens_out":1859,"would_cite":false,"duration_ms":21874,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","05C20","68W40","90C27","60C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"For dense digraphs, assignment gives a tight bound for ATSP","keywords":["asymmetric traveling salesman problem","assignment problem","Karp patching algorithm","dense digraphs","random edge costs","minimum degree","cycle cover","probabilistic analysis"],"falsifier":"Take $D$ to be the complete bipartite orientation: split $[n]$ into two parts of size $n/2$ and put every directed edge from each part to the other, then add $\\varepsilon n$ random edges per vertex so the minimum in- and out-degree is $(1/2+\\varepsilon)n$. Draw i.i.d. uniform$[0,1]$ costs, compute the optimal assignment and the optimal ATSP tour for $n$ between 200 and 1000 and small $\\varepsilon$, and compare $v(\\mathrm{ATSP})/v(\\mathrm{AP})$; if the ratio is bounded away from 1, Theorem 1 would be false, while a ratio approaching 1 even near $\\alpha=1/2$ would indicate the threshold is not necessary even though the proof's intersection mechanism is.","tokens_in":11891,"feed_emoji":"🧩","tokens_out":16037,"duration_ms":153529,"temperature":0.7,"pith_summary":"This paper claims that on a dense directed graph where every vertex has at least $\\alpha n$ incoming and $\\alpha n$ outgoing edges with a fixed $\\alpha>1/2$, the asymmetric traveling salesperson problem (the cheapest single cycle visiting every vertex) has the same asymptotic cost as the assignment problem (the cheapest collection of disjoint cycles covering all vertices), when edge costs are independent random variables from a broad class of distributions. More concretely, it proves that with high probability the optimal tour costs $(1+o(1))$ times the optimal assignment, and a small modification of Karp's patching algorithm—solve the assignment, then merge its cycles—finds such a tour in polynomial time. This matters because the assignment problem is computationally much easier than the traveling salesperson problem, so the paper shows that a cheap lower bound is tight across a large family of graphs, extending the classic complete-digraph result. The key reason the proof works is that with minimum degree above $n/2$, any two large sets of in-neighbors and out-neighbors overlap, which creates many low-cost ways to patch cycles together.","feed_headline":"Dense digraphs: patching attains the assignment bound","feed_subtitle":"When every vertex has over n/2 in- and out-edges, a matching-based heuristic reaches the ATSP optimum with high probability.","key_machinery":"The argument is carried by three mechanisms. First, the neighborhood-intersection property of digraphs with minimum degree $\\alpha n$, $\\alpha>1/2$: any two large sets, one of in-neighbors and one of out-neighbors, intersect in at least $2\\varepsilon n$ vertices, so every cycle in the assignment has many low-cost patching pairs joining it to other cycles. Second, expansion estimates for the subgraph of cheap edges show that every vertex pair is connected by a short alternating path of cheap edges, forcing the optimal assignment to avoid expensive edges; the analysis then transfers to a bipartite graph $G^+$ defined by the assignment LP's dual variables, where the optimal matching becomes asymptotically uniform, allowing a Markov chain on matchings (introduced in [3]) to bound the number of cycles. Third, when the cycle cover has few large cycles, a modified patching step deletes two edges per cycle, closes the resulting paths into a tour, and repairs each missing closing edge by a local replacement using the many cheap out- and in-neighbors that exist with high probability.","core_discovery":"On its own terms, the paper proves Theorem 1: for a digraph $D$ with minimum in- and out-degree at least $\\alpha n$, where $\\alpha=1/2+\\varepsilon$, and independent edge costs drawn from an acceptable distribution—one with density $f(x)=a+bx+O(x^2)$ as $x\\to 0$ and either an exponential tail or bounded support—the asymptotic identity $v(\\mathrm{ATSP})=(1+o(1))v(\\mathrm{AP})$ holds with high probability, and a small modification of Karp's patching algorithm finds a tour of that cost in polynomial time. This extends the original complete-digraph result to all digraphs of minimum degree above $n/2$, and it broadens the admissible cost distributions beyond uniform$[0,1]$ to include exponential and other acceptable laws. The proof also establishes that, with high probability, the optimal assignment uses only edges of cost $O(\\log^4 n / n)$ and decomposes into at most $n^{5/6}$ cycles, structural facts that drive the patching-cost analysis.","pith_inferences":["One testable extension is computational: on random dense digraphs with $n$ up to a few thousand and small $\\varepsilon$, compare optimal ATSP and AP costs under uniform$[0,1]$ costs; the ratio should approach 1, and a discrepancy at small $\\varepsilon$ would pinpoint where the proof needs strengthening.","The reliance on neighborhood overlap suggests the $\\alpha>1/2$ threshold may be an artifact of the technique, because random costs themselves create expansion; similar conclusions might hold under weaker degree assumptions such as $n/2+o(n)$ or with a small random perturbation.","The proof's logic suggests that only the local density at cost zero and the expansion of the cheap-edge subgraph matter, so the theorem likely extends to distributions with $f(0)>0$ and sufficiently light tails even if the density is not exactly linear at zero."],"forward_implications":["For every digraph with minimum in- and out-degree above $n/2$ and acceptable independent costs, the assignment problem's optimum is asymptotically achievable as a tour, so the assignment relaxation is tight for ATSP.","The modified patching algorithm runs in polynomial time and, with high probability, outputs a tour of cost $(1+o(1))$ times the optimum on this class.","The structural lemmas show that with high probability the optimal assignment uses only edges of cost $O(\\log^4 n / n)$ and decomposes into at most $n^{5/6}$ cycles, making the assignment LP well-behaved on dense digraphs.","The result covers uniform, exponential, and any acceptable distribution whose density is $a+bx+O(x^2)$ at zero with a subexponential tail or bounded support; for the uniform case the proof goes through an explicit cost transformation."],"supporting_citations":[{"why":"Defines the patching algorithm and proves its asymptotic optimality on the complete digraph, the result this paper extends.","marker":"[9]"},{"why":"Prior result for random perturbations of dense digraphs whose proof strategy is followed in parts of this paper.","marker":"[6]"},{"why":"Supplies the Markov chain on perfect and near-perfect matchings used to bound the number of cycles in the optimal assignment.","marker":"[3]"},{"why":"Earlier refinement of the patching-algorithm analysis for random asymmetric TSP whose case structure is adapted here.","marker":"[4]"},{"why":"Establishes the probabilistic AP/ATSP cost-comparison framework this paper extends to dense digraphs.","marker":"[7]"},{"why":"Textbook basis for representing an optimal assignment basis as a spanning tree with dual variables, used in Lemmas 7-9.","marker":"[1]"},{"why":"Source of the Chernoff-type bounds for hypergeometric variables in the expansion estimates of Lemma 4.","marker":"[8]"},{"why":"Reference for the concentration and bounded-differences inequalities used throughout the probabilistic estimates.","marker":"[5]"}],"fun_headline_variants":["Karp's patching attains assignment bound on dense digraphs","Patching beats half-density for ATSP","Dense digraphs: patching reaches assignment bound","Karp's algorithm works on all n/2-dense digraphs","Assignment bound matched by patching on dense digraphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof requires the minimum degree to be strictly above $n/2$, because its counting depends on any two large in- and out-neighborhoods having at least $2\\varepsilon n$ common vertices; at exactly $n/2$ a digraph can have bipartite-like disjoint neighborhoods and the patching-pair estimate collapses, which is why the paper leaves $\\alpha=1/2$ open.","fun_headline_variants_meta":{"raw":{"variants":["Karp's patching attains assignment bound on dense digraphs","Patching beats half-density for ATSP","Dense digraphs: patching reaches assignment bound","Karp's algorithm works on all n/2-dense digraphs","Assignment bound matched by patching on dense digraphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000737,"raw_usage":{"total_tokens":3321,"prompt_tokens":1003,"completion_tokens":2318,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":619,"completion_tokens_details":{"reasoning_tokens":2233}},"tokens_in":619,"tokens_out":2318,"duration_ms":18125,"temperature":1.0,"reasoning_tokens":2233,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:26:52.692924+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $D$ to be the complete bipartite orientation: split $[n]$ into two parts of size $n/2$ and put every directed edge from each part to the other, then add $\\varepsilon n$ random edges per vertex so the minimum in- and out-degree is $(1/2+\\varepsilon)n$. Draw i.i.d. uniform$[0,1]$ costs, compute the optimal assignment and the optimal ATSP tour for $n$ between 200 and 1000 and small $\\varepsilon$, and compare $v(\\mathrm{ATSP})/v(\\mathrm{AP})$; if the ratio is bounded away from 1, Theorem 1 would be false, while a ratio approaching 1 even near $\\alpha=1/2$ would indicate the threshold is not necessary even though the proof's intersection mechanism is.","supporting_citations":[{"cited_title":"Karp, A patching algorithm for the non-symmetric traveling salesman problem, SIAM Journal on Com- puting 8 (1979) 561–573","cited_arxiv_id":null,"evidence_quote":"Defines the patching algorithm and proves its asymptotic optimality on the complete digraph, the result this paper extends."},{"cited_title":"Frieze and P","cited_arxiv_id":null,"evidence_quote":"Prior result for random perturbations of dense digraphs whose proof strategy is followed in parts of this paper."},{"cited_title":"Broder, How hard is it to marry at random, ? (On the approximation of the permanent), Proceedings of the 18th Annual ACM Symposium on Theory of Computing , ACM Press, 1986, 50–58","cited_arxiv_id":null,"evidence_quote":"Supplies the Markov chain on perfect and near-perfect matchings used to bound the number of cycles in the optimal assignment."},{"cited_title":"Dyer and A.M","cited_arxiv_id":null,"evidence_quote":"Earlier refinement of the patching-algorithm analysis for random asymmetric TSP whose case structure is adapted here."},{"cited_title":"Frieze and G","cited_arxiv_id":null,"evidence_quote":"Establishes the probabilistic AP/ATSP cost-comparison framework this paper extends to dense digraphs."},{"cited_title":"Ahuja, T","cited_arxiv_id":null,"evidence_quote":"Textbook basis for representing an optimal assignment basis as a spanning tree with dual variables, used in Lemmas 7-9."},{"cited_title":"Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58 (1963) 13-30","cited_arxiv_id":null,"evidence_quote":"Source of the Chernoff-type bounds for hypergeometric variables in the expansion estimates of Lemma 4."},{"cited_title":"Frieze nd M","cited_arxiv_id":null,"evidence_quote":"Reference for the concentration and bounded-differences inequalities used throughout the probabilistic estimates."}],"review_version":1}