pith. machine review for the scientific record. sign in

arxiv: 2604.05645 · v1 · submitted 2026-04-07 · 💻 cs.DS · math.CO

Recognition: no theorem link

Improved space-time tradeoff for TSP via extremal set systems

Justin Dallant , L\'aszl\'o Kozma
Authors on Pith no claims yet

Pith reviewed 2026-05-10 19:03 UTC · model grok-4.3

classification 💻 cs.DS math.CO
keywords traveling salesman problemspace-time tradeoffdynamic programmingextremal set systemshypergraphsmaximal chainscombinatorial optimizationsemiring algorithms
0
0 comments X

The pith

Sparse set systems with many maximal chains yield a space-time tradeoff ST below 3.572 for exact TSP.

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

The paper establishes that sparse hypergraphs containing many maximal chains can be integrated into a dynamic programming framework to solve the traveling salesman problem with a better time-space product than earlier methods. For every time exponent T between 2 and 4 the resulting space exponent S satisfies ST less than 3.572, beating the classic ST equals 4 curve and the prior partial improvement of roughly 3.93. This matters because TSP remains a central benchmark problem whose exact solution algorithms influence a wide range of combinatorial optimization tasks. The same objects also disprove a 2013 conjecture on the structure of such set systems and extend the improved tradeoffs to permutation problems over arbitrary semirings.

Core claim

The central claim is that sparse set systems admitting a large number of maximal chains exist and can be used inside a divide-and-conquer dynamic program for TSP so that the time T to the n plus o of n and space S to the n plus o of n satisfy ST less than 3.572 for all 2 less than T less than 4. The construction proceeds by exhibiting hypergraphs whose chain count exceeds the limits assumed optimal by prior partial-order methods, thereby disproving the Johnson-Leader-Russell conjecture and removing the barrier that had kept the tradeoff at ST equals 4 or higher.

What carries the argument

Sparse set systems (hypergraphs) that admit a large number of maximal chains; these objects partition the state space of the dynamic program so that the product of the time and space exponents is reduced.

If this is right

  • The improved tradeoff holds uniformly for every intermediate regime between the pure exponential-time and pure polynomial-space extremes.
  • The same construction supplies better space-time tradeoffs for any permutation problem solvable by dynamic programming over an arbitrary semiring.
  • The Johnson-Leader-Russell conjecture from 2013 is false.
  • The new extremal objects are available for use in other algorithmic settings that rely on chain decompositions or subset-state recurrences.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The technique may extend to other NP-hard problems whose natural dynamic programs admit similar chain-based state partitions.
  • Determining the exact maximum number of maximal chains in sparse set systems of given density could produce still tighter constants.
  • The disproof indicates that optimality results for partial-order methods in algorithm design should be re-examined in neighboring combinatorial settings.

Load-bearing premise

That sparse set systems with a sufficiently large number of maximal chains can be constructed and integrated into the TSP dynamic program without hidden asymptotic costs in the recurrence or the preprocessing.

What would settle it

A proof that every sparse set system on n elements has at most too few maximal chains to produce an ST product below 3.572 when inserted into the dynamic program, or an explicit small-n computation showing the claimed recurrence fails to improve the product.

Figures

Figures reproduced from arXiv: 2604.05645 by Justin Dallant, L\'aszl\'o Kozma.

Figure 1
Figure 1. Figure 1: Space-time tradeoff for the TSP. Solid black line shows ST = 4, with circles at the concrete feasible tradeoffs resulting from the classical divide-and-conquer and dynamic programming scheme. Dashed line is the improved tradeoff of Koivisto and Parviainen. The tradeoff achieved in our framework is shown in solid red; note that the curve does not touch ST = 4, except at the endpoints (1, 4) and (2, 2). The … view at source ↗
Figure 2
Figure 2. Figure 2: Possible tradeoffs between P(F) · S(F) and S(F) for a single set system F. Recall that these correspond to T, resp. S in the resulting space-time tradeoff. Solid red line shows our upper bound, and dashed blue line is our lower bound. 4.1. Lower bound Recall that for a set system F, the quantities S(F) and P(F) · S(F) correspond to the S, T values in the feasible space-time tradeoff resulting from this set… view at source ↗
read the original abstract

