betaFeedback

WorksComputer Science

Traveling Salesman Problem on Graphs with Proportional Independent Set

Abstract

We give a deterministic algorithm for minimum-cost Hamiltonian cycle in undirected graphs with arbitrary real edge costs and an independent set of size at least αnαn, for any fixed 3/7<α≤1/23/7<α\le1/2. It runs in O∗(γ(α)n)O^*(γ(α)^n) time for an explicit constant γ(α)<2γ(α)<2; for bipartite graphs, the bound is O∗((1+22)n/2)≈O∗(1.957n)O^*((1+2\sqrt2)^{n/2})\approx O^*(1.957^n). The algorithm is based on a restricted Held–Karp dynamic program. Its state enumeration uses structural properties of minimum-cost assignments arising from a regular triangulation of a product of simplices.

Introduction

In the traveling salesman problem (TSP), one is given an undirected graph with real edge costs and seeks a Hamiltonian cycle, or tour, of minimum total cost. The dynamic program (DP) of Bellman [1] and of Held and Karp [11] solves the problem in O(n22n)O(n^2 2^n) time by storing the cheapest path from a fixed start for each visited vertex set and endpoint. Cook [5] asks the question of whether the exponential base 22 can be reduced for arbitrary costs; see also the earlier survey of Woeginger [19] and Nederlof’s formulation [14 Open Question 1].

Several faster algorithms exploit restrictions on the input graph or its edge costs. Stoian [15] improves the general TSP bound to 2nn2/2Ω(log⁡n)2^n n^2 / 2^{\Omega(\sqrt{\log n})} by batching DP transitions into min-plus matrix products, without reducing the exponential base. For graphs of maximum degree three, Eppstein [9] gives an O∗(2n/3)O^*(2^{n/3}) algorithm that also handles edge costs. More generally, Björklund, Husfeldt, Kaski, and Koivisto [2] obtain fixed-base improvements for bounded-degree graphs by trimming DP states. Rank-based dynamic programming of Bodlaender, Cygan, Kratsch, and Nederlof [4] gives deterministic algorithms for weighted connectivity problems, including TSP, on graphs of bounded treewidth; the matching-connectivity framework of Cygan, Kratsch, and Nederlof [6] is also used in subsequent work on bipartite TSP. For Hamiltonicity without edge costs, Björklund [Bjö14] gives an O∗(1.657n)O^*(1.657^n) randomized algorithm, whose extension to integer costs incurs a factor depending on the cost range. More recently, Stoian [16] transfers such unweighted speedups to TSP when the set of edge costs has bounded doubling, a restriction not imposed here. For bipartite graphs with arbitrary real costs, Nederlof [14] gives a randomized O(1.9999n)O(1.9999^n) algorithm assuming nearly quadratic time matrix multiplication.

In this paper, we give a deterministic improvement for bipartite graphs and, more generally, for graphs with a sufficiently large independent set. Throughout, O∗(⋅)O^*(\cdot) suppresses factors polynomial in nn in the exact arithmetic model; for binary-encoded rational costs it also suppresses factors polynomial in the input bit length. For 3/7<α≤1/23/7 < \alpha\le1/2, define

γ(α)=min⁡z≥122α−1(2+z+z2)1−αz−α.(1)\gamma(\alpha) = \min_{z \ge1} 2^{2\alpha-1}(2+z+z^2)^{1-\alpha}z^{-\alpha}. \tag*{(1)}

Theorem 1.1. Fix α∈(3/7,1/2]\alpha\in(3/7,1/2]. Given an undirected nn-vertex graph with real edge costs and containing an independent set of size at least αn\alpha n, a deterministic algorithm finds a minimum-cost Hamiltonian cycle or reports that none exists in O∗(γ(α)n)O^*(\gamma(\alpha)^n) time. It accesses the input costs only through additions and comparisons, and γ(α)<2\gamma(\alpha) < 2.

Here α\alpha is fixed independently of nn. We describe the algorithm with a suitable independent set RR supplied; RR can be obtained within the same time bound if needed.

At α=1/2\alpha= 1/2, the minimum in (1) occurs at z=2z = \sqrt{2}, giving γ(1/2)=1+22=1.956636…\gamma(1/2) = \sqrt{1+2\sqrt{2}} = 1.956636\ldots. A bipartite graph with a tour has equally sized parts, so we obtain the following consequence.

Corollary 1.2. Minimum-cost Hamiltonian cycle in an undirected bipartite graph with arbitrary real costs can be solved deterministically in O∗((1+22)n/2)O^*((1+2\sqrt{2})^{n/2}) time.

Overview

Let L=V∖RL = V \setminus R, m=∣L∣m = |L|, and k=∣R∣k = |R|, and write w=(wlr)l∈L,r∈Rw = (w_{lr})_{l\in L,r\in R} for the edge costs between LL and RR. We first assume that all these edges are present and ww is generic; these assumptions are removed in § 5.

Assignments in optimal tours. An assignment A ⁣:R→LA\colon R \to L chooses one neighbor in LL for every r∈Rr \in R; its load dd is the number of vertices of RR assigned to each vertex l∈Ll \in L. (The terminology comes from standard usage in scheduling problems.) Denote the unique minimum-cost assignment of each load by AdA_d. The structural result (Theorem 2.8) is that every minimum-cost tour contains some AdA_d with dl≤2d_l \le2. Its proof uses auxiliary prices on LL, Brouwer’s fixed-point theorem, and a Hamiltonian-cycle parity argument.

Structure of minimum-cost assignments. The cross-edge cost matrix also defines a tropical hyperplane arrangement, or equivalently a regular triangulation of a product of simplices [7, 10]. We use two known structural results from these studies, phrased in assignment language (Lemma 2.9): assignments with “neighboring” loads are all subgraphs of a spanning tree FdF_d, and moving one unit of load to a vertex preserves its previously assigned neighbors [10, 20].

