Introduction
The asymmetric traveling salesman problem (ATSP) asks for a minimum-cost tour visiting every vertex of a directed graph with nonnegative arc costs. In asymmetric path TSP, the walk must start at a given vertex s s s and end at a given distinct vertex t t t . We allow repeated vertices and arcs; on a complete directed metric, shortcutting gives a Hamiltonian tour or an ( s , t ) (s,t) ( s , t ) -path.
The first constant-factor approximation for ATSP was obtained by Svensson, Tarnawski, and Végh [6 ] . Their laminar framework was subsequently improved by Traub and Vygen [8 , 9 ] and by Vygen [11 ] , who gives a tour factor below 14.7 and an ( s , t ) (s,t) ( s , t ) -path factor of 15. We improve both guarantees to a common factor. Let LP ( G , c ) \operatorname{LP}(G,c) LP ( G , c ) and LP s , t ( G , c ) \operatorname{LP}_{s,t}(G,c) LP s , t ( G , c ) denote the optima of the standard tour and path subtour relaxations, defined in § 3 , and set
R ∗ = 6 + 2 + 15 + 6 2 ≈ 12.2604. R_* = 6+\sqrt{2}+\sqrt{15+6\sqrt{2}}\approx12.2604. R ∗ = 6 + 2 + 15 + 6 2 ≈ 12.2604.
Theorem 1.1 (Approximation guarantees). For every fixed ε > 0 \varepsilon>0 ε > 0 , there are polynomial-time algorithms that, on nonnegative rational arc costs, return a spanning tour of cost at most ( R ∗ + ε ) LP ( G , c ) (R_*+\varepsilon)\operatorname{LP}(G,c) ( R ∗ + ε ) LP ( G , c ) and a spanning s s s -t t t walk of cost at most ( R ∗ + ε ) LP s , t ( G , c ) (R_*+\varepsilon)\operatorname{LP}_{s,t}(G,c) ( R ∗ + ε ) LP s , t ( G , c ) , respectively. The ATSP input is strongly connected; the path input has a feasible path relaxation. The integrality ratio of each relaxation is at most R ∗ R_* R ∗ .
Our tour improvement builds on Svensson’s algorithm [7 ] , as formulated for vertebrate pairs by Traub and Vygen [9 Algorithm 7.19] . Such a pair consists of a strongly laminar instance and a connected Eulerian backbone B B B meeting every nonsingleton laminar set. Following Traub and Vygen [9 Definition 7.7] , a ( κ , η ) (\kappa,\eta) ( κ , η ) -algorithm adds arcs H H H so that B ∪ H B \cup H B ∪ H is a spanning tour and
c ( H ) ≤ κ L P + η ∑ v ∉ V ( B ) 2 y v c(H) \le\kappa\ \mathrm{LP} + \eta\sum_{v \notin V(B)} 2y_v c ( H ) ≤ κ LP + η v ∈ / V ( B ) ∑ 2 y v
where y v y_v y v is the singleton dual weight at v v v . Thus κ \kappa κ charges the LP value, and η \eta η charges the singleton weight missed by the backbone. Our strengthened subtour cover gives a ( 2 , η ) (2,\eta) ( 2 , η ) -algorithm for every η > 3 + 2 2 \eta> 3 + 2\sqrt{2} η > 3 + 2 2 , improving Vygen’s η > 4 + 2 2 \eta> 4 + 2\sqrt{2} η > 4 + 2 2 guarantee [11 Theorem 3] . We further improve the recursive reduction to vertebrate pairs by retaining the paths chosen through contracted regions. The dual weight visited by these paths reduces the cost of completing those regions, yielding the tour bound in Theorem 1.1 .
Our second result strengthens the reduction from asymmetric path TSP to vertebrate pairs. It applies to any algorithm with the standard guarantee above, independently of our subtour-cover construction.
Theorem 1.2 (Transfer from vertebrate pairs). Let κ ≥ 1 \kappa\ge1 κ ≥ 1 and η ≥ 0 \eta\ge0 η ≥ 0 be fixed rational constants. A polynomial-time ( κ , η ) (\kappa,\eta) ( κ , η ) -algorithm for vertebrate pairs gives polynomial-time LP-relative approximation algorithms with factors
ATSP: 3 κ + η + 2 , asymmetric path TSP: max { 3 κ + η + 2 , 4 κ + 5 − 4 κ + 4 2 κ + η + 2 } . \begin{aligned}
\textit{ATSP:}\quad&3\kappa+ \eta+ 2,\\
\textit{asymmetric path TSP:}\quad&\max\left\{3\kappa+ \eta+ 2,\ 4\kappa+ 5 - \frac{4\kappa+ 4}{2\kappa+ \eta+ 2}\right\}.
\end{aligned} ATSP: asymmetric path TSP: 3 κ + η + 2 , max { 3 κ + η + 2 , 4 κ + 5 − 2 κ + η + 2 4 κ + 4 } .
The tour factor is the established reduction to vertebrate pairs [9 Theorem 7.12] ; our contribution is the smaller path factor. The proof also accommodates the refined recursive reduction of Traub and Vygen [9 Exercises 7.5–7.7] , giving a path guarantee that matches Vygen’s refined tour bound (Corollary 7.4). Finally, the same path construction uses our stronger recursive estimate to obtain the path bound in Theorem 1.1 . This last application uses the retained-path analysis in addition to the ( 2 , η ) (2,\eta) ( 2 , η ) -guarantee.
Relation to previous work. Table 1 summarizes the recent approximation guarantees. Earlier tour-to-path reductions relate the two problems in several ways. Feige and Singh [2 Theorem 2] give a general directed reduction with a multiplicative loss of 2 + ε 2+\varepsilon 2 + ε . At the level of the subtour LP, Köhne, Traub, and Vygen [4 ] prove that a tour integrality ratio of ρ \rho ρ implies a path integrality ratio of at most 4 ρ − 3 4\rho-3 4 ρ − 3 . For the symmetric problem, Traub, Vygen, and Zenklusen [10 ] preserve the approximation ratio up to an arbitrarily small additive error.
Table 1. Selected LP-relative approximation guarantees, for fixed ε > 0 \varepsilon> 0 ε > 0 . The first algorithm is randomized; the others are deterministic. The first path entry uses the reduction of Köhne, Traub, and Vygen, as stated in [6 Corollary 11.4] . A dash indicates that no path bound is listed.
More closely related to our work, Traub and Vygen [9 Theorem 9.23 and Corollary 9.24] already obtained a common 17 + ε 17+\varepsilon 17 + ε guarantee for asymmetric tours and paths. Their reduction uses the guarantee for augmenting a partial solution, rather than only a complete-tour approximation factor. Its application to Vygen’s algorithm gives a path factor of 15, so it does not carry his improved tour factor over to paths.
Thin-tree rounding provides another approach to ATSP [1 ] . OpenAI’s recent preprint [5 ] gives a deterministic polynomial-time construction of strong thin trees with an unspecified universal constant. This provides another route to constant-factor approximation. Our explicit bounds refine the recursive laminar framework.
Organization. Section 2 gives the technical overview; Section 3 fixes notation. Sections 4–6 prove the boundary-closure, subtour-cover, and recursive-augmentation results. Section 7 proves the transfer and approximation guarantees. Appendix A treats concentrated boundary ports.
Technical overview
The tour improvement comes from accounting for a route through a contracted region together with the cost of completing that region. We first recall why the existing algorithms use this recursive representation. We then explain how retaining the actual routes improves the recursive analysis, how the stronger subtour cover pays for the connections, and how the resulting augmentation guarantee transfers to ( s , t ) (s,t) ( s , t ) -paths.
The recursive framework
The subtour LP supplies a fractional solution and a lower bound against which to charge the algorithm. To make this lower bound useful locally, Svensson, Tarnawski, and Végh [6 ] reduce ATSP to instances whose arc costs are represented by weighted cuts. The sets defining these cuts form a laminar family : any two are nested or disjoint. The reduction preserves the LP-relative approximation factor [9 Theorem 7.4] . We refer to it as the laminar reduction . After this reduction, an arc costs the sum of the weights of the cuts it crosses. These cuts are tight for the supplied fractional solution, so each contributes twice its weight to the LP value. We call this contribution its dual mass . The nested sets can now serve as regions for a recursive algorithm, with an explicit share of the lower bound assigned to each region.
The recursion starts with a connected Eulerian multigraph, called a partial backbone , and extends it until it spans the graph. Within a region W W W , it contracts the inclusion-maximal proper positive-weight laminar sets missed by the partial backbone. The contracted graph is a simpler instance in which these missed regions are represented by vertices. A solution on this quotient is lifted by replacing every visit to a contracted vertex by a path between its original entry and exit. The contracted regions are then completed recursively. This architecture is inherited from Svensson, Tarnawski, and Végh [6 Section 9.2] and Traub and Vygen [9 Algorithm 7.8 and Lemma 7.13] .
The quotient is where Svensson’s algorithm is used: the image of the backbone meets every remaining nonsingleton laminar set, giving a vertebrate pair. On such an instance, the algorithm maintains a local Eulerian solution outside the backbone. Here local means that an arc crosses no nonsingleton laminar cut. If y v y_v y v denotes the weight of the singleton cut at v v v , a local arc u v uv uv has cost y u + y v y_u+y_v y u + y v . A simple local circuit C C C therefore costs ∑ v ∈ V ( C ) 2 y v \sum_{v\in V(C)} 2y_v ∑ v ∈ V ( C ) 2 y v ; for a general local Eulerian multiset, the same accounting counts each visit. This identity lets the algorithm allocate vertex budgets and charge circuits to the components they meet. A subtour cover supplies connections between the current components and to the backbone. Its components meeting the backbone may use nonlocal arcs. Vygen [11 Sections 2–4] improves the initialization and charging analysis within this framework.
Retaining passage costs and recursive progress
In a recursive call, a quotient vertex represents an entire laminar region. Its entry and exit determine which internal path must be restored when the solution is lifted. For each endpoint pair, the reduction fixes one of the nice paths of Traub and Vygen [9 Lemma 7.5] : it lies in the smallest laminar set containing its endpoints (allowing the whole graph) and crosses each laminar boundary at most once in each direction. The basic recursive reduction assigns a fixed charge to the quotient vertex large enough to pay for every such path. Our extension of Svensson’s algorithm retains the actual entry, exit, and path of each selected passage instead.
This information links the cost of lifting to progress within the region. The nice-path identity [9 Lemma 7.6] equates the path cost, together with its entry and exit contributions, to the dual mass of the laminar sets it visits. We call this visited mass its coverage . A passage of small coverage is cheap but leaves more mass for recursive completion; a passage of large coverage is more expensive but can reduce the completion cost. Our extension of the initialization and charging analysis bounds the total cost of the retained passages while keeping this coverage available to the recursive analysis.
Coverage must belong to a connected object from which recursion can continue. Quotient connectivity alone does not provide such an object: two circuits meeting at one contracted vertex may lift to disjoint closed walks. For each contracted region L L L , we select a retained passage of maximum coverage. When processing L L L , the whole current connected Eulerian component containing that passage is a possible backbone B L B_L B L ; it may extend outside L L L . Its coverage is certified before the recursive call. Augmenting B L B_L B L with arcs inside L L L to visit every vertex of L L L then joins all other lifted components meeting L L L . Figure 1 illustrates the loss of connectivity under lifting and its restoration by an internal augmentation.
Figure 1. Lifting can disconnect circuits; internal Eulerian augmentation restores connectivity.
The recursive algorithm compares completing this inherited component with starting from a fresh partial backbone, as in the refined reduction of Traub and Vygen [9 Exercises 7.5–7.6] . Retaining passage-dependent costs improves the accounting of this choice. The resulting augmentation bound decreases with the dual mass already visited by the inherited backbone (Theorem 6.4). Svensson’s algorithm and the recursive completion have distinct roles: the former joins components in the quotient, whereas the latter completes contracted regions in the original graph.
Paying for subtour-cover repairs
To apply the subtour-cover algorithm inside a recursive region, we first need a fractional comparison circulation there. Restricting the original flow to the region can destroy balance. We choose and price internal return paths to restore it, while retaining the attachment information needed when the quotient solution is lifted (§ 4 ). This construction also accounts for the fresh backbone choices used by the recursion.
The subtour cover used by Vygen rounds a modified fractional circulation and then repairs the entry–exit pairing chosen by rounding. Its cost bound pays for these repairs through an additional singleton-mass term [9 Theorem 8.24] . We include the repair prices in the rounding objective and obtain
c ( F ) ≤ 2 c T x , c(F) \le2c^{\mathsf{T}}x, c ( F ) ≤ 2 c T x ,
where F F F is the cover and x x x is the supplied fractional comparison circulation. The difficulty is that rounding may choose a different pairing from the fractional one. We price all possible repair pairings and pay for them with fractional paths and cycles removed before rounding. This preserves the locality, degree bounds, and backbone visits required by Svensson’s algorithm and by recursive lifting (Theorem 5.1 ). The stronger cover reduces the cost of connecting quotient components; passage-dependent accounting reduces the cost of completing their contracted regions. The tour analysis combines these two improvements.
From augmentation to ( s , t ) (s,t) ( s , t ) -paths
The augmentation guarantee keeps information that a complete-tour factor does not express: the cost of completion decreases with the mass already covered by the partial solution. Our transfer uses this information to compare two initial walks before augmentation.
The standard normalization of the path LP supplies two inexpensive ( s , t ) (s,t) ( s , t ) -paths in the support of its fractional solution [9 Lemmas 9.9, 9.10, and 9.16] . One initial walk preserves both path sections within every strongly connected component. The other visits a maximum-coverage path from the fixed nice-path family in each component and connects it to the entry and exit. The component maximum coverages bound the added connector costs in the first construction; in the second, they also certify mass that no longer needs completion. The first completion bound increases with their sum, whereas the second decreases with it. Keeping this shared quantity in both bounds and selecting the better construction avoids the loss incurred by bounding each one separately.
The algorithm completes only the selected walk, with one augmentation call per component. To apply Eulerian augmentation, it closes the walk by one auxiliary return from t t t to s s s . The component augmentations use only internal arcs, so removing this return from the resulting Euler tour gives a spanning ( s , t ) (s,t) ( s , t ) -walk. § 7.2 gives the two constructions and proves the strengthened reduction to vertebrate pairs, then applies the same analysis to our recursive augmentation.
Preliminaries
Parallel arcs and multiset unions are allowed, and all costs count multiplicity. We discard self-loops. We call an arc multiset Eulerian when indegree equals outdegree at every vertex; connectivity is stated separately. “Connected” refers to the underlying undirected graph. A balanced connected multigraph is strongly connected on its vertices and has an Euler tour. A single vertex with no arcs is an allowed connected Eulerian multigraph.
For a vertex set S S S , let δ + ( S ) \delta^{+}(S) δ + ( S ) and δ − ( S ) \delta^{-}(S) δ − ( S ) be its outgoing and incoming arcs, and put δ ( S ) = δ + ( S ) ∪ δ − ( S ) \delta(S)=\delta^{+}(S)\cup\delta^{-}(S) δ ( S ) = δ + ( S ) ∪ δ − ( S ) . Write div x ( v ) = x ( δ + ( v ) ) − x ( δ − ( v ) ) \operatorname{div}x(v)=x(\delta^{+}(v))-x(\delta^{-}(v)) div x ( v ) = x ( δ + ( v )) − x ( δ − ( v )) . The tour relaxation is
LP ( G , c ) = min { c T x : div x = 0 , x ( δ − ( S ) ) ≥ 1 ( ∅ ≠ S ⊊ V ) , x ≥ 0 } . (1) \operatorname{LP}(G,c)=\min\{c^{T}x:\operatorname{div}x=0,\ x(\delta^{-}(S))\ge1\ (\varnothing\ne S\subsetneq V),\ x\ge0\}. \tag*{(1)} LP ( G , c ) = min { c T x : div x = 0 , x ( δ − ( S )) ≥ 1 ( ∅ = S ⊊ V ) , x ≥ 0 } . (1)
For asymmetric path TSP with terminals s , t s,t s , t , replace balance by div x = 1 s − 1 t \operatorname{div}x=\mathbf{1}_{s}-\mathbf{1}_{t} div x = 1 s − 1 t and impose x ( δ + ( S ) ) ≥ 1 x(\delta^{+}(S))\ge1 x ( δ + ( S )) ≥ 1 for every nonempty S ⊆ V ∖ { t } S\subseteq V\setminus\{t\} S ⊆ V ∖ { t } . Denote its optimum by LP s , t ( G , c ) \operatorname{LP}_{s,t}(G,c) LP s , t ( G , c ) .
Strongly laminar instances and path coverage
A strongly laminar instance consists of a strongly connected digraph G G G , a laminar family L \mathcal{L} L of nonempty proper vertex sets, a circulation x > 0 x>0 x > 0 feasible for (1) , and weights y L > 0 y_L>0 y L > 0 . Every G [ L ] G[L] G [ L ] is strongly connected and x ( δ − ( L ) ) = 1 x(\delta^{-}(L))=1 x ( δ − ( L )) = 1 . The induced arc cost is c y ( e ) = ∑ L : e ∈ δ ( L ) y L c_y(e)=\sum_{L:e\in\delta(L)}y_L c y ( e ) = ∑ L : e ∈ δ ( L ) y L , so c y T x = ∑ L 2 y L = LP ( G , c y ) c_y^{T}x=\sum_L2y_L=\operatorname{LP}(G,c_y) c y T x = ∑ L 2 y L = LP ( G , c y ) .
For singleton weights, write y v = y { v } y_v=y_{\{v\}} y v = y { v } when { v } ∈ L \{v\}\in\mathcal{L} { v } ∈ L and y v = 0 y_v=0 y v = 0 otherwise. A vertebrate pair consists of a strongly laminar instance and a connected Eulerian backbone B B B meeting every nonsingleton laminar set. Following Traub and Vygen [9 Definition 7.7] and Vygen [11 ] , a ( κ , η ) (\kappa,\eta) ( κ , η ) -algorithm adds an Eulerian multiset H H H such that B ∪ H B\cup H B ∪ H is a spanning tour and
c ( H ) ≤ κ LP + η ∑ v ∉ V ( B ) 2 y v . (2) c(H)\le\kappa\operatorname{LP}+\eta\sum_{v\notin V(B)}2y_v. \tag*{(2)} c ( H ) ≤ κ LP + η v ∈ / V ( B ) ∑ 2 y v . (2)
Thus κ \kappa κ prices the LP value and η \eta η prices uncovered singleton mass. For W ∈ L ∪ { V } W\in\mathcal{L}\cup\{V\} W ∈ L ∪ { V } , a partial backbone is a connected Eulerian multigraph B B B with V ( B ) ∩ W ≠ ∅ V(B)\cap W\ne\varnothing V ( B ) ∩ W = ∅ , without the requirement to meet all nonsingleton sets or to be contained in $W. This is the more general input in [9 Lemma 7.13] . When a recursive construction chooses a new partial backbone, we call it fresh to distinguish it from the inherited one.
Proposition 3.1 (Laminar reduction and nice paths). The following operations are polynomial time [9 Theorem 7.4 and Lemmas 7.5–7.6] .
(i) A ratio-ρ \rho ρ algorithm for strongly laminar instances gives the same LP-relative ratio for arbitrary nonnegative-cost ATSP. The reduction restricts to an optimal primal support and supplies potentials with c y ( u w ) = c ( u w ) + π u − π v c_y(uw)=c(uw)+\pi_u-\pi_v c y ( u w ) = c ( u w ) + π u − π v . Eulerian outputs on this support have the same original and induced costs.
(ii) For W ∈ L ∪ { V } W\in\mathcal{L}\cup\{V\} W ∈ L ∪ { V } and u , v ∈ W u,v\in W u , v ∈ W , one can find a simple path P u v W P^W_{uv} P uv W lying in their smallest laminar container and entering and leaving every laminar set at most once.
Following the terminology of [9 Lemma 7.5] , call these paths nice . Fix these paths once and for all, allowing P u v W P^W_{uv} P uv W to consist only of u u u . Our augmentation theorem applies to any such fixed family. For the classical bounds in § 7.2 , we use the global choice of [9 Section 7.3] : the same path for each endpoint pair is used in every containing region, independently of the dual weights. In both settings the caller and all recursive calls retain the chosen paths. All subsequent arcs stay on the support, and we write c = c y c=c_y c = c y until the path normalization in § 7.2 . For a region W W W , its descendant mass and vertex endpoint weights are
M W = ∑ J ∈ L : J ⊊ W 2 y J , h W ( u ) = ∑ J ∈ L : J ⊆ W , u ∈ J y J . (3) M_W=\sum_{J\in\mathcal{L}:J\subsetneq W}2y_J,\qquad h_W(u)=\sum_{J\in\mathcal{L}:J\subseteq W,\ u\in J}y_J. \tag*{(3)} M W = J ∈ L : J ⊊ W ∑ 2 y J , h W ( u ) = J ∈ L : J ⊆ W , u ∈ J ∑ y J . (3)
For a vertex set S S S , define
cov W ( S ) = ∑ J ∈ L , J ⊊ W J ∩ S ≠ ∅ 2 y J . \operatorname{cov}_{W}(S)=\sum_{\substack{J\in\mathcal{L},\,J\subsetneq W\\J\cap S\ne\varnothing}}2y_J. cov W ( S ) = J ∈ L , J ⊊ W J ∩ S = ∅ ∑ 2 y J .
For a path or subgraph H H H , write cov W ( H ) = cov W ( V ( H ) ) \operatorname{cov}_{W}(H)=\operatorname{cov}_{W}(V(H)) cov W ( H ) = cov W ( V ( H )) . The maximum coverage of a fixed nice path is
d W = max u , v ∈ W cov W ( P u v W ) . d_W=\max_{u,v\in W}\operatorname{cov}_{W}(P_{uv}^{W}). d W = u , v ∈ W max cov W ( P uv W ) .
This maximum is over a polynomial-size path family. In the notation of Traub and Vygen [9 Section 7.3] , M W M_W M W is value ( W ) \operatorname{value}(W) value ( W ) , cov W ( P u v W ) \operatorname{cov}_{W}(P_{uv}^{W}) cov W ( P uv W ) is D W ( u , v ) D_W(u,v) D W ( u , v ) , and d W d_W d W is D W D_W D W . For a partial backbone B B B , cov W ( B ) \operatorname{cov}_{W}(B) cov W ( B ) is their D W ( B ) D_W(B) D W ( B ) from [9 Exercise 7.5] .
Augmentation inside a region. An augmentation of B B B inside W W W is an Eulerian arc multiset E W E_W E W supported on E [ W ] E[W] E [ W ] such that B ∪ E W B\cup E_W B ∪ E W is connected and visits every vertex of W W W . The union retains every inherited copy of B B B ; the added cost is c ( E W ) c(E_W) c ( E W ) , even when an added arc also occurs in B B B . The backbone may extend outside W W W , but every added arc lies inside it. All algorithmic statements use rational input data, and polynomial time includes the encoding length of the given backbone and the explicit size of the added multiset.
Lemma 3.2 (Nice-path coverage identity [9 Lemma 7.6] ). For every fixed path P u v W P_{uv}^{W} P uv W ,
h W ( u ) + c ( P u v W ) + h W ( v ) = cov W ( P u v W ) ≤ d W ≤ M W . h_W(u)+c(P_{uv}^{W})+h_W(v)=\operatorname{cov}_{W}(P_{uv}^{W})\le d_W\le M_W. h W ( u ) + c ( P uv W ) + h W ( v ) = cov W ( P uv W ) ≤ d W ≤ M W . Also d W = 0 d_W=0 d W = 0 if and only if $M_W=0. Any subgraph containing this path has coverage at least cov W ( P u v W ) \operatorname{cov}_{W}(P_{uv}^{W}) cov W ( P uv W ) .
Proof. A visited set containing neither endpoint is crossed twice; a set containing one endpoint contributes once through its boundary and once through an endpoint weight. If both endpoints are in the set, the minimal-container property keeps the path inside it, and the two endpoint terms contribute its mass. An unvisited set contributes zero. Summing proves the identity. If M W > 0 M_W>0 M W > 0 , a vertex u u u in a positive descendant has $\operatorname{cov}_{W}(P_{uu}^{W})=2h_W(u)>0.
Locality, witnesses, and the split graph
An arc is local if it crosses no nonsingleton laminar set [9 Definition 7.14] . Thus c ( u v ) = y u + y v c(uv)=y_u+y_v c ( uv ) = y u + y v for a local arc, and for any local Eulerian multiset H H H ,
c ( H ) = ∑ v deg H − ( v ) 2 y v . c(H)=\sum_v\deg_H^-(v)\,2y_v. c ( H ) = v ∑ deg H − ( v ) 2 y v .
For a simple local circuit, every visited vertex has indegree one. This is the vertex-cost identity used by Svensson’s initialization and slack analysis. A subtour cover for a local Eulerian H H H outside a backbone B B B is an Eulerian multiset F F F crossing every component of H H H , with every component of F F F avoiding B B B local [9 Definition 7.14] . It need not be connected, and its components meeting B B B need not be local.
The witness flow and split graph enforce locality of components avoiding B B B when rounding [6 Section 10.1] . We recall the form of Traub and Vygen [9 Definition 8.3 and Lemmas 8.4–8.5] . Order the nonsingleton sets in L ∪ { V } \mathcal{L}\cup\{\mathord{V}\} L ∪ { V } by nonincreasing cardinality, breaking ties consistently, as L 1 = V , L 2 , … , L k L_1=V,L_2,\ldots,L_k L 1 = V , L 2 , … , L k . Set r ( v ) = max { i : v ∈ L i } r(v)=\max\{i:v\in L_i\} r ( v ) = max { i : v ∈ L i } . An arc u w uw u w is forward, backward, or neutral according as r ( u ) < r ( v ) r(u) < r(v) r ( u ) < r ( v ) , r ( u ) > r ( v ) r(u) > r(v) r ( u ) > r ( v ) , or r ( u ) = r ( v ) r(u) = r(v) r ( u ) = r ( v ) . Neutral arcs are exactly the local arcs. For a designated vertex set B 0 B_0 B 0 , a witness is a vector f f f satisfying
0 ≤ f ≤ x , f e = x e on forward arcs , f e = 0 on backward arcs , div f ( v ) ≥ 0 ( v ∉ B 0 ) . (4) \begin{aligned}
0 &\le f \le x, \qquad f_e = x_e \text{ on forward arcs}, \qquad f_e = 0 \text{ on backward arcs},\\
\operatorname{div} f(v) &\ge0 \qquad(v \notin B_0). \tag*{(4)}
\end{aligned} 0 div f ( v ) ≤ f ≤ x , f e = x e on forward arcs , f e = 0 on backward arcs , ≥ 0 ( v ∈ / B 0 ) . (4)
The standard witness lemma is stated for a backbone meeting the nonsingleton sets [9 Lemma 8.7] . The following form records exactly the property used by its proof.
Lemma 3.3 (A hitting set suffices for a witness). If B 0 B_0 B 0 meets every L i L_i L i , a witness exists and can be found in polynomial time. The set B 0 B_0 B 0 need not induce a connected subgraph.
Proof. Let C i = { v : r ( v ) = i } C_i = \{v : r(v) = i\} C i = { v : r ( v ) = i } and S i = ⋃ j ≥ i L j S_i = \bigcup_{j \ge i} L_j S i = ⋃ j ≥ i L j ; then C i ⊆ L i ⊆ S i C_i \subseteq L_i \subseteq S_i C i ⊆ L i ⊆ S i . Only the neutral variables in each C i C_i C i remain to be chosen. A capacitated flow feasibility test reduces to
x ( V ∖ S i → U ) ≤ x ( U → S i ∖ U ) ( U ⊆ C i ∖ B 0 ) . x(V \setminus S_i \to U) \le x(U \to S_i \setminus U) \qquad(U \subseteq C_i \setminus B_0). x ( V ∖ S i → U ) ≤ x ( U → S i ∖ U ) ( U ⊆ C i ∖ B 0 ) .
Indeed, these are exactly the cut conditions for routing the prescribed incoming forward flow through neutral arcs or outgoing forward arcs, with unconstrained absorption at B 0 B_0 B 0 . For i = 1 i = 1 i = 1 the left side is zero. For i ≥ 2 i \ge2 i ≥ 2 , L i ∖ U L_i \setminus U L i ∖ U is nonempty because B 0 B_0 B 0 meets L i L_i L i . Subtracting x ( δ − ( L i ) ) = 1 x(\delta^-(L_i)) = 1 x ( δ − ( L i )) = 1 from x ( δ − ( L i ∖ U ) ) ≥ 1 x(\delta^-(L_i \setminus U)) \ge1 x ( δ − ( L i ∖ U )) ≥ 1 gives x ( U → L i ∖ U ) ≥ x ( V ∖ L i → U ) x(U \to L_i \setminus U) \ge x(V \setminus L_i \to U) x ( U → L i ∖ U ) ≥ x ( V ∖ L i → U ) . The displayed inequality follows by containment. Max-flow feasibility in each rank class supplies the witness.
Replace each vertex by lower and upper copies v 0 v^0 v 0 , v 1 v^1 v 1 . Forward arcs occur only in the lower layer, backward arcs only in the upper layer, and neutral arcs in both. Put f e f_e f e on the lower copy and x e − f e x_e - f_e x e − f e on the upper copy. A downward switch v 1 v 0 v^1v^0 v 1 v 0 carries [ div f ( v ) ] + [\operatorname{div} f(v)]_+ [ div f ( v ) ] + ; an upward switch v 0 v 1 v^0v^1 v 0 v 1 carries [ − div f ( v ) ] + [-\operatorname{div} f(v)]_+ [ − div f ( v ) ] + and is permitted only at v ∈ B 0 v \in B_0 v ∈ B 0 . This is a circulation. Conversely its projection supplies a circulation and a witness. Switches have cost zero. Every nonlocal split circuit uses both layers and hence an upward switch at B 0 B_0 B 0 . If the lower support is acyclic, every circuit avoiding B 0 B_0 B 0 consists of neutral upper arcs.
Algorithmic primitives
We use integral bounded minimum-cost circulation, including ordinary vertex gates, and exact rational linear programming from separation. Finite integral lower and upper arc bounds ensure an integral optimum; cost coefficients may be signed. Cut constraints below are separated by directed minimum cuts. Integral circulation follows from [9 Theorem 3.11 and Corollary 3.12] ; optimization from separation follows from [TV25, Theorem 2.10 and [3 ] . We use only the polynomial-time rational version.
The exchange arguments in § 5 use the following consequence of optimization from separation.
Lemma 3.4 (Relative-interior point). For a nonempty rational polytope with polynomially bounded rational data and a polynomial-time separation oracle, a rational relative-interior point can be computed in polynomial time. Every valid linear inequality tight there is an equality on the entire polytope.
Proof. Starting with a feasible point, find the affine hull by optimizing basis functionals orthogonal to the affine span of the points found so far. A nonconstant functional supplies another feasible point outside that span. After at most the dimension many extensions, the collected points span the affine hull. Their average lies in no proper face: a valid inequality tight at the average is tight at every collected point, hence on their affine span. Optimization from separation [3 ] and rational linear algebra give the claimed complexity.
Boundary closure for recursive augmentation
Consider a recursive call on a proper laminar region W W W with a partial backbone B B B . Contracting the maximal descendants missed by B B B exposes an instance on which to run Svensson’s algorithm, as in the recursive reduction of Traub and Vygen [9 Lemma 7.13] . There are two issues before its subtour-cover subroutine can be used. The restriction of the fractional circulation to W W W need not be balanced, and a return through an identified exterior vertex need not preserve attachment when expanded into its prescribed path. We handle the cost and attachment issues here; § 5 proves the required rounding theorem for the resulting auxiliary circulation.
Both transportation problems below are minimizations over fixed nice paths. The reverse problem chooses paths from exits back to entries and closes the restricted circulation. The forward problem gives endpoint prices for passages through a child and a second way to choose a partial backbone inside it. These uses are separate from the maximum transportation problem in § 5 , which will price uncertain repair pairings after rounding.
Boundary transportation and partial backbone choices
For proper W ∈ L W \in\mathcal{L} W ∈ L , let
p u i n = x ( δ − ( W ) ∩ δ − ( u ) ) , p v o u t = x ( δ + ( W ) ∩ δ + ( v ) ) . p^{\mathrm{in}}_u=x\bigl(\delta^{-}(W)\cap\delta^{-}(u)\bigr),\qquad p^{\mathrm{out}}_v=x\bigl(\delta^{+}(W)\cap\delta^{+}(v)\bigr). p u in = x ( δ − ( W ) ∩ δ − ( u ) ) , p v out = x ( δ + ( W ) ∩ δ + ( v ) ) .
Both marginals have mass one. Allowed entry and exit ports are endpoints of support arcs crossing W W W ; later zero marginals do not authorize new arcs. Let T ( p i n , p o u t ) = { Q ≥ 0 : Q 1 = p i n , Q T 1 = p o u t } T(p^{\mathrm{in}},p^{\mathrm{out}})=\{Q\ge0:Q\mathbf{1}=p^{\mathrm{in}},Q^{T}\mathbf{1}=p^{\mathrm{out}}\} T ( p in , p out ) = { Q ≥ 0 : Q 1 = p in , Q T 1 = p out } . Define
c ⃗ W = min Q ∈ T ( p i n , p o u t ) ∑ u , v Q u v c ( P u v W ) , c ← W = min Q ∈ T ( p o u t , p i n ) ∑ v , u Q v u c ( P v u W ) . (5) \vec{c}_W=\min_{Q\in T(p^{\mathrm{in}},p^{\mathrm{out}})}\sum_{u,v}Q_{uv}c(P^W_{uv}),\qquad
\overleftarrow{c}_W=\min_{Q\in T(p^{\mathrm{out}},p^{\mathrm{in}})}\sum_{v,u}Q_{vu}c(P^W_{vu}). \tag*{(5)} c W = Q ∈ T ( p in , p out ) min u , v ∑ Q uv c ( P uv W ) , c W = Q ∈ T ( p out , p in ) min v , u ∑ Q v u c ( P v u W ) . (5)
b W = ∑ u p u i n h W ( u ) + ∑ v p v o u t h W ( v ) , e W = c ← W − b W . (6) b_W=\sum_u p^{\mathrm{in}}_u h_W(u)+\sum_v p^{\mathrm{out}}_v h_W(v),\qquad e_W=\overleftarrow{c}_W-b_W. \tag*{(6)} b W = u ∑ p u in h W ( u ) + v ∑ p v out h W ( v ) , e W = c W − b W . (6)
At the root set e V = 0 e_V=0 e V = 0 . By Lemma 3.2 ,
c ⃗ W + b W ≤ d W , c ← W + b W ≤ d W . (7) \vec{c}_W+b_W\le d_W,\qquad\overleftarrow{c}_W+b_W\le d_W. \tag*{(7)} c W + b W ≤ d W , c W + b W ≤ d W . (7)
The internal fractional cost is M W − b W M_W-b_W M W − b W , so adding reverse paths of total cost c ← W \overleftarrow{c}_W c W closes it at cost M W + e W M_W+e_W M W + e W .
Lemma 4.1 (Bounded forward prices). The forward transportation problem has an optimal dual φ u i n , φ v o u t \varphi^{\mathrm{in}}_u,\varphi^{\mathrm{out}}_v φ u in , φ v out with
φ u i n + φ v o u t ≤ c ( P u v W ) , ∑ u p u i n φ u i n + ∑ v p v o u t φ v o u t = c ⃗ W , − d W / 2 ≤ φ u i n , φ v o u t ≤ d W / 2. \varphi^{\mathrm{in}}_u+\varphi^{\mathrm{out}}_v\le c(P^W_{uv}),\qquad
\sum_u p^{\mathrm{in}}_u\varphi^{\mathrm{in}}_u+\sum_v p^{\mathrm{out}}_v\varphi^{\mathrm{out}}_v=\vec{c}_W,\qquad
-d_W/2\le\varphi^{\mathrm{in}}_u,\varphi^{\mathrm{out}}_v\le d_W/2. φ u in + φ v out ≤ c ( P uv W ) , u ∑ p u in φ u in + v ∑ p v out φ v out = c W , − d W /2 ≤ φ u in , φ v out ≤ d W /2. The bounds hold at every allowed port, including zero-marginal ports.
Proof. Start with any optimal dual. Add a common constant to all entry prices and subtract it from all exit prices until their maxima are equal. Both marginals have mass one, so the objective is unchanged; each pair’s sum is unchanged as well. The constraint for a maximizing entry and exit shows that both maxima are at most d W / 2 d_W/2 d W /2 . Raise every coordinate below − d W / 2 -d_W/2 − d W /2 to that value. Each affected pair then has sum at most zero, so feasibility is preserved. The objective cannot decrease, and weak duality preserves optimality. □ \square □
Lemma 4.2 (Two partial backbones inside a region). Let r > 1 r > 1 r > 1 be a coverage price , so a backbone’s score is its cost minus r r r times its coverage. One can compute a connected Eulerian B W max ⊆ G [ W ] B_W^{\max} \subseteq G[W] B W m a x ⊆ G [ W ] with cost at most 2 d W 2d_W 2 d W , coverage at least d W d_W d W , and
c ( B W max ) − r cov W ( B W max ) ≤ ( 2 − r ) d W . c(B_W^{\max}) - r\operatorname{cov}_W(B_W^{\max}) \le(2-r)d_W. c ( B W m a x ) − r cov W ( B W m a x ) ≤ ( 2 − r ) d W . For proper W W W one can also compute B W t r B_W^{\mathrm{tr}} B W tr with
c ( B W t r ) − r cov W ( B W t r ) ≤ c W ← − ( r − 1 ) c W ← − r b W . c(B_W^{\mathrm{tr}}) - r\operatorname{cov}_W(B_W^{\mathrm{tr}}) \le c_W^{\leftarrow} - (r-1)c_W^{\leftarrow} - rb_W. c ( B W tr ) − r cov W ( B W tr ) ≤ c W ← − ( r − 1 ) c W ← − r b W . Proof. For the first choice concatenate P u v W P_{uv}^W P uv W attaining d W d_W d W with P v u W P_{vu}^W P v u W . For the second, take an optimal forward coupling. The partial backbone P u v W + P v u W P_{uv}^W + P_{vu}^W P uv W + P v u W has score at most
c ( P u v W ) − ( r − 1 ) c ( P v u W ) − r ( h W ( u ) + h W ( v ) ) . c(P_{uv}^W) - (r-1)c(P_{vu}^W) - r(h_W(u)+h_W(v)). c ( P uv W ) − ( r − 1 ) c ( P v u W ) − r ( h W ( u ) + h W ( v )) . using the reverse path’s coverage. The transpose coupling is feasible for c W ← c_W^{\leftarrow} c W ← , so the average score has the asserted upper bound. Select the best supported pair by its actual score.
Prescribed returns and attachment to the partial backbone
Let B B B be a partial backbone, that is, a connected Eulerian multigraph meeting W W W , and let C \mathcal{C} C be the inclusion-maximal positive proper descendants of W W W missed by B B B . This is the usual contraction step in the recursive reduction [9 Lemma 7.13] . The sets in C \mathcal{C} C are disjoint, and every missed proper descendant lies in one of them. Then
M W = cov W ( B ) + ∑ L ∈ C ( 2 y L + M L ) . (8) M_W = \operatorname{cov}_W(B) + \sum_{L\in\mathcal{C}}(2y_L+M_L). \tag*{(8)} M W = cov W ( B ) + L ∈ C ∑ ( 2 y L + M L ) . (8)
Contract each L ∈ C L \in\mathcal{C} L ∈ C , keeping the original entry and exit labels of every boundary arc. The quotient retains the induced laminar structure. The image of B B B meets every remaining nonsingleton descendant of W W W . However, its portions inside W W W need not be connected without the excursions outside W W W .
An ordinary contraction of the exterior records only the total boundary flow. We must also keep each exit–entry pairing and its prescribed return path. We therefore use a separate exterior vertex for each pair with positive coupling mass. This is what “private” means below. The split graph will force a real visit to B B B between consecutive exterior visits, so the prescribed returns remain attached after lifting.
Lemma 4.3 (Private exterior). For proper W W W with M W > 0 M_W > 0 M W > 0 , choose an optimal reverse coupling Q Q Q . For each Q v u > 0 Q_{vu} > 0 Q v u > 0 , introduce a private vertex r v u r_{vu} r v u and arcs v r v u , r v u u vr_{vu}, r_{vu}u v r v u , r v u u , both of value Q v u Q_{vu} Q v u and of combined cost c ( P v u W ) c(P_{vu}^W) c ( P v u W ) . Together with the original flow inside W W W , these arcs form a circulation x W x^W x W . The same notation denotes its child contraction. Let V p r i v a t e V_{\mathrm{private}} V private be the private vertices and put B 0 = ( V ( B ) ∩ W ) ∪ V p r i v a t e B_0 = (V(B) \cap W) \cup V_{\mathrm{private}} B 0 = ( V ( B ) ∩ W ) ∪ V private in the quotient. Then:
(i) For every real set S ⊆ W S \subseteq W S ⊆ W before contraction, x W ( δ − ( S ) ) = x ( δ − ( S ) ) x^W(\delta^-(S)) = x(\delta^-(S)) x W ( δ − ( S )) = x ( δ − ( S )) . This also holds for quotient sets and their preimages. Every child retains its unit boundary marginals.
(ii) Before child contraction the fractional cost is M W + ϵ W M_W+\epsilon_W M W + ϵ W . Every integral private visit can be replaced at exactly its assigned cost by the prescribed path P v u W P_{vu}^W P v u W .
(iii) The quotient has a witness for B 0 B_0 B 0 with each private incoming arc upper and private outgoing arc lower. Private upward switches are forbidden. Every split-walk segment between consecutive private visits therefore contains a real vertex of V ( B ) ∩ W V(B)\cap W V ( B ) ∩ W .
Proof. The coupling preserves every real vertex’s incoming and outgoing boundary amounts, proving balance and (i). Proper-descendant cut mass is M W M_W M W ; its contribution on arcs crossing W W W is b W b_W b W . The internal flow therefore costs M W − b W M_W-b_W M W − b W , and the private arcs add c W ← c^{\leftarrow}_W c W ← . A private vertex has one entering and one leaving arc, so their integral multiplicities agree, proving (ii).
For (iii), first contract V ∖ W V\setminus W V ∖ W to a single ordinary exterior vertex, and contract the children. Keep W W W as a positive structural laminar set and retain all descendants not strictly inside a child. This is an ordinary strongly laminar quotient, with subtour-feasible circulation. The projected partial backbone B B B meets every retained nonsingleton set, so Lemma 3.3 applies. There are at least two real quotient vertices: otherwise W W W would be a singleton or all of it a missed child, contrary to M W > 0 M_W>0 M W > 0 and B ∩ W ≠ ∅ B\cap W\ne\varnothing B ∩ W = ∅ . Thus the structural set W W W makes every exterior rank smaller than every real rank. Split the exterior boundary according to Q Q Q . Its outgoing arcs are forward and its incoming arcs backward; all witness constraints at real vertices are unchanged. At r v u r_{vu} r v u , the downward switch has value Q v u Q_{vu} Q v u and the upward switch has value zero. These arc directions force the same values in any later witness normalization. A segment leaving a private vertex starts lower and arrives at the next private vertex upper. It must use an upward switch at a real vertex of B B B . □
The private singletons may have fractional degree below one, so this auxiliary graph is not an ordinary strongly laminar instance. Later comparison prices can also give its private arcs signed costs. The cover theorem accommodates these features by requiring cut inequalities only for subsets of its real parts. For connectivity tests the vertices of B 0 B_0 B 0 may be formally identified; this adds no usable network arc. At the root there is no exterior: use the projected original circulation and B 0 = V ( B ) B_0=V(B) B 0 = V ( B ) .
A strengthened subtour cover
The subtour cover used by Svensson’s algorithm crosses every component of the current local Eulerian solution. It may use nonlocal arcs, but every component containing such an arc must meet the backbone. The guarantee used by Vygen [11 Theorem 4] , from Traub and Vygen [9 Theorem 8.24] , is
c ( F ) ≤ 2 LP + ∑ v ∉ V ( B ) 2 y v , deg F − ( v ) ≤ 2 ( y v > 0 , the component of v avoids B ) . c(F) \le2\operatorname{LP}+\sum_{v\notin V(B)}2y_v,\qquad\deg_F^-(v)\le2\quad(y_v>0,\ \text{the component of }v\text{ avoids }B). c ( F ) ≤ 2 LP + v ∈ / V ( B ) ∑ 2 y v , deg F − ( v ) ≤ 2 ( y v > 0 , the component of v avoids B ) .
The degree bound controls the local circuits charged to initialization components; the total-cost bound pays for the terminal cover that attaches them to the backbone.
We modify the same witness-flow construction. In the existing cover, selected fractional paths crossing a current component W i W_i W i are rerouted through an auxiliary vertex, so that an integral visit there forces a crossing of W i W_i W i . Restoring this vertex after rounding leaves a chosen entry and exit that must be joined by a path inside W i W_i W i . These cover auxiliaries are distinct from the private exterior vertices of § 4 . The restoration path is local and simple, so its cost is bounded by ∑ v ∈ W i 2 y v \sum_{v\in W_i}2y_v ∑ v ∈ W i 2 y v ; summing over disjoint parts produces the singleton surcharge [9 Section 8.5 and proof of Theorem 8.24] . We instead include a price for every possible restoration in the rounding objective and pay for it with removed fractional flow. Our target is c ( F ) ≤ 2 c x T c(F)\le2c_x^T c ( F ) ≤ 2 c x T for the supplied circulation and costs, before these internal modifications.
The recursive application also changes the required interface. The input is the comparison circulation from § 4 , and its cost need not be the optimum of a subtour LP. Contracted children are tight vertices: the degree bound of four limits how often they must be expanded, while the bound of two in components avoiding the designated set preserves Svensson’s local-circuit analysis. We retain the split-walk decomposition and all visits to that set, so restoring private return paths preserves attachment to the actual partial backbone. Finally, comparison prices may make private arcs negative. Locality and the degree bounds are inherited requirements: degree four appears in Svensson, Tarnawski, and Végh [6 Lemma 10.3] , and degree two away from the backbone in Traub and Vygen [9 Theorem 8.24] . We establish them together with the improved cost and retained-visit guarantees in this more general setting.
Let x x x be a nonnegative rational circulation in a ranked directed graph, and let B 0 B_0 B 0 be a designated vertex set. Let W 1 , … , W k W_1,\ldots,W_k W 1 , … , W k partition V ∖ B 0 V \setminus B_0 V ∖ B 0 , where each W i W_i W i induces a strongly connected graph and lies in one rank class. Thus its internal arcs are neutral. A specified set V t i g h t ⊆ V ∖ B 0 V_{\mathrm{tight}} \subseteq V \setminus B_0 V tight ⊆ V ∖ B 0 contains the vertices at which degrees must be bounded. As usual, degree means indegree, which equals outdegree in an Eulerian multigraph. Let V p r i v a t e ⊆ B 0 V_{\mathrm{private}} \subseteq B_0 V private ⊆ B 0 be the set of private exterior vertices; every other vertex is real.
Theorem 5.1 (Subtour cover). Suppose that
x ( δ − ( S ) ) ≥ 1 x(\delta^{-}(S)) \ge1 x ( δ − ( S )) ≥ 1 for every nonempty S ⊆ W i S \subseteq W_i S ⊆ W i and every i i i ;
x x x has a witness for B 0 B_0 B 0 in the sense of Lemma 3.3 ;
x ( δ − ( v ) ) = x ( δ + ( v ) ) = 1 x(\delta^{-}(v)) = x(\delta^{+}(v)) = 1 x ( δ − ( v )) = x ( δ + ( v )) = 1 for every v ∈ V t i g h t v \in V_{\mathrm{tight}} v ∈ V tight ; and
c c c is nonnegative on arcs with two real endpoints. Arcs incident to V p r i v a t e V_{\mathrm{private}} V private may have signed costs.
A polynomial-time algorithm returns an Eulerian multiset F F F such that
c ( F ) ≤ 2 c T x , F ∩ δ ( W i ) ≠ ∅ ( i = 1 , … , k ) . c(F) \le2c^{\mathsf T}x,\qquad F \cap\delta(W_i) \ne\varnothing\quad(i=1,\ldots,k). c ( F ) ≤ 2 c T x , F ∩ δ ( W i ) = ∅ ( i = 1 , … , k ) . Every component disjoint from B 0 B_0 B 0 is local. Each v ∈ V t i g h t v \in V_{\mathrm{tight}} v ∈ V tight has degree at most four, and at most two if its component is disjoint from B 0 B_0 B 0 . The algorithm retains a decomposition into closed split walks. Every repair replaces a segment inside one W i W_i W i and preserves all visits to B 0 B_0 B 0 on that walk.
The proof keeps the split graph, acyclic witness, and doubling step of Traub and Vygen [9 Chapter 8] . A split vertex carrying at least half a unit can force an integral visit directly. Otherwise an auxiliary vertex collects half a unit of crossing walks, and rounding forces one visit there. Restoring that visit requires an internal path whose endpoints are chosen by the rounding. The difficulty is therefore to price every possible entry–exit pairing, not just the original fractional pairing.
We first express this repair cost by a maximum transportation problem and identify the fractional cost that can pay for it. We then normalize the witness and select the crossing walks. When these walks can all pass through a common vertex, their prefixes and suffixes may be paired at no additional cost. The capped-flow argument supplies such a certificate while keeping the actual rounded flow within the required degree bounds.
Paying for restoration before rounding
Write f f f for a witness and g = x − f g = x - f g = x − f . In the split graph, f f f uses the lower layer and g g g the upper layer. At v ∉ B 0 v \notin B_0 v ∈ / B 0 , the downward switch has value div f ( v ) ≥ 0 \operatorname{div} f(v) \ge0 div f ( v ) ≥ 0 and there is no upward switch. The upper throughput is g ( δ − ( v ) ) g(\delta^{-}(v)) g ( δ − ( v )) ; the lower throughput is f ( δ + ( v ) ) f(\delta^{+}(v)) f ( δ + ( v )) , including any flow supplied by the downward switch. At a vertex of V t i g h t V_{\mathrm{tight}} V tight , both are at most one. We impose a throughput bound by splitting a node and adding an ordinary gate arc. For a modified split circulation z z z , each arc has upper bound ⌈ 2 z e ⌉ \lceil2z_e\rceil ⌈ 2 z e ⌉ , and each node gate with throughput t t t has bounds ⌈ 2 t ⌉ \lceil2t\rceil ⌈ 2 t ⌉ and ⌈ 2 t ⌉ \lceil2t\rceil ⌈ 2 t ⌉ . Thus 2 z 2z 2 z is feasible, all bounds are finite and integral, and minimum-cost circulation gives an integral solution of no greater cost. Finite upper bounds allow signed objective coefficients.
Consider half a unit of selected split walks crossing a repair region contained in one W i W_i W i . Erase cycles in their projections. When a repeated vertex occurs first in the upper layer and then in the lower layer, replace the erased segment by the downward switch at that vertex. This decreases original-arc flow, preserves the entry and exit layers, and does not increase either copy’s throughput. Let p i n p^{\mathrm{in}} p in and p o u t p^{\mathrm{out}} p out be the entry and exit marginals of the resulting paths, and let C p a t h C_{\mathrm{path}} C path be their total internal cost. Redirect their boundary arcs through an auxiliary vertex v a u x v_{\mathrm{aux}} v aux . We use only two forms: all selected walks enter in the upper layer, or all exit in the lower layer. In the first form, v a u x v_{\mathrm{aux}} v aux has no lower original incoming arc and its upper throughput is 1 / 2 1/2 1/2 ; in the second, it has no upper original outgoing arc and its lower throughput is 1 / 2 1/2 1/2 . Giving the designated gate bounds 1 , 1 1,1 1 , 1 therefore forces exactly one original incoming and outgoing arc at v a u x v_{\mathrm{aux}} v aux . There is no upward switch at v a u x v_{\mathrm{aux}} v aux .
For each allowed pair ( u , v ) (u,v) ( u , v ) , let d u v d_{uv} d uv be the cost of a shortest simple u u u –v v v path inside the repair region. That region will be strongly connected, and all its costs are nonnegative. Set
C r e p a i r = max { ∑ u , v Q u v d u v : Q ≥ 0 , Q 1 = p i n , Q T 1 = p o u t } = min { ∑ u p u i n ϕ u i n + ∑ v p v o u t ϕ v o u t : ϕ u i n + ϕ v o u t ≥ d u v for all u , v } . (9) \begin{aligned}
C_{\mathrm{repair}}=\max\left\{\sum_{u,v}Q_{uv}d_{uv}: Q\geq0,\ Q\mathbf{1}=p^{\mathrm{in}},\ Q^{\mathsf{T}}\mathbf{1}=p^{\mathrm{out}}\right\} \\
&=\min\left\{\sum_u p_u^{\mathrm{in}}\phi_u^{\mathrm{in}}+\sum_v p_v^{\mathrm{out}}\phi_v^{\mathrm{out}}:\phi_u^{\mathrm{in}}+\phi_v^{\mathrm{out}}\geq d_{uv}\ \text{for all }u,v\right\}. \tag*{(9)}
\end{aligned} C repair = max { u , v ∑ Q uv d uv : Q ≥ 0 , Q 1 = p in , Q T 1 = p out } = min { u ∑ p u in ϕ u in + v ∑ p v out ϕ v out : ϕ u in + ϕ v out ≥ d uv for all u , v } . (9)
Add ϕ u i n \phi_u^{\mathrm{in}} ϕ u in to the redirected incoming stub labelled u u u and ϕ v o u t \phi_v^{\mathrm{out}} ϕ v out to the outgoing stub labelled v v v . The fractional objective increases by C r e p a i r C_{\mathrm{repair}} C repair . Whatever pair the integral circulation chooses, its two prices pay for the corresponding repair. Individual prices may be negative; the circulation bounds remain finite. This maximum transportation problem differs from both minimum transportation problems in § 4 : those choose fractional boundary routes, whereas this one covers the worst pairing that rounding may choose.
Lemma 5.2 (Repair accounting). Suppose that the construction cancels internal fractional cycles of total cost C c a n c e l C_{\mathrm{cancel}} C cancel and removes path families of costs C p a t h , i C_{\mathrm{path},i} C path , i in disjoint parts, whose repair transportation values are C r e p a i r , i C_{\mathrm{repair},i} C repair , i . After integral rounding and repair,
c ( F ) ≤ 2 c T x − 2 C c a n c e l + 2 ∑ i ( C r e p a i r , i − C p a t h , i ) . c(F)\leq2c^{\mathsf{T}}x-2C_{\mathrm{cancel}}+2\sum_i(C_{\mathrm{repair},i}-C_{\mathrm{path},i}). c ( F ) ≤ 2 c T x − 2 C cancel + 2 i ∑ ( C repair , i − C path , i ) .
Proof. The modified fractional objective is c T x − C c a n c e l − ∑ i C p a t h , i + ∑ i C r e p a i r , i c^{\mathsf{T}}x-C_{\mathrm{cancel}}-\sum_i C_{\mathrm{path},i}+\sum_i C_{\mathrm{repair},i} c T x − C cancel − ∑ i C path , i + ∑ i C repair , i . Integral circulation rounding costs at most twice this value. Each repaired auxiliary visit costs at most its two already-paid endpoint prices by (9) .
Modifications in distinct parts can share a boundary arc. This causes no conflict. In either layer, if the arc has flow z z z and selected tail and head amounts s , t ≤ z s,t\leq z s , t ≤ z , choose
h ∈ [ max { 0 , s + t − z } , min { s , t } ] . h\in[\max\{0,s+t-z\},\min\{s,t\}]. h ∈ [ max { 0 , s + t − z } , min { s , t }] .
Split the arc into four labelled classes of weights h , s − h , t − h , z − s − t + h h,s-h,t-h,z-s-t+h h , s − h , t − h , z − s − t + h , selected at both ends, only the tail, only the head, or neither. Redirect the flagged ends. Restoration retains the original arc once and pays each endpoint price once. This permits all part modifications to be assembled before one rounding operation.
We next normalize the witness. The primary boundary minimization is the one used in the acyclic-witness construction of Traub and Vygen [9 Lemma 8.18] . We add a secondary cut optimization to obtain the exchange properties needed for simultaneous modifications. Lemma 3.4 lets us choose an optimum at which every tight constraint is tight throughout the optimal face.
Lemma 5.3 (Witness normalization). One can compute an acyclic witness f f f minimizing ∑ i f ( δ ( W i ) ) \sum_i f(\delta(W_i)) ∑ i f ( δ ( W i )) . With its boundary values fixed, it maximizes, independently in each part, the quantity
μ i = min ∅ ≠ S ⊆ W i ( x − f ) ( δ − ( S ) ) . \mu_i = \min_{\varnothing\ne S \subseteq W_i} (x-f)(\delta^-(S)). μ i = ∅ = S ⊆ W i min ( x − f ) ( δ − ( S )) . For every inclusion-minimal minimizing shore A i A_i A i , g [ A i ] g[A_i] g [ A i ] is strongly connected and no positive-f f f path inside W i W_i W i leaves A i A_i A i and returns to it. Simultaneously contracting one such shore per part preserves acyclicity of the support of f f f .
Proof. Minimize the boundary objective over the witness polytope and fix each resulting boundary value. In each part maximize μ \mu μ subject to ( x − f ) ( δ − ( S ) ) ≥ μ (x-f)(\delta^-(S)) \ge\mu ( x − f ) ( δ − ( S )) ≥ μ for all its nonempty subsets. Contracting its complement to a root and taking minimum root–vertex cuts separates these constraints. The parts change disjoint sets of neutral arcs. Choose relative-interior optima and combine them into f 0 f_0 f 0 .
Finally minimize ∑ e f e \sum_e f_e ∑ e f e subject to f ≤ f 0 f \le f_0 f ≤ f 0 , the primary optimum, and the optimal cut constraints. A positive witness cycle uses only neutral arcs. Deleting it preserves divergence and increases, rather than decreases, upper cut capacities. If it decreased the primary boundary objective it would contradict that objective’s optimality. Otherwise deletion remains feasible in the final program. Hence its optimum f f f is acyclic. Boundary values only decrease and their sum is fixed, so each remains fixed. A cut slack at f 0 f_0 f 0 remains slack; a cut tight at f 0 f_0 f 0 is an equality throughout the optimal face and remains tight.
Fix one part and an inclusion-minimal minimum shore A A A . If g [ A ] g[A] g [ A ] had several strongly connected components, a source component would have incoming capacity at most g ( δ − ( A ) ) = μ g(\delta^-(A))=\mu g ( δ − ( A )) = μ , contradicting minimality. Cut submodularity also implies that any minimum shore intersecting A A A contains A A A : otherwise their intersection would be a smaller nonempty minimum shore.
Suppose that a positive-f f f path inside the part leaves A A A and returns. Decrease f f f along this excursion and increase it along a positive-g g g path in A A A with the same endpoints. A sufficiently small change preserves box constraints, divergence and boundary values. The internal path crosses no tight minimum shore. Thus no tight upper cut decreases, while the incoming capacity of A A A strictly increases. Small changes preserve all slack constraints, contradicting the universal tightness of the cut of A A A .
For simultaneous contraction, a new cycle confined to one part would be such a forbidden excursion. Any other new cycle consists of old positive witness segments between selected shores. Its ranks are nondecreasing, so all segments are neutral. Decrease f f f along them and reconnect inside each selected shore by a positive-g g g path, from its outgoing port to its incoming port. This preserves divergence and box feasibility for a small common amount. Internal changes do not affect part boundaries, whereas some decreased segment crosses a boundary. The primary objective strictly decreases, a contradiction.
An inclusion-minimal minimum shore is found by repeatedly testing whether a minimum shore survives after deleting a vertex from the current shore. Each test is another rooted minimum-cut problem; at most ∣ V ∣ |V| ∣ V ∣ strict reductions suffice.
Half a unit of walks through a common vertex
The preceding accounting reduces the cost bound to finding crossing walks whose removed cost, together with canceled cycles, pays for every repair. We obtain this certificate from walks visiting a common vertex w w w : prefixes and suffixes at w w w can be paired in any way without changing their combined cost. We first record a standard consequence of maximum flow.
Lemma 5.4 (Walk packing). Let a a a be a nonnegative circulation with vertices r , w r,w r , w . If every r r r –w w w cut has capacity at least 1 / 2 1/2 1/2 , half a unit of closed r r r -walks visiting w w w can be packed within a a a .
Proof. Take an r r r –w w w flow of value 1 / 2 1/2 1/2 . Subtracting it from a a a leaves supply 1 / 2 1/2 1/2 at w w w and demand 1 / 2 1/2 1/2 at r r r , so the residual contains a w w w –r r r flow of that value. Pair their path decompositions at w w w .
Remove the root and retain the boundary labels. Artificial root arcs have cost zero; original boundary arcs remain paid in the rounding objective. Re-pairing prefixes and suffixes at w w w realizes any entry–exit coupling. If cycle erasure leaves paths of cost C p a t h C_{\mathrm{path}} C path and removes cycles of cost C e r a s e C_{\mathrm{erase}} C erase , nonnegative internal costs therefore give
C r e p a i r ≤ C p a t h + C e r a s e . (10) C_{\mathrm{repair}} \le C_{\mathrm{path}} + C_{\mathrm{erase}}. \tag*{(10)} C repair ≤ C path + C erase . (10)
Applying this packing directly may give too much flow through a tight vertex. The next lemma separates the flow that will be rounded from an internal circulation. The former obeys the degree caps; the latter supplies closed detours to w w w solely for the repair-cost certificate. Canceling that circulation pays for the detours, without putting them into the rounded flow.
Lemma 5.5 (Capped flow). Let g ≥ 0 g \ge0 g ≥ 0 have nonpositive divergence at internal vertices of W W W , and assume g ( δ − ( S ) ) ≥ 1 / 2 g(\delta^{-}(S)) \ge1/2 g ( δ − ( S )) ≥ 1/2 for every nonempty S ⊆ W S \subseteq W S ⊆ W . Suppose 0 ≤ g 0 ≤ g 0 \le g_0 \le g 0 ≤ g 0 ≤ g has the same boundary values and divergence as g g g , and g 0 ( δ − ( v ) ) ≤ 1 / 2 g_0(\delta^{-}(v)) \le1/2 g 0 ( δ − ( v )) ≤ 1/2 at a specified set of capped vertices. For any w ∈ W w \in W w ∈ W , one can compute g c a p , g c y c ≥ 0 g^{\mathrm{cap}},g^{\mathrm{cyc}} \ge0 g cap , g cyc ≥ 0 such that g c a p + g c y c = g g^{\mathrm{cap}} + g^{\mathrm{cyc}} = g g cap + g cyc = g , g c y c g^{\mathrm{cyc}} g cyc is an internal circulation, and g c a p g^{\mathrm{cap}} g cap respects the same caps, together with half a unit of boundary-originating g c a p g^{\mathrm{cap}} g cap -walks that all visit w w w after inserting detours of combined arc usage at most g c y c g^{\mathrm{cyc}} g cyc . Each detour returns to its insertion vertex.
Proof. Use a g c a p g^{\mathrm{cap}} g cap layer, a g c y c = g − g c a p g^{\mathrm{cyc}} = g - g^{\mathrm{cap}} g cyc = g − g cap layer, and a one-way switch from each g c a p g^{\mathrm{cap}} g cap copy to its g c y c g^{\mathrm{cyc}} g cyc copy, of capacity 1 + ∑ e g e 1 + \sum_e g_e 1 + ∑ e g e . A root supplies the g c a p g^{\mathrm{cap}} g cap layer through the actual boundary entries; the target is the g c y c g^{\mathrm{cyc}} g cyc copy of w w w . A minimum cut cannot use a switch. Its two sink shores therefore satisfy w ∈ S ⊆ T ⊆ W w \in S \subseteq T \subseteq W w ∈ S ⊆ T ⊆ W , where S S S is in the g c y c g^{\mathrm{cyc}} g cyc layer and T T T in the g c a p g^{\mathrm{cap}} g cap layer. The minimum-cut value is
μ = min w ∈ S ⊆ T ⊆ W { g c y c ( δ − ( S ) ) + g c a p ( δ − ( T ) ) } . \mu= \min_{w \in S \subseteq T \subseteq W} \left\{g^{\mathrm{cyc}}(\delta^{-}(S)) + g^{\mathrm{cap}}(\delta^{-}(T))\right\}. μ = w ∈ S ⊆ T ⊆ W min { g cyc ( δ − ( S )) + g cap ( δ − ( T )) } .
Optimize g c a p g^{\mathrm{cap}} g cap with its fixed boundary, divergence, box and throughput constraints to maximize μ \mu μ . Layered minimum cuts give a separation oracle. Choose a relative-interior optimum.
Suppose μ < 1 / 2 \mu< 1/2 μ < 1/2 . Minimum cuts are closed under intersection, so there is an inclusion-minimal minimum pair ( S , T ) (S,T) ( S , T ) contained in every minimum pair. First, g c y c [ S ] g^{\mathrm{cyc}}[S] g cyc [ S ] is strongly connected. Otherwise remove a source or sink strongly connected component K K K not containing w w w . For a source, circulation balance shows that the incoming cut changes by − g c y c ( K , W ∖ S ) -g^{\mathrm{cyc}}(K,W \setminus S) − g cyc ( K , W ∖ S ) ; for a sink it changes by − g c y c ( W ∖ S , K ) -g^{\mathrm{cyc}}(W \setminus S,K) − g cyc ( W ∖ S , K ) . Keeping T T T fixed would yield a smaller minimum pair.
Every throughput cap in S S S is slack. Indeed, if a capped v ∈ S v \in S v ∈ S has g c a p g^{\mathrm{cap}} g cap -indegree 1 / 2 1/2 1/2 , the boundary input g c a p ( δ − ( T ) ) ≤ μ < 1 / 2 g^{\mathrm{cap}}(\delta^{-}(T)) \le\mu< 1/2 g cap ( δ − ( T )) ≤ μ < 1/2 and the absence of internal sources imply that a decomposition of g c a p [ T ] g^{\mathrm{cap}}[T] g cap [ T ] into simple boundary-originating paths and cycles contains a positive cycle through v v v . Move a small amount of this cycle from g c a p g^{\mathrm{cap}} g cap to g c y c g^{\mathrm{cyc}} g cyc . Caps only decrease. For every tight pair ( S ′ , T ′ ) (S',T') ( S ′ , T ′ ) , we have T ⊆ T ′ T \subseteq T' T ⊆ T ′ , so its g c a p g^{\mathrm{cap}} g cap cut is unchanged and its g c y c g^{\mathrm{cyc}} g cyc cut cannot decrease. Small changes preserve slack constraints. The cap at v v v becomes slack at another optimum, contradicting relative interiority.
There is no positive-g c a p g^{\mathrm{cap}} g cap excursion from S S S back to S S S inside T T T . Otherwise decrease g c a p g^{\mathrm{cap}} g cap along that excursion and increase it along a positive-g c y c g^{\mathrm{cyc}} g cyc path in S S S with the same endpoints. Caps in S S S are slack; elsewhere they can only decrease. Each tight pair contains S S S in its inner shore and T T T in its outer shore, so no tight cut capacity decreases. The capacity of ( S , T ) (S,T) ( S , T ) strictly increases, again contradicting universal tightness. Consequently no g c a p g^{\mathrm{cap}} g cap cycle crosses S S S , and each boundary-originating path in g c a p [ T ] g^{\mathrm{cap}}[T] g cap [ T ] enters S S S at most once. Thus
μ = g c y c ( δ − ( S ) ) + g c a p ( δ − ( T ) ) ≥ g c y c ( δ − ( S ) ) + g c a p ( δ − ( S ) ) = g ( δ − ( S ) ) ≥ 1 2 . \mu= g^{\mathrm{cyc}}(\delta^{-}(S)) + g^{\mathrm{cap}}(\delta^{-}(T))
\ge g^{\mathrm{cyc}}(\delta^{-}(S)) + g^{\mathrm{cap}}(\delta^{-}(S))
= g(\delta^{-}(S)) \ge\frac{1}{2}. μ = g cyc ( δ − ( S )) + g cap ( δ − ( T )) ≥ g cyc ( δ − ( S )) + g cap ( δ − ( S )) = g ( δ − ( S )) ≥ 2 1 .
a contradiction.
Take a connector flow of value 1 / 2 1/2 1/2 in the layered network. Its g c a p g^{\mathrm{cap}} g cap pieces are prefixes from boundary entries to switch vertices; let s v s_v s v be the amount switching at v v v . Complete g c a p g^{\mathrm{cap}} g cap to a circulation by root exits for boundary exits and internal sinks. After removing the prefixes, the residual routes their supplies s v s_v s v to the root, completing them into boundary-to-boundary or boundary-to-sink base walks within g c a p g^{\mathrm{cap}} g cap . The connector’s g c y c g^{\mathrm{cyc}} g cyc pieces route s v s_v s v from the switch vertices to w w w . As g c y c g^{\mathrm{cyc}} g cyc is a circulation, the residual routes the same total amount from w w w back to those vertices. Pair at w w w by insertion-vertex label. Each detour returns to the vertex where it was inserted, and their combined usage is at most g c y c g^{\mathrm{cyc}} g cyc .
Constructing and rounding the cover
Normalize f f f by Lemma 5.3 . Process each part W W W using labelled boundary stubs. First cancel upper cycles internal to W W W on a probe copy of g g g . If a lower throughput f ( δ + ( v ) ) f(\delta^{+}(v)) f ( δ + ( v )) or a probe upper throughput is at least 1 / 2 1/2 1/2 , commit the probe deletions and force a visit to that split copy by its gate. Both internal layers are now acyclic and there is no upward switch in W W W . The forced visit must therefore cross W W W . No repair is needed.
Otherwise all lower and probe upper throughputs are below 1 / 2 1/2 1/2 . Define μ = min ∅ ≠ S ⊆ W g ( δ − ( S ) ) \mu= \min_{\varnothing\ne S \subseteq W} g(\delta^{-}(S)) μ = min ∅ = S ⊆ W g ( δ − ( S )) using the original, uncanceled g g g . There are two cases.
A small upper cut. Suppose μ < 1 / 2 \mu< 1/2 μ < 1/2 , and let A A A be an inclusion-minimal minimizing shore. On a copy of g [ A ] g[A] g [ A ] , delete internal cycles, obtaining an acyclic flow with the original boundary values and divergence. Keep the comparison circulation x x x unchanged: this deletion reassigns flow to its lower complement. Reoptimize the upper flow g ~ \widetilde{g} g inside A A A , with these boundary values and divergence fixed and 0 ≤ g ~ ≤ x 0 \le\widetilde{g} \le x 0 ≤ g ≤ x , to maximize
min ∅ ≠ D ⊆ A ( x − g ~ ) ( δ − ( D ) ) . \min_{\varnothing\ne D \subseteq A} (x-\widetilde{g})(\delta^{-}(D)). ∅ = D ⊆ A min ( x − g ) ( δ − ( D )) .
Choose a relative-interior optimum and make it acyclic by a decrease-only minimization as in Lemma 5.3 . Write f ~ = x − g ~ \widetilde{f}=x-\widetilde{g} f = x − g . Internal arcs of A A A are neutral, so this repartition remains a valid witness representation.
For a minimal minimum incoming shore D D D of f ~ \widetilde{f} f , the same exchange proof, with g ~ , f ~ \widetilde{g},\widetilde{f} g , f replacing f , g f,g f , g , shows that f ~ [ D ] \widetilde{f}[D] f [ D ] is strongly connected and no g ~ \widetilde{g} g path inside A A A leaves D D D and returns. The acyclic g ~ \widetilde{g} g flow has no internal sources and total boundary input μ \mu μ . Its paths enter D D D at most once, giving
g ~ ( δ − ( D ) ) ≤ μ , f ~ ( δ − ( D ) ) ≥ 1 − μ > 1 2 . \widetilde{g}(\delta^{-}(D)) \le\mu,\qquad
\widetilde{f}(\delta^{-}(D)) \ge1-\mu> \frac{1}{2}. g ( δ − ( D )) ≤ μ , f ( δ − ( D )) ≥ 1 − μ > 2 1 .
Every nonempty incoming cut of f ~ \widetilde{f} f in A A A has the same lower bound.
Complete f ~ [ A ] \widetilde{f}[A] f [ A ] to a circulation with a root. Root entries represent actual lower boundary entries and internal sources div f ~ ( v ) ≥ 0 \operatorname{div}\widetilde{f}(v) \ge0 div f ( v ) ≥ 0 ; exits represent lower boundary exits. Added source arcs only increase rooted cut capacities. Lemma 5.4 supplies half a unit of walks through any chosen vertex in A A A . Extend walks starting at downward sources backward through g ~ \widetilde{g} g to actual upper boundary entries of A A A . These extensions fit within g ˉ \bar{g} g ˉ , since their selected demands are bounded by the downward-switch amounts, which are exactly its internal sink amounts. Every extended walk exits A A A in the lower layer.
Erase projected cycles, redirect the surviving paths through a lower-exiting auxiliary, and then cancel all remaining lower cycles inside A A A . Equation (10) and Lemma 5.2 show that the part incurs no positive repair excess. The order matters: cycle cancellation occurs after rerouting, because the union of selected and unselected flow could otherwise contain additional cycles.
These changes preserve global lower acyclicity. Boundary values on A A A are unchanged, and simultaneous contraction of the selected shores preserves acyclicity by Lemma 5.3 . Any new cycle would therefore lie wholly inside one shore, where it has just been canceled. A cycle using its auxiliary would project to a cycle through the contracted shore. Every rounded visit to the lower-exiting auxiliary consequently lies on a split circuit meeting B 0 B_0 B 0 ; its repair remains attached to that visit and crosses W W W .
No small upper cut. Now g ( δ − ( S ) ) ≥ 1 / 2 g(\delta^{-}(S)) \ge1/2 g ( δ − ( S )) ≥ 1/2 for every nonempty S ⊆ W S \subseteq W S ⊆ W . The acyclic probe is a feasible g 0 g_0 g 0 for Lemma 5.5 , with every vertex in V t i g h t ∩ W V_{\mathrm{tight}} \cap W V tight ∩ W capped at 1 / 2 1/2 1/2 . Apply that lemma. Extend base walks ending at internal upper sinks through the acyclic lower flow to actual boundary exits of W W W . The extensions fit because their demands are bounded by the downward switches. All selected walks enter in the upper layer.
Let C p a t h C_{\mathrm{path}} C path be the cost of their base paths after cycle erasure, and C e r a s e C_{\mathrm{erase}} C erase the cost erased. Inserting the g c y c g^{\mathrm{cyc}} g cyc detours makes every walk visit the common vertex. Re-pairing there therefore proves
C r e p a i r ≤ C p a t h + C e r a s e + c ( g c y c ) . C_{\mathrm{repair}} \le C_{\mathrm{path}} + C_{\mathrm{erase}} + c(g^{\mathrm{cyc}}). C repair ≤ C path + C erase + c ( g cyc ) .
Cancel g c y c g^{\mathrm{cyc}} g cyc , erase the selected base cycles, redirect only the remaining base paths through an upper-entering auxiliary, and cancel remaining upper cycles inside W W W . The detours certify the prices; they are not rerouted. Lemma 5.2 again gives no positive repair excess. This auxiliary has no lower original incoming arc and cannot create a lower cycle. Its unique upper incoming arc comes from outside W W W , so its restored visit crosses W W W .
One rounding and the final guarantees. Assemble all modifications using the four-class split of boundary arcs. Apply bounded minimum-cost integral circulation once, decompose its result into split circuits with integer multiplicities, and restore each auxiliary’s unique visit by its priced simple path. The preceding cost inequalities sum to c ( F ) ≤ 2 c T x c(F) \le2c^{\mathsf T}x c ( F ) ≤ 2 c T x . Every part is crossed, and projection is Eulerian.
Before repair the lower support is acyclic. Thus a split circuit using it has an upward switch and meets B 0 B_0 B 0 . A circuit disjoint from B 0 B_0 B 0 stays in the upper layer, where ranks never increase; it uses only neutral arcs. Any repair using the lower layer was already on a circuit meeting B 0 B_0 B 0 . Upper-to-upper repairs remain upper. Hence every final component disjoint from B 0 B_0 B 0 is local.
In the case without an auxiliary, each designated split copy has throughout at most one and rounds to at most two visits, giving degree four in total and two in total and two in that disjoint from B 0 B_0 B 0 . In the small-cut case, lower throughputs outside A A A are below 1 / 2 1/2 1/2 , while upper throughputs are at most one. Inside A A A , the acyclic upper flow has total input μ < 1 / 2 \mu< 1/2 μ < 1/2 , while lower throughput is at most one. Thus the two rounded layers contribute at most three visits at a designated vertex, and the unique simple repair adds at most one. That repair belongs to a component meeting B 0 B_0 B 0 , so disjoint components retain the upper bound two. In the capped case, each layer contributes at most one and the repair adds at most one, giving total degree at most three; a component disjoint from B 0 B_0 B 0 has only the upper contribution and a possible upper repair, hence degree at most two. The restored incoming boundary arc is part of this one added visit.
A repaired segment stays in its part and either preserves its layer or changes once from upper to lower. In the latter case use a neutral upper path followed by a downward switch at its exit. No repair introduces an upward switch outside B 0 B_0 B 0 , and none deletes a vertex of B 0 B_0 B 0 . In particular, a real visit to B 0 B_0 B 0 between two private exterior visits remains present. This proves all assertions of Theorem 5.1.
All programs above have polynomially many variables and the stated minimum-cut separation oracles. Cycle cancellation, flow decomposition, shortest paths and integral circulation are polynomial-time procedures. Each part uses at most one auxiliary, and boundary arcs split into only four classes per layer. Weighted walks and integral multiplicities are stored in binary; the later normalization of the primal circulation also bounds the explicit output size.
Svensson’s algorithm and recursive augmentation
We now use the strengthened subtour cover within Svensson’s algorithm. The algorithm joins connected components in a fixed quotient graph. After its execution, we lift the chosen paths and recursively complete the contracted regions. These are separate operations: the first changes an Eulerian solution on one graph, while the second descends the laminar hierarchy. The contraction and recursive architecture follow the vertebrate-pair reduction of Traub and Vygen [9 Lemma 7.13] ; our extension uses the selected paths’ coverage in the quotient algorithm’s charges and in the choice of the subsequent recursive completion.
Svensson’s algorithm with prescribed passages
Recall why the local-circuit analysis works in Vygen [11 Sections 2–4] . A local arc u v uv uv has cost y u + y v y_u+y_v y u + y v , so a simple local circuit C C C has cost ∑ v ∈ V ( C ) 2 y v \sum_{v\in V(C)}2y_v ∑ v ∈ V ( C ) 2 y v . For a general local Eulerian multiset K K K , the corresponding identity counts visits: c ( K ) = ∑ v deg − K ( v ) 2 y v c(K)=\sum_v \deg^-K(v)\,2y_v c ( K ) = ∑ v deg − K ( v ) 2 y v . The vertex budgets pay for these costs. Slack measures the budget left after paying for an initialization component, and a circuit either gives a better initialization or can be charged to the components it meets. The subtour cover supplies such circuits with bounded numbers of visits. Its components meeting the backbone are paid only in the final iteration; they need not be local.
After contraction, a vertex can represent a whole region L L L . A visit to it must be expanded into a prescribed nice path P P P between the original entry and exit ports. By Lemma 3.2, its contribution to a lifted local circuit is 2 y L + cov L ( P ) 2y_L+\operatorname{cov}_L(P) 2 y L + cov L ( P ) , including the endpoint weights on the incident arcs. The recursive reduction in Traub and Vygen [9 Algorithm 7.8] uses the fixed weight 2 y L + d L 2y_L+d_L 2 y L + d L at a contracted vertex. This pays for every path in the fixed family, but discards the saving from a cheaper route. We retain each route and extend the initialization and circuit-charging arguments to its actual passage value. The fixed worst-case costs will be used only to search for additional circuits.
Here the passage cost depends on the incoming and outgoing arcs together, while the terminal cover uses a separate comparison objective. The following theorem extends the initialization and charging argument to this setting.
Fix a contracted instance and a nonempty designated set B 0 B_0 B 0 . As in the private-return construction, B 0 B_0 B 0 represents attachments to one actual partial backbone; it need not induce a connected subgraph. Identify it as one component only for connectivity tests. This identification adds no usable arc. Write U = V ∖ B 0 U=V\setminus B_0 U = V ∖ B 0 and n 0 = ∣ U ∣ n_0=|U| n 0 = ∣ U ∣ . For v ∈ U v\in U v ∈ U , let y v , d v ≥ 0 y_v,d_v\ge0 y v , d v ≥ 0 and w v = 2 y v + d v w_v=2y_v+d_v w v = 2 y v + d v . Each passage through v v v has a prescribed route P P P , with certified coverage cov v ( P ) ∈ [ 0 , d v ] \operatorname{cov}_v(P) \in[0,d_v] cov v ( P ) ∈ [ 0 , d v ] . In this abstract statement, these coverage values are supplied labels; the recursive application uses the dual mass met by the nice path. Routes and their entry and exit ports are fixed when a circuit is stored. Assume that the cost of its lift is at most the sum of 2 y v + cov v ( P ) 2y_v+\operatorname{cov}_v(P) 2 y v + cov v ( P ) over its passages. The recursive application will satisfy this bound with equality for a local quotient circuit. Give each local arc u v uv uv , with u , v ∈ U u,v\in U u , v ∈ U , the fixed search cost c r a w ( u v ) = ( w u + w v ) / 2 c_{\mathrm{raw}}(uv)=(w_u+w_v)/2 c raw ( uv ) = ( w u + w v ) /2 .
At each iteration, apply Theorem 5.1 with a fixed comparison objective c r o u n d c_{\mathrm{round}} c round . The subtour-cover procedure returns an Eulerian cover F ′ F' F ′ crossing every component of the current local solution, with c r o u n d ( F ′ ) ≤ 2 c r o u n d T x c_{\mathrm{round}}(F')\le2c_{\mathrm{round}}^{\mathsf T}x c round ( F ′ ) ≤ 2 c round T x . Its components disjoint from B 0 B_0 B 0 are local, and have indegree at most two at every vertex with w v > 0 w_v>0 w v > 0 ; the whole cover has indegree at most four there. We assume c r o u n d c_{\mathrm{round}} c round is nonnegative on local arcs. We need no relation between c r o u n d c_{\mathrm{round}} c round and c r a w c_{\mathrm{raw}} c raw .
The parameter δ \delta δ is a relative restart threshold: a restart must gain more than δ \delta δ times the budget outside the current initialization component. It is chosen in terms of the requested approximation slack ε \varepsilon ε and controls the restart count and the resulting approximation loss. The parameter γ \gamma γ controls the initialization budgets, and θ \theta θ sets the minimum coverage price of a retained passage. Fix rational constants γ > 1 \gamma>1 γ > 1 , 0 < δ < 1 0<\delta<1 0 < δ < 1 , and 0 < θ ≤ 1 0<\theta\le1 0 < θ ≤ 1 such that
( γ − 1 ) θ ≥ 1. (11) (\gamma-1)\theta\ge1. \tag*{(11)} ( γ − 1 ) θ ≥ 1. (11)
We use a floor θ d v \theta d_v θ d v so that the search costs remain comparable to the passage prices, even for routes of very small coverage. For a stored passage, define
b v ( P ) = 2 y v + max { θ d v , cov v ( P ) } . b_v(P)=2y_v+\max\{\theta d_v,\operatorname{cov}_v(P)\}. b v ( P ) = 2 y v + max { θ d v , cov v ( P )} .
For a routed Eulerian multiset K K K , let c p a s s ( K ) c_{\mathrm{pass}}(K) c pass ( K ) be the sum of these prices over all its stored passages, and let b v ( K ) b_v(K) b v ( K ) be their maximum at v v v . For an empty singleton at v v v , set c p a s s ( K ) = 0 c_{\mathrm{pass}}(K)=0 c pass ( K ) = 0 and b v ( K ) = 2 y v + θ d v b_v(K)=2y_v+\theta d_v b v ( K ) = 2 y v + θ d v . Unions retain all passages with multiplicity; therefore c p a s s c_{\mathrm{pass}} c pass is additive, whereas b v b_v b v is monotone under union. We have
c l i f t ( K ) ≤ c p a s s ( K ) , θ c r a w ( K ) ≤ c p a s s ( K ) ≤ c r a w ( K ) , θ w v ≤ b v ( P ) ≤ w v . (12) c_{\mathrm{lift}}(K)\le c_{\mathrm{pass}}(K),\qquad\theta c_{\mathrm{raw}}(K)\le c_{\mathrm{pass}}(K)\le c_{\mathrm{raw}}(K),\qquad\theta w_v\le b_v(P)\le w_v. \tag*{(12)} c lift ( K ) ≤ c pass ( K ) , θ c raw ( K ) ≤ c pass ( K ) ≤ c raw ( K ) , θ w v ≤ b v ( P ) ≤ w v . (12)
For a simple circuit C C C , in particular, c p a s s ( C ) = ∑ v ∈ V ( C ) b v ( C ) c_{\mathrm{pass}}(C)=\sum_{v\in V(C)}b_v(C) c pass ( C ) = ∑ v ∈ V ( C ) b v ( C ) . For a multiset, the sum pays for every visit whereas the maximum supplies one budget at each vertex; the two quantities are not equal in general. This distinction will allow the final bound to be certified by an actual component after lifting: the component containing a maximum-coverage passage already covers at least as much mass as any other passage at that child. We do not assume that the different lifted passages intersect.
Theorem 6.1 (Svensson’s algorithm with prescribed passages). Under these assumptions, one can compute a local Eulerian multiset H H H and a pruned subtour cover F o u t F_{\mathrm{out}} F out such that B 0 ∪ H ∪ F o u t B_0\cup H\cup F_{\mathrm{out}} B 0 ∪ H ∪ F out is connected in the contracted graph. The final cover satisfies the subtour-cover procedure’s cost and degree bounds. Its components meeting B 0 B_0 B 0 retain their original closed walks and backbone visits; its other components retain their simple local circuits. Let b v f i n b_v^{\mathrm{fin}} b v fin be the maximum price of a retained quotient passage through v v v in H H H or the prescribed lift of F o u t F_{\mathrm{out}} F out , using the singleton baseline if there is none. Then
c l i f t ( H ) ≤ α ∑ v ∈ U b v f i n , α : = γ 1 − δ + 2 γ γ − 1 + δ θ . (13) c_{\mathrm{lift}}(H)\le\alpha\sum_{v\in U}b_v^{\mathrm{fin}},\qquad\alpha:=\frac{\gamma}{1-\delta}+\frac{2\gamma}{\gamma-1}+\frac{\delta}{\theta}. \tag*{(13)} c lift ( H ) ≤ α v ∈ U ∑ b v fin , α := 1 − δ γ + γ − 1 2 γ + θ δ . (13) For fixed parameters, the algorithm runs in polynomial time. Passages inside separately paid exterior returns are not included in b v f i n b_v^{\mathrm{fin}} b v fin .
Initialization and the two restart tests. Assume first that U ≠ ∅ U \ne\varnothing U = ∅ and w ( U ) : = ∑ v ∈ U w v > 0 w(U) := \sum_{v\in U} w_v > 0 w ( U ) := ∑ v ∈ U w v > 0 . Give every vertex the same perturbation Δ = δ w ( U ) / n 0 \Delta= \delta w(U)/n_0 Δ = δ w ( U ) / n 0 . This supplies a positive minimum budget even at zero-weight vertices. For a stored Eulerian multigraph K K K , define
ℓ K ( S ) = ∑ v ∈ S ∩ V ( K ) ( γ 1 − δ b v ( K ) + Δ ) , ℓ ( K ) = ℓ K ( V ( K ) ) , σ ( K ) = ℓ ( K ) − c p a s s ( K ) . \ell_K(S) = \sum_{v\in S\cap V(K)} \left(\frac{\gamma}{1-\delta}b_v(K) + \Delta\right), \qquad\ell(K) = \ell_K(V(K)), \qquad\sigma(K) = \ell(K) - c_{\mathrm{pass}}(K). ℓ K ( S ) = v ∈ S ∩ V ( K ) ∑ ( 1 − δ γ b v ( K ) + Δ ) , ℓ ( K ) = ℓ K ( V ( K )) , σ ( K ) = ℓ ( K ) − c pass ( K ) .
Our δ \delta δ plays the role of Vygen’s restart tolerance ε \varepsilon ε , and our budget coefficient γ / ( 1 − δ ) \gamma/(1-\delta) γ / ( 1 − δ ) corresponds to his parameter γ \gamma γ [11 Section 2.3] .
As in Svensson’s algorithm, the initialization is a local Eulerian multiset H ~ \widetilde{H} H . Write its connected components as I i I_i I i , with vertex sets W i = V ( I i ) W_i = V(I_i) W i = V ( I i ) partitioning U U U ; empty singletons are allowed. The additional stored information is the prescribed passage at every visit. Unlike Vygen’s fixed vertex budgets, ℓ K \ell_K ℓ K can increase when K K K retains a passage of larger value. Monotonicity of these maxima is what the restart proof below needs. The components I i I_i I i have nonnegative slack and are ordered so that σ ( I 1 ) ≥ ⋯ ≥ σ ( I k ) \sigma(I_1) \ge\cdots\ge\sigma(I_k) σ ( I 1 ) ≥ ⋯ ≥ σ ( I k ) . Set W 0 = B 0 W_0 = B_0 W 0 = B 0 . The index of an object is the least index of an initialization set it meets. The initialization and its order remain fixed throughout a stage.
Vygen’s two tests examine a cover circuit itself and the improvement obtained by adjoining it to its minimum-index initialization component [11 Lemmas 6–7 and Section 3.2] . Here, for each surviving simple local cover circuit C C C of index i > 0 i > 0 i > 0 , test both K = C K = C K = C and K = I i ∪ C K = I_i \cup C K = I i ∪ C for
σ ( K ) > σ ( I i ) + δ ℓ K ( V ( K ) ∖ W i ) . (14) \sigma(K) > \sigma(I_i) + \delta\ell_K(V(K) \setminus W_i). \tag*{(14)} σ ( K ) > σ ( I i ) + δ ℓ K ( V ( K ) ∖ W i ) . (14)
If a test succeeds, let J t o u c h J_{\mathrm{touch}} J touch be the other initialization indices touched by K K K , put ℓ j = ℓ K ( W j ∩ V ( K ) ) \ell_j = \ell_K(W_j \cap V(K)) ℓ j = ℓ K ( W j ∩ V ( K )) , and retain the indices J k e e p = { j ∈ J t o u c h : σ ( I j ) ≥ ℓ j } J_{\mathrm{keep}} = \{j \in J_{\mathrm{touch}} : \sigma(I_j) \ge\ell_j\} J keep = { j ∈ J touch : σ ( I j ) ≥ ℓ j } . Replace all touched objects by K ∗ = K ∪ ⋃ j ∈ J k e e p I j K^* = K \cup\bigcup_{j\in J_{\mathrm{keep}}} I_j K ∗ = K ∪ ⋃ j ∈ J keep I j , and make newly uncovered vertices empty singletons. Untouched objects remain. For K = I i ∪ C K = I_i \cup C K = I i ∪ C , the existing copy of I i I_i I i is used once. The new object is connected because every retained I j I_j I j intersects K K K .
Lemma 6.2 (Progress from a restart). Starting with empty singletons, these restarts preserve nonnegative slacks and occur polynomially many times, provided each tested circuit crosses the current component containing its minimum-index object.
Proof. Write σ j = σ ( I j ) \sigma_j = \sigma(I_j) σ j = σ ( I j ) and ℓ o u t = ∑ j ∈ J t o u c h ℓ j \ell_{\mathrm{out}} = \sum_{j\in J_{\mathrm{touch}}} \ell_j ℓ out = ∑ j ∈ J touch ℓ j . Monotonicity of the passage maxima gives
ℓ ( K ∗ ) ≥ ℓ ( K ) + ∑ j ∈ J k e e p ( ℓ ( I j ) − ℓ j ) . \ell(K^*) \ge\ell(K) + \sum_{j\in J_{\mathrm{keep}}} \bigl(\ell(I_j) - \ell_j\bigr). ℓ ( K ∗ ) ≥ ℓ ( K ) + j ∈ J keep ∑ ( ℓ ( I j ) − ℓ j ) .
Subtracting the additive passage costs and using (6.4), we obtain
σ ( K ∗ ) > σ i + δ ℓ o u t + ∑ j ∈ J t o u c h max { σ j − ℓ j , 0 } ≥ σ i + δ 2 ( ℓ o u t + ∑ j ∈ J t o u c h σ j ) . (15) \sigma(K^*) > \sigma_i + \delta\ell_{\mathrm{out}} + \sum_{j\in J_{\mathrm{touch}}} \max\{\sigma_j - \ell_j,0\} \ge\sigma_i + \frac{\delta}{2}\left(\ell_{\mathrm{out}} + \sum_{j\in J_{\mathrm{touch}}} \sigma_j\right). \tag*{(15)} σ ( K ∗ ) > σ i + δ ℓ out + j ∈ J touch ∑ max { σ j − ℓ j , 0 } ≥ σ i + 2 δ ℓ out + j ∈ J touch ∑ σ j . (15)
The last inequality follows from ( δ / 2 ) t + max { s − t , 0 } ≥ ( δ / 2 ) s (\delta/2)t + \max\{s-t,0\} \ge(\delta/2)s ( δ /2 ) t + max { s − t , 0 } ≥ ( δ /2 ) s for s , t ≥ 0 s,t \ge0 s , t ≥ 0 . Define
σ min = min v ∈ U ( γ 1 − δ ( 2 y v + θ d v ) + Δ ) , p = [ 2 δ ] , Φ = ∑ j σ j p . \sigma_{\min} = \min_{v\in U}\left(\frac{\gamma}{1-\delta}(2y_v + \theta d_v) + \Delta\right), \qquad p = \left[\frac{2}{\delta}\right], \qquad\Phi= \sum_j \sigma_j^p. σ m i n = v ∈ U min ( 1 − δ γ ( 2 y v + θ d v ) + Δ ) , p = [ δ 2 ] , Φ = j ∑ σ j p .
Every singleton has slack at least σ min \sigma_{\min} σ m i n , and (6.5) preserves this lower bound. Because the circuit crosses the current component containing I i I_i I i , its outside budget satisfies ℓ o u t ≥ σ min \ell_{\mathrm{out}} \ge\sigma_{\min} ℓ out ≥ σ m i n . Also σ i ≥ σ j \sigma_i \ge\sigma_j σ i ≥ σ j for every touched j j j . Convexity, p δ / 2 ≥ 1 p\delta/2 \ge1 p δ /2 ≥ 1 , and σ i ≥ σ min \sigma_i \ge\sigma_{\min} σ i ≥ σ m i n therefore give
σ ( K ∗ ) p > σ i p + ∑ j ∈ J t o u c h σ j p + σ min p . (16) \sigma(K^*)^p > \sigma_i^p + \sum_{j\in J_{\mathrm{touch}}} \sigma_j^p + \sigma_{\min}^p. \tag*{(16)} σ ( K ∗ ) p > σ i p + j ∈ J touch ∑ σ j p + σ m i n p . (16)
@page 20/39 starts_mid=0 ends_mid=1 Initialization and the two restart tests. Assume first that U ≠ ∅ U \ne\varnothing U = ∅ and w ( U ) : = ∑ v ∈ U w v > 0 w(U) := \sum_{v\in U} w_v > 0 w ( U ) := ∑ v ∈ U w v > 0 . Give every vertex the same perturbation Δ = δ w ( U ) / n 0 \Delta= \delta w(U)/n_0 Δ = δ w ( U ) / n 0 . This supplies a positive minimum budget even at zero-weight vertices. For a stored Eulerian multigraph K K K , define
ℓ K ( S ) = ∑ v ∈ S ∩ V ( K ) ( γ 1 − δ b v ( K ) + Δ ) , ℓ ( K ) = ℓ K ( V ( K ) ) , σ ( K ) = ℓ ( K ) − c p a s s ( K ) . \ell_K(S) = \sum_{v\in S\cap V(K)} \left(\frac{\gamma}{1-\delta}b_v(K) + \Delta\right), \qquad\ell(K) = \ell_K(V(K)), \qquad\sigma(K) = \ell(K) - c_{\mathrm{pass}}(K). ℓ K ( S ) = v ∈ S ∩ V ( K ) ∑ ( 1 − δ γ b v ( K ) + Δ ) , ℓ ( K ) = ℓ K ( V ( K )) , σ ( K ) = ℓ ( K ) − c pass ( K ) .
Our δ \delta δ plays the role of Vygen’s restart tolerance ε \varepsilon ε , and our budget coefficient γ / ( 1 − δ ) \gamma/(1-\delta) γ / ( 1 − δ ) corresponds to his parameter γ \gamma γ [11 Section 2.3] .
As in Svensson’s algorithm, the initialization is a local Eulerian multiset H ~ \widetilde{H} H . Write its connected components as I i I_i I i , with vertex sets W i = V ( I i ) W_i = V(I_i) W i = V ( I i ) partitioning U U U ; empty singletons are allowed. The additional stored information is the prescribed passage at every visit. Unlike Vygen’s fixed vertex budgets, ℓ K \ell_K ℓ K can increase when K K K retains a passage of larger value. Monotonicity of these maxima is what the restart proof below needs. The components I i I_i I i have nonnegative slack and are ordered so that σ ( I 1 ) ≥ ⋯ ≥ σ ( I k ) \sigma(I_1) \ge\cdots\ge\sigma(I_k) σ ( I 1 ) ≥ ⋯ ≥ σ ( I k ) . Set W 0 = B 0 W_0 = B_0 W 0 = B 0 . The index of an object is the least index of an initialization set it meets. The initialization and its order remain fixed throughout a stage.
Vygen’s two tests examine a cover circuit itself and the improvement obtained by adjoining it to its minimum-index initialization component [11 Lemmas 6–7 and Section 3.2] . Here, for each surviving simple local cover circuit C C C of index i > 0 i > 0 i > 0 , test both K = C K = C K = C and K = I i ∪ C K = I_i \cup C K = I i ∪ C for
σ ( K ) > σ ( I i ) + δ ℓ K ( V ( K ) ∖ W i ) . (17) \sigma(K) > \sigma(I_i) + \delta\ell_K(V(K) \setminus W_i). \tag*{(17)} σ ( K ) > σ ( I i ) + δ ℓ K ( V ( K ) ∖ W i ) . (17)
If a test succeeds, let J t o u c h J_{\mathrm{touch}} J touch be the other initialization indices touched by K K K , put ℓ j = ℓ K ( W j ∩ V ( K ) ) \ell_j = \ell_K(W_j \cap V(K)) ℓ j = ℓ K ( W j ∩ V ( K )) , and retain the indices J k e e p = { j ∈ J t o u c h : σ ( I j ) ≥ ℓ j } J_{\mathrm{keep}} = \{j \in J_{\mathrm{touch}} : \sigma(I_j) \ge\ell_j\} J keep = { j ∈ J touch : σ ( I j ) ≥ ℓ j } . Replace all touched objects by K ∗ = K ∪ ⋃ j ∈ J k e e p I j K^* = K \cup\bigcup_{j\in J_{\mathrm{keep}}} I_j K ∗ = K ∪ ⋃ j ∈ J keep I j , and make newly uncovered vertices empty singletons. Untouched objects remain. For K = I i ∪ C K = I_i \cup C K = I i ∪ C , the existing copy of I i I_i I i is used once. The new object is connected because every retained I j I_j I j intersects K K K .
Lemma 6.2 (Progress from a restart). Starting with empty singletons, these restarts preserve nonnegative slacks and occur polynomially many times, provided each tested circuit crosses the current component containing its minimum-index object.
Proof. Write σ j = σ ( I j ) \sigma_j = \sigma(I_j) σ j = σ ( I j ) and ℓ o u t = ∑ j ∈ J t o u c h ℓ j \ell_{\mathrm{out}} = \sum_{j\in J_{\mathrm{touch}}} \ell_j ℓ out = ∑ j ∈ J touch ℓ j . Monotonicity of the passage maxima gives
ℓ ( K ∗ ) ≥ ℓ ( K ) + ∑ j ∈ J k e e p ( ℓ ( I j ) − ℓ j ) . \ell(K^*) \ge\ell(K) + \sum_{j\in J_{\mathrm{keep}}} \bigl(\ell(I_j) - \ell_j\bigr). ℓ ( K ∗ ) ≥ ℓ ( K ) + j ∈ J keep ∑ ( ℓ ( I j ) − ℓ j ) .
Subtracting the additive passage costs and using (6.4), we obtain
σ ( K ∗ ) > σ i + δ ℓ o u t + ∑ j ∈ J t o u c h max { σ j − ℓ j , 0 } ≥ σ i + δ 2 ( ℓ o u t + ∑ j ∈ J t o u c h σ j ) . (18) \sigma(K^*) > \sigma_i + \delta\ell_{\mathrm{out}} + \sum_{j\in J_{\mathrm{touch}}} \max\{\sigma_j - \ell_j,0\} \ge\sigma_i + \frac{\delta}{2}\left(\ell_{\mathrm{out}} + \sum_{j\in J_{\mathrm{touch}}} \sigma_j\right). \tag*{(18)} σ ( K ∗ ) > σ i + δ ℓ out + j ∈ J touch ∑ max { σ j − ℓ j , 0 } ≥ σ i + 2 δ ℓ out + j ∈ J touch ∑ σ j . (18)
The last inequality follows from ( δ / 2 ) t + max { s − t , 0 } ≥ ( δ / 2 ) s (\delta/2)t + \max\{s-t,0\} \ge(\delta/2)s ( δ /2 ) t + max { s − t , 0 } ≥ ( δ /2 ) s for s , t ≥ 0 s,t \ge0 s , t ≥ 0 . Define
σ min = min v ∈ U ( γ 1 − δ ( 2 y v + θ d v ) + Δ ) , p = [ 2 δ ] , Φ = ∑ j σ j p . \sigma_{\min} = \min_{v\in U}\left(\frac{\gamma}{1-\delta}(2y_v + \theta d_v) + \Delta\right), \qquad p = \left[\frac{2}{\delta}\right], \qquad\Phi= \sum_j \sigma_j^p. σ m i n = v ∈ U min ( 1 − δ γ ( 2 y v + θ d v ) + Δ ) , p = [ δ 2 ] , Φ = j ∑ σ j p .
Every singleton has slack at least σ min \sigma_{\min} σ m i n , and (6.5) preserves this lower bound. Because the circuit crosses the current component containing I i I_i I i , its outside budget satisfies ℓ o u t ≥ σ min \ell_{\mathrm{out}} \ge\sigma_{\min} ℓ out ≥ σ m i n . Also σ i ≥ σ j \sigma_i \ge\sigma_j σ i ≥ σ j for every touched j j j . Convexity, p δ / 2 ≥ 1 p\delta/2 \ge1 p δ /2 ≥ 1 , and σ i ≥ σ min \sigma_i \ge\sigma_{\min} σ i ≥ σ m i n therefore give
σ ( K ∗ ) p > σ i p + ∑ j ∈ J t o u c h σ j p + σ min p . (19) \sigma(K^*)^p > \sigma_i^p + \sum_{j\in J_{\mathrm{touch}}} \sigma_j^p + \sigma_{\min}^p. \tag*{(19)} σ ( K ∗ ) p > σ i p + j ∈ J touch ∑ σ j p + σ m i n p . (19)
The linear term in the convexity inequality contributes at least ∑ j ∈ J t o u c h σ j p \sum_{j\in J_{\mathrm{touch}}}\sigma_j^p ∑ j ∈ J touch σ j p from the sum in (6.5), and at least σ min p \sigma_{\min}^p σ m i n p from ℓ o u t \ell_{\mathrm{out}} ℓ out . New singleton terms are nonnegative, so each restart increases Φ \Phi Φ by more than σ min p \sigma_{\min}^p σ m i n p . Since the initialization vertex sets are disjoint and b v ( I j ) ≤ w v b_v(I_j) \le w_v b v ( I j ) ≤ w v ,
Φ ≤ ( ∑ j σ j ) p ≤ ( γ w ( U ) 1 − δ + δ w ( U ) ) p , σ min ≥ δ w ( U ) n 0 . \Phi\le\left(\sum_j \sigma_j\right)^p \le\left(\frac{\gamma w(U)}{1-\delta}+\delta w(U)\right)^p,\qquad\sigma_{\min}\ge\frac{\delta w(U)}{n_0}. Φ ≤ ( j ∑ σ j ) p ≤ ( 1 − δ γ w ( U ) + δ w ( U ) ) p , σ m i n ≥ n 0 δ w ( U ) .
The number of restarts is consequently bounded by [ n 0 ( γ / ( 1 − δ ) + δ ) / δ ] p \left[n_0(\gamma/(1-\delta)+\delta)/\delta\right]^p [ n 0 ( γ / ( 1 − δ ) + δ ) / δ ] p . Each restart retains a subset of the old circuits and adds one simple circuit, so representations and rational arithmetic remain polynomial.
One stage of the algorithm. Initialize H = H ~ = ⋃ i I i H=\widetilde{H}=\bigcup_i I_i H = H = ⋃ i I i . We retain the three operations of Svensson’s algorithm: compute a subtour cover, test for a better initialization, and add selected local circuits. The procedure below either restarts or connects the quotient. No recursive call is made during this execution.
Obtain a subtour cover F ′ F' F ′ . Keep every component meeting B 0 B_0 B 0 intact, with its retained split walks. Decompose the remaining components into simple local circuits, reduce every positive circuit multiplicity to one, and assign their nice routes. Delete every such circuit contained in one component of B 0 ∪ H B_0\cup H B 0 ∪ H ; call the result F F F . Apply both restart tests to every remaining local circuit. If one succeeds, restart with the new initialization and discard the other objects from this stage.
Otherwise set X = ∅ X=\emptyset X = ∅ and select a component Z Z Z of B 0 ∪ H ∪ F ∪ X B_0\cup H\cup F\cup X B 0 ∪ H ∪ F ∪ X of largest index. If its index is zero, return H ∪ X H\cup X H ∪ X and F o u t = F F_{\mathrm{out}}=F F out = F .
For i = ind ( Z ) > 0 i=\operatorname{ind}(Z)>0 i = ind ( Z ) > 0 , search for a simple local circuit in G [ U ] G[U] G [ U ] crossing Z Z Z with search cost at most σ i ( γ − 1 ) θ \frac{\sigma_i}{(\gamma-1)\theta} ( γ − 1 ) θ σ i . If one exists, store it in X X X with its prescribed routes, and repeat the component selection in Step 2 without resetting X X X . If none exists, add to H H H all pieces of F ∪ X F\cup X F ∪ X contained in Z Z Z , discard the other temporary pieces, and return to Step 1.
All subtour-cover crossing arcs survive pruning. Thus every tested circuit crosses a current component, as required by Lemma 6.2. Distinct components have distinct minimum initialization indices because each I i I_i I i is connected and retained in H H H . A circuit crossing the selected largest-index component joins it to a smaller-index component. At most n 0 n_0 n 0 such insertions occur in a cover call. If the search fails, Z Z Z contains at least two components of B 0 ∪ H B_0\cup H B 0 ∪ H : otherwise the cover would not cross that component. Retaining its pieces strictly reduces the number of current components. There are therefore at most n 0 n_0 n 0 updates to H H H in a stage. The circuit search is polynomial: enumerate local arcs of G [ U ] G[U] G [ U ] leaving Z Z Z and find a shortest return path using only local arcs of G [ U ] G[U] G [ U ] , with objective c_raw. Nonnegative costs allow a simple shortest return path.
Every component retained before the terminal call avoids B 0 B_0 B 0 and contains only local circuits. Components of the cover meeting B 0 B_0 B 0 are retained only in F o u t F_{\mathrm{out}} F out . The returned union is connected, and pruning preserves the comparison-cost and degree guarantees because it removes only local circuits of nonnegative c r o u n d c_{\mathrm{round}} c round -cost.
Charging in the final stage. Consider the final stage, which has no restart. For a surviving local cover circuit C C C of index i i i , failure of the first restart test gives ℓ ( C ) − δ ℓ ( C ∖ W i ) − c p a s s ( C ) ≤ σ i \ell(C)-\delta\ell(C\setminus W_i)-c_{\mathrm{pass}}(C)\le\sigma_i ℓ ( C ) − δ ℓ ( C ∖ W i ) − c pass ( C ) ≤ σ i . The budget expression before subtracting c p a s s ( C ) c_{\mathrm{pass}}(C) c pass ( C ) is at least ( 1 − δ ) ℓ ( C ) ≥ γ c p a s s ( C ) (1-\delta)\ell(C)\ge\gamma c_{\mathrm{pass}}(C) ( 1 − δ ) ℓ ( C ) ≥ γ c pass ( C ) . Consequently,
( γ − 1 ) c p a s s ( C ) ≤ σ i , c r a w ( C ) ≤ σ i ( γ − 1 ) θ . (20) (\gamma-1)c_{\mathrm{pass}}(C)\le\sigma_i,\qquad c_{\mathrm{raw}}(C)\le\frac{\sigma_i}{(\gamma-1)\theta}. \tag*{(20)} ( γ − 1 ) c pass ( C ) ≤ σ i , c raw ( C ) ≤ ( γ − 1 ) θ σ i . (20)
For the second test, the budget of I i ∪ C I_i \cup C I i ∪ C on W i W_i W i is at least ℓ ( I i ) \ell(I_i) ℓ ( I i ) , and its outside budget equals that of C C C . Failure therefore implies
( γ − 1 ) ∑ v ∈ V ( C ) ∖ W i b v ( C ) ≤ ∑ v ∈ V ( C ) ∩ W i b v ( C ) , (\gamma- 1)\sum_{v\in V(C)\setminus W_i} b_v(C) \le\sum_{v\in V(C)\cap W_i} b_v(C), ( γ − 1 ) v ∈ V ( C ) ∖ W i ∑ b v ( C ) ≤ v ∈ V ( C ) ∩ W i ∑ b v ( C ) ,
whence
c p a s s ( C ) ≤ γ γ − 1 ∑ v ∈ V ( C ) ∩ W i b v ( C ) . (21) c_{\mathrm{pass}}(C) \le\frac{\gamma}{\gamma- 1}\sum_{v\in V(C)\cap W_i} b_v(C). \tag*{(21)} c pass ( C ) ≤ γ − 1 γ v ∈ V ( C ) ∩ W i ∑ b v ( C ) . (21)
An initialization index receives cover charges in at most one preterminal call. Indeed, suppose a call retains a component Z Z Z of index k k k containing a cover circuit of index i ≥ k i \ge k i ≥ k . Then W i ⊆ Z W_i \subseteq Z W i ⊆ Z , and retention certifies that no local circuit in G [ U ] G[U] G [ U ] crossing Z Z Z has search cost at most σ k ( γ − 1 ) θ \frac{\sigma_k}{(\gamma-1)\theta} ( γ − 1 ) θ σ k . In a later call, a surviving circuit of index i i i would meet W i W_i W i but leave its current H H H -component, which contains Z Z Z . It would cross Z Z Z with cost at most σ i ( γ − 1 ) θ ≤ σ k ( γ − 1 ) θ \frac{\sigma_i}{(\gamma-1)\theta} \le\frac{\sigma_k}{(\gamma-1)\theta} ( γ − 1 ) θ σ i ≤ ( γ − 1 ) θ σ k by (6.6), a contradiction. Within its one charged call, the cover uses at most two passages at each positive-price vertex. Summing (21) therefore bounds the preterminal cover cost by
2 γ γ − 1 ∑ v ∈ U b v f i n . (22) \frac{2\gamma}{\gamma- 1}\sum_{v\in U} b_v^{\mathrm{fin}}. \tag*{(22)} γ − 1 2 γ v ∈ U ∑ b v fin . (22)
Charge a retained additional circuit from Step 3 to the index of its selected component. Its insertion joins that component to one of smaller index. If the circuit is retained, that union enters H H H , so the charged index can never again be selected as a component minimum. Within its call it already disappears upon insertion. Thus each index pays for at most one retained additional circuit, including those retained in the terminal call. Together with the initialization, these circuits cost at most
∑ i ( c p a s s ( I i ) + σ i ( γ − 1 ) θ ) ≤ ∑ i ℓ ( I i ) ≤ γ 1 − δ ∑ v ∈ U b v f i n + n 0 Δ . \sum_i\left(c_{\mathrm{pass}}(I_i)+\frac{\sigma_i}{(\gamma-1)\theta}\right) \le\sum_i \ell(I_i) \le\frac{\gamma}{1-\delta}\sum_{v\in U} b_v^{\mathrm{fin}}+n_0\Delta. i ∑ ( c pass ( I i ) + ( γ − 1 ) θ σ i ) ≤ i ∑ ℓ ( I i ) ≤ 1 − δ γ v ∈ U ∑ b v fin + n 0 Δ.
Here ( γ − 1 ) θ ≥ 1 (\gamma-1)\theta\ge1 ( γ − 1 ) θ ≥ 1 , and every initialization passage is retained. Finally, n 0 Δ = δ w ( U ) ≤ ( δ / θ ) ∑ v b v f i n n_0\Delta=\delta w(U)\le(\delta/\theta)\sum_v b_v^{\mathrm{fin}} n 0 Δ = δ w ( U ) ≤ ( δ / θ ) ∑ v b v fin . Combining this inequality with (22) and (12) proves (13) .
If w ( U ) = 0 w(U)=0 w ( U ) = 0 , all raw and effective local costs vanish. Set all budgets to zero, omit restarts, and use threshold zero in Step 3; the same connectivity argument applies and the bound is zero. If U = ∅ U=\varnothing U = ∅ , return H = ∅ H=\varnothing H = ∅ and an unpruned subtour cover. Keeping that cover also preserves its comparison bound when c r o u n d T x < 0 c_{\mathrm{round}}^{T}x<0 c round T x < 0 . This completes the proof of Theorem 6.1 .
As δ ↓ 0 \delta\downarrow0 δ ↓ 0 , the coefficient approaches γ + 2 γ / ( γ − 1 ) \gamma+2\gamma/(\gamma-1) γ + 2 γ / ( γ − 1 ) , whose minimum is 3 + 2 2 3+2\sqrt{2} 3 + 2 2 at γ = 1 + 2 \gamma=1+\sqrt{2} γ = 1 + 2 . Taking θ = 3 / 4 \theta=3/4 θ = 3/4 satisfies (11) for rational γ \gamma γ sufficiently close to this value.
Corollary 6.3 (Removing the singleton surcharge). For every fixed η > 3 + 2 2 \eta>3+2\sqrt{2} η > 3 + 2 2 , there is a ( 2 , η ) (2,\eta) ( 2 , η ) -algorithm for vertebrate pairs in the sense of (2) .
Proof. Choose fixed parameters for Svensson’s algorithm for which the coefficient in (13) is at most η \eta η . Apply Theorem 6.1 on the original graph with B 0 = V ( B ) B_0=V(B) B 0 = V ( B ) and d v = 0 d_v=0 d v = 0 for every v ∉ B 0 v\notin B_0 v ∈ / B 0 . The backbone meets every nonsingleton laminar set, so all missed positive sets are singletons. Set V t i g h t = { v ∉ B 0 : y v > 0 } V_{\mathrm{tight}}=\{v\notin B_0:y_v>0\} V tight = { v ∈ / B 0 : y v > 0 } ; their singleton cuts are tight, and every local arc u v uv uv has cost y u + y v y_u+y_v y u + y v . Thus b v f i n = 2 y v b_v^{\mathrm{fin}}=2y_v b v fin = 2 y v , no nontrivial child path must be inserted, and the original costs can serve as c r o u n d c_{\mathrm{round}} c round . Theorem 5.1 bounds the terminal cover by 2 L P 2\mathrm{LP} 2 LP , and Theorem 6.1 bounds the additional local arcs by α ∑ v ∉ V ( B ) 2 y v ≤ η ∑ v ∉ V ( B ) 2 y v \alpha\sum_{v\notin V(B)}2y_v\le\eta\sum_{v\notin V(B)}2y_v α ∑ v ∈ / V ( B ) 2 y v ≤ η ∑ v ∈ / V ( B ) 2 y v . Their union with the backbone is a tour. □ \square □
One recursive augmentation call
The input now consists of a region W W W and a partial backbone B B B : an actual connected Eulerian multigraph meeting W W W , with no requirement to meet all its positive descendants. Such recursive completion already appears in the reduction to vertebrate pairs [9 Lemma 7.13] . Corollary 6.3 supplies its standard ( 2 , η ) (2,\eta) ( 2 , η ) input, with the circuit-charging coefficient α \alpha α bounded by η \eta η . Our sharper recursion uses more of this algorithm’s construction: the charge in Theorem 6.1 depends on the retained passages’ coverage, which the ( 2 , η ) (2,\eta) ( 2 , η ) guarantee alone does not specify. We preserve those routes and use their coverage when comparing recursive completions.
One call has the following order. Contract the inclusion-maximal positive proper descendants of W W W missed by B B B , retaining the entry and exit ports of their boundary arcs. Every remaining nonsingleton laminar set is met by B B B ; otherwise it would lie inside one of the contracted sets. For a proper W W W , close its fractional flow by the private return paths of Lemma 4.3. Run the extension of Svensson’s algorithm just proved on this quotient, then expand its prescribed paths. Finally, complete each contracted child by one recursive call. At this last step we compare reuse of a lifted component with the two fresh partial backbones of Lemma 4.2.
The quotient is connected when Svensson’s algorithm stops, but its lift can have several components: two visits to a contracted child may use disjoint internal paths. Recursive completion spans that child and joins all components incident with it. We prove this connectivity assertion separately from the cost comparison below.
Let ρ \rho ρ be the target tour approximation ratio. Choose fixed rational parameters satisfying
γ > 1 , 0 < δ < 1 , 0 < θ ≤ 1 , 1 ( γ − 1 ) θ ≤ 1 , α = γ 1 − δ + 2 γ γ − 1 + δ θ . (23) \gamma> 1,\quad0 < \delta< 1,\quad0 < \theta\le1,\quad\frac{1}{(\gamma-1)\theta} \le1,\quad\alpha= \frac{\gamma}{1-\delta} + \frac{2\gamma}{\gamma-1} + \frac{\delta}{\theta}. \tag*{(23)} γ > 1 , 0 < δ < 1 , 0 < θ ≤ 1 , ( γ − 1 ) θ 1 ≤ 1 , α = 1 − δ γ + γ − 1 2 γ + θ δ . (23)
ρ ≥ 10 , λ = 1 ρ − 3 , θ ≤ 1 − 2 ρ − 2 , ρ ≥ α + 6 + 4 λ . (24) \rho\ge10,\quad\lambda= \frac{1}{\rho-3},\quad\theta\le1-\frac{2}{\rho-2},\quad\rho\ge\alpha+ 6 + 4\lambda. \tag*{(24)} ρ ≥ 10 , λ = ρ − 3 1 , θ ≤ 1 − ρ − 2 2 , ρ ≥ α + 6 + 4 λ . (24)
The coefficient λ \lambda λ is the weight assigned to the forward transportation prices in the comparison objective. In particular ρ ≥ α + 2 \rho\ge\alpha+ 2 ρ ≥ α + 2 and λ ≤ 1 \lambda\le1 λ ≤ 1 . The last condition closes the recursive cost bound: the target ratio must satisfy ρ ≥ α + 6 + 4 / ( ρ − 3 ) \rho\ge\alpha+ 6 + 4/(\rho- 3) ρ ≥ α + 6 + 4/ ( ρ − 3 ) .
Theorem 6.4 (Recursive augmentation). Given a strongly laminar instance with its fixed nice paths, a region W ∈ L ∪ { V } W \in\mathcal{L} \cup\{V\} W ∈ L ∪ { V } , and a partial backbone B B B for W W W , the recursive extension of Theorem 6.1 computes an augmentation E W E_W E W of B B B inside W W W satisfying
c ( E W ) ≤ ρ M W + 2 e W − ( ρ − 2 ) cov W ( B ) . (25) c(E_W) \le\rho M_W + 2e_W - (\rho- 2)\operatorname{cov}_W(B). \tag*{(25)} c ( E W ) ≤ ρ M W + 2 e W − ( ρ − 2 ) cov W ( B ) . (25) For fixed rational parameters satisfying (6.9)–(6.10), the algorithm is polynomial time.
Since e W ≤ d W e_W \le d_W e W ≤ d W for proper W W W by (4.3) and e V = 0 e_V = 0 e V = 0 , the same output satisfies
c ( E W ) ≤ ρ M W + 2 d W − ( ρ − 2 ) cov W ( B ) . c(E_W) \le\rho M_W + 2d_W - (\rho- 2)\operatorname{cov}_W(B). c ( E W ) ≤ ρ M W + 2 d W − ( ρ − 2 ) cov W ( B ) .
This is exactly the augmentation bound used in Lemma 7.2 with κ = 2 \kappa= 2 κ = 2 ; its parameter condition ρ ≥ 3 κ + 2 \rho\ge3\kappa+ 2 ρ ≥ 3 κ + 2 follows from ρ ≥ 10 \rho\ge10 ρ ≥ 10 .
We prove this by induction on the laminar hierarchy. The algorithm below specifies which arcs are added; the child inequality proves their cost bound. If M W = 0 M_W = 0 M W = 0 , all internal arc costs vanish. Join a vertex of B ∩ W B \cap W B ∩ W to every vertex of W W W and back by support paths. Their union is a zero-cost Eulerian augmentation. In this case d W = e W = 0 d_W = e_W = 0 d W = e W = 0 . Suppose henceforth M W > 0 M_W > 0 M W > 0 . Form the children C C C , the quotient, and its private closure as in Section 4.
For each child L L L , define its fresh-backbone credit by
credit L = max { ( 1 − 2 ρ − 2 ) d L , ( ρ − 3 ) ( c L ← + b L ) − ( c L → + b L ) ρ − 2 } . (26) \operatorname{credit}_{L}=\max\left\{\left(1-\frac{2}{\rho-2}\right)d_{L},\frac{(\rho-3)(c_{L}^{\leftarrow}+b_{L})-(c_{L}^{\rightarrow}+b_{L})}{\rho-2}\right\}. \tag*{(26)} credit L = max { ( 1 − ρ − 2 2 ) d L , ρ − 2 ( ρ − 3 ) ( c L ← + b L ) − ( c L → + b L ) } . (26)
The first term comes from the maximum-coverage backbone; the second uses the forward and reverse transportation costs. At least one of the fresh backbones of Lemma 4.2 , applied with r = ρ − 2 r=\rho-2 r = ρ − 2 , has cost minus ( ρ − 2 ) (\rho-2) ( ρ − 2 ) times its coverage at most − ( ρ − 2 ) credit L -(\rho-2)\operatorname{credit}_{L} − ( ρ − 2 ) credit L . Thus this credit measures the cost-adjusted saving available from a fresh backbone in the completion comparison below. By (7) ,
( 1 − 2 ρ − 2 ) d L ≤ credit L ≤ ρ − 3 ρ − 2 d L , \left(1-\frac{2}{\rho-2}\right)d_{L}\leq\operatorname{credit}_{L}\leq\frac{\rho-3}{\rho-2}d_{L}, ( 1 − ρ − 2 2 ) d L ≤ credit L ≤ ρ − 2 ρ − 3 d L ,
( 1 − λ ) d L ≤ ( 1 + λ ) credit L ≤ d L . (27) (1-\lambda)d_{L}\leq(1+\lambda)\operatorname{credit}_{L}\leq d_{L}. \tag*{(27)} ( 1 − λ ) d L ≤ ( 1 + λ ) credit L ≤ d L . (27)
These formulas also apply when d L = 0 d_{L}=0 d L = 0 , in which case c L → = c L ← = b L = credit L = 0 c_{L}^{\rightarrow}=c_{L}^{\leftarrow}=b_{L}=\operatorname{credit}_{L}=0 c L → = c L ← = b L = credit L = 0 and we use zero endpoint prices. The fixed search weight at a child is 2 y L + d L 2y_{L}+d_{L} 2 y L + d L ; at an uncontracted vertex outside B 0 B_{0} B 0 it is zero, since every missed positive singleton is a child.
Let φ u L , i n , φ v L , o u t \varphi_{u}^{L,\mathrm{in}},\varphi_{v}^{L,\mathrm{out}} φ u L , in , φ v L , out be the bounded forward prices of Lemma 4.1 . For a surviving quotient arc e e e , let u e u_{e} u e be its original head label, v e v_{e} v e its original tail label, and let c ( e ) c(e) c ( e ) retain its original cost or its assigned share of a private return-path cost. Define the global rounding objective by
c r o u n d ( e ) = c ( e ) + ∑ L ∈ C : u e ∈ L ( − h L ( u e ) + ( 1 + λ ) credit L 2 − λ φ u e L , i n ) + ∑ L ∈ C : v e ∈ L ( − h L ( v e ) + ( 1 + λ ) credit L 2 − λ φ v e L , o u t ) . (28) \begin{aligned}
c_{\mathrm{round}}(e)={}&c(e)+\sum_{L\in\mathcal{C}:u_{e}\in L}\left(-h_{L}(u_{e})+\frac{(1+\lambda)\operatorname{credit}_{L}}{2}-\lambda\varphi_{u_{e}}^{L,\mathrm{in}}\right)\\
&+\sum_{L\in\mathcal{C}:v_{e}\in L}\left(-h_{L}(v_{e})+\frac{(1+\lambda)\operatorname{credit}_{L}}{2}-\lambda\varphi_{v_{e}}^{L,\mathrm{out}}\right). \tag*{(28)}
\end{aligned} c round ( e ) = c ( e ) + L ∈ C : u e ∈ L ∑ ( − h L ( u e ) + 2 ( 1 + λ ) credit L − λ φ u e L , in ) + L ∈ C : v e ∈ L ∑ ( − h L ( v e ) + 2 ( 1 + λ ) credit L − λ φ v e L , out ) . (28)
Each sum has at most one term. On a real arc, an endpoint’s remaining contribution is at least y L + ( ( 1 + λ ) credit L − λ d L ) / 2 ≥ 0 y_{L}+((1+\lambda)\operatorname{credit}_{L}-\lambda d_{L})/2\geq0 y L + (( 1 + λ ) credit L − λ d L ) /2 ≥ 0 . Thus real arcs are nonnegative; private coefficients may be signed, as permitted by Theorem 5.1 .
The exact fractional comparison value is
c r o u n d T x W = e W + cov W ( B ) + ∑ L ∈ C ( 2 y L + ( 1 + λ ) credit L − λ c L → ) . (29) c_{\mathrm{round}}^{T}x^{W}=e_{W}+\operatorname{cov}_{W}(B)+\sum_{L\in\mathcal{C}}\left(2y_{L}+(1+\lambda)\operatorname{credit}_{L}-\lambda c_{L}^{\rightarrow}\right). \tag*{(29)} c round T x W = e W + cov W ( B ) + L ∈ C ∑ ( 2 y L + ( 1 + λ ) credit L − λ c L → ) . (29)
Indeed, start with M W + e W M_{W}+e_{W} M W + e W . Contracting L L L removes original internal flow of cost M L − b L M_{L}-b_{L} M L − b L ; the endpoint subtractions remove a further b L b_{L} b L . Inflation contributes ( 1 + λ ) credit L (1+\lambda)\operatorname{credit}_{L} ( 1 + λ ) credit L , and the dual prices subtract λ c L → \lambda c_{L}^{\rightarrow} λ c L → . Apply (8) . The private paths are still paid in full: their internal arcs were not part of the original internal flow removed during contraction.
We check the hypotheses of Theorems 5.1 and 6.1 . Current local components are strongly connected and lie in one rank class. Every positive-price quotient vertex outside B 0 B_{0} B 0 is a tight child. A local circuit’s lift has cost equal to the sum of 2 y L + cov L ( P ) 2y_{L}+\operatorname{cov}_{L}(P) 2 y L + cov L ( P ) over its child passages. The witness and real cut constraints follow from Lemma 4.3 , or from the original quotient at the root. Apply Theorem 6.1 , with formal identification of B 0 B_{0} B 0 only for connectivity, to obtain local walks H H H and a terminal cover F o u t F_{\mathrm{out}} F out . Keep every route with its original entry and exit labels.
Lifting and selecting the recursive calls. A charged passage is a visit to a child in a retained quotient walk. Visits internal to a separately paid private return are excluded: their path costs were already included in the comparison objective. Expand the stored child passages and private returns, obtaining an Eulerian multiset K ⊆ E [ W ] K\subseteq E[W] K ⊆ E [ W ] . Initially set E W = K E_{W}=K E W = K . For each child L L L , fix a charged passage of maximum certified coverage. Process the children in a fixed order. Just before processing L L L , let B L B_L B L be the current actual component containing that passage. Compare
− ( ρ − 2 ) cov L ( B L ) , ( 4 − ρ ) d L , c L → − ( ρ − 3 ) c L ← − ( ρ − 2 ) b L . (30) -(\rho- 2)\operatorname{cov}_L(B_L), \qquad(4-\rho)d_L, \qquad c_L^{\to}-(\rho-3)c_L^{\leftarrow}-(\rho-2)b_L. \tag*{(30)} − ( ρ − 2 ) cov L ( B L ) , ( 4 − ρ ) d L , c L → − ( ρ − 3 ) c L ← − ( ρ − 2 ) b L . (30)
For the first choice, recursively augment ( L , B L ) (L,B_L) ( L , B L ) and add only the augmentation. For the second or third, build the corresponding fresh backbone from Lemma 4.2 , recursively augment it, and add both the fresh backbone and its augmentation. Execute only the selected call.
Connectivity and the recursive cost bound
The connectivity argument has two parts. Completing the children joins components by the elementary observation below. We then verify that the lifted walks satisfy its hypothesis and supply the coverage needed for the recursive cost bound.
Lemma 6.5 (Joining components through disjoint regions). Let H H H be an Eulerian multigraph whose vertex set contains W W W , including unvisited vertices of W W W as isolated vertices, and let C \mathcal{C} C be a family of disjoint nonempty subsets of W W W . Form the bipartite graph with one vertex for each component of H H H and each L ∈ C L \in\mathcal{C} L ∈ C , joining a component to a region when they intersect. Suppose this graph is connected. Process the regions in any order, adding inside each L L L an Eulerian multiset that joins all current components meeting L L L . The resulting multigraph is connected and Eulerian and spans W W W .
Proof. Adding arcs preserves balance and can only join components. Each initial component of H H H therefore lies in one final component. After processing L L L , all initial components incident with L L L lie in the same component, and later additions preserve this fact. Connectivity of the incidence graph implies that all initial components lie in one final component. They include every vertex of W W W . □ \square □
Lemma 6.6 (Actual components certify the lifted passages). The expanded multiset K K K is Eulerian, and every retained walk of F o u t F_{\mathrm{out}} F out that met B 0 B_0 B 0 lifts to a walk meeting the actual B B B . Each child has a charged passage. For the component B L B_L B L selected above, every charged passage P P P through L L L satisfies
cov L ( P ) ≤ min { cov L ( B L ) , d L } . (31) \operatorname{cov}_L(P) \le\min\{\operatorname{cov}_L(B_L),d_L\}. \tag*{(31)} cov L ( P ) ≤ min { cov L ( B L ) , d L } . (31) If the completion of each child joins all current components meeting that child and visits all its vertices, the final union with B B B is connected and spans W W W .
Proof. Every replacement uses a path with the same labeled endpoints, and hence preserves the closed walk containing it. A split walk meeting a real backbone vertex keeps that vertex. A walk visiting a private vertex has, between consecutive private visits, a real backbone upward switch by Lemma 4.3 . The cover’s repairs preserve that visit. Child expansion cannot delete it because children miss B B B , and replacing a private visit preserves both real endpoints. This proves attachment.
Every child lies outside the formal backbone, so quotient connectivity gives a charged passage through it. The maximum such passage is contained in one actual connected Eulerian component. Lemma 3.2 then gives (6.17); earlier additions only enlarge this component and its coverage.
For connectivity, form a bipartite incidence graph whose vertices are the actual components of B ∪ K B \cup K B ∪ K and the children. Join a component to each child it meets. Include unvisited vertices as isolated actual components; such vertices lie inside children. Every quotient intersection at an uncontracted real vertex is already an actual intersection. An intersection at a child is represented by the corresponding incidence vertex, and an attachment to B 0 B_0 B 0 is an attachment to the actual B B B . The incidence graph is therefore connected. Lemma 6.5 , with H = B ∪ K H=B \cup K H = B ∪ K and the unvisited vertices of W W W included, now proves the final assertion. □ \square □
Each choice in (30) has the required joining property. For reuse, induction connects and spans L L L together with B L B_L B L , so it intersects every existing component meeting L L L . A fresh completion is itself connected and spans L L L , and has the same effect. Thus the algorithm has the asserted connectivity.
For a terminal-cover passage entering L L L at u u u and leaving at v v v , restoring the endpoint weights and adding its internal path changes the paid cost by
cov L ( P u v L ) − ( 1 + λ ) credit L + λ ( φ u L , i n + φ v L , o u t ) ≤ ( 1 + λ ) ( cov L ( P u v L ) − credit L ) . (32) \operatorname{cov}_L(P_{uv}^{L})-(1+\lambda)\operatorname{credit}_L+\lambda(\varphi_{u}^{L,\mathrm{in}}+\varphi_{v}^{L,\mathrm{out}})\le(1+\lambda)\left(\operatorname{cov}_L(P_{uv}^{L})-\operatorname{credit}_L\right). \tag*{(32)} cov L ( P uv L ) − ( 1 + λ ) credit L + λ ( φ u L , in + φ v L , out ) ≤ ( 1 + λ ) ( cov L ( P uv L ) − credit L ) . (32)
The dual constraint is for this same nice path. No correction is needed for H H H , whose circuit-charging bound already measures its lift. Private returns are inserted at their assigned full price. Any additional coverage they create only helps; their internal visits need no terminal degree charge.
The child inequality. We now combine the three costs associated with a child: its local circuits, the terminal cover’s prescribed passages, and its recursive completion. A larger retained passage can cost more to lift, but it also makes the reuse choice less expensive by increasing certified coverage. The bound is largest where reuse becomes preferable to a fresh partial backbone. This is the tradeoff captured in the following calculation.
Induction and Lemma 4.2 bound the cost of completing L L L by
ρ M L + 2 e L + min { − ( ρ − 2 ) cov L ( B L ) , ( 4 − ρ ) d L , c L → − ( ρ − 3 ) c L ← − ( ρ − 2 ) b L } . (33) \rho M_L+2e_L+\min\left\{-(\rho-2)\operatorname{cov}_L(B_L),(4-\rho)d_L,c_L^{\to}-(\rho-3)c_L^{\leftarrow}-(\rho-2)b_L\right\}. \tag*{(33)} ρ M L + 2 e L + min { − ( ρ − 2 ) cov L ( B L ) , ( 4 − ρ ) d L , c L → − ( ρ − 3 ) c L ← − ( ρ − 2 ) b L } . (33)
The local-circuit charge at this child is at most α ( 2 y L + max { θ d L , min { cov L ( B L ) , d L } } ) \alpha(2y_L+\max\{\theta d_L,\min\{\operatorname{cov}_L(B_L),d_L\}\}) α ( 2 y L + max { θ d L , min { cov L ( B L ) , d L }}) . The terminal cover costs at most twice (29) and has at most four charged passages through L L L . Therefore its lifting excess is at most 4 ( 1 + λ ) [ min { cov L ( B L ) , d L } − credit L ] + 4(1+\lambda)[\min\{\operatorname{cov}_L(B_L),d_L\}-\operatorname{credit}_L]_+ 4 ( 1 + λ ) [ min { cov L ( B L ) , d L } − credit L ] + .
The fresh-backbone credit was chosen so that
min { − ( ρ − 2 ) cov L ( B L ) , ( 4 − ρ ) d L , c L → − ( ρ − 3 ) c L ← − ( ρ − 2 ) b L } ≤ − ( ρ − 2 ) max { cov L ( B L ) , credit L } . \min\left\{-(\rho-2)\operatorname{cov}_L(B_L),(4-\rho)d_L,c_L^{\to}-(\rho-3)c_L^{\leftarrow}-(\rho-2)b_L\right\}\le-(\rho-2)\max\{\operatorname{cov}_L(B_L),\operatorname{credit}_L\}. min { − ( ρ − 2 ) cov L ( B L ) , ( 4 − ρ ) d L , c L → − ( ρ − 3 ) c L ← − ( ρ − 2 ) b L } ≤ − ( ρ − 2 ) max { cov L ( B L ) , credit L } .
Indeed, the two fresh choices bound the minimum by − ( ρ − 2 ) credit L -(\rho-2)\operatorname{credit}_L − ( ρ − 2 ) credit L ; the transportation choice has a further nonpositive term − 2 b L -2b_L − 2 b L . Also
2 e L − 2 λ c L → ≤ 2 ( c L ← + b L ) − 2 λ ( c L → + b L ) , 2e_L-2\lambda c_L^{\to}\le2(c_L^{\leftarrow}+b_L)-2\lambda(c_L^{\to}+b_L), 2 e L − 2 λ c L → ≤ 2 ( c L ← + b L ) − 2 λ ( c L → + b L ) ,
since e L = c L ← − b L e_L=c_L^{\leftarrow}-b_L e L = c L ← − b L and λ ≤ 1 \lambda\le1 λ ≤ 1 . After removing the common term ρ M L \rho M_L ρ M L and the boundary weight, the remaining child charge is therefore bounded by the left-hand side of (34) , with A = cov L ( B L ) A=\operatorname{cov}_L(B_L) A = cov L ( B L ) .
Lemma 6.7 (Child charge). Under (24) , every child L L L and every A ≥ 0 A\ge0 A ≥ 0 satisfy
2 ( 1 + λ ) credit L + α max { θ d L , min { A , d L } } + 4 ( 1 + λ ) [ min { A , d L } − credit L ] + + 2 ( c L ← + b L ) − 2 λ ( c L → + b L ) − ( ρ − 2 ) max { A , credit L } ≤ 0. (34) \begin{aligned}
&2(1+\lambda)\operatorname{credit}_L+\alpha\max\{\theta d_L,\min\{A,d_L\}\}\\
&\quad+4(1+\lambda)[\min\{A,d_L\}-\operatorname{credit}_L]_+\\
&\quad+2(c_L^{\leftarrow}+b_L)-2\lambda(c_L^{\to}+b_L)-(\rho-2)\max\{A,\operatorname{credit}_L\}\le0. \tag*{(34)}
\end{aligned} 2 ( 1 + λ ) credit L + α max { θ d L , min { A , d L }} + 4 ( 1 + λ ) [ min { A , d L } − credit L ] + + 2 ( c L ← + b L ) − 2 λ ( c L → + b L ) − ( ρ − 2 ) max { A , credit L } ≤ 0. (34)
Proof. If d L = 0 d_L=0 d L = 0 , the left-hand side is − ( ρ − 2 ) A ≤ 0 -(\rho-2)A\le0 − ( ρ − 2 ) A ≤ 0 . Otherwise θ d L ≤ credit L < d L \theta d_L\le\operatorname{credit}_L<d_L θ d L ≤ credit L < d L . As a function of A A A , the left-hand side is nondecreasing on [ 0 , credit L ] [0,\operatorname{credit}_L] [ 0 , credit L ] . On [ credit L , d L ] [\operatorname{credit}_L,d_L] [ credit L , d L ] it has slope α + 6 + 4 λ − ρ ≤ 0 \alpha+6+4\lambda-\rho\le0 α + 6 + 4 λ − ρ ≤ 0 , and above d L d_L d L it has slope 2 − ρ 2-\rho 2 − ρ . It is therefore largest at A = credit L A=\operatorname{credit}_L A = credit L , where it equals
2 [ ( c L ← + b L ) − λ ( c L → + b L ) − ( 1 + λ ) credit L ] − ( ρ − α − 6 − 4 λ ) credit L . 2[(c_L^{\leftarrow}+b_L)-\lambda(c_L^{\to}+b_L)-(1+\lambda)\operatorname{credit}_L]-(\rho-\alpha-6-4\lambda)\operatorname{credit}_L. 2 [( c L ← + b L ) − λ ( c L → + b L ) − ( 1 + λ ) credit L ] − ( ρ − α − 6 − 4 λ ) credit L .
The first bracket is nonpositive by (26) and 1 + λ = ( ρ − 2 ) / ( ρ − 3 ) 1+\lambda=(\rho-2)/(\rho-3) 1 + λ = ( ρ − 2 ) / ( ρ − 3 ) . The second bracket is nonnegative by the parameter condition. This proves the inequality.
Boundary mass 2 y L 2y_L 2 y L has coefficient 2 + α ≤ ρ 2+\alpha\le\rho 2 + α ≤ ρ . Summing the child charges leaves the parent term 2 e W + 2 cov W ( B ) 2e_W+2\operatorname{cov}_W(B) 2 e W + 2 cov W ( B ) and at most ∑ L ∈ C ρ ( 2 y L + M L ) \sum_{L\in\mathcal{C}}\rho(2y_L+M_L) ∑ L ∈ C ρ ( 2 y L + M L ) . By (8) , this is exactly the right side of (25) . The connectivity argument above and the algorithmic bounds below complete the proof of Theorem 6.4.
Polynomial running time and explicit output size
All transportation problems, witness programs, cut separations, shortest paths, and bounded circulation optimizations use rational data of polynomial encoding length. The relative-interior constructions in Section 5 use polynomially many such optimizations. The initialization potential bounds the number of restarts by a polynomial for fixed δ \delta δ , γ \gamma γ , θ \theta θ ; between restarts every update to H H H reduces the number of quotient components.
We also need a polynomial bound on explicit arc multiplicities. Decompose the original primal circulation into at most ∣ E ∣ |E| ∣ E ∣ simple cycles and truncate every coefficient above one to one. A truncated cycle crosses no positive tight laminar cut, since otherwise its original contribution to that unit cut would exceed one. Thus truncation preserves every tight cut, its port marginals, and the induced objective. It preserves all other subtour inequalities as well: either no truncated cycle crosses the cut, or one retained unit cycle already supplies its required incoming value. Balance and positive support are unchanged, and now x e ≤ ∣ E ∣ x_e\le|E| x e ≤ ∣ E ∣ . Perform this normalization before computing the boundary data.
The private couplings have unit mass. Auxiliary constructions introduce only polynomially many labeled arcs. Each rounding upper bound is the ceiling of twice a polynomially bounded flow amount, so its integral output has polynomially many arc copies. Each stored nice path has at most ∣ V ∣ − 1 |V|-1 ∣ V ∣ − 1 arcs.
The recursive regions are original laminar sets. Distinct branches are disjoint, and a branch descends strictly, so each laminar set is processed at most once. Only one of the three choices is recursively executed. Inherited backbone arcs are kept by reference, not reinserted. The nonrecursive work of each call adds polynomially many new arcs, independently of inherited multiplicities. Summing over O ( ∣ V ∣ ) O(|V|) O ( ∣ V ∣ ) calls proves polynomial total output size and running time. The polynomial degree depends on the fixed approximation parameters.
Tour and path guarantees
We first choose the parameters for Theorem 6.4. We then prove one completion lemma that converts a recursive augmentation bound into tour and path guarantees. Applying it to the reduction of Traub and Vygen proves the transfer from vertebrate pairs; applying it to Theorem 6.4 proves the common guarantee in Theorem 1.1.
Choosing the approximation parameters
As δ ↓ 0 \delta\downarrow0 δ ↓ 0 and rational γ → 1 + 2 \gamma\to1+\sqrt{2} γ → 1 + 2 , with θ = 3 / 4 \theta=3/4 θ = 3/4 , the circuit-charging coefficient tends to α ∗ = 3 + 2 2 \alpha_\ast=3+2\sqrt{2} α ∗ = 3 + 2 2 . Equality in the decisive condition ρ ≥ α + 6 + 4 / ( ρ − 3 ) \rho\ge\alpha+6+4/(\rho-3) ρ ≥ α + 6 + 4/ ( ρ − 3 ) is
ρ 2 − ( α ∗ + 9 ) ρ + 3 α ∗ + 14 = 0. \rho^2-(\alpha_\ast+9)\rho+3\alpha_\ast+14=0. ρ 2 − ( α ∗ + 9 ) ρ + 3 α ∗ + 14 = 0.
Its larger root is
R ∗ = 6 + 2 + 15 + 6 2 . (35) R_* = 6 + \sqrt{2} + \sqrt{15 + 6\sqrt{2}}. \tag*{(35)} R ∗ = 6 + 2 + 15 + 6 2 . (35)
For any fixed ε > 0 \varepsilon> 0 ε > 0 , choose a rational ρ \rho ρ with R ∗ < ρ < R ∗ + ε R_* < \rho< R_* + \varepsilon R ∗ < ρ < R ∗ + ε , and set θ = 3 / 4 \theta= 3/4 θ = 3/4 and λ = 1 / ( ρ − 3 ) \lambda= 1/(\rho- 3) λ = 1/ ( ρ − 3 ) . Then ρ > α ∗ + 6 + 4 λ \rho> \alpha_* + 6 + 4\lambda ρ > α ∗ + 6 + 4 λ . The remaining inequalities involving γ \gamma γ , θ \theta θ , ρ \rho ρ hold strictly at γ = 1 + 2 \gamma= 1 + \sqrt{2} γ = 1 + 2 . Taking rational γ \gamma γ sufficiently close to this value and rational δ > 0 \delta> 0 δ > 0 sufficiently small therefore satisfies (23) –(24) . These parameters depend only on ε \varepsilon ε , so the augmentation algorithm runs in polynomial time for every fixed ε > 0 \varepsilon> 0 ε > 0 . The completion lemma below supplies the tour and path guarantees.
A stronger path reduction from vertebrate pairs
The path reduction of Traub and Vygen [9 Theorem 9.23] converts a ( κ , η ) (\kappa,\eta) ( κ , η ) -algorithm into factor max { 3 κ + η + 2 , 4 κ + 7 } \max\{3\kappa+\eta+2,4\kappa+7\} max { 3 κ + η + 2 , 4 κ + 7 } . Its second branch can prevent an improvement in the vertebrate-pair algorithm from reaching paths. For κ ≥ 1 \kappa\ge1 κ ≥ 1 , the following theorem lowers that branch.
Theorem 7.1 (Transfer from vertebrate pairs). For fixed rational κ ≥ 1 \kappa\ge1 κ ≥ 1 and η ≥ 0 \eta\ge0 η ≥ 0 , a polynomial-time ( κ , η ) (\kappa,\eta) ( κ , η ) -algorithm for vertebrate pairs gives a polynomial-time LP-relative approximation for asymmetric path TSP with factor
max { 3 κ + η + 2 , 4 κ + 5 − 4 κ + 4 2 κ + η + 2 } . (36) \max\left\{3\kappa+\eta+2,\ 4\kappa+5-\frac{4\kappa+4}{2\kappa+\eta+2}\right\}. \tag*{(36)} max { 3 κ + η + 2 , 4 κ + 5 − 2 κ + η + 2 4 κ + 4 } . (36)
The recursive reduction of Traub and Vygen [9 Lemma 7.13] extends a partial backbone B B B through a region W W W at added cost at most
κ ( M W + d W ) + ( 2 κ + η + 2 ) ( M W − cov W ( B ) ) . \kappa(M_W+d_W)+(2\kappa+\eta+2)(M_W-\operatorname{cov}_W(B)). κ ( M W + d W ) + ( 2 κ + η + 2 ) ( M W − cov W ( B )) .
This bound retains information that a complete-tour factor does not express: completion becomes cheaper as B B B visits more dual mass. We use this saving to compare two initial s s s –t t t walks. One preserves the coverage of two inexpensive paths; the other visits a maximum-coverage nice path in each strongly connected component of the positive LP support. Their completion bounds depend oppositely on the same sum of component coverage parameters. Combining them before eliminating that sum proves Theorem 7.1.
We state the calculation in terms of the resulting tour factor ρ \rho ρ . This also permits its use with the refined reduction of Traub and Vygen and with our stronger recursive augmentation.
Lemma 7.2 (Two-walk completion bound). Let κ ≥ 1 \kappa\ge1 κ ≥ 1 and ρ ≥ 3 κ + 2 \rho\ge3\kappa+2 ρ ≥ 3 κ + 2 be fixed rational constants. Suppose that, for every strongly laminar instance, one can choose a nice-path family in polynomial time such that the following holds for every region W ∈ L ∪ { V } W \in\mathcal{L} \cup\{V\} W ∈ L ∪ { V } and partial backbone B B B for W W W . A polynomial-time procedure returns an augmentation E W E_W E W of B B B inside W W W satisfying
c ( E W ) ≤ ρ M W + κ d W − ( ρ − κ ) cov W ( B ) . (37) c(E_W) \le\rho M_W+\kappa d_W-(\rho-\kappa)\operatorname{cov}_W(B). \tag*{(37)} c ( E W ) ≤ ρ M W + κ d W − ( ρ − κ ) cov W ( B ) . (37) Here d W d_W d W is defined using the selected family, fixed before W W W and B B B . Then there are polynomial-time LP-relative approximation algorithms with tour factor ρ \rho ρ and ( s , t ) (s,t) ( s , t ) -path factor
max { ρ , 4 κ + 5 − 4 κ + 4 ρ − κ } . (38) \max\left\{\rho,\ 4\kappa+5-\frac{4\kappa+4}{\rho-\kappa}\right\}. \tag*{(38)} max { ρ , 4 κ + 5 − ρ − κ 4 κ + 4 } . (38) These factors agree whenever
( ρ − κ ) ( ρ − 4 κ − 5 ) + 4 κ + 4 ≥ 0. (39) (\rho-\kappa)(\rho-4\kappa-5)+4\kappa+4 \ge0. \tag*{(39)} ( ρ − κ ) ( ρ − 4 κ − 5 ) + 4 κ + 4 ≥ 0. (39) For κ = 2 \kappa= 2 κ = 2 , this condition is ρ ≥ ( 15 + 73 ) / 2 \rho\ge(15+\sqrt{73})/2 ρ ≥ ( 15 + 73 ) /2 .
The path algorithm constructs two initial walks and chooses between their certified completion bounds. It then makes one augmentation call per strongly connected component. The implementation of the augmentation procedure is used only through (37) .
Proof. For tours, Proposition 3.1 reduces the problem to induced costs. At the root, B V max B^{\max}_V B V m a x from Lemma 4.2 is a partial backbone of cost at most 2 d V 2d_V 2 d V and coverage at least d V d_V d V . Applying (37) gives total cost at most
ρ M V + ( 2 κ + 2 − ρ ) d V ≤ ρ L P , \rho M_V + (2\kappa+ 2 - \rho)d_V \le\rho\mathrm{LP}, ρ M V + ( 2 κ + 2 − ρ ) d V ≤ ρ LP ,
since ρ ≥ 3 κ + 2 ≥ 2 κ + 2 \rho\ge3\kappa+ 2 \ge2\kappa+ 2 ρ ≥ 3 κ + 2 ≥ 2 κ + 2 . In the application to Theorem 6.4, its sharper bound with e V = 0 e_V = 0 e V = 0 gives
ρ M V + ( 4 − ρ ) d V ≤ ρ L P . (40) \rho M_V + (4 - \rho)d_V \le\rho\mathrm{LP}. \tag*{(40)} ρ M V + ( 4 − ρ ) d V ≤ ρ LP . (40)
Vertex potentials cancel on the Eulerian output, and metric shortcutting does not increase cost.
Normalization and component completion. For distinct terminals s , t s,t s , t , recall the path relaxation L P s , t \mathrm{LP}_{s,t} LP s , t from Section 3. We work on the positive support of an optimum solution x x x . The following facts are the path normalization and two-path construction in the framework of Köhne, Traub, and Vygen [4 ] , in the form of Traub and Vygen [9 Lemmas 9.9, 9.10, and 9.16] . In polynomial time one obtains a laminar family L ⊆ 2 V ∖ { s , t } \mathcal{L} \subseteq2^{V\setminus\{s,t\}} L ⊆ 2 V ∖ { s , t } , positive weights y L y_L y L , and vertex potentials π \pi π , such that each G [ L ] G[L] G [ L ] is strongly connected, x ( δ − ( L ) ) = x ( δ + ( L ) ) = 1 x(\delta^-(L)) = x(\delta^+(L)) = 1 x ( δ − ( L )) = x ( δ + ( L )) = 1 , and
c y ( u v ) = ∑ L : u v ∈ δ ( L ) y L = c ( u v ) + π u − π v , c_y(uv) = \sum_{L:uv\in\delta(L)} y_L = c(uv) + \pi_u - \pi_v, c y ( uv ) = L : uv ∈ δ ( L ) ∑ y L = c ( uv ) + π u − π v ,
L P s , t = M − π s + π t , M = ∑ L ∈ L 2 y L . (41) \mathrm{LP}_{s,t} = M - \pi_s + \pi_t,\qquad M = \sum_{L\in\mathcal{L}} 2y_L. \tag*{(41)} LP s , t = M − π s + π t , M = L ∈ L ∑ 2 y L . (41)
The potentials are chosen to minimize π s − π t \pi_s-\pi_t π s − π t among optimal dual solutions. There are support s s s –t t t paths P 1 , P 2 P_1,P_2 P 1 , P 2 whose combined number of crossings of each positive laminar cut is at most two. Consequently, the paths never both visit a set of L \mathcal{L} L , and their total induced cost is the mass of the sets visited by their union. If M > 0 M > 0 M > 0 , define τ ∈ [ 0 , 1 ] \tau\in[0,1] τ ∈ [ 0 , 1 ] by
c y ( P 1 ) + c y ( P 2 ) = τ M . (42) c_y(P_1) + c_y(P_2) = \tau M. \tag*{(42)} c y ( P 1 ) + c y ( P 2 ) = τ M . (42)
Since the original costs are nonnegative, 0 ≤ c ( P 1 ) + c ( P 2 ) = τ M − 2 ( π s − π t ) 0 \le c(P_1) + c(P_2) = \tau M - 2(\pi_s - \pi_t) 0 ≤ c ( P 1 ) + c ( P 2 ) = τ M − 2 ( π s − π t ) . Therefore
M ≤ 2 L P s , t 2 − τ . (43) M \le\frac{2\mathrm{LP}_{s,t}}{2-\tau}. \tag*{(43)} M ≤ 2 − τ 2 LP s , t . (43)
Let W 1 , … , W k W_1,\ldots,W_k W 1 , … , W k be the strongly connected components of the support, in topological order. All intercomponent arcs go from W i W_i W i to W i + 1 W_{i+1} W i + 1 , and their total x x x -value is one; also s ∈ W 1 s \in W_1 s ∈ W 1 and t ∈ W k t \in W_k t ∈ W k . Every P j P_j P j thus has a nonempty section in every component. Every positive laminar set is contained in a component because its induced graph is strongly connected. It cannot equal that component: both paths would then visit it. Thus every such set is a proper subset of one W i W_i W i .
To invoke the augmentation procedure, add a vertex r r r and arcs t r , r s tr,rs t r , r s , each with unit flow. This closes x x x to a feasible subtour circulation. Adjoin the sets W i W_i W i to the laminar family and give each a positive own weight, say one, solely for this invocation. These weights contribute only to arcs crossing component boundaries. Choose the family supplied by the hypothesis for this augmented instance and retain its paths inside each W i W_i W i in every invocation. Define
M i : = M W i , d i : = d W i , ∑ i M i = M , D : = ∑ i d i ≤ M . (44) M_i := M_{W_i},\qquad d_i := d_{W_i},\qquad\sum_i M_i = M,\qquad D := \sum_i d_i \le M. \tag*{(44)} M i := M W i , d i := d W i , i ∑ M i = M , D := i ∑ d i ≤ M . (44)
For this fixed family, M i M_i M i , d i d_i d i , cov W i ( Q ) \operatorname{cov}_{W_i}(Q) cov W i ( Q ) and internal arc costs are the same under the original and augmented weights. The initial walks and the augmentation bound use these same d i d_i d i . For every support s s s –t t t walk Q Q Q , the multigraph B = Q ∪ { t r , r s } B=Q\cup\{tr,rs\} B = Q ∪ { t r , r s } is connected and Eulerian. The assumed procedure returns Eulerian arcs E i ⊆ E [ W i ] E_i\subseteq E[W_i] E i ⊆ E [ W i ] such that B ∪ E i B\cup E_i B ∪ E i is connected and spans W i W_i W i , with
c y ( E i ) ≤ ρ M i + κ d i − ( ρ − κ ) cov W i ( Q ) . (45) c_y(E_i)\le\rho M_i+\kappa d_i-(\rho-\kappa)\operatorname{cov}_{W_i}(Q). \tag*{(45)} c y ( E i ) ≤ ρ M i + κ d i − ( ρ − κ ) cov W i ( Q ) . (45)
Every call uses the same inherited B B B . All costs in the rest of this section are evaluated with the original weights in (41) , not the temporary component weights.
The union of B B B and all E i E_i E i is connected, spanning, and Eulerian. Since the E i E_i E i are internal to the original components, the auxiliary vertex has exactly one entering and one leaving arc. Cutting an Euler tour there and deleting t r , r s tr,rs t r , r s gives a spanning s s s –t t t walk F F F with
c ( F ) = c y ( Q ) + ∑ i c y ( E i ) − π s + π t . (46) c(F)=c_y(Q)+\sum_i c_y(E_i)-\pi_s+\pi_t. \tag*{(46)} c ( F ) = c y ( Q ) + i ∑ c y ( E i ) − π s + π t . (46)
If M = 0 M=0 M = 0 , all internal induced costs vanish. An arbitrary support s s s –t t t path, completed by zero-cost closed walks within its components, already has cost π t − π s = L P s , t \pi_t-\pi_s=\mathrm{LP}_{s,t} π t − π s = LP s , t . We henceforth assume M > 0 M>0 M > 0 .
Two complementary initial walks. The two constructions trade the cost of visiting each component against the mass it leaves uncovered.
Preserving both paths. Inside odd-indexed components, traverse the section of P 1 P_1 P 1 followed by that of P 2 P_2 P 2 ; reverse this order in even-indexed components. Join the sections by one nice path. Between consecutive components, use the intercomponent arc of the path traversed last. The order alternation makes the concatenation a support s s s –t t t walk, which we denote by Q k e e p Q_{\mathrm{keep}} Q keep . It retains all vertices of P 1 ∪ P 2 P_1\cup P_2 P 1 ∪ P 2 and has
c y ( Q k e e p ) ≤ τ M + D , ∑ i cov W i ( Q k e e p ) ≥ τ M . c_y(Q_{\mathrm{keep}})\le\tau M+D,\qquad\sum_i\operatorname{cov}_{W_i}(Q_{\mathrm{keep}})\ge\tau M. c y ( Q keep ) ≤ τ M + D , i ∑ cov W i ( Q keep ) ≥ τ M .
Applying (45) and (46) , the completion of Q k e e p Q_{\mathrm{keep}} Q keep has cost at most
U k e e p : = L P s , t + [ ρ − 1 − ( ρ − κ − 1 ) τ ] M + ( κ + 1 ) D . (47) U_{\mathrm{keep}}:=\mathrm{LP}_{s,t}+\left[\rho-1-(\rho-\kappa-1)\tau\right]M+(\kappa+1)D. \tag*{(47)} U keep := LP s , t + [ ρ − 1 − ( ρ − κ − 1 ) τ ] M + ( κ + 1 ) D . (47)
Replacing the path sections. Let s i , t i s_i,t_i s i , t i be the first and last vertices of P 1 P_1 P 1 in W i W_i W i . Choose u i , v i ∈ W i u_i,v_i\in W_i u i , v i ∈ W i with cov W i ( P u i v i W i ) = d i \operatorname{cov}_{W_i}(P^{W_i}_{u_iv_i})=d_i cov W i ( P u i v i W i ) = d i . Inside W i W_i W i , traverse the three nice paths
P s i u i W i , P u i v i W i , P v i t i W i . P^{W_i}_{s_iu_i},\qquad P^{W_i}_{u_iv_i},\qquad P^{W_i}_{v_it_i}. P s i u i W i , P u i v i W i , P v i t i W i .
Use the P 1 P_1 P 1 arc t i s i + 1 t_is_{i+1} t i s i + 1 between successive components. This defines another support s s s –t t t walk, denoted by Q max Q_{\max} Q m a x .
Write h i = h W i h_i=h_{W_i} h i = h W i . The nice-path identity gives the internal cost bound
3 d i − h i ( s i ) − 2 h i ( u i ) − 2 h i ( v i ) − h i ( t i ) . 3d_i-h_i(s_i)-2h_i(u_i)-2h_i(v_i)-h_i(t_i). 3 d i − h i ( s i ) − 2 h i ( u i ) − 2 h i ( v i ) − h i ( t i ) .
Every original positive laminar set is strictly inside one component, so the intercomponent arc has cost
c y ( t i s i + 1 ) = h i ( t i ) + h i + 1 ( s i + 1 ) . c_y(t_is_{i+1})=h_i(t_i)+h_{i+1}(s_{i+1}). c y ( t i s i + 1 ) = h i ( t i ) + h i + 1 ( s i + 1 ) .
These endpoint terms telescope, and h 1 ( s ) = h k ( t ) = 0 h_1(s)=h_k(t)=0 h 1 ( s ) = h k ( t ) = 0 because the laminar sets exclude the terminals. Hence
c y ( Q max ) ≤ 3 D − 2 ∑ i ( h i ( u i ) + h i ( v i ) ) ≤ 3 D . (48) c_y(Q_{\max})\le3D-2\sum_i\bigl(h_i(u_i)+h_i(v_i)\bigr)\le3D. \tag*{(48)} c y ( Q m a x ) ≤ 3 D − 2 i ∑ ( h i ( u i ) + h i ( v i ) ) ≤ 3 D . (48)
The path P u i v i W i P_{u_i v_i}^{W_i} P u i v i W i certifies coverage at least d i d_i d i in W i W_i W i . Its completion therefore has cost at most
U max : = L P s , t + ( ρ − 1 ) M − ( ρ − 2 κ − 3 ) D . (49) U_{\max} := \mathrm{LP}_{s,t}+(\rho-1)M-(\rho-2\kappa-3)D. \tag*{(49)} U m a x := LP s , t + ( ρ − 1 ) M − ( ρ − 2 κ − 3 ) D . (49)
Figure 2 shows the two constructions inside consecutive components.
Figure 2. The two initial walks (i i i odd). Dashed segments are added nice paths.
Combining the guarantees. Both bounds are known before augmentation. We choose the initial walk with the smaller certified bound and complete only that walk, obtaining F F F with c ( F ) ≤ min { U k e e p , U max } c(F) \le\min\{U_{\mathrm{keep}}, U_{\max}\} c ( F ) ≤ min { U keep , U m a x } . Since ρ ≥ 3 κ + 2 \rho\ge3\kappa+2 ρ ≥ 3 κ + 2 and κ ≥ 1 \kappa\ge1 κ ≥ 1 , the weights ( ρ − 2 κ − 3 ) / ( ρ − κ − 2 ) (\rho-2\kappa-3)/(\rho-\kappa-2) ( ρ − 2 κ − 3 ) / ( ρ − κ − 2 ) and ( κ + 1 ) / ( ρ − κ − 2 ) (\kappa+1)/(\rho-\kappa-2) ( κ + 1 ) / ( ρ − κ − 2 ) are nonnegative and sum to one. Applying them to (47) and (49) , respectively, cancels D D D and gives
c ( F ) ≤ L P s , t + ( ρ − 1 − ( ρ − 2 κ − 3 ) ( ρ − κ − 1 ) ρ − κ − 2 τ ) M . (50) c(F) \le\mathrm{LP}_{s,t}+\left(\rho-1-\frac{(\rho-2\kappa-3)(\rho-\kappa-1)}{\rho-\kappa-2}\tau\right)M. \tag*{(50)} c ( F ) ≤ LP s , t + ( ρ − 1 − ρ − κ − 2 ( ρ − 2 κ − 3 ) ( ρ − κ − 1 ) τ ) M . (50)
Also D ≤ M D \le M D ≤ M in (47) gives c ( F ) ≤ L P s , t + ( ρ + κ − ( ρ − κ − 1 ) τ ) M c(F) \le\mathrm{LP}_{s,t}+(\rho+\kappa-(\rho-\kappa-1)\tau)M c ( F ) ≤ LP s , t + ( ρ + κ − ( ρ − κ − 1 ) τ ) M . Both coefficients of M M M are nonnegative on 0 ≤ τ ≤ 1 0 \le\tau\le1 0 ≤ τ ≤ 1 : the first has minimum 2 κ + 1 + ( κ + 1 ) / ( ρ − κ − 2 ) > 0 2\kappa+1+(\kappa+1)/(\rho-\kappa-2)>0 2 κ + 1 + ( κ + 1 ) / ( ρ − κ − 2 ) > 0 , and the second has minimum 2 κ + 1 2\kappa+1 2 κ + 1 . Thus (43) proves the ratio bound
1 + 2 2 − τ min { ρ − 1 − ( ρ − 2 κ − 3 ) ( ρ − κ − 1 ) ρ − κ − 2 τ , ρ + κ − ( ρ − κ − 1 ) τ } . (51) 1+\frac{2}{2-\tau}\min\left\{\rho-1-\frac{(\rho-2\kappa-3)(\rho-\kappa-1)}{\rho-\kappa-2}\tau,\ \rho+\kappa-(\rho-\kappa-1)\tau\right\}. \tag*{(51)} 1 + 2 − τ 2 min { ρ − 1 − ρ − κ − 2 ( ρ − 2 κ − 3 ) ( ρ − κ − 1 ) τ , ρ + κ − ( ρ − κ − 1 ) τ } . (51)
The two ratio bounds in (51) meet at τ = ( ρ − κ − 2 ) / ( ρ − κ − 1 ) \tau=(\rho-\kappa-2)/(\rho-\kappa-1) τ = ( ρ − κ − 2 ) / ( ρ − κ − 1 ) , and the first is smaller before that point. Its derivative has sign opposite to ( ρ − κ ) ( ρ − 4 κ − 5 ) + 4 κ + 4 (\rho-\kappa)(\rho-4\kappa-5)+4\kappa+4 ( ρ − κ ) ( ρ − 4 κ − 5 ) + 4 κ + 4 . The second branch is nonincreasing because ρ ≥ 3 κ + 2 \rho\ge3\kappa+2 ρ ≥ 3 κ + 2 . Hence the maximum of their lower envelope occurs at τ = 0 \tau=0 τ = 0 or at the meeting point. The two values are ρ \rho ρ and 4 κ + 5 − ( 4 κ + 4 ) / ( ρ − κ ) 4\kappa+5-(4\kappa+4)/(\rho-\kappa) 4 κ + 5 − ( 4 κ + 4 ) / ( ρ − κ ) , proving (38) . Comparing them gives (39) .
The fixed nice-path families and their maximum-coverage choices are computable in polynomial time. The selected walk invokes the augmentation algorithm once per component, and the components are disjoint. Thus the algorithm is polynomial time whenever the augmentation algorithm is.
Obtaining an internal augmentation from the classical bounds. The regional conclusions of Traub and Vygen [9 Lemma 7.13 and Exercises 7.5–7.6] give an Eulerian addition F F F such that B ∪ F B \cup F B ∪ F is a tour on W ∪ V ( B ) W \cup V(B) W ∪ V ( B ) , together with a bound on c y ( F ) c_y(F) c y ( F ) . We justify the internal-support condition needed in Lemma 7.2 directly from these conclusions. Both cost bounds depend only on κ \kappa κ , η \eta η , the refinement parameter, and the proper-descendant quantities M W M_W M W , d W d_W d W , cov W ( B ) \operatorname{cov}_W(B) cov W ( B ) .
For proper W W W , let R ≥ 0 R \ge0 R ≥ 0 denote the applicable source bound and replace only the weight of W W W by
y W ′ = y W + R + 1. y'_W = y_W + R + 1. y W ′ = y W + R + 1.
Use the global nice paths fixed in [9 Section 7.3] before this change; their choice depends only on the graph and laminar family. The same primal circulation remains feasible and tight, so the modified instance is strongly laminar. All proper-descendant quantities and all internal arc costs in W W W remain unchanged. Apply the cited regional guarantee to this modified instance. Its output satisfies c y ′ ( F ) ≤ R c_{y'}(F) \le R c y ′ ( F ) ≤ R . Every arc crossing W W W has cost at least y W ′ > R y'_W > R y W ′ > R , so none can occur in F F F .
Set E W = F ∩ E [ W ] E_W = F \cap E[W] E W = F ∩ E [ W ] , retaining multiplicities. Since F F F has no boundary arc, E W E_W E W is Eulerian. For a vertex of W W W outside B B B , follow a path in B ∪ F B \cup F B ∪ F to its first vertex of B B B . Before that vertex the path uses only F F F , hence remains inside W W W and is retained in E W E_W E W . Thus B ∪ E W B \cup E_W B ∪ E W is connected and spans W W W , while c y ( E W ) = c y ′ ( E W ) ≤ c y ′ ( F ) ≤ R c_y(E_W) = c_{y'}(E_W) \le c_{y'}(F) \le R c y ( E W ) = c y ′ ( E W ) ≤ c y ′ ( F ) ≤ R . For W = V W = V W = V the source output is already internal. The weight change and restriction take polynomial time and preserve polynomial encoding length for rational input data.
Proof of Theorem 7.1. Traub and Vygen’s recursive bound [9 Lemma 7.13] , localized as above, satisfies (37) with ρ = 3 κ + η + 2 \rho= 3\kappa+ \eta+ 2 ρ = 3 κ + η + 2 . Substitute this value in Lemma 7.2 and (39) . The path factor agrees with the standard tour factor 3 κ + η + 2 3\kappa+ \eta+ 2 3 κ + η + 2 whenever η 2 + ( κ − 1 ) η − 2 ( κ + 1 ) 2 ≥ 0 \eta^2 + (\kappa- 1)\eta- 2(\kappa+ 1)^2 \ge0 η 2 + ( κ − 1 ) η − 2 ( κ + 1 ) 2 ≥ 0 .
The refined reduction and the new augmentation
For κ = 2 \kappa= 2 κ = 2 , the previous transfer agrees with the standard tour factor only for η ≥ 7 \eta\ge7 η ≥ 7 . Theorem 7.1 lowers this threshold to ( 73 − 1 ) / 2 (\sqrt{73} - 1)/2 ( 73 − 1 ) /2 . In particular, it applies to Vygen’s ( 2 , 4 + 2 2 + ε ) (2, 4 + 2\sqrt{2} + \varepsilon) ( 2 , 4 + 2 2 + ε ) -algorithm [11 Theorem 3] . The refined recursive reduction used for his tour bound gives a stronger consequence. We express its guarantee directly in terms of the tour factor ρ \rho ρ .
Lemma 7.3 (Refined recursive reduction [9 Exercises 7.5–7.6] ). Given a polynomial-time ( κ , η ) (\kappa,\eta) ( κ , η ) -algorithm for vertebrate pairs, where κ ≥ 1 \kappa\ge1 κ ≥ 1 and η ≥ 0 \eta\ge0 η ≥ 0 are fixed rational constants, let ρ > κ + 2 \rho> \kappa+ 2 ρ > κ + 2 be a fixed rational constant satisfying
ρ ≥ 3 κ + η + 2 − 2 ρ − κ . (52) \rho\ge3\kappa+ \eta+ 2 - \frac{2}{\rho- \kappa}. \tag*{(52)} ρ ≥ 3 κ + η + 2 − ρ − κ 2 . (52) For every strongly laminar instance, one can choose a nice-path family in polynomial time such that, for every region W ∈ L ∪ { V } W \in\mathcal{L} \cup\{V\} W ∈ L ∪ { V } and partial backbone B B B for W W W , a polynomial-time procedure returns an augmentation of B B B inside W W W with cost bounded by (37) . The family is fixed before W W W and B B B ; d W d_W d W is defined using this family.
Proof. Set δ = 2 / ( ρ − κ ) \delta= 2/(\rho- \kappa) δ = 2/ ( ρ − κ ) . Since ρ > κ + 2 \rho> \kappa+ 2 ρ > κ + 2 , we have 0 < δ < 1 0 < \delta< 1 0 < δ < 1 . Condition (52) gives
2 κ + η + 2 − δ ≤ ρ − κ , ( 2 κ + η + 1 − δ ) δ ≤ 2 − δ . 2\kappa+ \eta+ 2 - \delta\le\rho- \kappa, \qquad(2\kappa+ \eta+ 1 - \delta)\delta\le2 - \delta. 2 κ + η + 2 − δ ≤ ρ − κ , ( 2 κ + η + 1 − δ ) δ ≤ 2 − δ . where the second inequality follows by multiplying the first by δ \delta δ and using ( ρ − κ ) δ = 2 (\rho- \kappa)\delta= 2 ( ρ − κ ) δ = 2 . Hence Traub and Vygen’s refined regional guarantee [9 Exercises 7.5–7.6] applies and bounds the added cost by
κ ( M W + d W ) + ( 2 κ + η + 2 − δ ) ( M W − cov W ( B ) ) . \kappa(M_W + d_W) + (2\kappa+ \eta+ 2 - \delta)(M_W - \operatorname{cov}_W(B)). κ ( M W + d W ) + ( 2 κ + η + 2 − δ ) ( M W − cov W ( B )) .
Localize this output by the preceding weight modification. Since M W − cov W ( B ) ≥ 0 M_W-\operatorname{cov}_W(B)\ge0 M W − cov W ( B ) ≥ 0 and 2 κ + η + 2 − δ ≤ ρ − κ 2\kappa+\eta+2-\delta\le\rho-\kappa 2 κ + η + 2 − δ ≤ ρ − κ , its cost is at most
κ ( M W + d W ) + ( ρ − κ ) ( M W − cov W ( B ) ) = ρ M W + κ d W − ( ρ − κ ) cov W ( B ) . \kappa(M_W+d_W)+(\rho-\kappa)(M_W-\operatorname{cov}_W(B))=\rho M_W+\kappa d_W-(\rho-\kappa)\operatorname{cov}_W(B). κ ( M W + d W ) + ( ρ − κ ) ( M W − cov W ( B )) = ρ M W + κ d W − ( ρ − κ ) cov W ( B ) .
The cited procedure, weight modification, and restriction are polynomial time.
Corollary 7.4 (Path guarantee from Vygen’s vertebrate-pair algorithm). For every fixed ε > 0 \varepsilon>0 ε > 0 , Vygen’s vertebrate-pair algorithm, the refined recursive reduction, and Lemma 7.2 give a polynomial-time LP-relative asymmetric path TSP approximation with factor
7 + 2 + 25 + 10 2 + ε . 7+\sqrt{2}+\sqrt{25+10\sqrt{2}}+\varepsilon. 7 + 2 + 25 + 10 2 + ε . The path relaxation has integrality ratio at most 7 + 2 + 25 + 10 2 7+\sqrt{2}+\sqrt{25+10\sqrt{2}} 7 + 2 + 25 + 10 2 .
Proof. Vygen [11 Theorem 3] gives κ = 2 \kappa=2 κ = 2 and any η > 4 + 2 2 \eta>4+2\sqrt{2} η > 4 + 2 2 . At the limiting value of η \eta η , equality in (52) gives the larger root
ρ = 7 + 2 + 25 + 10 2 . \rho=7+\sqrt{2}+\sqrt{25+10\sqrt{2}}. ρ = 7 + 2 + 25 + 10 2 .
This is above ( 15 + 73 ) / 2 (15+\sqrt{73})/2 ( 15 + 73 ) /2 , so Lemma 7.2 gives the same factor for paths. Rational parameters sufficiently close to these limits satisfy the strict inequalities and give the stated factor for every fixed ε > 0 \varepsilon>0 ε > 0 . Taking the infimum over ε \varepsilon ε gives the integrality bound.
This corollary matches the refined tour bound discussed by Vygen [11 Section 4] , improving his stated path factor 15 [11 Section 5.2] . It follows from the established vertebrate-pair machinery and our transfer; the strengthened subtour cover of § 5 is used for the smaller common bound below.
Application to the new augmentation bound. The passage-dependent extension of our vertebrate-pair algorithm proves the stronger recursive bound of Theorem 6.4. This additional bound is needed to reach the smaller common factor. It satisfies (37) with κ = 2 \kappa=2 κ = 2 , by the comparison immediately after Theorem 6.4. Its circulation normalization preserves positive support and unit laminar boundary marginals, so it also preserves the component quantities and the initial paths used in the transfer. Since R ∗ > ( 15 + 73 ) / 2 R_* >(15+\sqrt{73})/2 R ∗ > ( 15 + 73 ) /2 , every rational ρ > R ∗ \rho>R_* ρ > R ∗ chosen in § 7.1 satisfies the condition for equal factors in Lemma 7.2. That lemma gives factor ρ \rho ρ for both tours and paths. This proves the polynomial-time ( R ∗ + ε ) (R_*+\varepsilon) ( R ∗ + ε ) -approximation for every fixed ε > 0 \varepsilon>0 ε > 0 in Theorem 1.1 . Taking the infimum over ε \varepsilon ε gives integrality ratio at most R ∗ R_* R ∗ for both relaxations.
References
Prescribed return paths and structured instances
We prove stronger guarantees under explicit conditions on the boundary of each laminar set. Throughout, the parameters of Svensson’s algorithm are fixed, their coefficient is α \alpha α , and the target tour ratio ρ ≥ max { 10 , α + 2 } \rho\ge\max\{10,\alpha+2\} ρ ≥ max { 10 , α + 2 } is rational with θ ≤ 1 − 2 / ( ρ − 2 ) \theta\le1 - 2/(\rho- 2) θ ≤ 1 − 2/ ( ρ − 2 ) . The child-specific prices below replace (24) and (26) , while the parameters of Svensson’s algorithm (23) are retained.
Forcing a prescribed return
Lemma 3.3 permits an arbitrary designated hitting set. This is useful because the path to be forced is known before it belongs to the integral output.
Lemma A.1 (A forced private visit). Suppose a private exterior vertex r r r in the construction of Theorem 5.1 has one incoming backward arc and one outgoing forward arc, both of fractional value m ∈ { 1 / 2 , 1 } m \in\{1/2,1\} m ∈ { 1/2 , 1 } . The cover can be required to visit r r r exactly 2 m 2m 2 m times without changing its other guarantees. These visits survive in the terminal cover of Theorem 6.1 .
Proof. Every witness assigns zero to the incoming arc and m m m to the outgoing arc. The upper copy of r r r therefore has throughput m m m , transferred to its lower copy by a downward switch. Witness normalization preserves these values. All cancellations and repairs take place in parts disjoint from the designated vertex set, which contains r r r ; they preserve its throughput even if another endpoint of an incident arc is redirected. Add an ordinary node gate at the upper copy of r r r , with both integral bounds equal to 2 m 2m 2 m . The doubled comparison circulation remains feasible. Integral minimum-cost circulation therefore retains the same cost guarantee and forces exactly 2 m 2m 2 m visits. Repairs preserve them, and Svensson’s algorithm retains every component meeting the designated set intact.
For a proper region W W W , let p v i n , p v o u t p_v^{\mathrm{in}},p_v^{\mathrm{out}} p v in , p v out be its unit entry and exit marginals. Write dist W \operatorname{dist}_W dist W for shortest-path distance in G [ W ] G[W] G [ W ] . For a prescribed walk P r e t P_{\mathrm{ret}} P ret from v ∗ v^* v ∗ to u ∗ u^* u ∗ in G [ W ] G[W] G [ W ] , define
disp W ( v ∗ , u ∗ ) = ∑ v p v o u t dist W ( v , v ∗ ) + ∑ u p u i n dist W ( u ∗ , u ) , \operatorname{disp}_W(v^*,u^*)=\sum_v p_v^{\mathrm{out}}\operatorname{dist}_W(v,v^*)+\sum_u p_u^{\mathrm{in}}\operatorname{dist}_W(u^*,u), disp W ( v ∗ , u ∗ ) = v ∑ p v out dist W ( v , v ∗ ) + u ∑ p u in dist W ( u ∗ , u ) ,
excess W ( P r e t ) = c ( P r e t ) + disp W ( v ∗ , u ∗ ) − c ← W . \operatorname{excess}_W(P_{\mathrm{ret}})=c(P_{\mathrm{ret}})+\operatorname{disp}_W(v^*,u^*)-\overleftarrow{c}_W. excess W ( P ret ) = c ( P ret ) + disp W ( v ∗ , u ∗ ) − c W .
The excess excess W ( P r e t ) \operatorname{excess}_W(P_{\mathrm{ret}}) excess W ( P ret ) need not be nonnegative: c ← W \overleftarrow{c}_W c W uses fixed nice paths, whereas the connecting paths above are shortest paths.
Lemma A.2 (Prescribed return in the augmentation step). For a proper region W W W , at an induction step of Theorem 6.4, let P r e t P_{\mathrm{ret}} P ret meet the inherited partial backbone B B B , or let B = ∅ B=\varnothing B = ∅ . For m ∈ { 1 / 2 , 1 } m \in\{1/2,1\} m ∈ { 1/2 , 1 } , the exterior construction can be modified to return an Eulerian multiset E W ⊆ E [ W ] E_W \subseteq E[W] E W ⊆ E [ W ] containing 2 m 2m 2 m copies of P r e t P_{\mathrm{ret}} P ret , such that B ∪ E W B \cup E_W B ∪ E W is connected and spans W W W , with bound
c ( E W ) ≤ ρ M W + 2 e W + 2 m excess W ( P r e t ) − ( ρ − 2 ) cov W ( B ∪ P r e t ) . (53) c(E_W)\le\rho M_W+2e_W+2m\operatorname{excess}_W(P_{\mathrm{ret}})-(\rho-2)\operatorname{cov}_W(B\cup P_{\mathrm{ret}}). \tag*{(53)} c ( E W ) ≤ ρ M W + 2 e W + 2 m excess W ( P ret ) − ( ρ − 2 ) cov W ( B ∪ P ret ) . (53)
This modification uses the same descendant augmentation guarantees and the same child inequalities as the original induction step. In particular, it is valid for the parameters of Theorem 6.4.
Proof. If M W = 0 M_W=0 M W = 0 , every internal arc has cost zero, and d W = c ← W = b W = e W = disp W ( v ∗ , u ∗ ) = excess W ( P r e t ) = 0 d_W=\overleftarrow{c}_W=b_W=e_W=\operatorname{disp}_W(v^*,u^*)=\operatorname{excess}_W(P_{\mathrm{ret}})=0 d W = c W = b W = e W = disp W ( v ∗ , u ∗ ) = excess W ( P ret ) = 0 . Close P r e t P_{\mathrm{ret}} P ret by any u ∗ – v ∗ u^*\text{--}v^* u ∗ – v ∗ support path and include 2 m 2m 2 m copies of this closed walk. Add a path from v ∗ v^* v ∗ to each vertex of W W W and back. Their union is a connected, spanning, zero-cost Eulerian multiset containing the required copies of P r e t P_{\mathrm{ret}} P ret , with every repetition retained. If B B B is nonempty it intersects this multiset at a vertex of P r e t P_{\mathrm{ret}} P ret . Henceforth suppose M W > 0 M_W>0 M W > 0 . Let Q Q Q be an optimal reverse coupling. Keep its paired private returns with values ( 1 − m ) Q v u (1-m)Q_{vu} ( 1 − m ) Q v u . Add the following private two-arc passages: v → o v → v ∗ v \to o_v \to v^* v → o v → v ∗ of value m p v o u t m p^{\mathrm{out}}_v m p v out , with prescribed shortest lift; v ∗ → h → u ∗ v^* \to h \to u^* v ∗ → h → u ∗ of value m m m , with lift P r e t P_{\mathrm{ret}} P ret ; and u ∗ → i u → u u^* \to i_u \to u u ∗ → i u → u of value m p u i n m p^{\mathrm{in}}_u m p u in , again with shortest lift. Their assigned costs are the respective lift costs. The resulting flow is balanced. Set
B 0 = ( V ( B ) ∩ W ) ∪ V ( P r e t ) ∪ { private vertices } , B_0 = (V(B) \cap W) \cup V(P_{\mathrm{ret}}) \cup\{\text{private vertices}\}, B 0 = ( V ( B ) ∩ W ) ∪ V ( P ret ) ∪ { private vertices } ,
and contract the maximal proper laminar descendants missed by B ∪ P r e t B \cup P_{\mathrm{ret}} B ∪ P ret . Every real set avoiding v ∗ , u ∗ v^*,u^* v ∗ , u ∗ receives exactly its original boundary inflow. Consequently all parts and contracted children satisfy the cut and unit-degree hypotheses of Theorem 5.1 . The fractional cost before child contraction is
M W − b W + ( 1 − m ) c W ← + m ( c ( P r e t ) + disp W ( v ∗ , u ∗ ) ) = M W + e W + m excess W ( P r e t ) . M_W-b_W+(1-m)c_W^{\leftarrow}+m\left(c(P_{\mathrm{ret}})+\operatorname{disp}_W(v^*,u^*)\right)=M_W+e_W+m\operatorname{excess}_W(P_{\mathrm{ret}}). M W − b W + ( 1 − m ) c W ← + m ( c ( P ret ) + disp W ( v ∗ , u ∗ ) ) = M W + e W + m excess W ( P ret ) .
Obtain a witness before splitting the exterior into private vertices. In the ordinary quotient with one exterior vertex g g g , the real designated set ( V ( B ) ∩ W ) ∪ V ( P r e t ) (V(B)\cap W)\cup V(P_{\mathrm{ret}}) ( V ( B ) ∩ W ) ∪ V ( P ret ) meets every remaining nonsingleton laminar member. Lemma 3.3 supplies a witness. At least two real quotient vertices remain: W W W has at least two vertices, and the nonempty set V ( P r e t ) V(P_{\mathrm{ret}}) V ( P ret ) is disjoint from every contracted proper child. Thus W W W remains a nonsingleton structural set, making every private rank smaller than every real rank. Identifying all the new private vertices with g g g changes this ordinary circulation only by adding the two cycles g → v ∗ → g g\to v^*\to g g → v ∗ → g and g → u ∗ → g g\to u^*\to g g → u ∗ → g , each of value m m m . Extend the witness by assigning their arcs out of g g g to the lower layer and their arcs into g g g to the upper layer. Any extra negative divergence occurs only at the designated vertices v ∗ , u ∗ v^*,u^* v ∗ , u ∗ . Now split g g g according to the displayed private passages. All private incoming arcs are backward and all private outgoing arcs are forward, as in Lemma 4.3 . Thus their upward switches remain zero. Every retained segment between private visits still encounters a real designated vertex.
Use Lemma A.1 at h h h . The lifted terminal cover then contains 2 m ≥ 1 2m\ge1 2 m ≥ 1 copies of P r e t P_{\mathrm{ret}} P ret . Hence B ∪ P r e t B\cup P_{\mathrm{ret}} B ∪ P ret is an actual connected subgraph after lifting, including when B B B is empty. It connects the real designated vertices used in the formal identification. Every remaining quotient intersection is actual or occurs at a contracted child, so the component–child incidence graph is connected. Lemma 6.5 therefore proves connectivity after the child completions. The descendant calls concern sets missed by B ∪ P r e t B\cup P_{\mathrm{ret}} B ∪ P ret . In the cost calculation, the fractional comparison value changes by m excess W ( P r e t ) m\operatorname{excess}_W(P_{\mathrm{ret}}) m excess W ( P ret ) and the initial coverage becomes cov W ( B ∪ P r e t ) \operatorname{cov}_W(B\cup P_{\mathrm{ret}}) cov W ( B ∪ P ret ) . Doubling the comparison cost proves (A.1).
A fixed-parameter criterion and a dispersion bound
For each proper L L L with d L > 0 d_L>0 d L > 0 , fix a family P L \mathcal{P}_L P L of explicit walks of polynomial total encoding length, containing all fixed nice returns between its exit and entry ports. Define the completion credit, in the original cost units, by
credit L = min { d L , max { ( 1 − 2 ρ − 2 ) d L , ( ρ − 3 ) ( c L ← + b L ) − ( c L → + b L ) ρ − 2 , max w ∈ L 2 h L ( w ) , max P r e t ∈ P L m ∈ { 1 / 2 , 1 } ( cov L ( P r e t ) − 2 m ρ − 2 excess L ( P r e t ) ) } } . (54) \operatorname{credit}_L=\min\left\{d_L,\max\left\{\left(1-\frac{2}{\rho-2}\right)d_L,\frac{(\rho-3)(c_L^{\leftarrow}+b_L)-(c_L^{\rightarrow}+b_L)}{\rho-2},\max_{w\in L}2h_L(w),\max_{\substack{P_{\mathrm{ret}}\in\mathcal{P}_L\\m\in\{1/2,1\}}}\left(\operatorname{cov}_L(P_{\mathrm{ret}})-\frac{2m}{\rho-2}\operatorname{excess}_L(P_{\mathrm{ret}})\right)\right\}\right\}. \tag*{(54)} credit L = min ⎩ ⎨ ⎧ d L , max ⎩ ⎨ ⎧ ( 1 − ρ − 2 2 ) d L , ρ − 2 ( ρ − 3 ) ( c L ← + b L ) − ( c L → + b L ) , w ∈ L max 2 h L ( w ) , P ret ∈ P L m ∈ { 1/2 , 1 } max ( cov L ( P ret ) − ρ − 2 2 m excess L ( P ret ) ) ⎭ ⎬ ⎫ ⎭ ⎬ ⎫ . (54)
The four terms correspond to the maximum-coverage pair, the transportation pair, a single-vertex partial backbone, and Lemma A.2 with empty inherited partial backbone. The credit measures a cost saving in the completion bound; it need not be the coverage of a particular backbone. Together with reuse of a current component of coverage cov L ( B L ) \operatorname{cov}_L(B_L) cov L ( B L ) , these choices give the bound
ρ M L + 2 e L − ( ρ − 2 ) max { cov L ( B L ) , credit L } . (55) \rho M_L + 2e_L - (\rho- 2)\max\{\operatorname{cov}_L(B_L),\operatorname{credit}_L\}. \tag*{(55)} ρ M L + 2 e L − ( ρ − 2 ) max { cov L ( B L ) , credit L } . (55)
For 0 ≤ λ ≤ 1 0 \le\lambda\le1 0 ≤ λ ≤ 1 , define the following upper bound on the remaining child charge:
charge L ( λ ) = 2 ( c L ⋆ + b L ) − 2 λ ( c L ⋆ + b L ) − ( ρ − α − 4 − 2 λ ) credit L + 1 2 [ α + 6 + 4 λ − ρ ] + ( d L − credit L ) . \operatorname{charge}_L(\lambda) = 2(c_L^{\star} + b_L) - 2\lambda(c_L^{\star} + b_L)
- (\rho- \alpha- 4 - 2\lambda)\operatorname{credit}_L
+ \frac{1}{2}[\alpha+ 6 + 4\lambda- \rho]_+(d_L - \operatorname{credit}_L). charge L ( λ ) = 2 ( c L ⋆ + b L ) − 2 λ ( c L ⋆ + b L ) − ( ρ − α − 4 − 2 λ ) credit L + 2 1 [ α + 6 + 4 λ − ρ ] + ( d L − credit L ) .
Theorem A.3 (Local sufficient criterion). If every proper laminar member with d L > 0 d_L > 0 d L > 0 satisfies
min 0 ≤ λ ≤ 1 charge L ( λ ) ≤ 0 , (56) \min_{0 \le\lambda\le1}\operatorname{charge}_L(\lambda) \le0, \tag*{(56)} 0 ≤ λ ≤ 1 min charge L ( λ ) ≤ 0 , (56) then a polynomial-time algorithm returns a tour of cost at most ρ \rho ρ LP. The augmentation bound of Theorem 6.4 and (A.1) both hold with this ρ \rho ρ .
Proof. We prove the two augmentation statements simultaneously by induction on the laminar family. The case of zero descendant mass uses zero-cost paths as in Theorem 6.4. For a positive child, choose a minimizing λ L \lambda_L λ L in (A.4) and set
price L = ( 1 + λ L ) credit L + 1 4 [ α + 6 + 4 λ L − ρ ] + ( d L − credit L ) . \operatorname{price}_L = (1 + \lambda_L)\operatorname{credit}_L + \frac{1}{4}[\alpha+ 6 + 4\lambda_L - \rho]_+(d_L - \operatorname{credit}_L). price L = ( 1 + λ L ) credit L + 4 1 [ α + 6 + 4 λ L − ρ ] + ( d L − credit L ) . In the comparison objective (28) , charge price L / 2 \operatorname{price}_L/2 price L /2 at each endpoint of a child passage and use λ L \lambda_L λ L as the coefficient of the forward endpoint prices. Since credit L ≥ ( 1 − 2 / ( ρ − 2 ) ) d L ≥ 3 d L / 4 \operatorname{credit}_L \ge(1 - 2/(\rho- 2))d_L \ge3d_L/4 credit L ≥ ( 1 − 2/ ( ρ − 2 )) d L ≥ 3 d L /4 , we have
price L ≥ ( 1 + λ L ) 3 d L 4 ≥ λ L d L . \operatorname{price}_L \ge(1 + \lambda_L)\frac{3d_L}{4} \ge\lambda_L d_L. price L ≥ ( 1 + λ L ) 4 3 d L ≥ λ L d L . Thus real comparison costs remain nonnegative. Also price L ≤ ( 1 + λ L ) d L \operatorname{price}_L \le(1 + \lambda_L)d_L price L ≤ ( 1 + λ L ) d L , because ρ ≥ α + 2 \rho\ge\alpha+ 2 ρ ≥ α + 2 .
For actual component coverage A ≥ 0 A \ge0 A ≥ 0 , after removing the common term ρ M L \rho M_L ρ M L and the boundary weight, the remaining child charge is at most
2 price L + α max { θ d L , min { A , d L } } + 4 [ ( 1 + λ L ) min { A , d L } − price L ] + − 2 λ L ( c L ⋆ + b L ) + 2 ( c L ⋆ + b L ) − ( ρ − 2 ) max { A , credit L } . \begin{aligned}
&2\operatorname{price}_L + \alpha\max\{\theta d_L,\min\{A,d_L\}\}\\
&\quad+ 4[(1+\lambda_L)\min\{A,d_L\}-\operatorname{price}_L]_+\\
&\quad- 2\lambda_L(c_L^{\star}+b_L) + 2(c_L^{\star}+b_L) - (\rho-2)\max\{A,\operatorname{credit}_L\}.
\end{aligned} 2 price L + α max { θ d L , min { A , d L }} + 4 [( 1 + λ L ) min { A , d L } − price L ] + − 2 λ L ( c L ⋆ + b L ) + 2 ( c L ⋆ + b L ) − ( ρ − 2 ) max { A , credit L } . Here we used (A.3) and
2 e L − 2 λ L c L ⋆ ≤ 2 ( c L ⋆ + b L ) − 2 λ L ( c L ⋆ + b L ) . 2e_L - 2\lambda_L c_L^{\star} \le2(c_L^{\star}+b_L) - 2\lambda_L(c_L^{\star}+b_L). 2 e L − 2 λ L c L ⋆ ≤ 2 ( c L ⋆ + b L ) − 2 λ L ( c L ⋆ + b L ) . The displayed expression is nondecreasing for 0 ≤ A ≤ credit L 0 \le A \le\operatorname{credit}_L 0 ≤ A ≤ credit L , convex for credit L ≤ A ≤ d L \operatorname{credit}_L \le A \le d_L credit L ≤ A ≤ d L , and decreasing for A ≥ d L A \ge d_L A ≥ d L . Its value at A = credit L A = \operatorname{credit}_L A = credit L is charge L ( λ L ) \operatorname{charge}_L(\lambda_L) charge L ( λ L ) , and its value at A = d L A = d_L A = d L is
charge L ( λ L ) − [ ρ − α − 6 − 4 λ L ] + ( d L − credit L ) . \operatorname{charge}_L(\lambda_L) - [\rho- \alpha- 6 - 4\lambda_L]_+(d_L - \operatorname{credit}_L). charge L ( λ L ) − [ ρ − α − 6 − 4 λ L ] + ( d L − credit L ) . It is therefore nonpositive. The boundary coefficient is 2 + α ≤ ρ 2 + \alpha\le\rho 2 + α ≤ ρ . These are precisely the child inequalities needed in both induction steps, proving their bounds. At the root, the maximum-coverage initial pair of Lemma 4.2 gives the tour bound.
All parameters and walk lists are rational and explicit. For fixed ρ \rho ρ , charge L ( λ ) \operatorname{charge}_L(\lambda) charge L ( λ ) is piecewise linear in λ \lambda λ ; it suffices to test 0 0 0 , 1 1 1 , and ( ρ − α − 6 ) / 4 (\rho- \alpha- 6)/4 ( ρ − α − 6 ) /4 when the latter lies in [ 0 , 1 ] [0,1] [ 0 , 1 ] . The algorithm compares the finitely many completion scores and executes only the selected descendant call. Its running time is polynomial as in the main construction.
Define the boundary dispersion by
disp ( L ) = ∑ v , v ′ p v o u t p v ′ o u t dist L ( v , v ′ ) + ∑ u , u ′ p u i n p u ′ i n dist L ( u , u ′ ) . \operatorname{disp}(L)=\sum_{v,v'}p^{\mathrm{out}}_v p^{\mathrm{out}}_{v'}\operatorname{dist}_L(v,v')+\sum_{u,u'}p^{\mathrm{in}}_u p^{\mathrm{in}}_{u'}\operatorname{dist}_L(u,u'). disp ( L ) = v , v ′ ∑ p v out p v ′ out dist L ( v , v ′ ) + u , u ′ ∑ p u in p u ′ in dist L ( u , u ′ ) .
Corollary A.4 (Concentrated boundary ports). Suppose disp ( L ) ≤ β d L \operatorname{disp}(L)\leq\beta d_L disp ( L ) ≤ β d L for every proper laminar member with d L > 0 d_L>0 d L > 0 , where 0 ≤ β ≤ 2 0\leq\beta\leq2 0 ≤ β ≤ 2 . The tour guarantee is ρ \rho ρ whenever
ρ ≥ α + 6 , ( ρ − α − 6 ) ( ρ − 4 ) ≥ 2 β . \rho\geq\alpha+6,\qquad(\rho-\alpha-6)(\rho-4)\geq2\beta. ρ ≥ α + 6 , ( ρ − α − 6 ) ( ρ − 4 ) ≥ 2 β . In the limit α ↓ α ∗ : = 3 + 2 2 \alpha\downarrow\alpha_*:=3+2\sqrt{2} α ↓ α ∗ := 3 + 2 2 , the guarantee is
α ∗ + 10 + ( α ∗ + 2 ) 2 + 8 β 2 . \frac{\alpha_*+10+\sqrt{(\alpha_*+2)^2+8\beta}}{2}. 2 α ∗ + 10 + ( α ∗ + 2 ) 2 + 8 β . Every fixed additive relaxation is attained in polynomial time. In particular, β = 0 \beta=0 β = 0 gives limiting factor α ∗ + 6 \alpha_*+6 α ∗ + 6 . One may take the minimum of this bound and R ∗ R_* R ∗ by also running the unrestricted algorithm.
Proof. Draw ( v ∗ , u ∗ ) (v^*,u^*) ( v ∗ , u ∗ ) from an optimal reverse coupling and choose P r e t = P v ∗ u ∗ L P_{\mathrm{ret}}=P^L_{v^*u^*} P ret = P v ∗ u ∗ L with m = 1 / 2 m=1/2 m = 1/2 . Lemma Lemma A.2 gives expected coverage c L ← + b L c_L^{\leftarrow}+b_L c L ← + b L ; the expected walk cost is c L ← c_L^{\leftarrow} c L ← and the expected dispersion is disp ( L ) \operatorname{disp}(L) disp ( L ) . Consequently (A.2) gives
credit L ≥ max { ( 1 − 2 ρ − 2 ) d L , c L ← + b L − disp ( L ) ρ − 2 } . \operatorname{credit}_L\geq\max\left\{\left(1-\frac{2}{\rho-2}\right)d_L,c_L^{\leftarrow}+b_L-\frac{\operatorname{disp}(L)}{\rho-2}\right\}. credit L ≥ max { ( 1 − ρ − 2 2 ) d L , c L ← + b L − ρ − 2 disp ( L ) } . Indeed, the maximum of the prescribed-return credits is at least their expectation, and clipping at d L d_L d L preserves this lower bound because c L ← + b L ≤ d L c_L^{\leftarrow}+b_L\leq d_L c L ← + b L ≤ d L . With λ = 0 \lambda=0 λ = 0 and ρ ≥ α + 6 \rho\geq\alpha+6 ρ ≥ α + 6 , the criterion reduces to ( ρ − α − 4 ) credit L ≥ 2 ( c L ← + b L ) (\rho-\alpha-4)\operatorname{credit}_L\geq2(c_L^{\leftarrow}+b_L) ( ρ − α − 4 ) credit L ≥ 2 ( c L ← + b L ) . As a function of c L ← + b L ∈ [ 0 , d L ] c_L^{\leftarrow}+b_L\in[0,d_L] c L ← + b L ∈ [ 0 , d L ] , the expression
( ρ − α − 4 ) max { ( 1 − 2 ρ − 2 ) d L , c L ← + b L − β d L ρ − 2 } − 2 ( c L ← + b L ) (\rho-\alpha-4)\max\left\{\left(1-\frac{2}{\rho-2}\right)d_L,c_L^{\leftarrow}+b_L-\frac{\beta d_L}{\rho-2}\right\}-2(c_L^{\leftarrow}+b_L) ( ρ − α − 4 ) max { ( 1 − ρ − 2 2 ) d L , c L ← + b L − ρ − 2 β d L } − 2 ( c L ← + b L ) is minimized where the two branches meet, at c L ← + b L = ( 1 − ( 2 − β ) / ( ρ − 2 ) ) d L c_L^{\leftarrow}+b_L=(1-(2-\beta)/(\rho-2))d_L c L ← + b L = ( 1 − ( 2 − β ) / ( ρ − 2 )) d L . Its value there is
d L ρ − 2 ( ( ρ − α − 6 ) ( ρ − 4 ) − 2 β ) ≥ 0. \frac{d_L}{\rho-2}\bigl((\rho-\alpha-6)(\rho-4)-2\beta\bigr)\geq0. ρ − 2 d L ( ( ρ − α − 6 ) ( ρ − 4 ) − 2 β ) ≥ 0. Thus the criterion holds. The limiting expression solves its quadratic equality.
Finally, all fixed nice path costs are at most d L d_L d L and distances on the diagonal are zero. Thus the useful purely marginal sufficient bound is
disp ( L ) ≤ ( 2 − ∑ v ( p v o u t ) 2 − ∑ u ( p u i n ) 2 ) d L ≤ 2 d L . \operatorname{disp}(L)\leq\left(2-\sum_v(p_v^{\mathrm{out}})^2-\sum_u(p_u^{\mathrm{in}})^2\right)d_L\leq2d_L. disp ( L ) ≤ ( 2 − v ∑ ( p v out ) 2 − u ∑ ( p u in ) 2 ) d L ≤ 2 d L .
Replacing a passage when the ports are unique
Lemma A.5 (Passage replacement). Suppose the descendant augmentation guarantees and child inequalities of Lemma A.2 hold for a child L L L . Let a lifted Eulerian parent multiset contain a charged passage P o l d P_{\mathrm{old}} P old from u u u to v v v inside L L L . For a walk P r e t P_{\mathrm{ret}} P ret from v v v to u u u , that child can be completed while replacing P o l d P_{\mathrm{old}} P old , with net cost increase at most
ρ M L + c ( P r e t ) − c ( P o l d ) + 2 disp L ( v , u ) − 2 b L − ( ρ − 2 ) cov L ( P r e t ) . \rho M_L+c(P_{\mathrm{ret}})-c(P_{\mathrm{old}})+2\operatorname{disp}_L(v,u)-2b_L-(\rho-2)\operatorname{cov}_L(P_{\mathrm{ret}}). ρ M L + c ( P ret ) − c ( P old ) + 2 disp L ( v , u ) − 2 b L − ( ρ − 2 ) cov L ( P ret ) . The resulting multiset is Eulerian and joins every current component meeting L L L .
Proof. Apply Lemma A.2 with empty backbone and m = 1 m=1 m = 1 . Its connected spanning output E L E_L E L contains two copies of P r e t P_{\mathrm{ret}} P ret and costs at most ρ M L + 2 c ( P r e t ) + 2 disp L ( v , u ) − 2 b L − ( ρ − 2 ) cov L ( P r e t ) \rho M_L+2c(P_{\mathrm{ret}})+2\operatorname{disp}_L(v,u)-2b_L-(\rho-2)\operatorname{cov}_L(P_{\mathrm{ret}}) ρ M L + 2 c ( P ret ) + 2 disp L ( v , u ) − 2 b L − ( ρ − 2 ) cov L ( P ret ) . Delete P o l d P_{\mathrm{old}} P old from the parent and one copy of P r e t P_{\mathrm{ret}} P ret from E L E_L E L . The two removed paths have opposite divergences, so their deletion preserves balance in the union. Deleting one of two copies of P r e t P_{\mathrm{ret}} P ret preserves the entire underlying arc support of E L E_L E L , and hence its connectivity and spanning property. It contains both endpoints of P o l d P_{\mathrm{old}} P old , reconnects any pieces separated by its deletion, and meets every other component incident with L L L . Subtracting the two removed costs proves the bound. □ \square □
Theorem A.6 (One entry and one exit). Suppose every proper laminar member L L L with d L > 0 d_L>0 d L > 0 has one entry vertex and one exit vertex in the positive support. A polynomial-time algorithm has tour guarantee ρ \rho ρ whenever
ρ ≥ α + 6 − 4 ρ − 1 . \rho\ge\alpha+6-\frac{4}{\rho-1}. ρ ≥ α + 6 − ρ − 1 4 . The limiting value is ρ 1 \rho_1 ρ 1 , the larger root of
ρ 1 2 − ( α ∗ + 7 ) ρ 1 + α ∗ + 10 = 0. \rho_1^2-(\alpha_*+7)\rho_1+\alpha_*+10=0. ρ 1 2 − ( α ∗ + 7 ) ρ 1 + α ∗ + 10 = 0. Proof. Neither unique port lies in a proper positive descendant J J J of L L L . Indeed, positive support and strong connectivity give x ( L ∖ J → J ) > 0 x(L\setminus J\to J)>0 x ( L ∖ J → J ) > 0 , so tightness of J J J implies that the exterior entry mass at J J J is strictly less than one; the exit statement is symmetric. Thus b L = 0 b_L=0 b L = 0 .
Prove the augmentation statements simultaneously as above, but at each such child use λ = 0 \lambda=0 λ = 0 and charge c L → / 2 c_L^{\rightarrow}/2 c L → /2 at each endpoint of a passage. Every charged passage is the same nice entry–exit path, of coverage c L → c_L^{\rightarrow} c L → , so its total price is exact and no lifting correction is needed. Apart from ρ M L \rho M_L ρ M L and the boundary weight, the total child charge is at most
2 c L → + α max { θ d L , c L → } + min { 2 c L ← − ( ρ − 2 ) max { c L → , ( 1 − 2 ρ − 2 ) d L } , − c L → − ( ρ − 3 ) c L ← } . 2c_L^{\rightarrow}+\alpha\max\{\theta d_L,c_L^{\rightarrow}\}+\min\left\{2c_L^{\leftarrow}-(\rho-2)\max\left\{c_L^{\rightarrow},\left(1-\frac{2}{\rho-2}\right)d_L\right\},-c_L^{\rightarrow}-(\rho-3)c_L^{\leftarrow}\right\}. 2 c L → + α max { θ d L , c L → } + min { 2 c L ← − ( ρ − 2 ) max { c L → , ( 1 − ρ − 2 2 ) d L } , − c L → − ( ρ − 3 ) c L ← } . The first completion choice uses reuse or the maximum-coverage pair. The second uses Lemma A.5 with the nice reverse path: its dispersion is zero and its coverage equals its cost c L ← c_L^{\leftarrow} c L ← . For c L → ≥ ( 1 − 2 / ( ρ − 2 ) ) d L c_L^{\rightarrow}\geq(1-2/(\rho-2))d_L c L → ≥ ( 1 − 2/ ( ρ − 2 )) d L , the two affine functions of c L ← c_L^{\leftarrow} c L ← cross at c L ← = ( ρ − 3 ) c L → / ( ρ − 1 ) c_L^{\leftarrow}=(\rho-3)c_L^{\rightarrow}/(\rho-1) c L ← = ( ρ − 3 ) c L → / ( ρ − 1 ) ; their lower envelope is at most its value there. The displayed charge is consequently at most
c L → ( α + 6 − ρ − 4 ρ − 1 ) ≤ 0. c_L^{\rightarrow}\left(\alpha+6-\rho-\frac{4}{\rho-1}\right)\leq0. c L → ( α + 6 − ρ − ρ − 1 4 ) ≤ 0. For c L → < ( 1 − 2 / ( ρ − 2 ) ) d L c_L^{\rightarrow}<(1-2/(\rho-2))d_L c L → < ( 1 − 2/ ( ρ − 2 )) d L , distribute the preceding parent charge into the two branches. For fixed c L ← c_L^{\leftarrow} c L ← and d L d_L d L , both branches are nondecreasing in c L → c_L^{\rightarrow} c L → . Their minimum is therefore bounded by its value at c L → = ( 1 − 2 / ( ρ − 2 ) ) d L c_L^{\rightarrow}=(1-2/(\rho-2))d_L c L → = ( 1 − 2/ ( ρ − 2 )) d L , already handled. Boundary weights are covered because ρ ≥ α + 2 \rho\geq\alpha+2 ρ ≥ α + 2 . The same induction and root initialization finish the proof; solving the limiting equality gives the stated quadratic. □ \square □
Remark A.7 (Path guarantees). The dispersion bound transfers to path TSP with factor ρ \rho ρ when every positive laminar member of the normalized path instance satisfies its condition, since ρ ≥ α ∗ + 6 > ( 15 + 73 ) / 2 \rho\geq\alpha_*+6>(15+\sqrt{73})/2 ρ ≥ α ∗ + 6 > ( 15 + 73 ) /2 . The temporary SCC regions require the condition only on their proper laminar descendants. The one-entry/one-exit factor ρ 1 \rho_1 ρ 1 lies below the threshold for a common tour and path factor at k = 2 k=2 k = 2 in Lemma 7.2.