patternMinor
How does the half-integer spanning-tree problem contain the TSP?
Viewed 0 times
problemtspthehalfcontaindoeshowspanningintegertree
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#165460, answer score: 2
Revisions (0)
No revisions yet.