Enumerating compatible subsets. A subset U⊆L∪RU \subseteq L \cup R is compatible with an assignment AA if it is a union of the connected components of AA. Let C(w)\mathcal{C}(w) consist of the sets compatible with at least one AdA_d of load at most two. Our goal is to generate all sets in C(w)\mathcal{C}(w) efficiently.

For each load dd, we obtain the tree FdF_d using assignments with neighboring loads. Contracting edges in AdA_d and deleting selected edges gives a forest TdT_d on LL. Each proper two-coloring of TdT_d gives a compatible subset. The aforementioned structure guarantees that all subsets of C(w)\mathcal{C}(w) can be generated this way (Proposition 3.2).

With a standard generating function calculation (Proposition 3.4), the number of compatible subsets is

Nm,k=2k−m∑j=k2m[zj](2+z+z2)m≤min⁡z≥12k−mz−k(2+z+z2)m≤γ(α)n,N_{m,k}=2^{k-m}\sum_{j=k}^{2m}[z^j](2+z+z^2)^m \le\min_{z\ge1}2^{k-m}z^{-k}(2+z+z^2)^m \le\gamma(\alpha)^n,

where [zj]P(z)[z^j]P(z) is the coefficient of zjz^j in polynomial P(z)P(z). The corresponding exponential bound has base γ(α)<2\gamma(\alpha) < 2 for α>3/7\alpha> 3/7.

The restricted dynamic program. The assignment components in a tour containing AdA_d are paths on at most three vertices, traversed as consecutive blocks. Starting at s∈Rs \in R along its assignment edge, every completed-block prefix belongs to C(w)\mathcal{C}(w). Therefore a Bellman–Held–Karp dynamic program using only these vertex subsets, with transitions appending at most three vertices, retains an optimal tour (§ 4).

The combinatorics of assignments

Throughout Sections 2–4, G=(L∪R,E)G = (L \cup R, E) is a simple undirected graph, RR is independent, ∣L∣=m|L| = m, ∣R∣=k|R| = k, and 1≤k≤m1 \le k \le m. We also assume that all edges of L×RL \times R (i.e. cross-edges) are present, while the edges inside LL are not restricted. The symbol ww denotes the edge costs and, when used as a matrix, their restriction to L×RL \times R. We write lrlr for an edge with l∈Ll \in L, r∈Rr \in R, and 1∈RL\mathbf{1} \in\mathbb{R}^{L} for the all-ones vector.

Assignments, prices, and tight graphs

Definition 2.1. An assignment is a map A:R→LA: R \to L, identified with a collection of kk cross-edges in GG. The load of this assignment is a nonnegative integer vector dA∈NLd^A \in\mathbb{N}^{L} where dlA=∣A−1(l)∣d^A_l = |A^{-1}(l)|, and the cost w(A)w(A) is the sum of the costs of all edges of AA. A load vector is called balanced if dl∈{0,1,2}d_l \in\{0, 1, 2\} for all l∈Ll \in L.

In the bipartite case where m=km = k, an assignment is similar to but more flexible than the perfect matchings considered in [14].

Definition 2.2. For a simple cycle l1r1l2r2⋯ltrtl1l_1r_1l_2r_2 \cdots l_tr_tl_1 in KL,RK_{L,R}, its alternating sum is the sum of the costs of alternate edges minus the sum for the remaining edges. Equivalently, it is ∑i=1t(wliri−wli+1ri)\sum_{i=1}^{t}(w_{l_ir_i} - w_{l_{i+1}r_i}), where lt+1=l1l_{t+1} = l_1. The cost matrix ww is generic if every such sum is nonzero.

Definition 2.3. For a price vector a∈RLa \in\mathbb{R}^{L}, define the adjusted cost of a cross-edge by w~lr(a)=wlr+al\widetilde{w}_{lr}(a) = w_{lr} + a_l. An edge lrlr is tight (for aa) if it is one of the edges incident to rr with the minimum adjusted cost. The tight graph F(a)F(a) is the collection of tight edges over all r∈Rr \in R. An assignment is also called tight if all of its edges are tight.

Every r∈Rr \in R has at least one neighbor in LL, and adding a common constant to the prices does not change F(a)F(a). Moreover, the prices change the adjusted cost of all assignments with the same load equally, giving us the following properties:

Lemma 2.4. A tight assignment AA has minimum cost among all assignments of load dAd^A. Equality for another assignment holds only when it is also tight.

Lemma 2.5. If ww is generic, every tight graph F(a)F(a) is a forest.

Proof. On a cycle of tight edges, the two incident edges at each r∈Rr \in R have equal adjusted cost. Summing these equalities around the cycle cancels the prices and gives a zero alternating sum, contrary to genericity. □\square

Lemma 2.6. For generic ww and any nonnegative integer load vector dd with ∑ldl=k\sum_l d_l = k, the minimum-cost assignment of that load is unique; call the canonical assignment AdA_d.

Proof. Reassigning along a cycle alternating between assigned edges and unassigned edges preserves the load, so starting from a minimum-cost assignment its cost increase is nonnegative, and hence positive by genericity. The difference of two assignments of the same load decomposes into alternating cycles; therefore the optimum is unique.

Canonical assignment in optimal tours

We now show that an optimal Hamiltonian cycle contains a tight assignment. We use the following consequence of Thomason’s “lollipop” theorem for Hamiltonian paths [18].

Lemma 2.7. Let KK be a simple bipartite graph with equally sized parts XX and YY. If every vertex of XX has degree three, every edge of KK lies on an even number of Hamiltonian cycles. In particular, a Hamiltonian KK has a second Hamiltonian cycle.

Proof. Fix y0x0∈E(K)y_0x_0 \in E(K) with x0∈Xx_0 \in X. By [18 Theorem 1.1], the number of Hamiltonian paths beginning with y0,x0y_0,x_0 and ending at a neighbor of y0y_0 is even: each possible endpoint lies in XX and has degree three. Closing the paths by their last edge to y0y_0 gives the claimed parity.

