---
abstract: |
    Recently, Mömke and Svensson presented a beautiful new approach for the traveling salesman problem on a graph metric (graph-TSP), which yielded a $\frac{4}{3}$-approximation guarantee on subcubic graphs as well as a substantial improvement over the $\frac{3}{2}$-approximation guarantee of Christofides’ algorithm on general graphs. The crux of their approach is to compute an upper bound on the minimum cost of a circulation in a particular network, $C(G,T)$, where $G$ is the input graph and $T$ is a carefully chosen spanning tree. The cost of this circulation is directly related to the number of edges in a tour output by their algorithm. Mucha subsequently improved the analysis of the circulation cost, proving that Mömke and Svensson’s algorithm for graph-TSP has an approximation ratio of at most $\frac{13}{9}$ on general graphs.

    This analysis of the circulation is local, and vertices with degree four and five can contribute the most to its cost. Thus, hypothetically, there could exist a subquartic graph (a graph with degree at most four at each vertex) for which Mucha’s analysis of the Mömke-Svensson algorithm is tight. We show that this is not the case and that Mömke and Svensson’s algorithm for graph-TSP has an approximation guarantee 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 [*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 finding a cycle cover for which they can upper bound the number of components. This general approach was also taken by Boyd et al. who combined it with polyhedral ideas to obtain approximation guarantees of $4/3$ for cubic graphs and $7/5$ for subcubic graphs, i.e. graphs with degree at most three at each vertex [@boyd2011tsp]. Shortly afterwards, Oveis Gharan et al. proved that a subtle modification of Christofides’ algorithm has an approximation guarantee of $3/2-\eps_0$ for graph-TSP on general graphs, where $\eps_0$ is a fixed constant with value approximately $10^{-12}$ [@gharan2011randomized].

Mömke and Svensson then presented a beautiful new approach for graph-TSP, which resulted in a substantial improvement over the $3/2$-approximation guarantee of Christofides [@DBLP:conf/focs/MomkeS11]. Their approach also lead to a surprisingly simple algorithm with an $4/3$-approximation guarantee for subcubic graphs. We will discuss their algorithm in more detail in Section \[sec:MS\], since our paper is directly based on their approach. Ultimately, they were able to prove an approximation guarantee of $1.461$ for graph-TSP. Mucha subsequently gave an improved analysis, thereby proving that Mömke and Svensson’s algorithm for graph-TSP actually has an approximation ratio of at most $13/9$ [@DBLP:conf/stacs/Mucha12]. §and Vygen introduced an approach for graph-TSP based on ear decompositions and matroid intersection, which incorporated the techniques of Mömke and Svensson, and improved the approximation ratio to $7/5$, where it currently stands [@sebHo2012shorter]. For the special case of $k$-regular graphs, Vishnoi gave an algorithm for graph-TSP with an approximation guarantee that approaches 1 as $k$ increases [@vishnoi2012permanent].

Some of the new techniques for graph-TSP have also lead to progress on the metric $s$-$t$-path TSP, in which the goal is to find a path between two fixed vertices that visits every vertex at least once. Mömke and Svensson applied their techniques to the $s$-$t$-path graph-TSP for which they obtained a 1.586-approximation algorithm, improving on the previously best-known bound of $5/3$ due to Hoogeveen [@hoogeveen]. Mucha improved this ratio slightly to $19/12$ [@DBLP:conf/stacs/Mucha12]. §and Vygen gave a $3/2$-approximation algorithm for $s$-$t$-path graph-TSP, which matches the integrality gap of the standard linear programming relaxation for this problem [@sebHo2012shorter]. Even more recently, Gao gave another, extremely elegant, $3/2$-approximation for this problem [@gao2013lp]. His result was based on ideas introduced for the $s$-$t$-path TSP in general metrics by An et al. who gave a 1.618 approximation for this problem [@an2012improving], improving on the algorithm of Hoogeveen [@hoogeveen]. §improved the approximation ratio for the $s$-$t$-path TSP in general metrics to $8/5$, where it currently stands [@sebHo2013eight].

Mömke-Svensson’s approach to graph-TSP {#sec:MS}
--------------------------------------

Christofides’ algorithm for graph-TSP finds a spanning tree of the graph and adds to it a $J$-join, where $J$ is the set of vertices that have odd degree in the spanning tree. Since the spanning tree is connected, the resulting subgraph is clearly connected, and since the $J$-join corrects the parity of the spanning tree, the resulting subgraph is Eulerian. In contrast, the recent approach of Mömke and Svensson is based on removing an odd-join of the graph, which yields a possibly disconnected Eulerian subgraph. Thus, to maintain connectivity, one must double, rather than remove, some of the edges in the odd-join. The key step in proving the approximation guarantee of the algorithm is to show that many edges will actually be removed and relatively few edges will be doubled, resulting in a connected, Eulerian subgraph with few edges. First, Mömke and Svensson design a circulation network, $C(G,T)$, which is constructed based on the input graph $G$, an optimal solution to a linear programming relaxation for graph-TSP, and a carefully chosen spanning tree $T$. Using techniques of Naddef and Pulleyblank [@naddefpulleyblank], Mömke and Svensson show how to sample an odd-join of size $|E'|/3$, where $E'$ is the subset of edges contained in the circulation network $C(G,T)$. The number of edges that are doubled to guarantee connectivity is directly related to the minimum cost of a circulation of $C(G,T)$. Lemma 4.1 from [@DBLP:conf/focs/MomkeS11] relates this cost to the size of a solution output by their algorithm:

[**[[@DBLP:conf/focs/MomkeS11]]{}**]{}\[lem:MS\] Given a 2-vertex connected graph $G$ and a depth first search tree $T$ of $G$, let $C^*$ be a minimum cost circulation for $C(G,T)$ of cost $c(C^*)$. Then there is a spanning Eulerian multigraph in $G$ with at most $\frac{4}{3}n + \frac{2}{3} c(C^*)$ edges.

We defer a precise description of the circulation network $C(G,T)$ to Section \[sec:prelim\], where we formulate it using different notation from that in [@DBLP:conf/focs/MomkeS11]. For the moment, we emphasize that if one can prove a better upper bound on the value of $c(C^*)$, then this directly implies an improved upper bound on the number of edges in a tour output by Mömke and Svensson’s algorithm.

Our contribution
----------------

We consider the graph-TSP problem for [*subquartic*]{} graphs, i.e. graphs in which each vertex has degree at most four. As pointed out in Lemma 2.1 of [@DBLP:conf/focs/MomkeS11], we can assume that these graphs are 2-vertex connected. The best-known approximation guarantee for these graphs is inherited from the general case, even when the graph is 4-regular, and is therefore $7/5$ due to §and Vygen. For subquartic graphs, we give an improved upper bound on the minimum cost of a circulation for $C(G,T)$. Using Lemma \[lem:MS\], this leads to an improved approximation guarantee of $46/33$ for graph-TSP on these graphs. Before we give an overview of our approach, we first explain our motivation for studying graph-TSP on this restricted class of graphs.

As mentioned in Section \[sec:prog\], graph-TSP is now known to be approximable to within $4/3$ for subcubic graphs. So, on the one hand, trying to prove the same guarantee for subquartic graphs is arguably a natural next step. Additionally, it is a well-motivated problem to study the graph-TSP on sparse graphs, because the support of an optimal extreme point solution to the standard linear programming relaxation (reviewed in Section \[sec:LP\]) has at most $2n-1$ non-zero edges (see Theorem 4.9 in [@cornuejols1985traveling]). Thus, any graph that corresponds to the support of such an an optimal solution to the standard linear program has average degree less than four.

However, our actual motivation for studying graphs with degree at most four has more to do with understanding the Mömke-Svensson algorithm than with an abstract interest in subquartic graphs. The basic approach to computing an upper bound on the minimum cost circulation in $C(G,T)$ used in both [@DBLP:conf/focs/MomkeS11] and [@DBLP:conf/stacs/Mucha12] is to specify flow values on the edges of $C(G,T)$ that are functions of an optimal solution to the linear programming relaxation for graph-TSP on the graph $G$. The cost of the circulation obtained using these values can be analyzed in a local, vertex by vertex manner. Mucha showed that vertices with degree four or five potentially increase the cost of the circulation the most [@DBLP:conf/stacs/Mucha12]. In fact, one could hypothetically construct a tight example for Mucha’s analysis of the Mömke-Svensson algorithm on a graph where each vertex has degree at most four (or where each vertex has degree at most five). It therefore seems worthwhile to determine if the cost of the circulation can be improved on subquartic graphs. Our results actually hold for a slightly more general class of graphs than subquartic graphs: they hold for any graph that has an optimal solution to the standard linear programming 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 does not improve on the best-known guarantee of $7/5$. However, as we finally show in Section \[sec:combine\], if we take the best of the two circulations, we can show that at least one of the circulations will lead to an approximation guarantee of at most $46/33$.

We remark that our notation differs from that in [@DBLP:conf/focs/MomkeS11] and [@DBLP:conf/stacs/Mucha12], even though we are using exactly the same circulation network and we use their approach for obtaining the feasible circulation described in Section \[sec:x-circ\]. This different notation allows us to more easily analyze the tradeoff between the two circulations.

Preliminaries: Notation and definitions {#sec:prelim}
=======================================

Throughout this paper, we make use of the following well-studied linear programming relaxation for graph-TSP.

Linear program for graph-TSP {#sec:LP}
----------------------------

For a graph $G=(V,E)$, the following linear program is a relaxation of graph-TSP. We refer to Section 2 of [@DBLP:conf/focs/MomkeS11] for a discussion of its derivation and history. $$\begin{aligned}
& \min & \sum_{e \in E} y_e \\
y(\delta(S)) & \geq &  2  ~~ {\text{for }} \emptyset \neq S \subset V,   \\
y & \geq & 0.\end{aligned}$$ We denote this linear program by $LP(G)$ and we denote the value of an optimal solution for $LP(G)$ by $OPT_{LP}(G)$. Let $n$ be the number of vertices in $V$. We can assume that $G$ has the following two properties: (i) $|E| \leq 2n-1$, and (ii) $G$ is 2-vertex connected. Assumption (i) is based on the fact that any extreme point of $LP(G)$ has at most $2n-1$ edges (see Theorem 4.9 in [@cornuejols1985traveling]), and restricting the graph to the edges in the support of an extreme point with optimal value does not increase the optimal value $OPT_{LP}(G)$. Assumption (ii) is based on Lemma 2.1 from [@DBLP:conf/focs/MomkeS11]. We note that the two theorems we just cited may have to be applied multiple times to guarantee that $G$ has the desired properties (i) and (ii).

\[lem:xisone\] Let $G=(V,E)$ be a 2-edge connected graph. Then there exists $x \in
LP(G),~ x \leq 1$ minimizing the sum of coordinates of a vector in $LP(G)$.

Let $x \in LP(G)$ be an extreme point that minimizes the sum of coordinates of a vector in $LP(G)$. Suppose that there is some $x_e >
1$ for $e \in E$. Since $G$ is 2-edge connected, each cut crossing edge $e$ must include at least one other edge. Suppose that $x_e$ does not belong to any tight cuts, i.e. $x(\delta(S)) > 2$ for all $S$ such that $e \in \delta(S)$. Then we can decrease the value of $x_e$ and obtain a smaller solution, which is a contradiction to the optimality of $x$.

Therefore, suppose that $e$ is in exactly one tight cut. Since there is at least one other edge besides $e$ crossing this cut and this edge must have value strictly less than 1, we can increase the $x$-value on this edge and decrease $x_e$. Since the cut is still tight, the solution is still feasible and has the same value as the original solution.

The other case to consider is when $e$ belongs to at least two tight cuts. Consider the cuts $(S+A,\bar{S}\setminus{A})$ and $(S + B,
\bar{S}\setminus{B})$, where $S, A,$ and $B$ are disjoint. Suppose that $e=ij$ and $i \in S$ and $j \in \bar{S}\setminus{A \cup B}$. Then edge $e$ crosses both these cuts. $$\begin{aligned}
\delta(S+ A) & = & E(S,\bar{S}\setminus{A \cup B}) + E(S,B) +  E(A, B)
+ E(A, \bar{S}\setminus{A \cup B}),\\
\delta(S+B) & = &  E(S,\bar{S}\setminus{A \cup B}) + E(S,A) + E(A,B) +
E(B, \bar{S}\setminus{A \cup B}).\end{aligned}$$ Then we have: $$\begin{aligned}
x(\delta(S \cup A)) + x(\delta(S \cup B)) & = & 2\cdot x(E(S,\bar{S}\setminus{A
  \cup B})) + 2\cdot x(E(A,B))  + E(B,S) \label{eq:new}\\ && + ~ E(A,
\bar{S}\setminus{A \cup B}) + E(A,S) + E(B, \bar{S}\setminus{A \cup
  B}).\nonumber\end{aligned}$$ Since both of these cuts are tight and since $x_e > 1$ and $x_e \in
E(S, \bar{S}\setminus{A \cup B})$, it follows that: $$\begin{aligned}
x(\delta(S\cup A)) + x(\delta(S\cup B)) - 2\cdot x(E(S,
\bar{S}\setminus{A\cup B})) & < & 2.\end{aligned}$$ By , this implies that: $$\begin{aligned}
2\cdot x(E(A,B)) +  E(B,S)  +  E(A, \bar{S}\setminus{A \cup B}) +
E(A,S) + E(B, \bar{S}\setminus{A \cup B}) ~ < ~ 2. \label{eq:new2}\end{aligned}$$ However, if we consider the cut $E(A\cup B, ~V\setminus{A\cup B})$, we know that $x(E(A\cup B, ~V\setminus{A\cup B})) \geq 2$. $$\begin{aligned}
x(E(A\cup B, V\setminus{A \cup B})) & = & x(E(A,S)) + x(E(A,
\bar{S}\setminus{A \cup B})) + x(E(B,S)) \label{eq:new3} \\ && +~
x(E(B, \bar{S}\setminus{A \cup B}) ).\nonumber\end{aligned}$$ Since the quantity in is at most the quantity on the lefthand side of , it must be strictly less than 2, which is a contradiction. Therefore, we can conclude that the edge $x_e$ occurs in at most one tight cut, a case that we addressed above.

Applying Lemma \[lem:xisone\], we define $x \in {\mathbb R}^{|E|}$ to be an optimal solution for $LP(G)$ with the following properties: (i) the support of $x$ contains at most $2n-1$ edges, (ii) the support of $x$ is 2-vertex connected, and (iii) $x \leq 1$. We will refer to the set of values $\{x_e\}$ for $e \in E$ as $x$-values.

Let $\sum_{e \in E} x_e = OPT_{LP}(G) = (1+\eps)n$ for some $\eps$, where $0 \leq \eps \leq 1$. We will eventually make use of the following definitions.

The [*excess*]{} $x$-value $\eps(v)$ at a vertex $v$ is the amount by which the total value on the adjacent edges exceeds 2, i.e $\eps(v) =
x(\delta(v)) -2.$

A vertex $v \in V$ is called [*heavy*]{} if $\x(\delta(v)) > 2$.

The following fact will be useful in our analysis. If $OPT_{LP}(G) = (1+\eps)n$, then, $$\begin{aligned}
\sum_{v \in V} \x(\delta(v)) & = & \sum_{v \in V} (2 + \eps(v)) ~~ =
~~ 2 (1 + \eps)n.\end{aligned}$$ This implies, $$\begin{aligned}
\sum_{v \in V} \eps(v) & = & 2 \eps n.\label{eps-vertices}\end{aligned}$$

Spanning trees and circulations {#sec:stc}
-------------------------------

Let us recall some useful definitions from the approach of Mömke and Svensson [@DBLP:conf/focs/MomkeS11] that we use throughout this paper.

A [*greedy DFS tree*]{} is a spanning tree formed via a depth-first search of $G$. If there is a choice as to which edge to traverse next, the edge with the highest $\x$-value is chosen.

For a given graph $G$ and an optimal solution to $LP(G)$, let $T$ denote a greedy DFS tree with root $r$. We orient $T$ to be an arborescence with root r, and we orient $B(T):= E \setminus{T}$ “backwards", that is, so that each edge in $B(T)$ forms an directed cycle with a path of the tree. This is possible since $T$ is a DFS tree. We use the notation $(i,j)$ to denote an edge directed from $i$ to $j$. Note that once we have fixed a tree $T$, all edges in $E$ can be viewed as directed edges. When we wish to refer to an undirected edge in $E$, we use the notation $ij \in E$. With respect to the greedy DFS tree $T$, we have the following definitions.

An [*internal*]{} node in $T$ is a vertex that is neither the root of $T$ nor a leaf in $T$. We use $T_{int}$ to denote this subset of vertices.

An [*expensive*]{} vertex is a vertex in $T_{int}$ with two incoming edges that belong to $B(T)$. We use $T_{exp}$ to denote this subset of vertices.

As we will see in Lemma \[lem:four\], expensive vertices are the vertices that can contribute to the cost of $C(G,T)$. The root can also contribute a negligible value of either one or two to the cost of $C(G,T)$. For the sake of simplicity, we ignore the contribution of the root in most of our calculations.

[**Fact.** ]{}\[exp:bound\] The number of expensive vertices is bounded as follows: $|T_{exp}| \leq n/2$.

A [*branch*]{} vertex in $T$ is a vertex with at least two outgoing tree edges.

Note that the root of $T$ is not be a branch vertex, since $G$ is 2-vertex connected.

\[lem:bex\] If $G$ is subquartic, then a branch vertex in $T_{int}$ is not expensive.

In a graph with vertex degree at most four, a branch vertex can have at most one incoming back edge and therefore cannot be expensive.

A [*tree cut*]{} is the partition of the vertices of the tree $T$ induced when we remove an edge $(u,v) \in T$.

For each edge $(i,j) \in B(T)$, let $b(i,j) \leq 1$ be a non-negative value.

Consider a tree cut corresponding to edge $(u,v) \in T$ and remove all back edges $(w,u) \in B(T)$, where $w$ belongs to the subtree of $v$ in $T$. We say that the remaining back edges that cross this tree cut [*cover*]{} the cut. If the total $b$-value of the edges that cover the cut is at least 1, then we say that this tree cut is [ *satisfied by $b$*]{}.

We extend this definition to the vertices of $T$.

A vertex $v$ in $T$ is [*satisfied by $b$*]{} if for each adjacent outgoing edge in $T$, the corresponding tree cut is satisfied by $b$. On the other hand, if there is at least one adjacent outgoing edge whose corresponding tree cut is not satisfied by $b$, then the vertex $v$ is [*unsatisfied by $b$*]{}.

Mömke and Svensson define a circulation network, $C(G,T)$ (see Section 4 of [@DBLP:conf/focs/MomkeS11]), and use the cost of a feasible circulation to upper bound the length of a TSP tour in $G$. (See Lemma \[lem:MS\].)

\[lem:four\] Let $b: B(T) \rightarrow [0,1]$ and let $G$ be a subquartic graph. If each internal vertex in $T$ is satisfied by $b$, then there is a feasible circulation of $C(G,T)$ whose cost is upper bounded by the following function: $$\begin{aligned}
\sum_{j \in T_{exp}} \max \left\{ 0, ~\left(\sum_{i:(i,j) \in B(T)}
b(i,j)\right) -1\right\}.\label{cost-func-main}\end{aligned}$$

The ultimate purpose of the circulation network $C(G,T)$ in [@DBLP:conf/focs/MomkeS11] is to find a subset of back edges, $S
\subseteq B(T)$, so that $T\cup S$ is 2-vertex connected and so that the following cost function has a low value: $$\begin{aligned}
\sum_{j \in T_{exp}} \max \left\{ 0, ~\left(\sum_{i:(i,j) \in S} 1
\right) -1\right\}.\end{aligned}$$ If we assign values to the edges in $B(T)$, then the only vertices that can add to the cost function are the expensive vertices, since the maximum value allowed on an edge is one. When computing the cost of the 2-vertex connected subgraph that corresponds to an integral circulation of $C(G,T)$, Mömke and Svensson use a special rule to account for the cost on a branch vertex $u$: for each outgoing edge $(u,v) \in T$, the number of incoming back edges in the form of $(w,u)$ emanating from the subtree rooted at $v$ minus one is added to the cost. However, in the case of subquartic graphs, a branch vertex is not expensive (Lemma \[lem:bex\]). Thus, in this special case, the simplified cost function in is valid.

If $b: B(T) \rightarrow \{0,1\}$ is an integral function and every internal vertex in $T$ is satisfied by $b$, then the edges with $b$-value 1 form a set $S$ such that $T+S$ is 2-vertex connected. We can instead use a fractional function $b:B(T) \rightarrow [0,1]$ to obtain an upper bound on the cost of such a 2-vertex connected subgraph using the cost function .

One can verify that all internal vertices being satisfied by $b$ corresponds to the edges with unit demand in the network $C(G,T)$ having their demands satisfied and that, for subquartic graphs, the cost function equals the cost function used in [@DBLP:conf/focs/MomkeS11] to upper bound the cost of a circulation in $C(G,T)$.

Although finding $b$-values for the back edges that satisfy all the vertices in $T_{int}$ is equivalent to finding a feasible circulation of $C(G,T)$, and we could have stuck to the notation presented in [@DBLP:conf/focs/MomkeS11], we believe our notation results in a clearer presentation of our main theorems.

Subquartic graphs: $OPT_{LP}(G) = n$ {#sec:lpn}
====================================

We now show that in the special case when $OPT_{LP}(G)=n$ and $G$ is subquartic, there is a circulation with cost zero. Note that if $|E|
= n$, then each edge in $E$ must have $x$-value 1. Thus, $G$ is a Hamiltonian cycle. If $|E| > n$, then we can show that we can find a greedy DFS tree $T$ for $G$ such that each edge $ij \in E$ with $x$-value $x_{ij} = 1$ (a “1-edge”) belongs to $T$.

\[lem:one-edge\] When $OPT_{LP}(G) = n$ and $|E| > n$, there is a greedy DFS tree $T$ such that all 1-edges are in $T$.

By the assumptions in the lemma, there is some edge $ij
\in E$ that has $x$-value $x_{ij} < 1$. In this case, both vertices $i$ and $j$ can have at most one adjacent 1-edge. Thus, we choose one of these vertices, say $i$, to be the root of the greedy DFS tree. If $i$ is adjacent to a 1-edge, then this 1-edge belongs to the resulting tree by the rules defining the construction of a greedy DFS tree.

Suppose that after we are done constructing the greedy DFS tree, there is a back edge $(i,j)$ that has $x$-value 1. Then when vertex $j$ was traversed in the depth-first search, it should have taken this edge as a tree edge. Otherwise, the edge it did traverse/add to the tree also had an $x$-value of 1, which is a contradiction because a vertex with degree at least three can have at most one adjacent 1-edge, since the $x$-value at each vertex is exactly two, i.e. $x(\delta(i)) = 2$, when $OPT_{LP}(G)=n$.

For the rest of Section \[sec:lpn\], let $T$ denote a greedy DFS tree in which all 1-edges are tree edges.

\[lem:two-edge\] If $OPT_{LP}(G)=n$, $G$ is subquartic and each back edge $(i,j) \in
B(T)$ is assigned value $f(i,j) = 1/2$, then each vertex in $T_{int}$ is satisfied by $f$.

Suppose we set $g(i,j) = x_{ij}$ for each back edge. Then by the cut argument of Mömke and Svensson, each tree cut is satisfied by $g$, because $LP(G) = n$ and each vertex $v \in V$ has $x(\delta(v))=2$. Since there are no 1-edges in the set of back edges, this implies that each tree cut must in fact be covered by at least two edges. Thus, setting $f(i,j) = 1/2$ results in each tree cut being satisfied by $f$.

\[lem:three-edge\] If $OPT_{LP}(G)=n$ and $G$ is subquartic, setting $f(i,j) = 1/2$ for each edge $(i,j) \in B(T)$ yields a circulation with cost zero.

This follows from the fact that each vertex in $T_{int}$ has in-degree at most two and therefore the total $f$-value coming into a vertex is at most one. Thus, the circulation value is zero. (Note that the root can contribute $1/2$ to the circulation, but the minimum circulation is integral and will therefore still be zero.)

If $OPT_{LP}(G) =n$ and $G$ is a subquartic graph, then $G$ has a TSP tour of length at most $4n/3$.

Subquartic graphs: General case {#sec:gen}
===============================

In this section, we consider the general case of subquartic graphs. For a graph $G=(V,E)$, [^2] suppose $OPT_{LP}(G) = (1+\eps)n$ for some $\eps > 0$. There is a fixed greedy DFS tree $T$ as defined in Section \[sec:stc\]. If we assign values to the edges in $B(T)$, then the only vertices that can add to the cost function are the expensive vertices, as we have defined them, since the maximum value allowed on an edge is one. Let $x(i,j) =
x_{ij}$ for all back edges in $B(T)$. Recall that the $\{x_{ij}\}$ values are obtained from the solution to $LP(G)$ in Section \[sec:LP\].

\[lem:tree-cut-sat\] A vertex $v$ in $T_{int}$ has at most one outgoing tree edge whose corresponding tree cut is not satisfied by $x$.

If $v$ has only one outgoing tree edge, then the lemma holds. Suppose $v$ is a branch vertex. First, let us consider the case when $v$ has three outgoing tree edges. In this case, if we consider the tree cut corresponding to one of these outgoing edges, the total $x$-value of the edges that cover this cut must be at least $1$, since this set of edges plus the tree edge forms a cut in the graph (which has $x$-value at least 2 by the constraints in $LP(G)$). Since the tree edge has $x$-value at most 1, the edges that cover the cut must have value at least 1. This argument can be applied to the tree cut corresponding to each of the three outgoing edges. So when $v$ has three outgoing tree edges, then $v$ is satisfied by $x$.

Now let us consider the case when $v$ has two outgoing tree edges. In a subquartic graph, there is at most one incoming back edge into a branch vertex $v$. This back edge comes from the subtree connected to one of the outgoing tree edges. It may be the case that the tree cut corresponding to this tree edge is not satisfied by $x$. However, in this case, consider the other outgoing tree edge that is connected to a subtree from which there is no back edge connected directly to $v$. If we remove this outgoing tree edge, the $x$-value crossing this cut is at least 1 and all of the edges in this cut cover the cut.

A vertex $v \in T_{int}$ that is satisfied by $x$ is called [ *LP-satisfied*]{}.

A vertex $v \in T_{int}$ that is not satisfied by $x$ is called [ *LP-unsatisfied*]{}.

\[lem:expensive\] An expensive vertex is LP-satisfied.

An expensive vertex $v$ in $T_{int}$ has two incoming back edges. Since each vertex has maximum degree four, it may not have any outgoing back edges. Thus, the cut formed by removing the incoming tree edge is crossed by back edges that have $x$-value at least $1$ and these back edges also cover the tree cut obtained by removing the outgoing tree edge adjacent to $v$.

\[lem:heavy\] An LP-unsatisfied vertex is heavy.

If the vertex $v$ is a non-branch vertex, then consider the north cut and the south cut on vertex $v$. Each of these cuts has value greater than $1$, otherwise the cut would be LP-satisfied.

If the vertex is a branch vertex with three outgoing tree edges, it must be LP-satisfied. If it has two outgoing tree edges and one incoming back edge, then consider the tree cut obtained by removing the outgoing tree edge directed towards the subtree from which the incoming back edge emanates. (The other tree cut is satisfied by $x$.) Let $S \subset B(T)$ denote the back edges that cover this tree cut. If this tree cut is not satisfied by $x$, then the $x$-value of the tree edge and the incoming back edge must be greater than one. Similiarly, note that the edges in $S$ plus the incoming tree edge and the other outgoing tree edge form a cut. Since the value $x(S) < 1$, it follows that the total $x$-value of the two tree edges in this cut is greater than $1$. Thus, the vertex $v$ is heavy.

The reason we emphasize that an LP-unsatisfied vertex is heavy is that we can use the excess $x$-value of this vertex to increase an edge that covers the unsatisfied tree cut corresponding to one of its adjacent outgoing edges so that this tree cut becomes satisfied. We also wish to use the excess $x$-value of an expensive vertex to pay for some of its contribution to the cost function incurred by the back edges coming into the vertex. For each vertex $v$, we want to use the quantity $\eps(v)$ at most once in this payment scheme. This will be guaranteed by the fact that LP-unsatisfied vertices and expensive vertices are disjoint sets.

The $x$-circulation {#sec:x-circ}
-------------------

In this section, we use the $x$-values to obtain an upper bound on the cost of a circulation, essentially following the arguments of Mömke and Svensson [@DBLP:conf/focs/MomkeS11] and Mucha [@DBLP:conf/stacs/Mucha12]. We present the analysis here, since we refer to it in Section \[sec:combine\] when we analyze the cost of taking the best of two circulations. Also, the arguments can be somewhat simplified due to the subquartic structure of the graph, which is useful for our analysis.

For each back edge in $B(T)$, set $x(i,j) = x_{ij}$, where $x \in
\mathbb{R}^{|E|}$ is an optimal solution to $LP(G)$. (For a vertex $j
\in T_{int}\setminus{T_{exp}}$, we can actually set $x(i,j) = 1$, since there is at most one incoming back edge to vertex $j$, but this does not change the worst-case analysis.)

For each vertex $j \in T_{exp}$, let $\xij \leq \xaj$ denote the $x$-values of the two incoming back edges to vertex $j$. Let $c_x(j)
= \xij + \xaj -1 - \eps(j)$.

We will show that there is a function $x': B(T) \rightarrow [0,1]$ such that each vertex in $T_{int}$ is satisfied by $x'$ and the cost of the circulation can be bounded by: $$\begin{aligned}
\sum_{j \in T_{exp}} \max \left\{0, \left(\sum_{i: (i,j) \in B(T)}
x'(i,j)\right) - 1 \right\} & \leq & \sum_{j \in T_{exp}}
\max\{0,c_x(j)\} + \sum_{j \in T_{int}}\eps(j). ~\label{cost-func}\end{aligned}$$

\[lem:fact\] For an expensive vertex $j \in T_{exp}$, the following holds: $$\begin{aligned}
2\cdot x_{max}(j) + \xi(j) \leq 2 + \eps(j).\end{aligned}$$

By the construction of $T$, we note that the $x$-value of the tree edge leaving vertex $j$ must be at least $\xaj$. Thus, the above inequality holds.

\[lem:thirteen\] The value $c_x(j)$ can be upper bounded as follows: $$\begin{aligned}
c_x(j) & \leq & \frac{\xij}{2} - \frac{\eps(j)}{2} ~ \leq ~ 1 - \xij.\end{aligned}$$

For a vertex $j \in T_{exp}$, we can use Lemma \[lem:fact\] to show: $$\begin{aligned}
c_x(j) ~= ~\xa(j) + \xi(j) - 1 - \eps(j) & \leq & (2 + \eps(j) -
\xi(j))/2 + \xi(j) -1 -\eps(j)\\
& = & \frac{\xi(j)}{2} - \frac{\eps(j)}{2}.\end{aligned}$$ Lemma \[lem:fact\] also implies: $$\begin{aligned}
\frac{x_{min}(j)}{2} - \frac{\eps(j)}{2} & \leq & 1-\xaj ~ \leq ~ 1-\xij.\end{aligned}$$

\[lem:fourteen\] For a vertex $j \in T_{exp}$, $c_x(j) \leq 1/3$.

We have: $$\begin{aligned}
c_x(j) & \leq & \min\left\{\frac{\xij}{2}, ~1-\xij\right\}.\end{aligned}$$ This implies that $c_x(j) \leq 1/3$, which occurs when $\xij = 2/3$, as shown by Mucha [@DBLP:conf/stacs/Mucha12].

To make the circulation feasible, we need to increase the $x$-values of some of the back edges in $B(T)$ so that all of the LP-unsatisfied vertices become satisfied. By Lemma \[lem:heavy\], these vertices are heavy. Thus, we will use $\eps(v)$ for an LP-unsatisfied vertex $v$ to “pay" for increasing the $x$-value on an appropriate back edge. For ease of notation, we now set $x'(u,v) := x(u,v)$ for all $(u,v) \in B(T)$. We will update the $x'(u,v)$ values so that each LP-unsatisfied vertex is satisfied by $x'$.

Consider an LP-unsatisfied, non-branch vertex $j \in T$, and consider the tree cut corresponding to the single edge $(j,t_2)$ outgoing from $j$ in $T$. Let $S \subseteq B(T)$ denote the edges that cover this tree cut. Let $(i,j), (j,k) \in B(T)$ represent the adjacent back edges, and let $(t_1,j) \in T$ denote the incoming tree edge. Recall that in this tree cut, both edges $(j,t_2)$ and $(i,j)$ are removed and the remaining edges in $B(T)$ that cross this cut [*cover*]{} it. We have: $$x_{jt_2} + x_{jt_1} + x(j,k) + x(i,j) = 2 + \eps(j).$$ Since, $$\begin{aligned}
x(S) + x_{jt_2} + x(i,j) ~\geq~ 2, \quad x(S) + x(j,k) + x_{jt_1} ~ \geq ~ 2,\end{aligned}$$ it follows that $$\begin{aligned}
2 \cdot x(S) ~ \geq ~ 2 - \eps(j) \quad \Rightarrow \quad x(S) ~ \geq
~ 1 - \eps(j)/2.\end{aligned}$$ Let $(u,v) \in S$ be an arbitrary edge in $S$. We will update the value of $x'(u,v)$ as follows: $$x'(u,v) := \min\{1, ~x'(u,v) +
\eps(j)/2\}.$$ We use this recursive notation, because a back edge’s value can be increased multiple times in the process of satisfying all LP-unsatisfied vertices.

If $j$ is an LP-unsatisfied branch vertex, then it must have two outgoing edges in $T$ (call them $(j,t_2)$ and $(j,t_3)$) and one incoming back edge $(i,j) \in B(T)$. Let $(t_1,j)$ denote the incoming tree edge. Suppose that vertex $i$ is in the subtree hanging from $t_2$ in $T$. Then consider the tree cut corresponding to edge $(j,t_2)$, i.e. remove edges $(j,t_2)$ and $(i,j)$. Let $S \subset
B(T)$ denote the back edges that cover this tree cut. Then we have, $$\begin{aligned}
x(S) + x(j,t_2) + x(i,j) ~ \geq ~ 2, \quad x(S) + x(j,t_3) + x(t_1,j)
~ \geq ~ 2.\end{aligned}$$ We can conclude that $x(S) \geq 1-\eps(j)/2$. Thus, as we did previously, we can increase the $x'$-value of some edge in $S$ by the quantity $\eps(j)/2$. The following Lemma follows by the construction of the $x'$ values.

\[lem:fix\] The cost of satisfying all of the LP-unsatisfied vertices is at most $\sum_{j \in T_{int}\setminus{T_{exp}}} \eps(j)/2$. In other words: $$\begin{aligned}
\sum_{(u,v) \in B(T)} (x'(u,v) - x(u,v)) & \leq & \sum_{j \in
  T_{int}\setminus{T_{exp}}} \frac{\eps(j)}{2}.\end{aligned}$$

Since all vertices in $T$ are now satisfied by $x'$, the $x'$-values can be used to compute an upper bound on the cost of a feasible circulation of $C(G,T)$.

\[thm:two\] The function $x': B(T) \rightarrow [0,1]$ corresponds to a feasible circulation of $C(G,T)$ with cost at most: $$\begin{aligned}
\sum_{j \in T_{exp}} \max\{0,~c_x(j)\} + \sum_{j \in T_{int}}\eps(j).\end{aligned}$$

By construction, every vertex in $T_{int}$ is satisfied by $x'$. Thus, the $x'$-values correspond to a feasible circulation of $C(G,T)$. The cost of the circulation based on the $x'$-values is: $$\begin{aligned}
\sum_{j \in T_{exp}} \max \left\{0, \left(\sum_{i: (i,j) \in B(T)}
x'(i,j)\right) - 1 \right\} & \leq & \sum_{j \in T_{exp}} \max
\left\{0, \left(\sum_{i: (i,j) \in B(T)} x(i,j)\right) - 1 \right\}
\\ 
&& + \sum_{(u,v) \in B(T)} (x'(u,v) - x(u,v)).\end{aligned}$$ We have: $$\begin{aligned}
\sum_{j \in T_{exp}} \max \left\{0, \left(\sum_{i: (i,j) \in B(T)}
x(i,j)\right) - 1 \right\} & = & \sum_{j \in T_{exp}} \max \left\{0,
\xaj + \xij - 1 \right\}\\
& \leq & \sum_{j \in T_{exp}} \left( \max \left\{0, \xaj + \xij - 1 -
\eps(j) \right\} + \eps(j)\right) \\
& \leq & \sum_{j \in T_{exp}} \max\{0,~c_x(j)\} + \sum_{j \in
  T_{exp}}\eps(j).\end{aligned}$$ Combining the above inequality with Lemma \[lem:fix\] proves the theorem.

\[thm:three\] When $OPT_{LP}(G) = (1+\eps)n$ and $G$ is subquartic, there is a feasible circulation for $C(G,T)$ with cost at most $n/6 + 2\eps n$.

The number of expensive vertices is at most $n/2$ and each expensive vertex $j \in T_{exp}$ can add at most $1/3 + \eps(j)$ to the cost function. Each vertex $j \in T_{int}\setminus{T_{exp}}$ can add at most $\eps(j)$ to the cost function. Using the fact that $\sum_{j \in
  T_{int}} \eps(j) \leq 2 \eps n$, yields the theorem.

The $f$-circulation {#sec:f-circ}
-------------------

Now we describe a new method to obtain a feasible circulation, i.e. how to obtain values $f'(i,j)$ for each edge $(i,j) \in B(T)$ such that each vertex in $T_{int}$ is satisfied by $f'$. The values will be used to demonstrate an improved upper bound on the cost of a circulation of $C(G,T)$ when $G$ is a subquartic graph. In this section, we will prove the following theorem, which implies that the Mömke-Svensson algorithm has an approximation guarantee of $17/12$ for graph-TSP on subquartic graphs.

\[thm:f\] When $OPT_{LP}(G) = (1+\eps)n$ and $G$ is subquartic, there is a feasible circulation for $C(G,T)$ with cost at most $n/8 + 2\eps n$.

Consider a vertex $v \in T_{exp}$. If both incoming back edges had $f$-value $1/2$, then this vertex would not contribute anything to the cost of the circulation. Thus, on a high level, our goal is to find $f$-values that are as close to half as possible, while at the same time not creating any additional unsatisfied vertices. The $f$-value therefore corresponds to a decreased $x$-value if the $x$-value is high, and an increased $x$-value if the $x$-value is low. A set of $f$-values corresponding to decreased $x$-values may pose a problem if they correspond to the set of back edges that cover an LP-unsatisfied vertex. However, we note that in Section \[sec:x-circ\], we only used $\eps(j)/2$ to satisfy an LP-unsatisfied vertex $j$. We can actually use at least $\eps(j)$. This observation allows us to decrease the $x$-values. We use the rules depicted in Figure \[fig:rules\] to determine the values $f: B(T) \rightarrow [0,1]$.

\[lem:sat-by-f\] If a vertex $v$ is LP-satisfied, then it is satisfied by $f$.

Let $S \subseteq B(T)$ denote the set of back edges that covers a particular tree cut. If $S$ consists of a single edge with $x$-value 1, then the $f$-value of this edge will also be 1. Let us now suppose the set $S$ contains multiple edges, whose total $x$-value is at least 1. Consider the following three cases: First, suppose $S$ contains at least two edges with $x$-value at least $1/2$. In this case, the $f$-value on each of these edges remains at least $1/2$. Second, if the set $S$ contains only edges that have $x$-value at most $1/2$, then the total $f$-value is at least the total $x$-value, since the $f$-value does not decrease in this case.

The third case is when $S$ contains only one edge with $x$-value at least half. Suppose that this edge $e$ has value $x_e=1-\gamma \geq
1/2$. The remaining edges in $S$ must have total $x$-value at least $\gamma$. If at least one of these edges has $f$-value half, or $x$-value at least $1/4$, then we are done. Thus, all the edges in the set $S\setminus{e}$ must have $x$-value less than $1/4$. In this case, the total $f$-value for these edges is at least $2\gamma$. Note that the $f$-value of edge $e$ is at least $1-2\gamma$.

For each vertex $j \in T_{exp}$, let $c_f(j) = \sum_{i:(i,j) \in B(T)}
f(i,j) - 1 - \eps(j)$.

For ease of notation, set $f'(u,v) := f(u,v)$ for all $(u,v) \in B(T)$.

\[lem:sat-v\] For an LP-unsatisfied vertex $v \in T_{int}$, if we increase by the amount $\eps(v)$ the $f'$-value of an edge that covers its unsatisfied tree cut, then vertex $v$ will be satisfied by $f'$.

We will argue, as we did in Section \[sec:x-circ\], that each LP-unsatisfied vertex $j \in T_{int}\setminus{T_{exp}}$ can be satisfied by increasing the $f'$-value of a single back edge that covers the unsatisfied tree cut corresponding to one of its outgoing tree edges.

Let $S \subseteq B(T)$ be the set of back edges that cover the tree cut corresponding to edge $(j,t_2)$. Suppose $(t_1,j)$ is the incoming tree edge, and $(i,j)$ and $(j,k)$ are the incoming and outgoing back edges, respectively. Then we have: $$\begin{aligned}
x_{jt_2} + x(i,j) + x(S) & \geq & 2,\\
x_{jt_1} + x(j,k) + x(S) & \geq & 2.\end{aligned}$$ Since $j$ is LP-unsatisfied, $x(S) = 1-\gamma < 1$. Thus: $$\begin{aligned}
x_{jt_2} + x(i,j) + x_{jt_1} + x(j,k) & = & 2 + 2\gamma.\end{aligned}$$ So $\eps(j) = 2\gamma$. Therefore, since the $f$-value of the edges in $S$ is at least $1-2\gamma$, the amount $2\gamma$ is sufficient to “correct” the $f$-values so that $j$ is satisfied by $f'$.

\[lem:end1\] For $j \in T_{exp}$, if $\xij \geq 1/2$ or if $\xaj \leq 3/4$, then $c_f(j) \leq 0$.

We consider the following three cases.

[**Case (i):**]{} First, we consider the case in which $\xij \geq 3/4$. Then, the total $f$-value of the back edges coming into vertex $j$ is: $$\begin{aligned}
c_f(j) + 1 + \eps(j)  & = & 2 \cdot \xaj -1 + 2 \cdot \xij -
1\label{incoming} \\
& \leq & (2 + \eps(j) - \xij) + 2 \cdot \xij -2\\
& = & \xij + \eps(j).\end{aligned}$$ This implies that: $$\begin{aligned}
c_f(j) & \leq &  \xij - 1 ~ \leq ~ 0.\end{aligned}$$

[**Case (ii):**]{} Now let us consider the case when $\xaj \geq 3/4$ and $1/2 \leq \xij \leq 3/4$. The total $f$-value of the incoming back edges is: $$\begin{aligned}
c_f(j) + 1 + \eps(j) ~ = ~ 2\cdot \xaj - 1 + \frac{1}{2} & = & 2 \cdot
\xaj - \frac{1}{2}\\ 
& \leq & 3/2 - \xij + \eps(j).\end{aligned}$$ This implies that: $$\begin{aligned}
c_f(j) & \leq & 1/2 - \xij.\end{aligned}$$ Since $\xij \geq 1/2$, this implies that $c_f(j) \leq 0$.

[**Case (iii):**]{} Now let us consider the case when $\xaj \leq
3/4$. Note that in this case, the $f$-value for each incoming back edge is at most $1/2$. Thus, $c_f(j) \leq 0$.

It remains to examine the case when $\xaj > 3/4$ and $0 < \xij \leq
1/2$. This is the only situation when $c_f(j)$ can be positive.

\[lem:end2\] If $\xaj \geq 3/4$ and $0 < \xij \leq 1/2$, then $c_f(j) \leq
\min\{\xij, ~1/2-\xij \}$.

[**Case (iv):**]{} Now let us consider the case when $\xaj \geq 3/4$ and $1/4 \leq \xij < 1/2$. The total $f$-value of the incoming back edges is, using Lemma \[lem:fact\]: $$\begin{aligned}
c_f(j) + 1 + \eps(j) ~ = ~ 2\cdot \xaj  - 1 + \frac{1}{2} & \leq &
\frac{3}{2} - \xij + \eps(j).\end{aligned}$$ Therefore: $$\begin{aligned}
c_f(j) & \leq & \frac{1}{2} - \xij.\end{aligned}$$

[**Case (v):**]{} Now let us consider the case when $\xaj \geq 3/4$ and $0 < \xij < 1/4$. The total $f$-value of the incoming back edges is, using Lemma \[lem:fact\]: $$\begin{aligned}
c_f(j) + 1 + \eps(j) ~ = ~ 2\cdot \xaj  - 1 + 2 \cdot \xij  & \leq &
\xij + 1 + \eps(j).\end{aligned}$$ Therefore: $$\begin{aligned}
c_f(j) & \leq & \xij.\end{aligned}$$

We now have the following theorem.

\[thm:end3\] When $OPT_{LP}(G) = (1+\eps)n$ and $G$ is subquartic, there is a feasible circulation for $C(G,T)$ with cost at most $n/8 + 2\eps n$.

Lemmas \[lem:end1\] and \[lem:end2\] show that $c_f(j) \leq
\min\{x_{min}(j), 1/2 - x_{min}(j)\}$ for $0 \leq x_{min}(j) \leq 1/2$ and $c_f(j) = 0$ otherwise. Thus, $c_f(j) \leq 1/4$. So, we have: $$\begin{aligned}
\sum_{j \in T_{exp}} (c_f(j) + \eps(j)) + \sum_{j \in T_{int}\setminus{T_{exp}}}
\eps(j) & = &  |T_{exp}| \cdot \frac{1}{4} + \sum_{j \in T_{int}} \eps(j)\\
& \leq & \frac{n}{8} + 2\eps n,\end{aligned}$$ where the last inequality follows from Fact \[exp:bound\] and Equation .

Combining the $x$- and the $f$-circulations {#sec:combine}
===========================================

We can classify each vertex in $T_{exp}$ according to the value of $\xij$. Intuitively, if many vertices contribute a lot, say $1/3$ to the $x$-circulation, then they will not contribute a lot of the $f$-circulation, and vice versa.

\[thm:f\] When $OPT_{LP}(G) = (1+\eps)n$ and $G$ is subquartic, there is a feasible circulation for $C(G,T)$ with cost at most $n/11 + 2\eps n$.

We can compute the cost of the $x$-circulation and the cost of the $f$-circulation for $C(G,T)$. We will show that the minimum of the two costs is upper bounded by the guarantee in the theorem.

Let $\beta \in [0,1]$ represent the fraction of vertices in $T_{exp}$ for which $\xij \in [0,1/2]$. Note that we can assume that any vertex with $\xij \in [0,1/4]$ is actually $1/2 - \xij \in [1/4,1/2]$, since in this range, the cost $c_f(j)$ is the same, but the cost $c_x(j)$ is more, so the situation is strictly worse for our analysis. Let $(1-\beta)$ be the remaining fraction of the vertices, for which $\xij
\in (1/2,1]$.

Let $\bar{x}_{min}$ denote that average value of $\xij$ for the $\beta$-fraction of the vertices in $T_{exp}$ with $\xij \in
[1/4,1/2]$. Note that $\beta \cdot \bar{x}_{min}/2$ is the average contribution of these vertices to the $x$-circulation and that $\beta
(1/2 - \bar{x}_{min})$ is the average contribution of these vertices to the $f$-circulation. We can take the following convex combination of the $x$- and $f$-circulations to obtain the following inequality: $$\begin{aligned}
\frac{6}{11} \left(\beta \cdot \frac{\bar{x}_{min}}{2} + (1-\beta)
\cdot \frac{1}{3}\right) + \frac{5}{11}\left(\beta(\frac{1}{2} -
\bar{x}_{min}) \right) & \leq & \frac{2}{11}.\label{eq:balance}\end{aligned}$$ Since Equation holds when $c_x \geq 1/4$, and $c_x
\in [1/4,1/2]$ by definition, we can conclude that the average contribution of a vertex in $T_{exp}$ to the circulation is at most $2/11$. Since there are at most $n/2$ vertices in $T_{exp}$, the worst-case cost of the circulation is $n/11 + 2\eps n$.

\[thm:final\] The approximation guarantee of the Mömke-Svensson algorithm on subquartic graphs is at most $46/33$.

Using Lemma 4.1 from [@DBLP:conf/focs/MomkeS11], we can compute an upper bound on the cost of a TSP tour using Theorem \[thm:f\]: $$\begin{aligned}
\frac{\frac{4n}{3} + \frac{2}{3}\left(\frac{n}{11} + 2\eps n
  \right)}{(1+\eps)n} ~ \leq ~ \frac{\frac{46}{33} + \frac{4\eps}{3}}{(1+\eps)} ~ \leq ~\frac{46}{33}.\end{aligned}$$

Final remarks
=============

We note that we can actually obtain an approximation ratio slightly better than $46/33$. We are proving an upper bound on the minimum cost circulation of $C(G,T)$ in the form of $c(C^*) \leq c_1 \cdot n +
(2 + c_2)\eps n$. In our approximation guarantee, we set $c_1 = 1/11$ and $c_2 = 0$. In order to obtain an approximation ratio of $4/3$ using the approach of Mömke and Svensson, we must demonstrate that there is a circulation of cost at most $2\eps n$ when $OPT_{LP}(G) =
(1+\eps)n$. However, since we are not proving such a low approximation ratio, we can afford to let $c_2 > 0$, which would allow us to map a larger range of $x$-values to $f$-value $1/2$, thus making it possible to decrease $c_1$ slightly. In other words, we could use the assignment strategy shown in Figure \[fig:rules2\].

To pay for satisfying an LP-unsatisfied vertex $v \in T_{int}$ (as in Lemma \[lem:sat-v\]), we can afford to pay $(1 + c_2/2)\eps(v)$, permitting a larger decrease when going from the large $x$-values to the $f$-values, as shown in Figure \[fig:rules2\]. However, the improvement obtained from this is extremely small (approximately $1.393$ as opposed to $1.\overline{39}$) and is not worth the technical calculations.

Acknowledgements {#acknowledgements .unnumbered}
================

We wish to thank Sylvia Boyd, Satoru Iwata, R. Ravi, and Ola Svensson for helpful discussions and comments. We also thank the anonymous referees for their detailed remarks. This work was done in part while the author was a member of the THL2 group at EPFL.

[^1]: CNRS-Université Grenoble Alpes and G-SCOP, F-38000 Grenoble, France. Supported in part by LabEx PERSYVAL-Lab (ANR–11-LABX-0025). Email: [[ firstname.lastname@grenoble-inp.fr]{}]{}

[^2]: From now on, in all the lemmas we prove, we will always implicitly assume that $G$ is subquartic. This is in contrast to the previous sections, where, for example, Lemmas \[lem:xisone\] and \[lem:one-edge\] hold for general graphs.
