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 , for any fixed . It runs in time for an explicit constant ; for bipartite graphs, the bound is . 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 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 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 by batching DP transitions into min-plus matrix products, without reducing the exponential base. For graphs of maximum degree three, Eppstein [9] gives an 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 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 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, suppresses factors polynomial in in the exact arithmetic model; for binary-encoded rational costs it also suppresses factors polynomial in the input bit length. For , define
Theorem 1.1. Fix . Given an undirected -vertex graph with real edge costs and containing an independent set of size at least , a deterministic algorithm finds a minimum-cost Hamiltonian cycle or reports that none exists in time. It accesses the input costs only through additions and comparisons, and .
Here is fixed independently of . We describe the algorithm with a suitable independent set supplied; can be obtained within the same time bound if needed.
At , the minimum in (1) occurs at , giving . 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 time.
Overview
Let , , and , and write for the edge costs between and . We first assume that all these edges are present and is generic; these assumptions are removed in § 5.
Assignments in optimal tours. An assignment chooses one neighbor in for every ; its load is the number of vertices of assigned to each vertex . (The terminology comes from standard usage in scheduling problems.) Denote the unique minimum-cost assignment of each load by . The structural result (Theorem 2.8) is that every minimum-cost tour contains some with . Its proof uses auxiliary prices on , 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 , and moving one unit of load to a vertex preserves its previously assigned neighbors [10, 20].
Enumerating compatible subsets. A subset is compatible with an assignment if it is a union of the connected components of . Let consist of the sets compatible with at least one of load at most two. Our goal is to generate all sets in efficiently.
For each load , we obtain the tree using assignments with neighboring loads. Contracting edges in and deleting selected edges gives a forest on . Each proper two-coloring of gives a compatible subset. The aforementioned structure guarantees that all subsets of can be generated this way (Proposition 3.2).
With a standard generating function calculation (Proposition 3.4), the number of compatible subsets is
where is the coefficient of in polynomial . The corresponding exponential bound has base for .
The restricted dynamic program. The assignment components in a tour containing are paths on at most three vertices, traversed as consecutive blocks. Starting at along its assignment edge, every completed-block prefix belongs to . 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, is a simple undirected graph, is independent, , , and . We also assume that all edges of (i.e. cross-edges) are present, while the edges inside are not restricted. The symbol denotes the edge costs and, when used as a matrix, their restriction to . We write for an edge with , , and for the all-ones vector.
Assignments, prices, and tight graphs
Definition 2.1. An assignment is a map , identified with a collection of cross-edges in . The load of this assignment is a nonnegative integer vector where , and the cost is the sum of the costs of all edges of . A load vector is called balanced if for all .
In the bipartite case where , an assignment is similar to but more flexible than the perfect matchings considered in [14].
Definition 2.2. For a simple cycle in , its alternating sum is the sum of the costs of alternate edges minus the sum for the remaining edges. Equivalently, it is , where . The cost matrix is generic if every such sum is nonzero.
Definition 2.3. For a price vector , define the adjusted cost of a cross-edge by . An edge is tight (for ) if it is one of the edges incident to with the minimum adjusted cost. The tight graph is the collection of tight edges over all . An assignment is also called tight if all of its edges are tight.
Every has at least one neighbor in , and adding a common constant to the prices does not change . 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 has minimum cost among all assignments of load . Equality for another assignment holds only when it is also tight.
Lemma 2.5. If is generic, every tight graph is a forest.
Proof. On a cycle of tight edges, the two incident edges at each have equal adjusted cost. Summing these equalities around the cycle cancels the prices and gives a zero alternating sum, contrary to genericity.
Lemma 2.6. For generic and any nonnegative integer load vector with , the minimum-cost assignment of that load is unique; call the canonical assignment .
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 be a simple bipartite graph with equally sized parts and . If every vertex of has degree three, every edge of lies on an even number of Hamiltonian cycles. In particular, a Hamiltonian has a second Hamiltonian cycle.
Proof. Fix with . By [18 Theorem 1.1], the number of Hamiltonian paths beginning with and ending at a neighbor of is even: each possible endpoint lies in and has degree three. Closing the paths by their last edge to gives the claimed parity.
Theorem 2.8. Let be a minimum-cost Hamiltonian cycle of . There exist prices such that every is incident to an edge of . Consequently, contains an assignment of minimum cost for its load. For generic , this assignment is a canonical assignment of a balanced load vector.
Proof. For each and , let
The condition is equivalent to for all , and thus to every having a tight edge in .
Fix and put . Taking maxima in the definition of gives
Thus the continuous map sends the compact convex box into itself. Brouwer’s theorem gives a fixed point , so with . It remains to show that .
Suppose . For each , choose attaining the maximum defining . Then
so and is cheaper in adjusted cost than either tour edge incident to . Subdivide the edges of within (i.e. adding a vertex at the middle of these edges, and putting the added vertices in ), and add edge for every . The resulting bipartite graph has two parts of size , with degree three at every vertex of , so Lemma 2.7 gives another Hamiltonian cycle, and suppressing the degree-two subdivision vertices yields a different tour retaining all - edges of .
At each , the same number of incident edges are added and removed when we go from to . Every added edge has adjusted cost at most , while every removed edge has adjusted cost at least . Since retains exactly the - edges of , each vertex of has the same cross-edge degree in both tours. Their price contributions therefore cancel, so has strictly lower total cost than , contradicting optimality. Thus and , as desired.
Neighboring assignments and tight trees
For the remainder of this section and Sections 3–4, we assume that the cost matrix is generic.
Fix an order . For each (not necessarily balanced) load vector , let be the smallest index with positive load, and let . All assignments of load are supported on . For any load vector , one can compute by minimum-cost perfect matching between and copies of each vertex in polynomial time [12, 13]. Let with mild abuse of notation.
We use the following known properties of minimum-cost assignments. Let denote the unit vector at .
Lemma 2.9. Let and let be supported on , with . Then is a spanning tree on and for each . Given , each can be obtained by assigning each to the first vertex in on the unique path from to in .
For every with , if is assigned to in , then it is also assigned to in . (Also, there is exactly one additional vertex assigned to in compared to .)
This lemma follows by applying [10 Proposition 3.4] on (regular) triangulations of products of two simplices induced by the restricted cost matrix on ; 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 . The following construction gives a normalized price vector and a corresponding tight tree for each load .
Lemma 2.10. Let and for each , and define . These are the coordinatewise least prices with making tight on . The resulting tight graph is
which is a spanning tree on the vertex set . When is rooted at , every has parent , and each has exactly children; each has a parent in .
For fixed , different load vectors yield different . The prices and tree are computable from in polynomial time.
Proof. If , Lemma 2.9 gives . Reassigning from to in yields an assignment of load whose cost is at least that of . Consequently, for every we have
Thus is a tight edge for every , and by definition (since ).
If a different price vector with also makes tight, since a tight assignment minimizes total adjusted cost, and has load , we have
Thus for every , showing that is coordinatewise minimal.
At , each has the same adjusted cost as the tight assignment , so it is tight as well. Their union is the spanning tree by Lemma 2.9. By Lemma 2.5, the tight graph is a forest, so
it equals this tree. Its degree at is and at each is , giving the desired structure when rooted at .
Given some price , we can compute the tight graph directly, and its vertex degrees allow us to recover . Given , one can compute each using the perfect matching algorithm, and hence also the tight graph using the union definition in (2.1) in polynomial time.
Figure 1. An example of a canonical assignment with load , its three neighboring canonical assignments, and a tight graph 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 , put . The locus of for which this minimum is attained at least twice is called a tropical hyperplane. Collecting all tropical hyperplanes for each gives an arrangement of tropical hyperplanes. For each point , the minimizing indices for each form the type of , representing the relative position of with respect to the tropical hyperplane arrangement. The tight graph encodes the same information as this type using edges of . In particular,
where is the minimum assignment cost with load . The right-hand side is the min-plus tropical polynomial whose coefficients are the assignment values . We refer the reader to [7] for further connections to tropical geometry.
The same matrix lifts each vertex of a product of two simplices to height . Tight graphs encode the lower faces of the resulting polytope, corresponding to a regular subdivision of , and genericity of 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 are called semi-matchings or topes, and 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 is compatible with an assignment if exactly when , for every . Equivalently, is a union of components of the assignment graph, including isolated vertices of .
For generic , let be the family of sets compatible with some canonical assignment with balanced. Complementary sets are treated as distinct members of .
For a fixed assignment , a compatible set can be identified with a -coloring of where every is given the same color as .
The key insight to improving the classic Bellman–Held–Karp algorithm is that it suffices to perform dynamic programming over sets in , since an optimal Hamiltonian cycle contains some canonical assignment, which decomposes into a collection of connected components, any sub-collection of which belongs to . It therefore suffices to generate 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 and use the notation , , and from Subsection 2.3. For each with , let be the unique vertex newly assigned to by relative to . By Lemma 2.9, is the unique edge in incident to that is not in , hence is the parent edge of in . Define the forest on
Equivalently, is a selectively pruned contraction of the tree : contract all assignment edges in , delete the parent edges at vertices with , and adjoin as isolated vertices. Note that each component contains exactly one vertex or with .
Consider all proper -colorings of (where adjacent vertices are given opposite colors). For each coloring, if consists of the vertices colored 1, output . Observe that is clearly compatible with .
Intuitively speaking, each edge of corresponds to a possible way to reassign a vertex to get another canonical assignment with a neighboring balanced load. (The deleted edges after contracting by 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 is still covered despite this restriction.
Proposition 3.2. *Over all balanced load vectors , the process above generates every set in at least once. Its number of outputs, counted with multiplicity, is , where

Figure 2. Constructing the forest from the example tight graph from Figure 1. The contracted edges of are bolded in .
is the number of connected components of . The list can be generated deterministically in time.
Proof. Fix and choose a compatible balanced load maximizing and then minimizing . Assume for the sake of contradiction that an edge of has both endpoints on the same side of (where is further away from the root in ), then clearly is also on the same side as well. Now reassign from to . The old and new assignment edges both lie in , so the new assignment is compatible with and minimum-cost for its load : indeed, every assignment of load is supported on . Thus by Lemmas 2.4 and 2.6, and its loads remain at most two. As , the choice of forces . Since is tight for , Lemma 2.10 gives coordinatewise, with equality only if . Hence the sum of prices strictly decreases, which is a contradiction. Therefore, induces a proper coloring on , so the process generates .
Now list the balanced loads and store their canonical assignments, with polynomial work per load. These give each forest in polynomial time and its colorings with polynomial work per output. Since every load contributes at least one output, total time is .
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 without repetition. Therefore, .
Proof. Suppose is generated by distinct balanced loads , with . If , the prices are distinct by Lemma 2.10; interchange the loads if necessary so that . If , subtract a sufficiently large common constant from ; this preserves its tight graph and the argument below.
Let , and choose a maximizing vertex closest to in . Note that ; the case is impossible since by definition of normalized prices. Every edge of incident to is also tight for : for ,
If , then has three tight incident edges in and hence also in , so (since only has degree 2) and there are no other incident edges in (since the maximum degree is 3), and therefore its parent edge in is common to both trees. Otherwise, its parent edge in crosses and cannot belong to the compatible assignment . This edge must therefore also be the parent edge in , again common to both trees and with .
In both cases, let be this common parent edge and (i.e. the parent of in ). Since is tight for , while and are tight for , we have
Subtracting the two gives , so is also a maximizing vertex, but is closer to than in , a contradiction to the choice of . 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 , the number of outputs in Proposition 3.2 is
Consequently, for every ,
Proof. Introduce a formal variable to record the total load, with each choice of contributing a factor . Let . Grouping the loads by their first positive index and considering the contributions from vertices , , and separately, it is not difficult to see that
where we use for the last equality. Since , we have
Expanding therefore gives
Finally, , so , giving (3.2). The bound (3.3) follows by using for and real .
Exponential bound. For , the right side of (6) is
At the bracket equals , and its logarithmic derivative with respect to at is . This is negative for , so . The expression tends to infinity as for , so the minimum is attained.
For fixed , increasing multiplies the expression in (1.1) by a positive power of , so the function is nonincreasing for . In particular, if , then .
Restricted dynamic programming
We restrict the Held–Karp state space to compatible subsets . 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 and fix an arbitrary start vertex . Use states with , , and , together with the initial state . Each entry stores the minimum cost of an admitted path from to visiting exactly the set . Set and all other entries to .
Process states in the order of increasing . From , consider every simple path with and . Let ; if is a stored state, update
All paths use available edges of . Close each full path by an edge back to : the answer is
and the tour can be recovered by looking at predecessors. An infinite value means no tour exists.
Proposition 4.1. Given generic costs and an independent set , the procedure solves TSP deterministically in time.
Proof. Every finite entry represents a simple path with vertex set , so closing a full path gives a feasible tour.
By Theorem 2.8, a minimum-cost tour contains some . Orient to traverse the assignment edge at first. The connected components of are consecutive blocks of at most three vertices, and 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 , so (7) admits this path and its closing edge.
Generate the sets in using Proposition 3.2. Store the subsets by cardinality in a deterministic dictionary keyed by -bit strings. There are states, each with candidate extensions, giving time.
The algorithm below includes the step for handling arbitrary inputs, justified in § 5. On such inputs the family is 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 with costs and an independent set of size at least , proceed as follows.
Set , , and ; if or , report no tour and stop.
Fix , label , and construct the completed costs as in (5.1). Initialize an empty deterministic dictionary of vertex subsets.
List all loads with . Compute and store each by minimum-cost perfect matching with costs .
For each listed load, form the forest from (3.1). For every proper two-coloring of with , put and insert into the dictionary.
Run (4.1) with , using the original edges and costs. Minimize over edges and recover a tour, or report nonexistence if the minimum is infinite.
If needed, obtain by computing a maximum independent set in time [17]. Its time is absorbed by the stated bound since .
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 with . Add all missing – edges, retaining the original edges within and adding none within . Assign distinct nonnegative identifiers to the completed graph edges and use lexicographically ordered costs
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 by . For sufficiently small , 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 : addition is componentwise, negation swaps the sums, and iff . 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 . If , no tour exists; otherwise . 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 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]Richard Bellman. Dynamic programming treatment of the travelling salesman problem. Journal of the ACM, 9(1):61–63, 1962.DOI
- [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
- [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.
- [5]William J. Cook. In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press, 2012.
- [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.
- [7]Mike Develin and Bernd Sturmfels. Tropical convexity. Documenta Mathematica, 9:1–27, 2004.
- [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.
- [9]David Eppstein. The traveling salesman problem for cubic graphs. Journal of Graph Algorithms and Applications, 11(1):61–81, 2007.
- [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
- [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.
- [12]Harold W. Kuhn. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1–2):83–97, 1955.
- [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
- [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.
- [15]Mihail Stoian. TSP escapes the O(2^n n^2) curse. arXiv preprint arXiv:2405.03018, 2024.arxiv.org/abs/2405.03018
- [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.
- [17]Robert Endre Tarjan and Anthony E. Trojanowski. Finding a maximum independent set. SIAM Journal on Computing, 6(3):537–546, 1977.DOI
- [18]Andrew G. Thomason. Hamiltonian cycles and uniquely edge colourable graphs. Annals of Discrete Mathematics, 3:259–268, 1978.DOI
- [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.
- [20]Yuan Yao. Linkage axioms for generic tropical oriented matroids. arXiv preprint arXiv:2506.11265, 2025.arxiv.org/abs/2506.11265
