pith. sign in

arxiv: 1907.11669 · v1 · pith:B24V2HCGnew · submitted 2019-07-26 · 💻 cs.DM · cs.DS· math.OC

Subtour Elimination Constraints Imply a Matrix-Tree Theorem SDP Constraint for the TSP

Samuel C. Gutekunst , David P. Williamson This is my paper

Pith reviewed 2026-05-24 15:05 UTC · model grok-4.3

classification 💻 cs.DM cs.DSmath.OC
keywords traveling salesman problemsubtour eliminationsemidefinite programmingmatrix-tree theoremlinear programming relaxationspanning treesTSP polytope
0
0 comments X

The pith

Subtour elimination constraints imply the matrix-tree theorem SDP constraint for the 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 a semidefinite programming constraint for the traveling salesman problem holds for any weighted 2-edge-connected graph. This constraint requires that the total weight of all spanning trees in a fractional solution is at least as large as the total for a cycle graph on the same vertices. The authors prove that the constraint follows directly from the subtour elimination inequalities that define the standard linear programming relaxation of the TSP. Because the SDP requirement is a consequence of these linear inequalities, it adds no additional cutting power. A reader cares because the result shows how one nonlinear relaxation technique is already enforced by a finite collection of linear cuts.

Core claim

De Klerk, Pasechnik, and Sotirov give a semidefinite programming constraint for the Traveling Salesman Problem based on the matrix-tree Theorem. This constraint says that the aggregate weight of all spanning trees in a solution to a TSP relaxation is at least that of a cycle graph. In this note, we show that the semidefinite constraint holds for any weighted 2-edge-connected graph and, in particular, is implied by the subtour elimination constraints of the subtour elimination linear program. Hence, this semidefinite constraint is implied by a finite set of linear inequality constraints.

What carries the argument

the matrix-tree theorem SDP constraint on the aggregate weight of spanning trees, shown to be forced by the subtour elimination inequalities

If this is right

  • Any solution satisfying the subtour elimination constraints automatically satisfies the SDP constraint.
  • The SDP constraint is redundant once the subtour LP is enforced.
  • The implication holds for every weighted 2-edge-connected graph, not merely for TSP instances.
  • The SDP bound can be obtained from a finite number of linear inequalities without semidefinite programming.

Where Pith is reading between the lines

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

  • Similar linear derivations may exist for other SDP constraints used in combinatorial optimization.
  • The result links the matrix-tree theorem directly to the classical description of the TSP subtour polytope.
  • Computational implementations of TSP relaxations could drop the SDP constraint when subtour inequalities are already present.

Load-bearing premise

The SDP constraint is defined exactly as the total weight of spanning trees being at least the total for a cycle graph, and the input graph is 2-edge-connected.

What would settle it

A weighted 2-edge-connected graph whose subtour LP solution has strictly less total spanning-tree weight than the cycle graph would falsify the claim.

Figures

Figures reproduced from arXiv: 1907.11669 by David P. Williamson, Samuel C. Gutekunst.

Figure 1
Figure 1. Figure 1: A sample tree instantiation in T e G, T 1 G′, and T 2 G′ We first use it to prove the following: Proposition 3.2. Let G = (V, E) be a weighted simple graph with rational edge weights given by x ∈ R E. If x is an extreme point of the subtour LP (1), then X T ∈TG Y e∈T xe ≥ n. Theorem 1.1 will then follow as an immediate consequence. To prove Proposition 3.2, we start with a symmetric, simple weighted graph … view at source ↗
Figure 2
Figure 2. Figure 2: The left shows a simple, weighted graph G where dashed edges have weight 1/2 and full edges have weigh 1. In this case R = 2 and the right shows the corresponding unweighted multigraph G′ . where T i G′ consists of those spanning trees including edge i for i = 1, 2 and T 0 G′ consists of those trees including neither e1 nor e2. We analogously partition TG = T 0 G ⊔ T e G, where T 0 G consists of spanning t… view at source ↗
read the original abstract

De Klerk, Pasechnik, and Sotirov give a semidefinite programming constraint for the Traveling Salesman Problem (TSP) based on the matrix-tree Theorem. This constraint says that the aggregate weight of all spanning trees in a solution to a TSP relaxation is at least that of a cycle graph. In this note, we show that the semidefinite constraint holds for any weighted 2-edge-connected graph and, in particular, is implied by the subtour elimination constraints of the subtour elimination linear program. Hence, this semidefinite constraint is implied by a finite set of linear inequality constraints.

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

0 major / 2 minor

Summary. The paper claims that the matrix-tree theorem SDP constraint for TSP (aggregate spanning-tree weight at least that of the n-cycle, per De Klerk et al.) holds for every weighted 2-edge-connected graph; since every feasible solution to the subtour-elimination LP induces such a graph (exact degree 2, no cut of capacity less than 2), the SDP constraint is implied by the finite set of linear subtour inequalities.

Significance. If the implication holds, the result shows that a known SDP cut is redundant once the subtour LP is imposed, clarifying the relative strength of linear versus semidefinite relaxations for TSP. The derivation is parameter-free, invokes only the classical weighted matrix-tree theorem, and supplies an explicit, falsifiable link between 2-edge-connectivity and the tree-weight inequality.