Theorem 2.8. Let HH be a minimum-cost Hamiltonian cycle of GG. There exist prices a∈RLa \in\mathbb{R}^{L} such that every r∈Rr \in R is incident to an edge of H∩F(a)H \cap F(a). Consequently, HH contains an assignment of minimum cost for its load. For generic ww, this assignment is a canonical assignment of a balanced load vector.

Proof. For each r∈Rr \in R and j∈Lj \in L, let

Mr(a)=min⁡i∈NH(r)w^ir(a),Φj(a)=max⁡r∈R(Mr(a)−wjr).M_r(a) = \min_{i \in N_H(r)} \widehat{w}_{ir}(a), \qquad\Phi_j(a) = \max_{r \in R}\left(M_r(a) - w_{jr}\right).

The condition Φ(a)≤a\Phi(a) \le a is equivalent to w^jr(a)≥Mr(a)\widehat{w}_{jr}(a) \ge M_r(a) for all j,rj,r, and thus to every r∈Rr \in R having a tight edge in HH.

Fix s∈Ls \in L and put B=max⁡i,j∈L, r∈R∣wir−wjr∣B = \max_{i,j \in L,\ r \in R} \lvert w_{ir} - w_{jr}\rvert. Taking maxima in the definition of Φ\Phi gives

∣Φj(a)−Φs(a)∣≤max⁡r∈R∣wsr−wjr∣≤B.\lvert\Phi_j(a) - \Phi_s(a)\rvert\le\max_{r \in R}\lvert w_{sr} - w_{jr}\rvert\le B.

Thus the continuous map Ψ(a)=Φ(a)−Φs(a)1\Psi(a) = \Phi(a) - \Phi_s(a)\mathbf{1} sends the compact convex box {a:as=0, ∣aj∣≤B for all j}\{a : a_s = 0,\ \lvert a_j\rvert\le B \text{ for all } j\} into itself. Brouwer’s theorem gives a fixed point aa, so Φ(a)=a+λ1\Phi(a) = a + \lambda\mathbf{1} with λ=Φs(a)\lambda= \Phi_s(a). It remains to show that λ≤0\lambda\le0.

Suppose λ>0\lambda> 0. For each jj, choose r(j)r(j) attaining the maximum defining Φj(a)\Phi_j(a). Then

w^jr(j)(a)=Mr(j)(a)−λ<Mr(j)(a),\widehat{w}_{j r(j)}(a) = M_{r(j)}(a) - \lambda< M_{r(j)}(a),

so jr(j)∉Hj r(j) \notin H and is cheaper in adjusted cost than either tour edge incident to r(j)r(j). Subdivide the m−km-k edges of HH within LL (i.e. adding a vertex at the middle of these edges, and putting the m−km-k added vertices in RR), and add edge jr(j)j r(j) for every j∈Lj \in L. The resulting bipartite graph has two parts of size mm, with degree three at every vertex of LL, so Lemma 2.7 gives another Hamiltonian cycle, and suppressing the degree-two subdivision vertices yields a different tour H′H' retaining all LL-LL edges of HH.

At each r∈Rr \in R, the same number of incident edges are added and removed when we go from HH to H′H'. Every added edge has adjusted cost at most Mr(a)−λM_r(a)-\lambda, while every removed edge has adjusted cost at least Mr(a)M_r(a). Since H′H' retains exactly the LL-LL edges of HH, each vertex of LL has the same cross-edge degree in both tours. Their price contributions therefore cancel, so H′H' has strictly lower total cost than HH, contradicting optimality. Thus λ≤0\lambda\le0 and Φ(a)≤a\Phi(a) \le a, as desired.

Neighboring assignments and tight trees

For the remainder of this section and Sections 3–4, we assume that the cost matrix ww is generic.

Fix an order L={1,…,m}L = \{1,\ldots,m\}. For each (not necessarily balanced) load vector dd, let p=p(d)p=p(d) be the smallest index with positive load, and let Lp={p,…,m}L_p=\{p,\ldots,m\}. All assignments of load dd are supported on LpL_p. For any load vector dd, one can compute AdA_d by minimum-cost perfect matching between RR and dld_l copies of each vertex l∈Ll\in L in polynomial time [12, 13]. Let w(d)=w(Ad)w(d)=w(A_d) with mild abuse of notation.

We use the following known properties of minimum-cost assignments. Let ej∈ZL\mathbf{e}_j\in\mathbb{Z}^L denote the unit vector at j∈Lj\in L.

Lemma 2.9. Let S⊆LS\subseteq L and let u∈Z≥0Lu\in\mathbb{Z}_{\geq0}^L be supported on SS, with ∑lul=k−1\sum_{l}u_l=k-1. Then TS(u):=⋃j∈SAu+ejT_S(u):=\bigcup_{j\in S}A_{u+\mathbf{e}_j} is a spanning tree on S∪RS\cup R and deg⁡TS(u)(l)=ul+1\deg_{T_S(u)}(l)=u_l+1 for each l∈Sl\in S. Given TS(u)T_S(u), each Au+ejA_{u+\mathbf{e}_j} can be obtained by assigning each r∈Rr\in R to the first vertex in SS on the unique path from rr to jj in TS(u)T_S(u).

For every i,j∈Si,j\in S with i≠ji\ne j, if r∈Rr\in R is assigned to ii in Au+ejA_{u+\mathbf{e}_j}, then it is also assigned to ii in Au+eiA_{u+\mathbf{e}_i}. (Also, there is exactly one additional vertex assigned to ii in Au+eiA_{u+\mathbf{e}_i} compared to Au+ejA_{u+\mathbf{e}_j}.)

This lemma follows by applying [10 Proposition 3.4] on (regular) triangulations of products of two simplices induced by the restricted cost matrix on S×RS\times R; the union formulation is also directly given in [20 Proposition 3.8]. See the next subsection for some further discussion on this connection.

We now apply this lemma with S=LpS=L_p. The following construction gives a normalized price vector a(d)a^{(d)} and a corresponding tight tree FdF_d for each load dd.