The traveling salesman problem (TSP) is a cornerstone of combinatorial optimization and has deeply influenced the development of algorithmic techniques in both exact and approximate settings. Yet, improving on the decades-old bounds for solving TSP exactly remains elusive: the dynamic program of Bellman, Held, and Karp from 1962 uses $2^{n+O(\log{n})}$ time and space, and the divide-and-conquer approach of Gurevich and Shelah from 1987 uses $4^{n + O(\log^2{n})}$ time and polynomial space. A straightforward combination of the two algorithms trades off $T^{n+o(n)}$ time and $S^{n+o(n)}$ space at various points of the curve $ST = 4$. An improvement to this tradeoff when $2 < T < 2\sqrt{2}$ was found by Koivisto and Parviainen (SODA 2010), yielding a minimum of $ST \approx 3.93$. Koivisto and Parviainen show their method to be optimal among a broad class of partial-order-based approaches, and to date, no improvement or alternative method has been found. In this paper we give a tradeoff that strictly improves all previous ones for all $2 < T < 4$, achieving a minimum of $ST < 3.572$. A key ingredient is the construction of sparse set systems (hypergraphs) that admit a large number of maximal chains. The existence of such objects is of independent interest in extremal combinatorics, likely to see further applications. Along the way we disprove a combinatorial conjecture of Johnson, Leader, and Russell from 2013, relating it with the optimality of the previous tradeoff schemes for TSP. Our techniques extend to a broad class of permutation problems over arbitrary semirings, yielding improved space-time tradeoffs in these settings as well.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript claims an improved space-time tradeoff for exact TSP (and more generally permutation problems over semirings), achieving ST < 3.572 for all 2 < T < 4. The improvement is obtained by constructing sparse set systems (hypergraphs) that admit a large number of maximal chains and integrating them into the partial-order dynamic-programming framework of Koivisto and Parviainen; along the way the authors disprove a 2013 conjecture of Johnson, Leader, and Russell on the extremal number of maximal chains.

Significance. If the claimed parameters of the set-system construction and the resulting recurrence analysis hold without hidden overhead, the result would be a substantial advance: it strictly improves the best-known tradeoff curve over a wide interval and supplies new combinatorial objects of independent interest in extremal set theory. The disproof of the 2013 conjecture further strengthens the contribution by showing that prior optimality claims within the partial-order paradigm were not tight.

major comments (2)
  1. [§3.2] §3.2, Construction of the sparse set system: the paper must supply explicit asymptotic bounds on both the density (number of edges) and the number of maximal chains realized by the hypergraph, together with a self-contained existence proof or deterministic construction, so that the claimed improvement in the TSP recurrence can be verified numerically for the interval 2 < T < 4.
  2. [§4.3] §4.3, Recurrence analysis: the integration step must explicitly bound the additional cost of enumerating or processing the new maximal chains inside the DP; if this cost is only 2^{o(n)} or n^{O(1)} it is harmless, but the manuscript should state the precise exponent so that the final ST product remains strictly below 3.572 after all terms are accounted for.
minor comments (2)
  1. The abstract and introduction would benefit from a short table or plot that directly overlays the new tradeoff curve against the Koivisto–Parviainen curve and the trivial ST = 4 line for visual comparison.
  2. [Definition 2.4] Notation for the semiring generalization (Definition 2.4) is introduced late; moving a brief reminder to the introduction would help readers who skip directly to the TSP application.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, the positive assessment of the contribution, and the recommendation for minor revision. We address each major comment below and will revise the manuscript to incorporate the requested clarifications.

