Subtour Elimination Constraints Imply a Matrix-Tree Theorem SDP Constraint for the TSP
Samuel C. Gutekunst David P. Williamson
cs.DM cs.DS math.OC

Reducing the dependence of the neural network function to systematic uncertainties in the input space
    Stefan Wunsch Simon Jörger Roger Wolf Günter Quast
    
  First Draft: July 26, 2019 

  Current Draft: August 31, 2020
=====================================================================================================






De Klerk, Pasechnik, and Sotirov <cit.> 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.






§ INTRODUCTION AND THE MATRIX-TREE THEOREM
 

The Traveling Salesman Problem (TSP) is a fundamental problem in combinatorial optimization and a canonical NP-hard problem.  Efficiently computable relaxations of the TSP are used to find optimal and near-optimal TSP solutions, and recently, several relaxations based on semidefinite programs (SDPs) have been proposed (see, e.g., Cvetković, Čangalović, and Kovačević-Vujčić <cit.>, de Klerk, Pasechnik, and Sotirov <cit.>, and de Klerk and Sotirov <cit.>).  

A common source of SDP constraints for the TSP is spectral graph theory: the SDP of Cvetković  et al.  <cit.> is based on algebraic connectivity, and de Klerk et al. <cit.> give a constraint based on  Kirchoff's matrix-tree theorem.  Goemans and Rendl <cit.>  show that the constraints used in the SDP relaxation of Cvetković et al. <cit.> are implied by the canonical TSP relaxation, the subtour elimination linear program (see Equation (<ref>) below for the precise definition of this linear program). In this note we show that the matrix-tree theorem constraint of de Klerk et al. <cit.> is also implied by the subtour elimination linear program constraints.

The matrix-tree theorem dates back to the mid-19th century (Kirchoff <cit.>)  and connects the number of spanning trees of a graph to the Laplacian matrix of that graph. Let G=(V, E) be a simple, undirected graph, and suppose each edge e has weight x_e≥ 0.  Let X be the corresponding weighted adjacency matrix, so that X has zero diagonal and X_ij=X_ji=x_{i, j}.  The Laplacian of X is the |V|× |V| matrix L(X) defined entrywise as 
    L(X)_i, j =  -x_e,   {i, j}∈ E 
    ∑_e: e∩ i ≠∅ x_e ,    i=j 
     0,    else.
 Suppose that 𝒯_G is the set of spanning trees of G.  The matrix-tree theorem is the remarkable result that  any principal minor of L(X) (i.e., the determinant of the matrix obtained by removing the ith row and column of L(X) for any 1≤ i≤ |V|) equals ∑_T∈𝒯_G∏_e∈ T x_e.  In the case that x_e=1 for every edge in G, the term ∑_T∈𝒯_G∏_e∈ T x_e counts the number of spanning trees of G.  See Theorem VI.29 in <cit.>, e.g., for a proof of this general version of the matrix-tree theorem.

De Klerk  et al. <cit.> notice that any Hamiltonian cycle on n vertices has n spanning trees (delete any individual edge).  They use the matrix-tree theorem to derive a constraint for SDP relaxations of the TSP saying that “the aggregate weight of spanning trees is at least n.”  We show that this constraint is implied by constraints in the subtour elimination linear program:

Let x∈^E be a feasible solution to the subtour LP (<ref>) and let G be the complete graph.  Let X be the symmetric matrix where X_ij=X_ji=x_{i, j} and X_ii=0 for all i.  Then X satisfies the matrix-tree theorem constraint:

    ∑_T∈𝒯_G∏_e∈ T x_e ≥ n.


Our results show that the matrix-tree theorem constraint (requiring linear matrix inequalities) of  de Klerk et al. <cit.>  is  weaker than the subtour LP (using just linear inequalities). They can also be stated more generally: any graph G that is 2-edge-connected in a weighted sense (i.e. ∑_e:|e∩ S|=1x_e ≥ 2 for every ∅⊊ S ⊊ V) satisfies ∑_T∈𝒯_G∏_e∈ T x_e ≥ n.  Our result follows from a theorem of  Ok and Thomassen <cit.> that lower-bounds the number of spanning trees in an unweighted, loopless, undirected multigraph.  In Section <ref>, we provide background on the TSP and relaxations.  In Section <ref> we then state the theorem from Ok and Thomassen <cit.> and use it to deduce Theorem <ref>.





§ PRELIMINARIES


The   Traveling Salesman Problem can be stated as follows.  Let G=K_n be the complete graph on V=[n]:={1, 2, ..., n}.  For each e={i, j}∈ G, associate an edge cost c_e  (interpreted  as the cost of traveling from vertex i to vertex j or vice versa).  The TSP is to find a minimum-cost tour on G visiting every vertex exactly once, i.e., to find a minimum-cost Hamiltonian cycle on K_n with respect to the edge costs.   