Lemma 2.10. Let u=d−epu=d-\mathbf{e}_p and d(j)=u+ejd^{(j)}=u+\mathbf{e}_j for each j∈Lpj\in L_p, and define aj(d)=w(d)−w(d(j))a_j^{(d)}=w(d)-w(d^{(j)}). These are the coordinatewise least prices with ap=0a_p=0 making AdA_d tight on Lp×RL_p\times R. The resulting tight graph is

Fd:=TLp(u)=⋃j∈LpAd(j).(2)F_d:=T_{L_p}(u)=\bigcup_{j\in L_p} A_{d^{(j)}}. \tag*{(2)}

which is a spanning tree on the vertex set Lp∪RL_p\cup R. When FdF_d is rooted at pp, every r∈Rr\in R has parent Ad(r)A_d(r), and each l∈Lpl\in L_p has exactly dld_l children; each l>pl>p has a parent in RR.

For fixed pp, different load vectors dd yield different a(d)a^{(d)}. The prices a(d)a^{(d)} and tree FdF_d are computable from dd in polynomial time.

Proof. If Ad(r)=iA_d(r)=i, Lemma 2.9 gives Ad(i)(r)=iA_{d^{(i)}}(r)=i. Reassigning rr from ii to jj in Ad(i)A_{d^{(i)}} yields an assignment of load d(j)d^{(j)} whose cost is at least that of Ad(j)A_{d^{(j)}}. Consequently, for every j∈Lpj\in L_p we have

w(d(j))≤w(d(i))+wjr−wirandw^ir(a(d))≤w^jr(a(d)).w(d^{(j)})\leq w(d^{(i)})+w_{jr}-w_{ir} \quad\text{and}\quad \widehat{w}_{ir}(a^{(d)})\leq\widehat{w}_{jr}(a^{(d)}).

Thus Ad(r)=iA_d(r)=i is a tight edge for every rr, and ap(d)=0a_p^{(d)}=0 by definition (since d(p)=dd^{(p)}=d).

If a different price vector a′a' with ap′=0a'_p=0 also makes AdA_d tight, since a tight assignment minimizes total adjusted cost, and Ad(j)A_{d^{(j)}} has load d−ep+ejd-\mathbf{e}_p+\mathbf{e}_j, we have

w(d)+d⋅a′≤w(d(j))+(d−ep+ej)⋅a′.w(d)+d\cdot a'\leq w(d^{(j)})+(d-\mathbf{e}_p+\mathbf{e}_j)\cdot a'.

Thus aj′≥w(d)−w(d(j))=aj(d)a'_j\geq w(d)-w(d^{(j)})=a_j^{(d)} for every jj, showing that a(d)a^{(d)} is coordinatewise minimal.

At a(d)a^{(d)}, each Ad(j)A_{d^{(j)}} has the same adjusted cost as the tight assignment AdA_d, so it is tight as well. Their union is the spanning tree FdF_d by Lemma 2.9. By Lemma 2.5, the tight graph is a forest, so

it equals this tree. Its degree at pp is up+1=dpu_p+1=d_p and at each l>pl>p is ul+1=dl+1u_l+1=d_l+1, giving the desired structure when rooted at pp.

Given some price a(d)a^{(d)}, we can compute the tight graph directly, and its vertex degrees allow us to recover dd. Given dd, one can compute each Ad(j)A_{d(j)} using the perfect matching algorithm, and hence also the tight graph FdF_d using the union definition in (2.1) in polynomial time.

Figure 1. An example of a canonical assignment AdA_d with load d=(0,1,0,2,1)d=(0,1,0,2,1), its three neighboring canonical assignments, and a tight graph FdF_d that is the union of these four assignments.

Geometric interpretation

This subsection is intended to provide some geometric background for the assignment construction in this section, and can be skipped safely.

For each r∈Rr\in R, put hr(a)=min⁡l∈L(wlr+al)h_r(a)=\min_{l\in L}(w_{lr}+a_l). The locus of a∈RLa\in\mathbb{R}^L for which this minimum is attained at least twice is called a tropical hyperplane. Collecting all tropical hyperplanes for each rr gives an arrangement of tropical hyperplanes. For each point aa, the minimizing indices ll for each rr form the type of aa, representing the relative position of aa with respect to the tropical hyperplane arrangement. The tight graph F(a)F(a) encodes the same information as this type using edges of L×RL\times R. In particular,

∑r∈Rhr(a)=min⁡d∈Z≥0L∑l∈Ldl=k(w(d)+∑l∈Ldlal)(3)\sum_{r\in R} h_r(a)=\min_{\substack{d\in\mathbb{Z}_{\geq0}^{L}\\ \sum_{l\in L}d_l=k}}\left(w(d)+\sum_{l\in L}d_l a_l\right) \tag*{(3)}

where w(d)w(d) is the minimum assignment cost with load dd. The right-hand side is the min-plus tropical polynomial whose coefficients are the assignment values w(d)w(d). We refer the reader to [7] for further connections to tropical geometry.

The same matrix ww lifts each vertex (el,er)(e_l,e_r) of a product of two simplices Δm−1×Δk−1\Delta_{m-1}\times\Delta_{k-1} to height wlrw_{lr}. Tight graphs encode the lower faces of the resulting polytope, corresponding to a regular subdivision of Δm−1×Δk−1\Delta_{m-1}\times\Delta_{k-1}, and genericity of ww ensures that this is a triangulation.

The simplices of this triangulation correspond to bipartite forests, and its maximal simplices to spanning trees [10]. The combinatorial structure of these triangulations has been studied extensively, and many properties also extend to non-regular triangulations. In this general context, the assignments AdA_d are called semi-matchings or topes, and TS(u)T_S(u) is called a tope-linkage covector, which is always a tree due to the linkage axiom/property. We refer the reader to [20] for a more comprehensive overview.

Enumeration of compatible subsets