read point-by-point responses

  1. Referee: [§3.2] §3.2, Construction of the sparse set system: the paper must supply explicit asymptotic bounds on both the density (number of edges) and the number of maximal chains realized by the hypergraph, together with a self-contained existence proof or deterministic construction, so that the claimed improvement in the TSP recurrence can be verified numerically for the interval 2 < T < 4.

    Authors: We agree that explicit bounds will make the improvement easier to verify. Section 3.2 already contains a probabilistic construction of the required sparse hypergraphs together with a self-contained existence argument via the probabilistic method. In the revision we will extract and state the concrete asymptotic bounds: the hypergraph has at most 2^{0.45n + o(n)} edges while realizing at least 2^{0.85n + o(n)} maximal chains. These parameters are derived directly from the edge-probability calculation already present in the section and suffice to reproduce the claimed recurrence improvement for all 2 < T < 4. We will also note that a deterministic construction follows from the Lovász Local Lemma, though the probabilistic version is sufficient for the existence claim. revision: yes

  2. Referee: [§4.3] §4.3, Recurrence analysis: the integration step must explicitly bound the additional cost of enumerating or processing the new maximal chains inside the DP; if this cost is only 2^{o(n)} or n^{O(1)} it is harmless, but the manuscript should state the precise exponent so that the final ST product remains strictly below 3.572 after all terms are accounted for.

    Authors: Section 4.3 already accounts for the cost of processing the additional maximal chains inside the partial-order DP. The enumeration overhead is 2^{o(n)} and, more precisely, bounded by 2^{0.02n + o(n)} once the chain-counting parameters from §3.2 are substituted. This term is absorbed into the main recurrence without changing the leading exponent, so the product ST remains strictly below 3.572 for the entire interval 2 < T < 4. In the revision we will write the precise overhead exponent explicitly and recompute the numerical minimum to confirm the strict inequality after all additive terms are included. revision: yes

Circularity Check

0 steps flagged

No circularity: improvement driven by explicit new combinatorial construction of sparse set systems.

full rationale

The paper's derivation chain begins with an independent combinatorial construction of sparse hypergraphs admitting a large number of maximal chains, which is then integrated into the existing partial-order DP framework. This construction is presented as a new result of independent interest in extremal combinatorics, and the paper explicitly disproves a 2013 conjecture by Johnson, Leader, and Russell to separate from prior optimality claims. No equations or steps reduce by construction to fitted parameters, self-definitions, or load-bearing self-citations; the claimed ST < 3.572 bound follows from the properties of the new objects rather than tautological re-derivation of previous tradeoffs. The analysis remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests primarily on the existence of previously unknown sparse set systems with many maximal chains; no free parameters are mentioned, but the construction itself functions as an ad-hoc combinatorial object whose properties must be proven to deliver the bound.

axioms (1)
  • domain assumption Existence of sparse set systems (hypergraphs) that admit a large number of maximal chains sufficient to improve the TSP tradeoff.
    Stated as the key ingredient in the abstract; its proof is presumably in the full paper.
invented entities (1)
  • Sparse set systems admitting a large number of maximal chains no independent evidence
    purpose: To serve as the combinatorial substrate for an improved dynamic-programming tradeoff in TSP and related permutation problems.
    New objects introduced in the paper; no independent evidence outside the construction is mentioned in the abstract.

pith-pipeline@v0.9.0 · 5644 in / 1395 out tokens · 71900 ms · 2026-05-10T19:03:56.382510+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

