Background of my question is an idea for generating an initial subtour for general symmetric TSPs:

  • Add to a MST a set of edges with minimal weight sum, that renders the resulting graph free of articulation points
  • remove from that graph all MST-edges that appear in at least two shortest paths in the MST between a pair of vertices that is adjacent to the same edge that has been added in the previous step.

The plural for MST was used intentionally to cover modifications due to adding vertex weights.

It is not too hard to come up with an LP formulation of determining the edges of a weight-optimal augmentation of MSTs to biconnected graphs:

for every $(t_u,t_v)$ edge in the MST there must be at least one added edge $e_{ij}\in E\setminus MST$ for which the path $\pi(i,j)$ connecting vertices $i$ and $j$ in the MST contains $(t_u,t_v)$.

Enumerating all such external edges for a given tree-edge $(t_u,t_v)$ is also straight forward:
removing $(t_u,t_v)$ from MST results in two connected components, possibly with an isolated vertex, of which the vertex sets define a complete bipartite graph $K(t_u,t_v) := K(t_v,t_u)$ of which all edges, of course except $(t_u,t_v)$, qualify.

The LP formulation is then

$$\min_{x_{ij}\in [0,1]} \sum_{e_{ij}\in E\setminus MST} {x_{ij}e_{ij}}$$ so that $$\sum_{e_{ij}\in K(t_u,t_v)}{x_{ij}} \ge 1$$


  • has such an augmentation of MSTs already been studied, especially in the context of TSP heuristics of general applicability?

  • is the solution of the LP formulation integral?

  • $\begingroup$ My guess is MST means minimal spanning tree, but I have no idea what TSP and LP mean. In general, it would be good to avoid undefined acronyms. $\endgroup$ – Abdelmalek Abdesselam Mar 3 at 16:56
  • $\begingroup$ @AbdelmalekAbdesselam TSP = Traveling Salesman Problem; LP = Linear Program. Those two abbreviations are commonly known. $\endgroup$ – Manfred Weis Mar 3 at 18:35
  • $\begingroup$ Commonly known perhaps, but not in all circles. $\endgroup$ – Abdelmalek Abdesselam Mar 3 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.