Karp’s patching algorithm on dense digraphs

Alan Frieze · 2025

Read Karp’s patching algorithm on dense digraphs by Alan Frieze (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-21645.txt.

Introduction

Alan Frieze analyzes a classic routing fix on dense directed graphs in a 2025 paper. The asymmetric traveling salesperson problem asks for the cheapest tour through one way streets. Karp's patching algorithm starts from the assignment relaxation and stitches its cycles into a tour. Frieze studies dense graphs, where every vertex keeps edges to over half the others, with random edge costs.

On such graphs the patched tour's cost lands, with high probability, asymptotically on the assignment bound: patching loses almost nothing. The algorithm runs in polynomial time. Dense instances model well connected road and data networks, where the result says a fast classic method is already near perfect.

Catalog record

CREATORAlan Frieze
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-21645

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Karp’s patching algorithm on dense digraphs Alan Frieze Abstract We consider the following question. We are given a dense digraph D D with n n vertices and minimum in- and out-degree at least α ​ n \alpha n , where α > 1 / 2 \alpha>1/2 is a constant. The edges E ⁡ ( D ) E(D) of D D are given independent edge costs C ⁡ ( e ) , e ∈ E ⁡ ( D ) C(e),e\in E(D) , such that (i) C C has a density f f that satisfies f ⁡ ( x ) = a + b ​ x + O ⁡ ( x 2 ) f(x)=a+bx+O(x^{2}) , for constants a > 0 , b a>0,b as x → 0 x\to 0 and such that in general either (ii) ℙ ⁡ ( C ≥ x ) ≤ α ​ e − β ​ x \mathbb{P}(C\geq x)\leq\alpha e^{-\beta x} for constants α , β > 0 \alpha,\beta>0 , or f ⁡ ( x ) = 0 f(x)=0 for x > ν x>\nu for some constant ν > 0 \nu>0 . Let C ⁡ ( i , j ) , i , j ∈ [ n ] C(i,j),i,j\in[n] be the associated n × n n\times n cost matrix where C ⁡ ( i , j ) = ∞ C(i,j)=\infty if ( i , j ) ∉ E (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. 1 Introduction Let {\mathcal{D}}(\alpha,n) be the set of digraphs with vertex set [n]=\left\{1,2,\ldots,n\right\} and with minimum in- and out-degree at least \alpha n . 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(x) where f(x)=a+bx+O(x^{2}) as x\to 0 and such that in general either (ii) \mathbb{P}(C\geq x)\leq\alpha e^{-\beta x} for constants \alpha,\beta>0 , or f(x)=0 for x>\nu for some constant \nu>0 . We say that such distributions are acceptable . The prime examples will be the uniform [0,1] distribution ( a=1,b=0 ) and the exponential mean 1 distribution EXP(1) ( a=1,b=-1,\alpha=\beta=1 ). 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(D) . Here we are interested in using the relationship between the Assignment Problem (AP) and the Asymmetric Traveling Salesperson Problem (ATSP) associated with the cost matrix C(i,j),i,j\in[n] to find a tour whose cost \widehat{v}(ATSP) satisfies v(AP)\leq v(ATSP)\leq\widehat{v}(ATSP)\leq(1+o(1))v(AP) w.h.p., where v(\bullet) denotes the optimal cost. We say that the output of the algorithm is asymptotically optimal i.e. it produces a tour whose cost is at most (1+o(1)) times optimal The problem AP is that of computing the minimum cost perfect matching in the complete bipartite graph K_{n,n} when edge (i,j) is given a cost C(i,j) . Equivalently, when translated to the complete digraph \vec{K}_{n} it becomes the problem of finding the minimum cost collection of vertex disjoint directed cycles that cover all vertices. The problem ATSP is that of finding a single cycle of minimum cost that covers all vertices. As such it is always the case that v(ATSP)\geq v(AP) . Karp [ 9 ] considered the case where D=\vec{K}_{n} . He showed that if the cost matrix comprised independent copies of the uniform [0,1] random variable U then w.h.p. v(ATSP)=(1+o(1))v(AP) . He proves this by the analysis of a patching algorithm. Karp’s result has been refined in [ 4 ] , [ 7 ] and [ 10 ] . Karp’s Patching Algorithm: First solve AP to obtain a minimum cost perfect matching M and let {\mathcal{A}}_{M}=\left\{C_{1},C_{2},\ldots,C_{\ell}\right\} be the associated collection of vertex disjoint cycles covering [n] . Then patch two of the cycles together, as explained in the next paragraph. Repeat until there is one cycle. A pair e=(x,y),f=(u,v) of edges in different cycles C_{1},C_{2} are said to be a patching pair if the edges e^{\prime}=(u,y),f^{\prime}=(x,v) both exist. In which case we can replace C_{1},C_{2} by a single cycle (C_{1}\cup C_{2}\cup\left\{e^{\prime},f^{\prime}\right\})\setminus\left\{e,f\right\} . The edges e,f are chosen to minimise the increase in cost of the set of cycles. Theorem 1 . Suppose that D\in{\mathcal{D}}(\alpha),n , \alpha=1/2+\varepsilon where \varepsilon is a positive constant. Suppose that each edge e of D is given an independent cost drawn from an acceptable distribution Then w.h.p. v(ATSP)=(1+o(1))v(AP) and (a small modification to ) Karp’s patching algorithm finds a tour of the claimed cost in polynomial time. In an earlier paper Frieze and Michaeli [ 6 ] proved a similar result where D=D_{0}+R and D_{0}\in{\mathcal{D}}(\alpha,n),\alpha>0 and R is a set of o(n^{2}) random edges. This being an example of the perturbed model introduced in Bohman, Frieze and Martin [ 2 ] . Our proof strategy follows that of [ 6 ] in some places and is significantly different in other places. For the moment assume that C is distributed as EXP(1) i.e \mathbb{P}(X\geq x)=e^{-x} . We will discuss more general distributions in Section 5 . Notation Let G denote the bipartite graph with vertex partition A=\left\{a_{1},a_{2},\ldots,a_{n}\right\},\,B=\left\{b_{1},b_{2},\ldots,b_{n}\right\} and an edge \left\{a_{i},b_{j}\right\} for every directed edge (i,j)\in E(D) . A matching M of G induces a collection {\mathcal{A}}_{M} of vertex disjoint paths and cycles in D and vice-versa. If the matching is perfect, then there are only cycles. 2 Proof of Theorem 1 Notation We begin by solving AP. We prove the following: Lemma 2 . W.h.p., the solution to AP contains only edges of cost C(i,j)\leq\gamma_{n}=\frac{\log^{4}n}{n} . Lemma 3 . W.h.p., after solving AP, the number \nu_{C} of cycles is at most \nu_{0}=n^{5/6} . Bounding the number of cycles has been the most difficult task. Karp proves O(\log n) w.h.p. for the complete digraph \vec{K}_{n} and we conjecture this to be true here. Karp’s proof relies on the key insight that if D=\vec{K}_{n} then the optimal assignment comes from a uniform random permutation. This is not true in general. Let L denote the set of edges of cost greater than \gamma_{n} . Given Lemmas 2 , 3 , for the purposes of proof, we temporarily replace costs C(e),e\in L by infinite costs in order to solve AP. Lemma 2 implies that w.h.p. we get the same optimal assignment as we would without the cost changes. Having solved AP, the memoryless property of the exponential distribution, implies that the unused edges in L really have a cost which is distributed as \gamma_{n}+EXP(1) . Let {\mathcal{C}}=C_{1},C_{2},\ldots,C_{\rho} be a cycle cover and let c_{i}=|C_{i}| where c_{1}\leq c_{2}\leq\cdots\leq c_{\rho} , \rho\leq\nu_{0} . Different edges in C_{i} give rise to disjoint patching pairs. We ignore the saving associated with deleting e,f and only look at the extra cost C(e^{\prime})+C(f^{\prime}) incurred. Case 1: \rho>\nu_{1}=3\varepsilon^{-1} . We see that if c_{\sigma}<\varepsilon n/2\leq c_{\sigma+1} then the number of possible patching pairs \phi({\mathcal{C}}) satisfies \phi({\mathcal{C}})\geq\sum_{i=1}^{\sigma}2\left(\varepsilon n-c_{i}\right)c_{i}\geq\varepsilon n\sum_{i=1}^{\sigma}c_{i}\geq\varepsilon n\sigma\geq\varepsilon n(\rho-2\varepsilon^{-1}). (1) Explanation: Having chosen e=(x,y) in a cycle C_{i} we let U denote the in-neighbors of y in D that are not in C_{i} . Then let U^{\prime} denote the predecessors of U in the cycles {\mathcal{C}} . Let V denote the out-neighbors of x . We have |U^{\prime}|,|V|\geq\alpha n-c_{i} and so |U^{\prime}\cap V|\geq 2(\varepsilon n-c_{i}) .

Read the complete text