Karp's patching algorithm on dense digraph

Alan Frieze

REVIEW 3 major objections 6 minor 11 references

Karp's patching algorithm on dense digraph

T0 review · 3 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For dense digraphs, assignment gives a tight bound for ATSP

desk verdict 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. read the letter →

arxiv 2505.21645 v2 pith:LHZL3PFI submitted 2025-05-27 math.CO cs.DM

Alan Frieze This is my paper

classification math.COcs.DM MSC 05C8005C2068W4090C2760C05

keywords asymmetrictravelingsalesmanproblemassignmentKarppatchingalgorithmdensedigraphsrandomedgecostsminimumdegreecyclecoverprobabilisticanalysis

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

The 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.

Other 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.

Who 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.

Referee Report

3 major / 6 minor

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.

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 (3)

[4.3] 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.
[4.2 (Lemma 8)] 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.
[5] 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.

minor comments (6)

[4.3 (Broder chain)] 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)).
[3 (Eq. (4))] 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.
[Footnote 1] 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.
[4.3 (end)] 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}.
[4.2 (Lemmas 11-12)] Both lemmas state 'for i=1,2,...,r' with r undefined; this should be n.
[References] Reference [6] lacks publication data, and reference [5] has a typo in the author name ('nd').

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof derives v(ATSP) ≈ v(AP) from independent probabilistic and polyhedral arguments, with no fitted parameter renamed as a prediction and no load-bearing self-citation.

full rationale

I walked the derivation chain: Lemma 2 is proved by constructing low-cost M-alternating paths from expansion estimates on the low-cost subgraph (Lemma 4), then using optimality of the assignment to rule out expensive edges; Lemma 3 is proved through LP duality, the structure of optimal bases, the distribution of the optimal matching in G+ (Lemma 9), and the Broder Markov chain with concentration estimates in Lemmas 11 and 12; the patching analysis in Section 2 then adds o(1) to v(AP) in three cases with explicit probabilistic bounds. None of these steps assumes v(ATSP) or the theorem's conclusion, and no parameter is fitted to the quantity being predicted. The citation to Frieze and Michaeli [6] is explicitly described as a proof-strategy source ('Our proof strategy follows that of [6] in some places') and does not carry the central claim; the core expansion, dual-variable, and Markov-chain arguments are self-contained and checkable from the paper. The manuscript's own remark that alpha = 1/2 looks 'very challenging' is a scope limitation, not a circularity. The Section 4.3 concern that delta_t is used ambiguously as a net change and as a positive increment is a correctness/completeness issue in the written chain of inequalities, not a reduction of the result to its inputs. Therefore no circular step satisfies the standard of quoting an equation or definition that makes the claimed output equal to its input by construction.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper is a self-contained probabilistic proof. No data are fitted; the thresholds such as gamma_n and beta are proof parameters chosen for concentration, not tuned to empirical measurements. The load-bearing background consists of standard concentration inequalities, LP duality and complementary slackness, and Broder's uniform Markov chain theorem. No new entities are introduced.

assumptions (5)

standard math Standard concentration inequalities (Chernoff, Hoeffding, McDiarmid) hold for the binomial and hypergeometric counts used in Lemma 4.
Used throughout Section 3; the paper cites [5] and [8].
standard math The assignment LP has an optimal basis tree containing an optimal matching, with complementary slackness C(i,j)=u_i+v_j on tree edges and dual feasibility on non-tree edges.
Invoked in Section 4.2; from Ahuja-Magnanti-Orlin [1].
standard math Broder's Markov chain, started at a uniform perfect or near-perfect matching, remains uniform over the state space.
Used in Section 4.3 to model a random perfect matching of G+; cited to Broder [3].
domain assumption The cost distribution is acceptable: density f(x)=a+bx+O(x^2) at 0, with either an exponential tail or bounded support.
Defined in Section 1; needed for the cost conversion y+O(y^2) in Section 5 and for the memoryless-type patching bounds.
domain assumption The input digraph has minimum in- and out-degree at least alpha n with alpha=1/2+epsilon for a positive constant epsilon.
Core model; expansion estimates in Lemma 4 and the patching-pair lower bound (1) depend on alpha>1/2.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Karp's patching algorithm on dense digraph." pith.science (2026). https://pith.science/paper/LHZL3PFI