Definition 3.1. A vertex set U⊆L∪RU \subseteq L \cup R is compatible with an assignment AA if r∈Ur \in U exactly when A(r)∈UA(r) \in U, for every r∈Rr \in R. Equivalently, UU is a union of components of the assignment graph, including isolated vertices of LL.

For generic ww, let C(w)C(w) be the family of sets compatible with some canonical assignment AdA_d with dd balanced. Complementary sets are treated as distinct members of C(w)C(w).

For a fixed assignment AA, a compatible set can be identified with a {0,1}\{0,1\}-coloring of L∪RL \cup R where every r∈Rr \in R is given the same color as A(r)∈LA(r) \in L.

The key insight to improving the classic Bellman–Held–Karp algorithm is that it suffices to perform dynamic programming over sets in C(w)C(w), since an optimal Hamiltonian cycle contains some canonical assignment, which decomposes into a collection of connected components, any sub-collection of which belongs to C(w)C(w). It therefore suffices to generate C(w)C(w) efficiently.

Generating all compatible subsets

Listing the compatible subsets separately for each assignment would repeat many of them. We describe how to avoid these repetitions below.

Fix a balanced load dd and use the notation p=p(d)p = p(d), FdF_d, and AdA_d from Subsection 2.3. For each j>pj > p with dj≤1d_j \leq1, let rj∈Rr_j \in R be the unique vertex newly assigned to jj by Ad−ep+ejA_{d-e_p+e_j} relative to AdA_d. By Lemma 2.9, jrjjr_j is the unique edge in FdF_d incident to jj that is not in AdA_d, hence is the parent edge of jj in FdF_d. Define the forest on LL

Td={{j,Ad(rj)}:j>p, dj≤1}.(4)T_d = \{\{j,A_d(r_j)\}: j > p,\ d_j \leq1\}. \tag*{(4)}

Equivalently, TdT_d is a selectively pruned contraction of the tree FdF_d: contract all assignment edges in FdF_d, delete the parent edges at vertices j>pj > p with dj=2d_j = 2, and adjoin 1,…,p−11,\ldots,p-1 as isolated vertices. Note that each component contains exactly one vertex j≤pj \leq p or with dj=2d_j = 2.

Consider all proper {0,1}\{0,1\}-colorings of TdT_d (where adjacent vertices are given opposite colors). For each coloring, if S⊆LS \subseteq L consists of the vertices colored 1, output U=S∪Ad−1(S)U = S \cup A_d^{-1}(S). Observe that UU is clearly compatible with AdA_d.

Intuitively speaking, each edge of TdT_d corresponds to a possible way to reassign a vertex r∈Rr \in R to get another canonical assignment with a neighboring balanced load. (The deleted edges after contracting TdT_d by AdA_d correspond to reassignments that cause a load to be un-balanced.) The proper coloring thus ensures that no valid single-vertex reassignment is compatible with the same coloring. We now use the same intuition to show that every coloring in C(w)C(w) is still covered despite this restriction.

Proposition 3.2. *Over all balanced load vectors dd, the process above generates every set in C(w)C(w) at least once. Its number of outputs, counted with multiplicity, is Nm,k:=∑d2b(d)N_{m,k} := \sum_d 2^{b(d)}, where b(d):=b(d) :=

Constructing the forest $T_d$ from the example tight graph $F_d$

Figure 2. Constructing the forest TdT_d from the example tight graph FdF_d from Figure 1. The contracted edges of AdA_d are bolded in FdF_d.

p(d)+∣{l>p(d):dl=2}∣p(d)+|\{l>p(d):d_l=2\}| is the number of connected components of TdT_d. The list can be generated deterministically in O∗(Nm,k)O^*(N_{m,k}) time.

