relaxation of graph-TSP with subquartic support.

Organization
------------

In Section \[sec:LP\], we discuss the standard linear programming relaxation for graph-TSP, and in Section \[sec:stc\], we present notation and definitions necessary for defining the circulation network $C(G,T)$. In Section \[sec:lpn\], we show that if, for a subquartic graph, the optimal solution to the linear program has value equal to the number of vertices in $G$, then the network $C(G,T)$ has a circulation of cost zero, implying that the Mömke-Svensson algorithm has an approximation ratio of $4/3$. This observation provides us with some intuition as to how one may attempt to design a better circulation for general subquartic graphs.

In Section \[sec:gen\], we describe two different methods to obtain feasible circulations. In Section \[sec:x-circ\], we detail the method used by Mömke-Svensson and Mucha, which becomes somewhat simpler in the special case of subquartic graphs. This method directly uses values from the optimal solution to the linear program to obtain flow values on edges in the network. In Section \[sec:f-circ\], we present a new method that “rounds” the values from the optimal solution to the linear program. The latter circulation alone leads to an improved analysis over $13/9$ for subquartic graphs, but it 