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

Question

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?

Answer 1

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.

Answer 2

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.