@misc{pith2026250521645,
  author       = {Pith},
  title        = {Pith review of: Karp's patching algorithm on dense digraph},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LHZL3PFI}},
  note         = {Machine review of arXiv:2505.21645}
}

abstract

We consider the following question. We are given a dense digraph $D$ with $n$ vertices and minimum in- and out-degree at least $\alpha n$, where $\alpha>1/2$ is a constant. The edges $E(D)$ of $D$ are given independent edge costs $C(e),e\in E(D)$, such that (i) $C$ has a density $f$ that satisfies $f(x)=a+bx+O(x^2)$, for constants $a>0,b$ as $x\to 0$ and such that in general either (ii) $\Pr(C\geq x)\leq \a e^{-\b x}$ for constants $\a,\b>0$, or $f(x)=0$ for $x>\n$ for some constant $\n>0$. Let $C(i,j),i,j\in[n]$ be the associated $n\times n$ cost matrix where $C(i,j)=\infty$ if $(i,j)\notin E$. We show that w.h.p. (a small modification to) the patching algorithm of Karp finds a tour for the asymmetric traveling salesperson problem that is asymptotically equal to that of the associated assignment problem. The algorithm runs in polynomial time.

Figures

Figures reproduced from arXiv: 2505.21645 by the authors.

**Figure 1.** Removing (y1, x2) So w.h.p. this case adds only O(n −1/10) to the cost of the constructed tour. This completes the proof of Theorem 1, modulo proving Lemmas 2 and 3. 3 Proof of Lemma 2 We show that w.h.p. for any pair of vertices a ∈ A, b ∈ B and any perfect matching between A and B that there is an M-alternating path from a to b that only uses non-M edges of cost at most log3 n n . Furthermore this path uses o(log … view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages

[1]

Ahuja, T

R. Ahuja, T. Magnanti and J. Orlin, Network Flows: Theory, Algorithms and Applications, Prentice Hall, 1991. 11

work page 1991
[2]

Bohman, A.M

T. Bohman, A.M. Frieze and R. Martin, How many random edges make a dense graph Hamiltonian?, Random Structures and Algorithms 22 (2003) 33-42

work page 2003
[3]

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

A. 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. Erratum in Proceedings of the 20th Annual ACM Symposium on Theory of Computing , 1988, p. 551

work page 1986
[4]

Dyer and A.M

M.E. Dyer and A.M. Frieze, On patching algorithms for random asymmetric travelling salesman problems, Mathematical Programming 46 (1990) 361-378

work page 1990
[5]

Frieze nd M

A.M. Frieze nd M. Karo´ nski, Introduction to random graphs, Cambridge University Press, 2015

work page 2015
[6]

Frieze and P

A.M. Frieze and P. Michaeli, Karp’s patching algorithm on random perturbations of dense digraphs

work page
[7]

Frieze and G

A.M. Frieze and G. Sorkin, The probabilistic relationship between the assignment and asymmetric traveling salesman problems, SIAM Journal on Computing 36 (2007) 1435-1452

work page 2007
[8]

Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58 (1963) 13-30

W. Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58 (1963) 13-30

work page 1963

Show all 11 references

[9]

Karp, A patching algorithm for the non-symmetric traveling salesman problem, SIAM Journal on Com- puting 8 (1979) 561–573

R.M. Karp, A patching algorithm for the non-symmetric traveling salesman problem, SIAM Journal on Com- puting 8 (1979) 561–573

1979
[10]

Karp and J.M

R.M. Karp and J.M. Steele, Probabilistic analysis of heuristics, in The traveling salesman problem: a guided tour of combinatorial optimization, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys Eds. (1985) 181–206

1985
[11]

McDiarmid, On the method of bounded differences, in Surveys in Combinatorics, ed

C. McDiarmid, On the method of bounded differences, in Surveys in Combinatorics, ed. J. Siemons, London Mathematical Society Lecture Notes Series 141, Cambridge University Press, 1989. 12

1989

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Ahuja, T

R. Ahuja, T. Magnanti and J. Orlin, Network Flows: Theory, Algorithms and Applications, Prentice Hall, 1991. 11

work page 1991

[2] [2]

Bohman, A.M

T. Bohman, A.M. Frieze and R. Martin, How many random edges make a dense graph Hamiltonian?, Random Structures and Algorithms 22 (2003) 33-42

work page 2003

[3] [3]

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

A. 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. Erratum in Proceedings of the 20th Annual ACM Symposium on Theory of Computing , 1988, p. 551

work page 1986

[4] [4]

Dyer and A.M

M.E. Dyer and A.M. Frieze, On patching algorithms for random asymmetric travelling salesman problems, Mathematical Programming 46 (1990) 361-378

work page 1990

[5] [5]

Frieze nd M

A.M. Frieze nd M. Karo´ nski, Introduction to random graphs, Cambridge University Press, 2015

work page 2015

[6] [6]

Frieze and P

A.M. Frieze and P. Michaeli, Karp’s patching algorithm on random perturbations of dense digraphs

work page

[7] [7]

Frieze and G

A.M. Frieze and G. Sorkin, The probabilistic relationship between the assignment and asymmetric traveling salesman problems, SIAM Journal on Computing 36 (2007) 1435-1452

work page 2007

[8] [8]

Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58 (1963) 13-30

W. Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58 (1963) 13-30

work page 1963