Dual Charging for Half-Integral TSP

There has been exciting recent progress on two important variants of TSP, graphic TSP, in which the input graph is unweighted, and path TSP in which the goal is to find the shortest $s$-$t$ walk visiting every vertex. For graphic TSP, Oveis Gharan, Saberi, and Singh [29] first demonstrated that max entropy was a $\frac{3}{2}-ϵ$ approximation for a small constant $ϵ>0$. Using different methods, Mömke and Svensson [27] then obtained a 1.461 approximation. This was further improved by Mucha [28] to $\frac{13}{9}$ and then to 1.4 by Sebö and Vygen [32]. For path TSP, Zenklusen showed a $\frac{3}{2}$ approximation [36] using a dynamic programming approach. Traub, Vygen, and Zenklusen then showed that given an $\alpha$ approximation for TSP there is an $\alpha +ϵ$ approximation for Path TSP for any $ϵ>0$.

As discussed, in the max entropy algorithm we first solve the subtour LP to obtain a solution $x\in {ℝ}_{\ge 0}^E$. The subtour LP is as follows, where $\delta (S)$ for $S⊊V$ is the set of edges with exactly one endpoint in $S$ and for $F\subseteq E$, $x(F)={\sum }_{e\in F}{x}_e$.

Then, using $x$, we find a maximum entropy distribution $\mu$ over spanning trees¹¹1Technically, over spanning trees plus an edge. subject to the constraint that ${\mathbb{P}}_{T\sim \mu }\left[e\in T\right]=x_e$ for all $e\in E$, up to a small multiplicative error (see Section 2.3 for more discussion on this sampling procedure). Finally, we sample a tree $T$ from $\mu$ and add a minimum cost matching $M$ on the odd vertices of the tree $T$. $T\uplus M$ is an Eulerian graph and thus contains an Eulerian walk, which is a solution to the metric TSP problem.²²2Using the fact that the costs form a metric, one can then shortcut the Eulerian tour to a Hamiltonian cycle of no greater cost if desired. The main goal, then, is to bound the expected cost of the matching over the randomness of the sampled tree $T$. To do so, we find a function that given a tree $T$ constructs a vector $y\in {ℝ}_{\ge 0}^E$ so that $c(M)\le c(y)$, and then bound the expected cost of $y$. In particular, $y$ will be a feasible point in the $O$-Join polytope (where $O$ is the set of odd vertices in $T$); see Section 2 for further details.

This is the approach taken by all previous papers analyzing max entropy [29, 22, 23] or variants of this algorithm [12], and we do not deviate from this here. However, here we construct $y$ in a new way that streamlines the analysis and allows for a sharper guarantee. While previous works bounded $𝔼[c(y)]$ by bounding the contribution to $y$ of each edge individually, we instead bound the contribution of each dual variable to $𝔼[c(y)]$. By complementary slackness, the dual variables correspond to tight cuts with $x(\delta (S))=2$, which contain multiple edges $e$ with $x_e\in \{\frac{1}{2},1\}$. By bounding the cost of groups of edges in terms of ${\sum }_{e\in \delta (S)}{y}_e$, the argument becomes much more flexible. Previously, analyses had to deal with pathological cases where single edges had a high $𝔼[y_e]$ and create workarounds. By looking at groups of edges, issues due to these pathological edges are averaged out. Previously it was necessary to bound for all $e\in E$ (as this would correspond to an expected cost of less than $\frac{1}{2}c(x)$ for the matching), in our construction there may be edges with $𝔼[y_e]>\frac{x_e}{2}$.

There is one other big advantage of this approach, which is as follows.³³3Understanding this advantage is a bit technical, so we recommend readers unfamiliar with work on the max entropy algorithm come back to this point after having read the body of the paper. In the analysis of max entropy, typically one begins with $y=\frac{x_e}{2}$ for all edges. Then, depending on the parity of certain cuts in the tree, some edges have $y$ decreased and other edges have $y$ increased. In the per-edge argument, it was important to bound the expected increase of each edge carefully. However, when considering a cut, these increases and decreases often cancel out, simplifying things quite a bit. (Despite this, our analysis is not simpler than [22]. This is because we take care to improve the analysis in several places which require additional casework.)