Proof. Fix U∈C(w)U\in C(w) and choose a compatible balanced load dd maximizing p=p(d)p=p(d) and then minimizing ∑j∈Lpaj(d)\sum_{j\in L_p}a_j^{(d)}. Assume for the sake of contradiction that an edge lAd(rl)lA_d(r_l) of TdT_d has both endpoints on the same side of UU (where ll is further away from the root in FdF_d), then clearly rlr_l is also on the same side as well. Now reassign rlr_l from Ad(rl)A_d(r_l) to ll. The old and new assignment edges both lie in FdF_d, so the new assignment A′A' is compatible with UU and minimum-cost for its load d′≠dd'\ne d: indeed, every assignment of load d′d' is supported on LpL_p. Thus A′=Ad′A'=A_{d'} by Lemmas 2.4 and 2.6, and its loads remain at most two. As p(d′)≥pp(d')\ge p, the choice of dd forces p(d′)=pp(d')=p. Since Ad′A_{d'} is tight for a(d)a^{(d)}, Lemma 2.10 gives a(d′)≤a(d)a^{(d')}\le a^{(d)} coordinatewise, with equality only if d′=dd'=d. Hence the sum of prices strictly decreases, which is a contradiction. Therefore, UU induces a proper coloring on TdT_d, so the process generates UU.

Now list the balanced loads and store their canonical assignments, with polynomial work per load. These give each forest TdT_d in polynomial time and its 2b(d)2^{b(d)} colorings with polynomial work per output. Since every load contributes at least one output, total time is Nm,knO(1)N_{m,k}n^{O(1)}.

Non-repetition

In fact, with some more analysis we can show that every set is generated exactly once using the process in the previous section, making it unnecessary to deduplicate the outputs. This subsection does not affect the algorithm or the runtime analysis, and can be skipped safely.

Proposition 3.3. The same process as Proposition 3.2 generates every set in C(w)C(w) without repetition. Therefore, ∣C(w)∣=Nm,k|C(w)|=N_{m,k}.

Proof. Suppose UU is generated by distinct balanced loads d,d′d,d', with p=p(d)≤p′=p(d′)p=p(d)\le p'=p(d'). If p=p′p=p', the prices are distinct by Lemma 2.10; interchange the loads if necessary so that max⁡j(aj(d)−aj(d′))>0\max_j(a_j^{(d)}-a_j^{(d')})>0. If p<p′p<p', subtract a sufficiently large common constant from a(d′)a^{(d')}; this preserves its tight graph and the argument below.

Let δ=max⁡j∈Lp′(aj(d)−aj(d′))>0\delta=\max_{j\in L_{p'}}(a_j^{(d)}-a_j^{(d')})>0, and choose a maximizing vertex l∈Lp′l\in L_{p'} closest to p′p' in Fd′F_{d'}. Note that l>pl>p; the case l=p=p′l=p=p' is impossible since al(d)=al(d′)=0a_l^{(d)}=a_l^{(d')}=0 by definition of normalized prices. Every edge lrlr of FdF_d incident to ll is also tight for a(d′)a^{(d')}: for i∈Lp′i \in L_{p'},

al(d′)+wlr=al(d)+wlr−δ≤ai(d)+wir−δ≤ai(d′)+wir.a_l^{(d')} + w_{lr} = a_l^{(d)} + w_{lr} - \delta\le a_i^{(d)} + w_{ir} - \delta\le a_i^{(d')} + w_{ir}.

If dl=2d_l = 2, then ll has three tight incident edges in FdF_d and hence also in Fd′F_{d'}, so l≠p′l \ne p' (since p′p' only has degree 2) and there are no other incident edges in Fd′F_{d'} (since the maximum degree is 3), and therefore its parent edge in FdF_d is common to both trees. Otherwise, its parent edge in FdF_d crosses UU and cannot belong to the compatible assignment Ad′A_{d'}. This edge must therefore also be the parent edge in Fd′F_{d'}, again common to both trees and with l≠p′l \ne p'.

In both cases, let lrlr be this common parent edge and j=Ad′(r)j = A_{d'}(r) (i.e. the parent of rr in Fd′F_{d'}). Since lrlr is tight for a(d)a^{(d)}, while lrlr and jrjr are tight for a(d′)a^{(d')}, we have

wlr+al(d)≤wjr+aj(d),wlr+al(d′)=wjr+aj(d′).w_{lr} + a_l^{(d)} \le w_{jr} + a_j^{(d)}, \qquad w_{lr} + a_l^{(d')} = w_{jr} + a_j^{(d')}.

Subtracting the two gives δ=al(d)−al(d′)≤aj(d)−aj(d′)≤δ\delta= a_l^{(d)} - a_l^{(d')} \le a_j^{(d)} - a_j^{(d')} \le\delta, so jj is also a maximizing vertex, but jj is closer to p′p' than ll in Fd′F_{d'}, a contradiction to the choice of ll. Hence different loads have disjoint outputs. It is also clear no load generates the same set more than once.

Upper bound of the number of outputs

Proposition 3.4. For 1≤k≤m1 \le k \le m, the number of outputs in Proposition 3.2 is

Nm,k=2k−m∑j=k2m[zj](2+z+z2)m.(5)N_{m,k} = 2^{k-m} \sum_{j=k}^{2m} [z^j](2+z+z^2)^m. \tag*{(5)}

Consequently, for every z≥1z \ge1,

∣C(w)∣=Nm,k≤2k−mz−k(2+z+z2)m.(6)|\mathcal{C}(w)| = N_{m,k} \le2^{k-m}z^{-k}(2+z+z^2)^m. \tag*{(6)}

Proof. Introduce a formal variable zz to record the total load, with each choice of dld_l contributing a factor zdlz^{d_l}. Let P(z)=1+z+2z2P(z) = 1+z+2z^2. Grouping the loads by their first positive index pp and considering the contributions from vertices l<pl<p, l=pl=p, and l>pl>p separately, it is not difficult to see that

Nm,k=∑d2b(d)=[zk]∑p=1m2p−1(2z+2z2)P(z)m−pN_{m,k} = \sum_d 2^{b(d)} = [z^k]\sum_{p=1}^{m}2^{p-1}(2z+2z^2)P(z)^{m-p}
=[zk] 2z(1+z)2m−P(z)m2−P(z)=[zk]2z(2m−P(z)m)1−2z,= [z^k]\,2z(1+z)\frac{2^m-P(z)^m}{2-P(z)} = [z^k]\frac{2z(2^m-P(z)^m)}{1-2z},

where we use 2−P(z)=(1+z)(1−2z)2-P(z)=(1+z)(1-2z) for the last equality. Since P(1/2)=2P(1/2)=2, we have

2m=∑j=02m2−j[zj]P(z)m.2^m=\sum_{j=0}^{2m}2^{-j}[z^j]P(z)^m.

Expanding 2z(1−2z)−1=∑t≥1(2z)t2z(1-2z)^{-1}=\sum_{t\ge1}(2z)^t therefore gives

Nm,k=[zk](2m−P(z)m)∑t≥1(2z)t=2k+m−∑t≥1[zk−t]2tP(z)mN_{m,k}=[z^k](2^m-P(z)^m)\sum_{t\ge1}(2z)^t =2^{k+m}-\sum_{t\ge1}[z^{k-t}]2^tP(z)^m
=2k(2m−∑j=0k−12−j[zj]P(z)m)=2k∑j=k2m2−j[zj]P(z)m.=2^k\left(2^m-\sum_{j=0}^{k-1}2^{-j}[z^j]P(z)^m\right) =2^k\sum_{j=k}^{2m}2^{-j}[z^j]P(z)^m.

Finally, 2P(z/2)=2+z+z22P(z/2)=2+z+z^2, so [zj](2+z+z2)m=2m−j[zj]P(z)m[z^j](2+z+z^2)^m=2^{m-j}[z^j]P(z)^m, giving (3.2). The bound (3.3) follows by using zj≥zkz^j \ge z^k for j≥kj \ge k and real z≥1z \ge1.

Exponential bound. For k/n=αk/n=\alpha, the right side of (6) is

[22α−1(2+z+z2)1−αz−α]n.\left[2^{2\alpha-1}\left(2+z+z^{2}\right)^{1-\alpha}z^{-\alpha}\right]^n.

At z=1z=1 the bracket equals 22, and its logarithmic derivative with respect to zz at z=1z=1 is (3−7α)/4(3-7\alpha)/4. This is negative for α>3/7\alpha>3/7, so γ(α)<2\gamma(\alpha)<2. The expression tends to infinity as z→∞z\to\infty for α≤1/2\alpha\le1/2, so the minimum is attained.

For fixed z≥1z\ge1, increasing α\alpha multiplies the expression in (1.1) by a positive power of 4/[z(2+z+z2)]≤14/[z(2+z+z^2)]\le1, so the function γ\gamma is nonincreasing for α∈(3/7,1/2]\alpha\in(3/7,1/2]. In particular, if k/n≥αk/n\ge\alpha, then Nm,k≤γ(α)nN_{m,k}\le\gamma(\alpha)^n.

Restricted dynamic programming

We restrict the Held–Karp state space to compatible subsets C(w)\mathcal{C}(w). Since every connected component of an assignment has at most three vertices, transitions may append up to three vertices at a time, and can be computed in polynomial time.

We assume n≥3n\ge3 and fix an arbitrary start vertex s∈Rs\in R. Use states (U,v)(U,v) with U∈C(w)U\in\mathcal{C}(w), s∈Us\in U, and v∈U∖{s}v\in U\setminus\{s\}, together with the initial state ({s},s)(\{s\},s). Each entry stores the minimum cost of an admitted path from ss to vv visiting exactly the set UU. Set DP⁡({s},s)=0\operatorname{DP}(\{s\},s)=0 and all other entries to +∞+\infty.

Process states in the order of increasing ∣U∣|U|. From DP⁡(U,u)\operatorname{DP}(U,u), consider every simple path P=(u,x1,…,xt)P=(u,x_1,\ldots,x_t) with 1≤t≤31\le t\le3 and xi∉Ux_i\notin U. Let U′=U∪{x1,…,xt}U'=U\cup\{x_1,\ldots,x_t\}; if (U′,xt)(U',x_t) is a stored state, update

DP⁡(U′,xt)←min⁡{DP⁡(U′,xt),DP⁡(U,u)+w(P)}.(7)\operatorname{DP}(U',x_t)\leftarrow\min\{\operatorname{DP}(U',x_t),\operatorname{DP}(U,u)+w(P)\}. \tag*{(7)}

All paths use available edges of GG. Close each full path by an edge back to ss: the answer is

min⁡v∈NG(s)(DP⁡(V,v)+wvs),\min_{v\in N_G(s)}\left(\operatorname{DP}(V,v)+w_{vs}\right),

and the tour can be recovered by looking at predecessors. An infinite value means no tour exists.

Proposition 4.1. Given generic costs ww and an independent set RR, the procedure solves TSP deterministically in O∗(Nm,k)O^*(N_{m,k}) time.

Proof. Every finite entry represents a simple path with vertex set UU, so closing a full path gives a feasible tour.

By Theorem 2.8, a minimum-cost tour HH contains some AdA_d. Orient HH to traverse the assignment edge at s∈Rs\in R first. The connected components of AdA_d are consecutive blocks of at most three vertices, and ss is an endpoint of its block. Complete this first block from the initial state, then append the remaining blocks. Every block union is compatible with AdA_d, so (7) admits this path and its closing edge.

Generate the sets in C(w)\mathcal{C}(w) using Proposition 3.2. Store the subsets by cardinality in a deterministic dictionary keyed by nn-bit strings. There are O(nNm,k)O(nN_{m,k}) states, each with O(n3)O(n^3) candidate extensions, giving Nm,knO(1)N_{m,k}n^{O(1)} time.

The algorithm below includes the step for handling arbitrary inputs, justified in § 5. On such inputs the family is C(w~)\mathcal{C}(\widetilde{w}) for the completed symbolic costs, while the dynamic program uses original edges and costs.

Algorithm 1 (Deterministic TSP with an independent set). Given a simple graph G=(V,E)G = (V, E) with costs ww and an independent set RR of size at least α∣V∣\alpha|V|, proceed as follows.

  1. Set L=V∖RL = V \setminus R, m=∣L∣m = |L|, and k=∣R∣k = |R|; if k>mk > m or ∣V∣<3|V| < 3, report no tour and stop.

  1. Fix s∈Rs \in R, label L={1,…,m}L = \{1,\ldots,m\}, and construct the completed costs w~\widetilde{w} as in (5.1). Initialize an empty deterministic dictionary C(w~)C(\widetilde{w}) of vertex subsets.

  1. List all loads d∈{0,1,2}Ld \in\{0,1,2\}^{L} with ∑ldl=k\sum_l d_l = k. Compute and store each AdA_d by minimum-cost perfect matching with costs w~\widetilde{w}.

  1. For each listed load, form the forest TdT_d from (3.1). For every proper two-coloring c:L→{0,1}c : L \to\{0,1\} of TdT_d with c(Ad(s))=1c(A_d(s)) = 1, put S=c−1(1)S = c^{-1}(1) and insert S∪Ad−1(S)S \cup A_d^{-1}(S) into the dictionary.

  1. Run (4.1) with DP⁡({s},s)=0\operatorname{DP}(\{s\},s) = 0, using the original edges and costs. Minimize DP⁡(V,v)+wvs\operatorname{DP}(V,v) + w_{vs} over edges vs∈Evs \in E and recover a tour, or report nonexistence if the minimum is infinite.

If needed, obtain RR by computing a maximum independent set in O∗(2n/3)O^*(2^{n/3}) time [17]. Its time is absorbed by the stated bound since 21/3<γ(1/2)≤γ(α)2^{1/3} < \gamma(1/2) \le\gamma(\alpha).

Arbitrary costs and edges

We remove the assumptions of complete cross-edges and generic costs by introducing deterministic perturbations to the costs.

Fix an independent set RR with k=∣R∣≤m=∣L∣k = |R| \le m = |L|. Add all missing LL–RR edges, retaining the original edges within LL and adding none within RR. Assign distinct nonnegative identifiers ι(e)<n2\iota(e) < n^2 to the completed graph edges and use lexicographically ordered costs

w~e={(0,we,2ι(e)),e∈E,(1,0,2ι(e)),e∉E.(8)\widetilde{w}_e = \begin{cases} (0,w_e,2^{\iota(e)}), & e \in E,\\ (1,0,2^{\iota(e)}), & e \notin E. \end{cases} \tag*{(8)}

The first coordinate counts added edges, the second gives the original cost, and the third breaks ties. Thus, whenever an original tour exists, every symbolic minimum-cost tour is an original optimum. Every alternating cycle has a nonzero third coordinate, since distinct powers of two have nonzero signed sum, so the cross-edge matrix is generic.

This is a symbolic perturbation in the spirit of simulation of simplicity [8]. The next lemma supplies the real realization needed for the structural arguments.

Lemma 5.1. For each fixed input, real edge costs with a generic cross-edge matrix can reproduce the canonical assignments, coloring forests, and minimum-cost tours determined by (5.1). The algorithm does not compute such a realization.

Proof. Replace each triple (x0,x1,x2)(x_0,x_1,x_2) by x0+εx1+ε2x2x_0+\varepsilon x_1+\varepsilon^2 x_2. For sufficiently small ε>0\varepsilon> 0, this preserves all comparisons among the finitely many assignment and tour costs. It also preserves genericity: every alternating-cycle sum has a nonzero third coordinate. Thus the canonical assignments and optimal tours are unchanged, and so are the coloring forests defined by (3.1).

The algorithm works directly with triples, using coordinatewise addition and subtraction and lexicographic comparison. The integer coordinates have polynomial bit length; only the middle coordinate involves input reals. To implement subtraction using additions and comparisons, store each signed expression as a difference of sums p−qp-q: addition is componentwise, negation swaps the sums, and p−q≤p′−q′p-q \leq p^{\prime}-q^{\prime} iff p+q′≤p′+qp+q^{\prime} \leq p^{\prime}+q. Each matching computation uses polynomially many such operations, and the dynamic program uses only sums of original costs. For rational inputs all these operations have polynomial bit complexity.

Proof of Theorem 1.1. Run Algorithm 1 with ∣R∣≥αn|R| \geq\alpha n. If k>mk>m, no tour exists; otherwise αn≤k≤n/2\alpha n \leq k \leq n/2. Whenever an original tour exists, a symbolic optimum is an original optimum. Lemma 5.1 and the block argument of Proposition 4.1 show that the dynamic program admits such a tour. Every returned tour uses original edges, so the answer is correct. The time is O∗(Nm,k)≤O∗(γ(α)n)O^{*}(N_{m,k}) \leq O^{*}(\gamma(\alpha)^{n}) by Proposition 3.4 and monotonicity. The optional preprocessing and arithmetic discussion above give the remaining guarantees. □

AI use. The Odin Automatic AI Research Agent was used to find the initial proof. The final content and proofs in this paper were written and verified by the authors.

References

  1. [1]Richard Bellman. Dynamic programming treatment of the travelling salesman problem. Journal of the ACM, 9(1):61–63, 1962.DOI
  2. [2]Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. The traveling salesman problem in bounded degree graphs. ACM Transactions on Algorithms, 8(2), Article 18, 2012.DOI
  3. [4]Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Information and Computation, 243:86–111, 2015.
  4. [5]William J. Cook. In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press, 2012.
  5. [6]Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Fast Hamiltonicity checking via bases of perfect matchings. Journal of the ACM, 65(3), Article 12, 2018.
  6. [7]Mike Develin and Bernd Sturmfels. Tropical convexity. Documenta Mathematica, 9:1–27, 2004.
  7. [8]Herbert Edelsbrunner and Ernst Peter Mücke. Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms. ACM Transactions on Graphics, 9(1):66–104, 1990.
  8. [9]David Eppstein. The traveling salesman problem for cubic graphs. Journal of Graph Algorithms and Applications, 11(1):61–81, 2007.
  9. [10]Pavel Galashin, Gleb Nenashev, and Alexander Postnikov. Trianguloids and triangulations of root polytopes. Journal of Combinatorial Theory, Series A, 201:105802, 2024.arxiv.org/abs/1803.06239
  10. [11]Michael Held and Richard M. Karp. A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 10(1):196–210, 1962.
  11. [12]Harold W. Kuhn. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1–2):83–97, 1955.
  12. [13]James Munkres. Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics, 5(1):32–38, 1957.DOI
  13. [14]Jesper Nederlof. Bipartite TSP in O(1.9999^n) time, assuming quadratic time matrix multiplication. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 40–53. ACM, 2020.
  14. [15]Mihail Stoian. TSP escapes the O(2^n n^2) curse. arXiv preprint arXiv:2405.03018, 2024.arxiv.org/abs/2405.03018
  15. [16]Mihail Stoian. Mind the gap. Doubling constant parametrization of weighted problems: TSP, Max-Cut, and more. In Proceedings of the 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026), LIPIcs 364, pages 79:1–79:19. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2026.
  16. [17]Robert Endre Tarjan and Anthony E. Trojanowski. Finding a maximum independent set. SIAM Journal on Computing, 6(3):537–546, 1977.DOI
  17. [18]Andrew G. Thomason. Hamiltonian cycles and uniquely edge colourable graphs. Annals of Discrete Mathematics, 3:259–268, 1978.DOI
  18. [19]Gerhard J. Woeginger. Exact algorithms for NP-hard problems: A survey. In Combinatorial Optimization—Eureka, You Shrink!, Lecture Notes in Computer Science 2570, pages 185–207. Springer, 2003.
  19. [20]Yuan Yao. Linkage axioms for generic tropical oriented matroids. arXiv preprint arXiv:2506.11265, 2025.arxiv.org/abs/2506.11265

Paper details

vlnc:W_fg66vpwc
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents