of at most $\frac{46}{33}$ on subquartic graphs. To prove this, we present a different method to upper bound the minimum cost of a circulation on the network $C(G,T)$. Our approximation guarantee actually holds for all graphs that have an optimal solution to a standard linear programming relaxation of graph-TSP with subquartic support.
author:
- 'Alantha Newman[^1]'
bibliography:
- 'tsp.bib'
title: 'An improved analysis of the Mömke-Svensson algorithm for graph-TSP on subquartic graphs'
---

§[Sebő ]{}

Introduction
============

The [*metric*]{} traveling salesman problem (TSP) is one of the most well-known problems in the field of combinatorial optimization and approximation algorithms. Given a complete graph, $G=(V,E)$, with non-negative edge weights that satisfy the triangle inequality, the goal is to compute a minimum cost tour of $G$ that visits each vertex exactly once. Christofides’ algorithm, dating from almost four decades ago, yields a tour with cost no more than $3/2$ times that of an optimal tour [@christofides1976worst]. It remains a major open problem to improve upon this approximation factor.

Recently, there have been many exciting developments relating to [ *graph*]{}-TSP. In this setting, we are given an unweighted graph $G=(V,E)$ and the goal is to find the shortest tour that visits each vertex 