One other aspect of our improvement is to incrementally improve some of the important probabilistic bounds from [22] using polynomial capacity (see e.g. [16] for usage of this tool in TSP) or more precise arguments. However the impact of this is relatively minor compared to that of the move to a dual-based analysis.

The subtour LP is given in Equation 1. We will also crucially use the dual linear program in our analysis. By the parsimonious property [11], the subtour bound does not change after dropping the equality constraints. Thus, the dual can be seen to have the following formulation:

We will also make significant use of the following characterization of the cost of the matching. It is well known (see [8], for example) that given a metric, the following LP bounds upper bounds the cost of an integral perfect matching on a set of vertices $O$:

This is known as the $O$-Join polyhedron, and we call a feasible point $y$ in this polyhedron an $𝑶$-Join solution, where $O$ is the set of vertices in the sampled tree $T$ with odd degree. In this context, note that the set of cuts $S$ which have constraints in (3) are exactly those for which ${\delta }_T(S)$ is odd.

A distribution $\mu$ over spanning trees is $\lambda$-uniform if $\lambda \in {ℝ}_{\ge 0}^E$ and for every spanning tree $T$ of the graph,

Given $\lambda$, we will let ${\mu }_{\lambda }$ denote the resulting $\lambda$-uniform distribution. Given a point $z$ in the spanning tree polytope, [1] show that one can efficiently find a $\lambda$-uniform tree with marginals arbitrarily close to $z$:

Since $ϵ$ can be chosen to be exponentially small in $n$, following previous work on half integral TSP, we will assume for brevity that we may set $ϵ=0$. This error can be handled using the stability of max entropy distributions [34] (one can see this applied in [23]).

$\lambda$-uniform spanning tree distributions have maximum entropy over all distributions with the same marginal vector. Therefore, when one can set $ϵ=0$, they are indeed the distributions of maximal entropy respecting the constraints.

We will study the version of the max entropy algorithm used by [22]. Here, we first fix an edge $e^{+}=(u,v)$ where $u,v$ have two parallel edges between them. Such an edge always exists in any extreme point solution (see [3]), or as noted in [22] one can create such an edge by splitting a vertex in two and putting an edge of value 1 and cost 0 between its two endpoints. After fixing $e^{+}$, we iteratively select a minimal proper tight set $S$ that is not crossed (and $e^{+}\notin E(S)$), compute the max entropy distribution $\mu$ inside $S$, sample $T_S\sim \mu$, and contract it. When no such set exists, the graph must be a cycle $v_1,\mathrm{\dots },v_k$, at which point we sample a random cycle. In particular, for every $v_i,v_{i+1}$ that share two edges we sample one of them independently and uniformly at random. The sampled tree $T$ at the end is the union of all trees $T_S$ sampled during the procedure. See Algorithm 1 for a complete description and [22] for further details.

Following [22], we call every tight set contracted by the algorithm a critical set. In addition, we call vertices critical sets. For a critical set $S$, we call $\delta (S)$ a critical cut. The collection of critical sets is a laminar family $ℒ$, where recall a family is laminar if for all $S,T\in ℒ$, $S\cap T\in \{\mathrm{\varnothing },S,T\}$.

There are two types of sets $S\in ℒ$. If at the moment before contraction, there are no proper minimum cuts inside $S$, then call $S$ a degree cut. Otherwise, call $S$ a cycle cut, in which case at the moment before contraction $S$ is a path with two edges between every pair of adjacent vertices. See Figure 1(b) for examples of each type of cut in $G$, and see Section 3.1 for more details.