minor comments (2)
  1. [Abstract] The abstract and introduction should state the precise SDP inequality (the one appearing in De Klerk et al.) rather than describing it only in words, so that the claimed implication can be checked equation-by-equation.
  2. A short remark on whether the same argument applies to the degree-constrained subtour polytope (or only to the pure subtour polytope) would clarify the scope.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive recommendation and for the accurate summary of the paper's main result. We are pleased that the contribution is viewed as clarifying the relationship between the subtour LP and the matrix-tree SDP constraint.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper proves that the SDP constraint (aggregate spanning-tree weight at least that of the cycle) holds for any weighted 2-edge-connected graph and is therefore implied by the subtour elimination LP constraints. This is established directly via the standard weighted matrix-tree theorem applied to the Laplacian of any such graph; no parameters are fitted, no quantities are defined in terms of the target result, and no load-bearing step reduces to a self-citation or prior ansatz by the same authors. The derivation is self-contained against external benchmarks (the matrix-tree theorem and the definition of 2-edge-connectivity).

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on standard results from graph theory (matrix-tree theorem) and convex optimization (SDP definitions) with no free parameters or new entities introduced.

axioms (1)
  • standard math Matrix-tree theorem and semidefinite programming properties as used in De Klerk et al.
    The paper invokes these established theorems to derive the implication.

pith-pipeline@v0.9.0 · 5634 in / 1098 out tokens · 32171 ms · 2026-05-24T15:05:43.352170+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

13 extracted references · 13 canonical work pages · 1 internal anchor

  1. [1]

    Boyd and L

    S. Boyd and L. Vandenberghe. Convex optimization . Cambridge University Press, 2004

    work page 2004

  2. [2]

    Cvetkovi´ c, M

    D. Cvetkovi´ c, M. ˇCangalovi´ c, and V. Kovaˇ cevi´ c-Vujˇ ci´ c. Semidefinite programming methods for the symmetric traveling salesman problem. In G. Cornu´ e jols, R. E. Burkard, and G. J. Woeginger, editors, Integer Programming and Combinatorial Optimization, 7th Inte rnational IPCO Conference, Graz, Austria, June 9-11, 1999, Proceedings , volume 1610 ...

    work page 1999

  3. [3]

    Dantzig, R

    G. Dantzig, R. Fulkerson, and S. Johnson. Solution of a la rge-scale traveling-salesman problem. Journal of the Operations Research Society of America , 2(4):393–410, 1954

    work page 1954

  4. [4]

    de Klerk, D

    E. de Klerk, D. V. Pasechnik, and R. Sotirov. On semidefini te programming relaxations of the traveling salesman problem. SIAM Journal on Optimization , 19(4):1559–1573, 2008

    work page 2008

  5. [5]

    de Klerk and R

    E. de Klerk and R. Sotirov. Improved semidefinite program ming bounds for quadratic as- signment problems with suitable symmetry. Mathematical Programming, 133(1):75–91, Jun 2012

    work page 2012

  6. [6]

    Goemans and F

    M. Goemans and F. Rendl. Combinatorial optimization. In H. Wolkowicz, R. Saigal, and L. Vandenberghe, editors, Handbook of Semidefinite Programming: Theory, Algorithms, a nd Applications, pages 343–360. Springer, Boston, 2000

    work page 2000

  7. [7]

    S. C. Gutekunst and D. P. Williamson. The unbounded integ rality gap of a semidefinite relaxation of the traveling salesman problem. SIAM Journal on Optimization , 28(3):2073– 2096, 2018

    work page 2073

  8. [8]

    S. C. Gutekunst and D. P. Williamson. Semidefinite progra mming relaxations of the traveling salesman problem and their integrality gaps. 2019. Available at https://arxiv.org/abs/1907.09054

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  9. [9]

    Held and R

    M. Held and R. M. Karp. The traveling-salesman problem an d minimum spanning trees. Operations Research, 18(6):1138–1162, 1970

    work page 1970

  10. [10]

    Kirchhoff

    G. Kirchhoff. Ueber die aufl¨ osung der gleichungen, auf we lche man bei der untersuchung der linearen vertheilung galvanischer str¨ ome gef¨ uhrt wird.Annalen der Physik , 148(12):497–508, 1847

    work page

  11. [11]

    Nemirovskii

    A. Nemirovskii. Lectures on modern convex optimizatio n, Lecture Notes Georgia Tech., 2005. Available at https://www2.isye.gatech.edu/~nemirovs/Lect ModConvOpt.pdf

    work page 2005

  12. [12]

    Ok and C

    S. Ok and C. Thomassen. On the minimum number of spanning trees in k-edge-connected graphs. Journal of Graph Theory , 84(3):286–296, 2017

    work page 2017

  13. [13]

    W. Tutte. Graph theory , volume 21 of Encyclopedia of Mathematics and its Applications . Cambridge University Press, 2001. 8

    work page 2001