[*at least*]{} once. This problem is equivalent to the special case of metric TSP where the shortest path distances in $G$ define the metric. It is also equivalent to the problem of finding a connected, Eulerian multigraph in $G$ with the minimum number of edges.

A promising approach to improving upon the factor of $3/2$ for metric TSP is to round a linear programming relaxation known as the Held-Karp relaxation [@held1970traveling]. A lower bound of $4/3$ on its integrality gap can be demonstrated using a family of graph-TSP instances. Since it is widely conjectured that its integrality gap is also upper bounded by $4/3$, proving this for graph-TSP would be a step towards a more comprehensive understanding of the relaxation and would, hopefully, provide insights applicable to metric TSP. However, even in this special case of metric TSP, graph-TSP had also long resisted significant progress before the recent spate of results.

Recent progress on graph-TSP {#sec:prog}
----------------------------

In 2005, Gamarnik et al. presented an algorithm for graph-TSP on cubic 3-edge connected graphs with an approximation factor of $3/2-5/389$ [@gamarnik2005improved], thus proving that Christofides’ approximation factor of $3/2$ is not optimal for this class of graphs. Their approach is based on 