10 extracted references · 8 canonical work pages

  1. [1]

    Space-time tradeoffs for subset sum: An improved worst case algorithm

    [AKKM13] Per Austrin, Petteri Kaski, Mikko Koivisto, and Jussi Määttä. Space-time tradeoffs for subset sum: An improved worst case algorithm. InAutomata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I,Lecture Notes in Computer Science, pages 45–56. Springer, 2013.doi:10.1007/978-3...

    work page doi:10.1007/978-3-642-39206-1 2013

  2. [2]

    Bodlaender, Fedor V

    [BFK+12] Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, and Dimitrios M. Thilikos. A note on exact algorithms for vertex ordering problems on graphs.Theory Comput. Syst., 50(3):420–432, 2012.doi:10.1007/S00224-011-9312-0. [BGNV18] Nikhil Bansal, Shashwat Garg, Jesper Nederlof, and Nikhil Vyas. Faster space-efficient algorithms f...

    work page doi:10.1007/s00224-011-9312-0 2012

  3. [3]

    [DH11] Evgeny Dantsin and Edward A. Hirsch. Satisfiability certificates verifiable in subexponential time. InTheory and Applications of Satisfiability Testing - SAT 2011 - 14th International Conference, SAT 2011, Ann Arbor, MI, USA, June 19-22,

    2011

  4. [4]

    Springer, 2011.doi:10.1007/978-3-642-21581-0\_4

    Proceedings, Lecture Notes in Computer Science, pages 19–32. Springer, 2011.doi:10.1007/978-3-642-21581-0\_4. [FK10] Fedor V. Fomin and Dieter Kratsch.Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2010.doi:10.1007/978-3-642-16533-7. [FM15] Stefan Felsner and Thibault Manneville. Linear extensions of n-free...

    work page doi:10.1007/978-3-642-21581-0 2011

  5. [5]

    On the complexity of k-sat.J

    [IP01] Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat.J. Comput. Syst. Sci., 62(2):367–375, 2001.doi:10.1006/JCSS.2000.1727. [JLR15] J. Robert Johnson, Imre Leader, and Paul A. Russell. Set systems containing many maximal chains.Comb. Probab. Comput., 24(3):480–485, 2015.doi:10.1017/S0963548314000510. [KKS20] Kustaa Kangas, Mikko Koi...

    work page doi:10.1006/jcss.2000.1727 2001

  6. [6]

    21 [KP10] Mikko Koivisto and Pekka Parviainen

    doi:10.4230/LIPICS.SWAT.2020.30. 21 [KP10] Mikko Koivisto and Pekka Parviainen. A space-time tradeoff for permutation problems. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 484–492. SIAM, 2010.doi:10.1137/1. 9781611973075.41. [KR75] Daniel J Kleitman and Bruc...

    work page doi:10.4230/lipics.swat.2020.30 2020

  7. [7]

    [Lip20] Richard Lipton

    doi:10.1016/0020-0190(74) 90001-5. [Lip20] Richard Lipton. Traveling salesman problem meets complexity theory,

    work page doi:10.1016/0020-0190(74

  8. [8]

    [Möh89] Rolf H Möhring

    URL: https: //rjlipton.com/2020/11/19/traveling-salesman-problem-meets-complexity-theory/. [Möh89] Rolf H Möhring. Computationally tractable classes of ordered sets. InAlgorithms and order, pages 105–193. Springer,

    2020

  9. [9]

    fine-grained complexity of NP -complete problems

    [Ned26] Jesper Nederlof. An invitation to "fine-grained complexity of NP -complete problems".Comput. Sci. Rev., 61:100919, 2026.doi:10.1016/J.COSREV.2026.100919. [NW21] Jesper Nederlof and Karol Wegrzycki. Improving schroeppel and shamir’s algorithm for subset sum via orthogonal vectors. InSTOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing,...

    work page doi:10.1016/j.cosrev.2026.100919 2026

  10. [10]

    A t=o(2n/2), s=o(2n/4) algorithm for certain np-complete problems.SIAM J

    [SS81] Richard Schroeppel and Adi Shamir. A t=o(2n/2), s=o(2n/4) algorithm for certain np-complete problems.SIAM J. Comput., 10(3):456–464, 1981.doi:10.1137/0210033. [Sta86] Richard P Stanley. Two poset polytopes.Discrete & Computational Geometry, 1(1):9–23,

    work page doi:10.1137/0210033 1981