# How does the half-integer spanning-tree problem contain the TSP?

I am trying the understand the following statement from the book of Grotschel, Lovasz and Schrijver:

Here, $$\delta(W)$$ is the set of edges incident to a set of vertices $$W$$.

They define an optimization problem whose solution is a nonnegative real vector. If we add a constraint that all elements of the vector must be integers, then the problem is equivalent to the minimum spanning tree problem, and therefore is solvable in polynomial time. However, if the constraint says that all elements of the vector must be half-integers (that is, either an integer or an integer plus $$1/2$$), the problem becomes NP-complete, as it includes the symmetric travelling salesman problem.

I do not see the connection: why does the problem with half-integer constraints contain the TSP?

• What is $\delta(W)$? Commented Feb 8 at 22:20
• @Highheath $\delta(W)$ is the set of edges with one endpoint in $W$ and the other endpoint in $V\setminus W$. Commented Feb 9 at 8:08

Reduction from Hamiltonian Cycle (which is just a special case of TSP anyway):

Take an unweighted graph $$G$$ and make into a complete weighted graph $$G'$$ by adding a heavy edge (say, $$\ell(e) = 2n$$) for every $$e\not\in E(G)$$, and keeping $$\ell(e)=1$$ for $$e\in E(G)$$.

For any vector $$\mathbf{x}$$ that is a solution to the half-integer spanning tree problem, the subset of edges $$F$$ with $$\mathbf{x}(e) > 0$$ for $$e\in F$$ must obviously make a connected subgraph of $$G$$. This implies that $$|F| \geq n-1$$. If $$|F| = n-1$$, then $$(V(G), F)$$ is a tree and contains at least two leaves $$u,v$$. The edges $$e_u,e_v$$ incident on these leaves must have a weight of 1 in $$\mathbf{x}$$. Therefore the combined weight $$\sum_{e\in F} \mathbf{x}(e)$$ is at least $$\frac{n+1}{2}$$. Also, if $$|F| \geq n+1$$, then of course the combined weight is at least $$\frac{n+1}{2}$$.

On the other hand, if $$|F| = n$$ and every edge has a weight of $$\frac{1}{2}$$ in $$\mathbf{x}$$, then the combined weight is only $$\frac{n}{2}$$. This is only possible if $$(V(G), F)$$ is a cycle.

Therefore, $$\sum_{e\in F} \mathbf{x}(e)\ell(e)$$ can achieve a minimum value of $$\frac{n}{2}$$ if and only if $$G$$ contains a Hamiltonian cycle.

• "For any vector x, the subset of edges F with ... " did you mean here: "For any vector x that is a solution to the half-integer spanning-tree problem"? Commented Mar 28 at 14:04
• Edited, thank you. Commented Mar 29 at 23:02

Let $$P=u_1,u_2,\ldots$$ a solution to the STSP with cost $$l$$, we associate to it the vector $$x_P$$ such that $$(x_P)_e = \frac{1}{2}\#\{i; \{u_i,u_{i+1}\}=e\}$$ (each time the tour takes an edge, we add $$\frac{1}{2}$$ to $$x_P$$). It is a solution to $$\frac{1}{2}$$-Spanning Tree: let $$W$$ be a cut, the tour has to leave it and enter it at least once, so $$x_P\cdot\delta(W)\geq 1$$. Here $$x\cdot l = \frac{1}{2}c(P)$$ where $$c(P)$$ is the usual cost associated with the tour $$P$$. Hence the miminum $$\frac{1}{2}$$-ST solution is at least half the minimum STSP solution.

EDIT: the following is wrong, see comments

The other way around, given $$x$$ a solution, we construct a multigraph on $$V(G)$$ by putting $$2x_{\{u,v\}}$$ edges between each pair of vertices $$u,v$$. Now each vertex has degree at least $$2$$ (since $$x\cdot \delta(\{u\})\ge 1$$), so we find a tour the same way we find Eulerian tours in even degree graphs: find a cycle starting from the source, if some vertices aren't visited by the current tour $$P$$, we have at least two edges in $$\delta(V(P))$$, so we can leave, follow a path in $$V(G)\setminus V(P)$$ until we can go back to $$P$$, an obtain a bigger tour. A tour visiting all vertices uses a subset of the edges we built, and as such has weight at most $$2x\cdot l$$. Hence the minimum STSP solution is at most twice the miminum $$\frac{1}{2}$$-ST solution.

It follows the problems are equivalent.

• In the Eulerian path, isn't it possible that the same vertex is visited more than once? If so, then it is not a solution to STSP. Commented Feb 10 at 20:17
• You are right, I forgot about this condition, and there are some graphs (e.g. 2 cycles with one identified vertex) which have 1/2-spanning trees and no TSP tour. Maybe we have to prove that if there is a TSP tour, any solution to 1/2-ST can be made into a tour? Commented Feb 12 at 10:04
• Maybe the minimum 1/2-ST is always a TSP tour? Commented Feb 12 at 12:09