1
$\begingroup$

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

enter image description here

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?

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

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Feb 10 at 20:17
  • $\begingroup$ 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? $\endgroup$
    – pasthec
    Feb 12 at 10:04
  • $\begingroup$ Maybe the minimum 1/2-ST is always a TSP tour? $\endgroup$ Feb 12 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.