The prototypical TSP relaxation is the the subtour elimination linear program (also referred to as the Dantzig-Fulkerson-Johnson relaxation <cit.> and the Held-Karp bound <cit.>, and which we will refer to as the subtour LP).   For S⊂ V, denote the set of edges with exactly one endpoint in S by δ(S):={e={i, j}: |{i, j}∩ S|=1} and let δ(v):=δ({v}).  For F⊂ E, let x(F) denote the sum of x over those edges in F: x(F)=∑_e∈ F x_e.  The subtour LP is:

    [             min  ∑_e∈ E c_e x_e                ;      subject to    x(δ(v)) = 2,       v=1, …, n;                    x(δ(S)) ≥ 2, S⊂ V: S≠∅, S≠ V;                     0≤ x_e ≤ 1,           e∈ E. ]

The subtour LP is a relaxation of the TSP because 1) every Hamiltonian cycle has a corresponding feasible solution to the subtour LP, and 2) the value of the subtour LP for such a feasible solution equals the cost of the corresponding Hamiltonian cycle.   

Significant recent research has gone into developing relaxations instead based on semidefinite programs (SDPs).  See, e.g., Cvetković, Čangalović, and Kovačević-Vujčić <cit.> (who both introduce an SDP relaxation based on algebraic connectivity), de Klerk, Pasechnik, and Sotirov <cit.> (who introduce an SDP relaxation based on the theory of association schemes and give the matrix-tree theorem-based SDP constraint), and  de Klerk and Sotirov <cit.> (who use symmetry reduction to strengthen the SDP of  de Klerk et al. <cit.>).  Various results have characterized the performance of these SDPs (Goemans and Rendl <cit.>, Gutekunst and Williamson <cit.>, and Gutekunst and Williamson <cit.>).

The TSP SDP relaxations generally have some symmetric matrix variable X that can be interpreted as a weighted adjacency matrix. There are typically constraints enforcing that X_ii=0, and since X is symmetric, X_ij=X_ji can be thought of as the weight x_e on edge e={i, j}.   In a feasible solution to the SDP relaxation taking on integral values, constraints force X to be the weighted adjacency matrix of a Hamiltonian cycle.  There are generally constraints that directly enforce that X is 2-regular in a weighted sense: every row of X sums to 2, in analogy to the subtour LP constraints that x(δ(v))=2.  If G is the graph with edge weights x_e, the constraints imply that the corresponding Laplacian matrix to X is L(X)=2I-X.  Throughout we treat X as the weighted adjacency matrix of a complete graph G=K_n where edges can have weight zero.[Any spanning tree T containing an edge of weight zero has ∏_e∈ T x_e =0 and doesn't contribute to ∑_T∈𝒯_G∏_e∈ T x_e ≥ n.  We can let G=K_n without loss of generality, as any other graph can be extended to the complete graph by placing a weight of zero on all missing edges; the weighted adjacency matrix, Laplacian, and aggregate spanning tree weight ∑_T∈𝒯_G∏_e∈ T x_e ≥ n will not change.]

  Let A_-i denote the matrix obtained by deleting the ith row and column of A. Note that 2I-X is positive semidefinite, so (2I-X)_-i is positive semidefinite for all i.   De Klerk et al. <cit.>'s observation that a Hamiltonian cycle has n spanning trees, together with the aforementioned matrix-tree theorem, allows them to introduce the SDP constraint  
    det((2I-X)_-1) ≥ n.
  Since the set {Z≽ 0: det(Z) ≥ n} can be expressed as a linear matrix inequality (see, e.g., Section 3.2 of Nemirovskii <cit.>),  the constraint in  Equation (<ref>) can be written as a linear matrix inequality for use in TSP SDP relaxations.  De Klerk  et al. <cit.> note  that this constraint strengthens a semidefinite programming relaxation of the TSP from Cvetković, Čangalović, and Kovačević-Vujčić <cit.>.
 We refer to Equation (<ref>) as the “matrix-tree theorem constraint.”  
 




§ THE MATRIX-TREE THEOREM CONSTRAINT


To prove our main result, we will use the following result from Ok and Thomassen <cit.> which relates edge-connectivity to spanning trees. An unweighted, undirected, loopless multigraph G=(V, E) is k-edge-connected if G is still connected after the removal of any k-1 edges.   



Let G be an weighted, loopless, undirected multigraph that is k-edge-connected.  Then G has at least n(k2)^n-1 spanning trees.
 
We first use it to prove the following:

Let G=(V, E) be a weighted simple graph with rational edge weights given by x∈^E.   If x is an extreme point of the subtour LP (<ref>), then 
    ∑_T∈𝒯_𝒢∏_e∈ T x_e ≥ n.
  

Theorem <ref> will then follow as an immediate consequence.  

To prove Proposition <ref>, we start with a symmetric, simple weighted graph G=(V, E) with edge weights given by x∈^E.  Because x is rational, we will be able to scale x so that Rx∈^E.  Then we let G'=(V, E') be an undirected, loopless, unweighted multigraph with Rx_e copies of edge e.  Moreover, if x(δ(S))≥ 2 then Rx(δ(S))≥ 2R so that G' will be 2R-edge-connected.  We can then appeal to Theorem <ref>, find a large number of spanning trees, and find corresponding spanning trees in G.  

We first verify that the aggregate weight of spanning trees in G' (as an unweighted multigraph with Rx_e copies of edge e) matches the aggregate weight of spanning trees in G (as a weighted simple graph where edge e has weight Rx_e).  To do so, we  apply the following lemma iteratively.





Let G be a weighted loopless multigraph.  Let e={u, v}∈ G and let G' be obtained from G by splitting e into two copies e_1=e_2={u, v} and assigning nonnegative weights x' to the edges in G' so that x_e=x'_e_1+x'_e_2 (and x_f=x'_f for all other edges f in G). Then 

    ∑_T∈𝒯_G∏_f∈ T x_f=∑_T∈𝒯_G'∏_f∈ T x'_f.



In the proof, we use ⊔ to denote a partition: S=A⊔ B means S=A∪ B and A∩ B=∅.  We also use \ for set-minus, so that S\ A={x∈ S: x∉ A}.


This result follows by partitioning 𝒯_G'.  No T∈𝒯_G' can contain both e_1 and e_2 so we write 
    𝒯_G'=𝒯^0_G'⊔𝒯^1_G'⊔𝒯^2_G'
 where 𝒯^i_G' consists of those spanning trees including edge i for i=1, 2 and  𝒯^0_G' consists of those trees  including neither e_1 nor e_2.
We analogously partition 
    𝒯_G=𝒯^0_G⊔𝒯^e_G,
 where 𝒯^0_G consists of spanning trees not using e and 𝒯^e_G consists of spanning trees using e.  

The trees in  𝒯^1_G', 𝒯^2_G', and 𝒯^e_G all use exactly one edge {u, v} (and other than using exactly one of e_1, e_2, or e as {u, v}, use the exact same other edges).  Hence if T∈𝒯^1_G', then  (T\ e_1)∪ e_2∈𝒯^2_G' and (T\ e_1)∪ e ∈𝒯^e_G.  This process gives a one-to-one correspondence between trees in 𝒯^1_G', 𝒯^2_G', and 𝒯^e_G; see Figure <ref>.  Analogously, 𝒯^0_G'=𝒯^0_G.  Hence:

    ∑_T∈𝒯_G'∏_f∈ T x'_f 
       =∑_T∈𝒯^0_G'∏_f∈ T x'_f+∑_T∈𝒯^1_G'∏_f∈ T x'_f+∑_T∈𝒯^2_G'∏_f∈ T x'_f 
       =∑_T∈𝒯^0_G∏_f∈ T x_f+(x'_e_1+x'_e_2)∑_T∈𝒯^1_G'∏_f∈ T, f≠ e_1 x'_f 
       =∑_T∈𝒯^0_G∏_f∈ T x_f+x_e∑_T∈𝒯^1_G∏_f∈ T, f≠ e x_f 
       =∑_T∈𝒯^0_G∏_f∈ T x_f+∑_T∈𝒯^1_G∏_f∈ T x_f 
       =∑_T∈𝒯_G∏_f∈ T x_f.



We now prove our main theorem in the special case of subtour LP extreme points.