We also note here that by definition, edges which are in $G_S$ and $G_{S^{\prime }}$ for critical cuts $S\ne S^{\prime }$ are independent. This fact will be used crucially throughout the proof.

The algorithm constructs a natural hierarchy of min-cuts. That is, the critical cuts form a laminar family of min cuts, and therefore can be arranged in a hierarchical structure. At the bottom of this hierarchy are the singleton vertex cuts.

Let $S$ be a critical cut. Based on the structure of the contracted graph $G_S$, we classify $S$ into one of two types. Note that, we assumed $G_S$ is the support graph after contracting $V\setminus S$ and all critical cuts lower than $S$ in the hierarchy.

1. 1.

   Degree cut: If $G_S$ contains no proper min-cuts, we call $S$ a degree cut.

2. 2.

   Cycle cut: Otherwise, $G_S$ must form a cycle with two parallel edges between each pair of consecutive vertices. In this case, we call $S$ a cycle cut. We call the parallel edges in $G[S]$ that share their endpoints companions. Note that a pair of companions $e,f$ has the property that exactly one is in the tree and the event of which edge is chosen is independent of all other events. The remaining two pairs of parallel edges sharing endpoints in $G_S$ are called cycle partners.

For an edge $e$, let $S_e$ denote the minimal critical cut such that $e\in G[S_e]$. We will distinguish edges into two types depending the structure of $S_e$.

We define a similar notation for the critical cuts.

Moreover, for an edge $e$, we define the Last Cuts of $e$ as the two maximal min cuts $S$ such that $e\in \delta (S)$. More precisely, let $e$ be a bottom edge where $S_e$ has child cuts $S_1,\mathrm{\cdots },S_k$ with two edges between $S_i$ and $S_{i+1}$ for $1\le i\le k-1$. If $e$ is between $S_i$ and $S_{i+1}$, then, the last cuts of $e$ are $S_1\cup \mathrm{\cdots }\cup S_i$ and $S_{i+1}\cup \mathrm{\cdots }\cup S_k$.

Note that the last cuts of a top edge are critical cuts, meanwhile, last cuts of a bottom edge are not necessarily a critical cut.

Given a tree $T$ sampled from the max-entropy distribution, we will describe a randomized process to construct a feasible solution for the $O$-Join formulation (Equation 3) where $O$ is the odd degree vertices of $T$.

Before describing the construction, we will restate the definition of even at last edges from [22].

Let $x$ be the optimal solution of the subtour LP (Equation 1). We will initialize $y=\frac{x}{2}$ so that $y$ satisfies the $O$-Join constraints. Now, when an edge $e$ is even at last, we will decrease $y_e$ by $\tau$, where $\tau$ is a parameter we will set later. Since an even at last edge can still cover lower level min-cuts in the hierarchy that are odd in $T$, we will increase the value of $y_e$ accordingly to make $y$ a feasible $O$-Join solution.

We utilize the fact that when an edge $e$ is even at last, lower level cuts $S$ such that $e\in \delta (S)$ are (in most cases) still even with probability $\mathrm{\Omega }(1)$. For an edge $e$, let $p_e$ denote the probability of $e$ being even at last. Unfortunately, some edges can have $p_e\approx 0$ (see [23]). This is an issue for arguments that bound the contribution of each edge individually. Therefore, deviating from prior work, we will instead look at the expected number of even at last edges in $\delta (S)$ for a min cut $S$. This value is denoted by $p(\delta (S))={\sum }_{e\in \delta (S)}{p}_e$. We show lower bounds for this value for every min cut $S$, which in turn gives that $y(\delta (S))$ decreases meaningfully for each min cut $S$ in the $O$-Join solution we construct. Moreover, when we increase edges to cover the violated $O$-Join constraint of a cut, we increase them according to (roughly) their $p_e$ value. This in turn means that edges that increase in the third step of our construction, should also decrease meaningfully in the second step. A more accurate and complete description of this process is provided in Section 5.