Let x be a feasible extreme point of the subtour LP.  Then  x(δ(S))≥ 2 for all S with 1≤ |S| ≤ |V|-1 and, moreover, it is well-known that x is rational.[Extreme points occur where a certain number of constraints hold with equality.  Cramer's rule, e.g., shows that if the constraints of a linear program have rational coefficients, then every extreme point is rational.  This is the case for the subtour LP.]

We first convert G into a loopless, unweighted multigraph.  To do so, suppose that x_e_i=s_ir_i in lowest terms.  Let 
    R=ℒ𝒞ℳ(r_1, ..., r_m).
  Let G' denote the graph G with weights x'_e=Rx_e for all e∈ G and let X'=RX.  Then we make two observations: x'_e∈ for all e, and properties of deteriminants imply 
    det((L(X')_-1)) = R^n-1det((L(X)_-1)).
  To compute det((L(X')_-1)) we appeal to the matrix-tree theorem; by Lemma <ref> it is equivalent (in terms of the aggregate weight of spanning trees) to view G' as a loopless unweighted multigraph where there are x'_e copies of edge e (so that there are s_i Rr_i∈ copies of edge e_i, each of weight 1).   See Figure <ref>.

Note that x(δ(S))≥ 2 implies that x'(δ(S))≥ 2R.  Thus G' is 2R-edge-connected and by Theorem <ref>, G' has at least nR^n-1 spanning trees; since every edge of G' has weight 1, the matrix-tree theorem states

    det((L(X')_-1))=∑_T∈𝒯_G'∏_f∈ T x'_f ≥ nR^n-1.
 Combining with Equation <ref> we have:


    R^n-1det((L(X)_-1))
        =  det((L(X')_-1)) 
       ≥ nR^n-1.

That is, 
    det((L(X)_-1))≥ n
 and the matrix-tree theorem implies 
    ∑_T∈𝒯_𝒢∏_e∈ T x_e ≥ n.
 

We can now show that the matrix-tree theorem constraint (<ref>) holds for any feasible point of the subtour LP.  We restate our main theorem in slightly more detail.

[Theorem <ref>, restated]
Let x∈^E be a feasible solution to the subtour LP (<ref>) and let G be the complete graph.  Let X be the symmetric matrix where X_ij=X_ji=x_{i, j} and X_ii=0 for all i.  Then X satisfies the matrix-tree theorem constraint:
 
    det((2I-X)_-1) ≥ n.
   Equivalently, 
    ∑_T∈𝒯_G∏_e∈ T x_e ≥ n.



 The subtour LP is bounded, so that every feasible x for the subtour LP can be written as a convex combination of extreme points to the subtour LP.  For any extreme point of the subtour LP y, let Y be the matrix where Y_ij=Y_ji=y_{i, j} and Y_ii=0.  Feasibility of the subtour LP means y(δ(i))=2 for all i∈ V, so the associated Laplacian is 2I-Y.  By Proposition <ref> and the matrix-tree theorem, det((2I-Y)_-1) ≥ n.  

We now show that any convex combination of two extreme points of the subtour LP also satisfies the matrix-tree theorem constraint; extending to general convex combinations is left as an exercise.  Note that the determinant is well-known to be log concave on symmetric positive definite matrixes (see, e.g., section 3.1 of Boyd and Vandenberghe <cit.>)  so that det(tA+(1-t)B)≥det(A)^t det(B)^1-t for 0≤ t≤ 1 if A, B≻ 0.  

Consider two extreme points of the subtour LP, with weighted adjacency matrices A and B.  Denote their graph Laplacians as L(A)=2I-A and L(B)=2I-B respectively.  For a graph with weighted adjacency matrix X, all principal subminors of L(X) are nonnegative so that all principal subminors of L(X)_-1 are as well: these are just the principal subminors of L(X) that include row/column 1 being removed.  This implies that L(X)_-1≽ 0.  By Proposition  <ref>, det((L(A)_-1)), det((L(B)_-1))  ≥ n so that zero cannot be an eigenvalue of (L(A)_-1) or (L(N)_-1) and so both are positive definite.  By log-concavity,

    det   (t(L(A)_-1)+(1-t)(L(B)_-1)) 
       ≥(det(L(A)_-1))^t (det(L(B)_-1))^1-t
       ≥ n^t n^1-t
       = n.

Hence, tA+(1-t)B satisfies the matrix-tree-theorem constraint (<ref>). 



Note that the proof of Theorem <ref> for any x such that x(δ(S))≥ 2 for each S⊂ V with 1≤ |S|≤ |V|-1.  Hence, any x with x(δ(S))≥ 2 for all such S and corresponding weighted adjacency matrix X satisfies 
    det((L(X)_-1)) =∑_T∈𝒯_G∏_e∈ T x_e ≥ n.
  However, it need not be the case that that rows of sum to X, so possibly L(X)≠ 2I-X.




§ CONCLUSION


Theorem <ref> has several implications.  Goemans and Rendl <cit.> show that the subtour LP is stronger than a TSP SDP relaxation of Cvetković et al. <cit.> in the following sense: Any feasible solution for the subtour LP corresponds to a feasible solution of the same cost for the SDP.  Hence, on any given instance, the optimal value of the subtour LP is at least as close to the cost of a TSP solution as the optimal value of the SDP.  Theorem <ref> gives a comparable weakness result for the matrix-tree theorem constraint (<ref>).  Moreover, it implies that Goemans and Rendl <cit.>'s result extends to the case where the matrix-tree theorem constraint (<ref>) is added to the SDP of Cvetković et al. <cit.>.  More generally, our results show that matrix semidefinite inequalities used to impose the matrix-tree theorem are implied by a set of linear inequalities.




§ ACKNOWLEDGMENTS

This work was supported by NSF grant CCF-1908517.  This material is also based upon work supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE-1650441. Any opinions,
findings, and conclusions or recommendations expressed in this material are those of the
authors and do not necessarily reflect the views of the National Science Foundation.  



 
abbrv