Our main goal is to show that the $O$-Join solution of a tree sampled from the max entropy algorithm has cost at most $0.49776\cdot c(x)$ in expectation. This immediately proves Theorem 1 as the $O$-Join polyhedron (Equation 3) has an integrality gap of 1. To do so, we will show the $O$-Join solution $y$ has expected cost at most $0.49776\cdot c(x)$. Instead of bounding the contribution of each edge, we will bound the expectation on each minimum cut $S$ as follows:

To analyze the cost of our solution, we utilize the dual formulation of the subtour LP (Equation 2). Now, we will use Lemma 9 to prove Theorem 1.

Given a distribution $\mu :{\mathbb{Z}}_{\ge 0}^n\to {ℝ}_{\ge 0}$ over ground set $[n]$, its generating polynomial $g_{\mu }$ is defined

where $z^{\kappa }={\prod }_{i=1}^n{z}_i^{{\kappa }_i}$. $\mu$ is strongly Rayleigh (SR) [2] if $g_{\mu }(z)$ is real stable. A polynomial $p(z)$ is real stable if $p(z)\ne 0$ for all $z\in {ℂ}^n$ with $\text{Im}(z_i)>0$ for all $i\in [n]$. In other words, $p$ is strongly Rayleigh if it has no zeros in the upper half of the complex plane. $\lambda$-uniform spanning tree distributions are strongly Rayleigh (see e.g. [2, 29]).

The capacity at $\alpha \in {\mathbb{N}}_{+}^n$ of a real stable polynomial $p(x_1,\mathrm{\dots },x_n)$ with positive coefficients is defined as:

A classical result of Gurvits [14] relates the capacity of a polynomial to the coefficient of ${\prod }_{i=1}^n{x}_i$ for $n$-variate homogeneous polynomials of degree $n$ as follows (where $\mathrm{𝟏}$ is the vector consisting of $n$ 1s):

Note that ${\frac{{\partial }^n}{\partial x_1\mathrm{\dots }\partial x_n}p|}_{x_1=\mathrm{\cdots }=x_n=0}$ is exactly the coefficient of ${\prod }_{i=1}^n{x}_i$. There are various similar statements in the literature, and we will use the following, first stated as Theorem 5.1 of [15] and restated as follows in [4]:

Furthermore, the capacity of a real stable polynomial can be bounded using its gradient. In particular, we can apply the following theorem of Gurvits and Leake [17] (also see [16]) generalizing [13]. (We do not need the generalization here, but we state the stronger form regardless.)

We will use the following corollary in this work, which follows easily from the above.

In this section, we recall some basic facts about the structure of critical cuts. For proofs, we refer the interested reader to Section 3 of [22]. These facts are used solely to ensure that our case analysis is exhaustive and covers all possible scenarios.

The following two corollaries are immediate.

We will also prove the following simple fact.

As previously mentioned, for an edge $e$, there cannot be any meaningful lower bound on the probability of $e$ being even at last as there can be edges with $p_e\approx 0$. In contrast, we will show that for any top cut $S$, there are strong lower bounds on $p({\delta }^{\to }(S))$. This intuitively shows that in expectation, $y(\delta (S))$ can be decreased for every min cut.

The following lemma can be thought of as as the analog of Lemma 5.3 of [22] (which showed at least one edge in each cut has $p_e\ge \frac{1}{27}$) when adapted to our framework, and uses similar proof ideas.

In this section, we show that if a degree cut $S$ satisfies a certain structure, then $G_S$ must be the graph $K_5$. We use this fact in Section 5 to show that if many edges in ${\delta }^{\to }(S)$ have conditions that prevent them from decreasing reasonably, the degree cut $S$ must have a simple structure. In particular, $G_S$ must be a $K_5$. We note that Gupta et al. [12] also treated $K_5$ as a special case, and adapted the algorithm to treat these cuts differently. While we do not change the algorithm, we similarly analyze this case separately.