1 Introduction

Given the complete graph \(K_n = (V_n, E_n)\) on n nodes with non-negative edge costs \(c \in {\mathbb R}^{E_n}\), the traveling salesman problem (henceforth TSP) is to find a Hamiltonian cycle of minimum cost in \(K_n\). When the costs are metric, i.e. satisfy the triangle inequality \(c_{ij} + c_{jk} \ge c_{ik}\) for all \(i,j,k \in V_n\), the problem is called the metric TSP. If the metric is defined by the shortest (cardinality) paths of a graph, then it is called a graph metric; the TSP specialized to graph metrics is the graph TSP.

For \(G=(V,E)\), \(x \in {\mathbb R}^E\) and \(F \subseteq E\), \(x(F):=\sum _{e \in F} x_e\); for \(U \subseteq V\), \(\delta (U):=\delta _G(U):=\{uv \in E : u \in U, v \in V{\setminus } U\}\); \(E[U]:=\{uv \in E : u \in U, v \in U\}\). The scalar product of vectors a and x of the same dimension will simply be denoted by ax. A path is the edge set of a connected subgraph with two nodes of degree 1 and all other nodes of degree 2, and a cycle is the edge set of a connected subgraph with all node degrees equal to 2. A multisubgraph of G is a subgraph where taking more than one copy of an edge of G is allowed.

A natural linear programming relaxation for the TSP is the following subtour LP:

$$\begin{aligned} \text{ minimize } cx \end{aligned}$$
(1)
$$\begin{aligned} \text{ subject } \text{ to: } x(\delta (v)) = 2&\quad \text{ for } \text{ all } v \in V_n, \end{aligned}$$
(2)
$$\begin{aligned} x(\delta (S)) \ge 2&\quad \text{ for } \text{ all } \emptyset \ne S\subsetneq V_n, \end{aligned}$$
(3)
$$\begin{aligned} 0 \le x_e \le 1&\quad \text{ for } \text{ all } e \in E_n. \end{aligned}$$
(4)

For a given cost function \(c\in \mathbb {R}^{E_n}\), we use LP(c) to denote the optimal solution value for the subtour LP and \(\textit{OPT}(c)\) to denote the optimal solution value for the TSP. The polytope associated with the subtour LP, called the subtour elimination polytope and denoted by \(\mathcal {S}^n\), is the set of all vectors x satisfying the constraints of the subtour LP, i.e. \(\mathcal {S}^n = \lbrace x \in \mathbb {R}^{E_n} : x\) satisfies (2)–(4)\(\rbrace \).

The metric TSP is known to be NP-hard. One approach taken for finding reasonably good solutions is to look for a \(\rho \)-approximation algorithm for the problem, i.e. a polynomial-time algorithm that always computes a solution of value at most \(\rho \) times the optimum. Currently the best such algorithm known for the metric TSP is the algorithm due to Christofides [9] for which \(\rho = \frac{3}{2}\). Although it is widely believed that a better approximation algorithm is possible, no one has been able to improve upon Christofides algorithm in 4 decades. For arbitrary nonnegative costs not constrained by the triangle inequality there does not exist a \(\rho \)-approximation algorithm for any \(\rho \in \mathbb {R}\) unless P = NP, since such an algorithm would be able to decide if a given graph is Hamiltonian.

For an approximation guarantee of a minimization problem one needs lower bounds for the optimum, often provided by linear programming. For the metric TSP with cost function c, a commonly used lower bound is LP(c). Then finding a solution, i.e. a Hamiltonian cycle, of objective value at most \(\rho \) LP(c) in polynomial time for every metric cost function c implies at the same time a \(\rho \)-approximation algorithm, and establishes that the integrality gap for the subtour LP, i.e. \(max_{c \; metric}\) OPT(c)/LP(c), is at most \(\rho \). (Without the metric assumption the integrality ratio OPT(c)/LP(c) is unbounded already for the graph TSP by putting infinite costs on non-edges of the defining graph.) Since up until now the bounds on the integrality gap have been proved via polynomial algorithms constructing the Hamiltonian cycles, the best approximation ratio achievable in polynomial time is conjectured not to be larger than the integrality gap.

It is known that the integrality gap for the subtour LP is at most \(\frac{3}{2}\) [10, 25, 26], however no example for which the ratio OPT(c)/LP(c) is greater than \(\frac{4}{3}\) is known. In fact, a famous conjecture, often referred to as the \(\frac{4}{3}\) Conjecture, states the following:

Conjecture 1

The integrality gap for the subtour LP with metric c is at most \(\frac{4}{3}\).

Well-known families of examples have the ratio OPT(c)/LP(c) asymptotically equal to \(\frac{4}{3}\). In almost 30 years, there have been no improvements made to the upper bound of \(\frac{3}{2}\) or lower bound of \(\frac{4}{3}\) for the integrality gap for the subtour LP with metric c.

Define a tour to be the edge set of a spanning Eulerian (i.e. connected with all degrees even) multisubgraph of \(K_n\). If none of the multiplicities can be decreased (i.e. by removing two copies of an edge), then all multiplicities are at most two; however, there are some technical advantages to allowing higher multiplicities.

For any multiset \(J\subseteq E_n\), the incidence vector of J, denoted by \(\chi ^J\), is the vector in \(\mathbb {R}^{E_n}\) for which \(\chi ^{J}_e\) is equal to the number of copies of edge e in J for all \(e \in E_n\). We use \(\mathcal {T}^n\) to denote the convex hull of incidence vectors of tours of \(K_n\), and for costs \(c\in \mathbb {R}^{E_n}\) we use OPT\(_{\mathcal {T}^n}(c)\) to denote the cost of a minimum cost tour. Note that \(\mathcal {T}^n\) is an unbounded polyhedron, as \(\mathcal {T}^n + \mathbb {R}^{E_n}_+ = \mathcal {T}^n\): each edge may have arbitrarily large multiplicity.

For any \(\rho \in {\mathbb R}\),  \(\rho \,\mathcal {S}^n\) denotes \(\{y \in {\mathbb R}^{E_n} : y = \rho x, ~ x \in \mathcal {S}^n \}\). The definition of the integrality gap can be reformulated in terms of a containment relation between the two polyhedra \(\rho \mathcal {S}^n\) and \(\mathcal {T}^n\) (Theorem 1) that does not depend on the objective function. We not only use this reformulation here, but also develop a specific way of exploiting it, and for our arguments this is the very tool that works. Showing for some constant \(\rho \in \mathbb {R}\) that \(\rho \,x \in \mathcal {T}^n\) for each \(x\in \mathcal {S}^n\), i.e. that \(\rho \,x\) is a convex combination of incidence vectors of tours, gives an upper bound of \(\rho \) on the integrality gap for the subtour LP: it implies that for any cost function \(c\in \mathbb {R}^{E_n}\) and \(x\in \mathcal {S}^n\) such that \(cx = \textit{LP}(c)\), at least one of the tours in the convex combination has cost at most \(\rho \,(cx) = \rho \textit{LP}(c)\). If the costs are metric, this tour can be shortcut to a TSP solution of cost at most \(\rho \textit{LP}(c)\), giving a ratio of OPT(c)/LP(c) \(\le \rho \). A shortcut means to fix an Eulerian tour and replace a sequence of nodes (a, b, c) by (a, c), whenever b has already been visited by the tour. The essential part “(i) implies (ii)” of the following theorem, due to Goemans [14] (also see [8]), asserts that the converse is also true: if \(\rho \) is at least the integrality gap, then \(\rho \,\mathcal {S}^n\) is a subset of \(\mathcal {T}^n\).

Theorem 1

[8, 14] Let \(K_n = (V_n, E_n)\) be the complete graph on n nodes and let \(\rho \in \mathbb {R}, \rho \ge 1\). The following statements are equivalent:

  1. (i)

    For any metric cost function \(c:E_n\longrightarrow \mathbb {R}_+, \textit{OPT}(c)\le \rho \textit{LP}(c)\).

  2. (ii)

    For any \(x\in \mathcal {S}^n\), \(\rho x \in \mathcal {T}^n\).

  3. (iii)

    For any vertex x of \(\mathcal {S}^n\), \(\rho x \in \mathcal {T}^n\).

By Theorem 1, Conjecture 1 can be equivalently reformulated as follows:

Conjecture 2

The polytope \(\frac{4}{3}\,\mathcal {S}^n\) is contained in the polyhedron \(\mathcal {T}^n\), that is, \(\frac{4}{3}\,\mathcal {S}^n \subseteq \mathcal {T}^n\).

Given a vector \(x \in \mathcal {S}^n\), the support graph  \(G_x=(V_n, E_x)\) of x is defined with \(E_x = \{e\in E_n: x_e >0 \}\). We call a point \(x \in \mathcal {S}^n\) \(\frac{1}{2}\)-integer if \(x_e \in \{0, \frac{1}{2}, 1\}\) for all \(e \in E_n\). For such a vector we call the edges \(e \in E_n\) \(\frac{1}{2}\)-edges if \(x_e = \frac{1}{2}\) and 1-edges if \(x_e = 1\). Note that the 1-edges of \(\frac{1}{2}\)-integer points form a set of disjoint paths that we call 1-paths of x, and the \(\frac{1}{2}\)-edges form a set of edge-disjoint cycles that we call the \(\frac{1}{2}\)-cycles of x.

For Conjecture 1, it seems that \(\frac{1}{2}\)-integer vertices play an important role (see [1, 7, 20]). In fact the following has been conjectured by Schalekamp, Williamson and van Zuylen [20] (note that here we state a weaker version of their original conjecture for simplicity):

Conjecture 3

The integrality gap for the subtour LP is reached on metric cost functions optimized at \(\frac{1}{2}\)-integer vertices of \(\mathcal {S}^n\).

Very little progress has been made on the above conjectures, even though they have been around for a long time and have been well-studied. For the special case of graph TSP an upper bound of \(\frac{7}{5}\) is known for the integrality gap [23]. Conjecture 2 has been verified for the so-called triangle vertices \(x\in \mathcal {S}^n\) for which the values are \(\frac{1}{2}\)-integer, and the \(\frac{1}{2}\)-edges form triangles in the support graph [4]. The lower bound of \(\frac{4}{3}\) for the integrality gap is provided by triangle vertices with just two triangles.

A concept first introduced by Carr and Ravi [7] (for the 2-edge-connected subgraph problem) is that of a fundamental class, which is a class of points F in the subtour elimination polytopes \(\mathcal {S}^n\), \(n\ge 3\) with the following property: showing that \(\rho \,x\) is a convex combination of incidence vectors of tours for all vertices \(x \in F\) implies the same holds for all vertices of polytopes \(\mathcal {S}^n\), and thus implies that the integrality gap for the subtour LP is at most \(\rho \).

Two main classes of such vertices have been introduced, one by Carr and Vempala [8], the other by Boyd and Carr [4]. In this paper we will focus on the latter one, that is, we define a Boyd–Carr point [4] to be a point \(x \in \mathcal {S}^n\) that satisfies the following conditions:

  1. (i)

    The support graph \(G_x\) of x is cubic.

  2. (ii)

    In \(G_x\), there is exactly one 1-edge incident to each node.

  3. (iii)

    The fractional edges of \(G_x\) form disjoint 4-cycles.

A Carr–Vempala point [8] is one that satisfies (i), (ii) and instead of (iii), the fractional edges form a Hamiltonian cycle. We use fundamental point as a common name for points that are either Boyd–Carr or Carr–Vempala points. It has been proved that the Boyd–Carr points [4] and Carr–Vempala points [8] each form fundamental classes. The support graph of a fundamental point will be called a fundamental graph. In other words, a fundamental graph is a cubic graph where there exists a perfect matching whose deletion leads to a graph whose components are 4-cycles, or a Hamiltonian cycle. Note that the support graphs of instances of Carr–Vempala points are 3-edge-connected: the Hamiltonian cycle of edges \(\{e\in E_n: x(e)<1\}\) has at least two edges in every cut, but two such edges alone do not suffice for constraints (3) of the subtour LP. Moreover, the 3-edge-connected instances of Boyd–Carr points also form a fundamental class: this can be verified from the construction of these points (see [4]).

Despite their significance and simplicity, no effort has been deployed to exploring new integrality gap bounds for these classes, and no improvement on the general \(\frac{3}{2}\) upper bound on the integrality gap has been made for them, not even for special cases. A natural first step in this endeavour is to try to improve the general bounds for the special case of \(\frac{1}{2}\)-integer Boyd–Carr or Carr–Vempala points.

In this paper we improve the upper bound for the integrality gap from \(\frac{3}{2}\) to \(\frac{10}{7}\) for any metric cost function for which the subtour LP is optimized by a \(\frac{1}{2}\)-integer Boyd–Carr point, and also provide a \(\frac{10}{7}\)-approximation algorithm for metric TSP for such cost functions. In fact we generalize these results to a superclass of these points. If instead of 1-edges connecting the squares we allow 1-paths of arbitrary length, we get all the \(square points \), that is, \(\frac{1}{2}\)-integer points of \(\mathcal {S}^n\) for which the \(\frac{1}{2}\)-edges form disjoint 4-cycles, called squares of the support graph. We also show that there exists a subclass of square points that provide instances where the integrality gap is at least \(\frac{4}{3}\). Thus square points provide new tight examples for the lower bound of the conjectures.

In the endeavour to find improved upper bounds on the integrality gap we examine the structure of the support graphs of Boyd–Carr points. We show that they are all Hamiltonian, an important ingredient of our bounding of their integrality gap. Hamiltonicity can be seen as an implication of a theorem of Kotzig [19] on Eulerian trails with forbidden transitions. An Eulerian trail in a graph is a closed walk containing each of its edges exactly once. Contrary to tours, it is more than just an edge set, the order of the edges also plays a role. The connection of tours to Eulerian trails leads us to delta-matroids (Sect. 5) and to developing related algorithms (Sect. 4).

In Sect. 2.1 we show a first, basic application of our ideas, where some parts of the difficulties do not occur. We prove for both classes of fundamental graphs that all of their edges can be uniformly covered 6 / 7 times by tours whenever the graph is 3-edge-connected. This is better than the conjectured 8 / 9 multiplier of the all one vector that would follow for arbitrary 3-edge-connected cubic graphs from Conjecture 2, and to have as small a multiplier as possible is relevant because of the close connection of this multiplier with the integrality ratio (see after Theorem 4).

Another new way of using classical combinatorial optimization for the TSP occurs in Sect. 2.2, where we use an application of Edmonds’ matroid intersection theorem to write the optimum x of the subtour elimination polytope as the convex combination of incidence vectors of “rainbow” spanning trees in edge-coloured graphs. The idea of using spanning trees with special structures to get improved results has recently been used successfully in [13] for graph TSP, and in [15, 24] for a related problem, namely the metric s–t path TSP. However, note that we obtain and use our trees in a completely different way.

Our main results concerning the integrality ratio of \(\frac{1}{2}\)-integer Boyd–Carr points and square points are proved in Sect. 3. We conclude that section by outlining a potential strategy for using the Carr–Vempala points of [8] for proving the \(\frac{4}{3}\) Conjecture for any metric cost function optimized at \(\frac{1}{2}\)-integer points of the subtour polytope.

Finally, in Sect. 4, we provide polynomial-time optimization algorithms for some of the existence theorems of previous sections, including a \(\frac{10}{7}\)-approximation algorithm for the metric TSP for any cost function which is optimized by a square point for the subtour LP, and in Sect. 5 we provide some insights from the viewpoint of delta-matroids.

2 Polyhedral preliminaries and other useful tools

In this section we discuss some useful and powerful tools that we need in the proof of our main result in Sect. 3. We begin with some preliminaries.

Given a graph \(G=(V,E)\) with a node in V labelled 1, a 1-tree is a subset F of E such that \(|F\cap \delta (1)| = 2\) and \(F\backslash \delta (1)\) forms a spanning tree on \(V\backslash \{1\}\). The convex hull of the incidence vectors of 1-trees of G, which we will refer to as the 1-tree polytope of the graph G, is given by the following [16, p. 262]:

$$\begin{aligned}&\left\{ x\in \mathbb {R}^E: ~ x(\delta (1)) = 2, ~ x((E[U])) \le |U| - 1 \quad \text{ for } \text{ all } \emptyset \ne U \subseteq V\backslash \{1\},\right. \nonumber \\&\quad \left. 0 \le x_e \le 1 \quad \text{ for } \text{ all } e \in E ,~ x(E)=|V|\right\} . \end{aligned}$$
(5)

It is well-known that the 1-trees of a connected graph satisfy the basis axioms of a matroid (see [16, pp. 262–263]).

Given \(G=(V,E)\) and \(T\subseteq V\), |T| even, a T-join of G is a set \(J\subseteq E\) such that T is the set of odd degree nodes of the graph (V, J). A cut \(C=\delta (S)\) for some \(S\subset V\) is called a T-cut if \(|S\cap T|\) is odd. We say that a vector majorates another if it is coordinatewise greater than or equal to it. The set of all vectors x that majorate some vector y in the convex hull of incidence vectors of T-joins of G is given by the following [12]:

$$\begin{aligned} \{x\in \mathbb {R}^E: x(C) \ge 1 \text{ for } \text{ each } T\text{-cut } \text{ C, } x_e \ge 0 \quad \text{ for } \text{ all } e \in E\}. \end{aligned}$$
(6)

This is the T-join polyhedron of the graph G.

The following two results are well-known (see [10, 25, 26]), but we include the proofs as they introduce the kind of polyhedral arguments we will use:

Lemma 1

[10, 25, 26] If \(x\in \mathcal {S}^n\), then (i) it is a convex combination of incidence vectors of 1-trees of \(K_n\), and (ii) x / 2 majorates a convex combination of incidence vectors of T-joins of \(K_n\) for every \(T\subseteq V_n\), |T| even.

Proof

Constraints (2) and (3) of the subtour LP together imply that \(x(E_n) = n\) and \(x(E_n[S])\le |S|-1\), for all \(\emptyset \ne S\subsetneq V_n\). Thus \(x\in \mathcal {S}^n\) satisfies all of the constraints of the 1-tree polytope of \(K_n\) and (i) of the lemma follows. To check (ii), note that for all \(T\subseteq V_n\), |T| even, x / 2 satisfies the constraints of the T-join polyhedron of \(K_n\) (in fact \(x(C)/2\ge 1\) for every cut C), that is, it majorates a convex combination of incidence vectors of T-joins. \(\square \)

Theorem 2

[10, 25, 26] If \(x\in \mathcal {S}^n\), \(\frac{3}{2} x \in \mathcal {T}^n\).

Proof

By (i) of Lemma 1, x is a convex combination of incidence vectors of 1-trees of \(K_n\). Let F be any 1-tree of such a convex combination, and \(T_F\) be the set of odd degree nodes in the graph \((V_n,F)\). Then by (ii) of Lemma 1, x / 2 majorates a convex combination of incidence vectors of \(T_F\)-joins. So \(\chi ^F + x/2\) majorates a convex combination of incidence vectors of tours, and taking the average with the coefficients of the convex combination of 1-trees, we get that \(x+x/2\) majorates a convex combination of incidence vectors of tours. Since adding 2 to the multiplicity of any edge in a tour results in another tour, it follows that \(\frac{3}{2} x \in \mathcal {T}^n\). \(\square \)

The tools of the following two subsections are new for the TSP and appear to be very useful.

2.1 Eulerian trails with forbidden bitransitions

Let \(G=(V,E)\) be a connected 4-regular multigraph. For any node \(v\in V\), a bitransition (at v) is a partition of \(\delta (v)\) into two pairs of edges. Clearly every Eulerian trail of G uses exactly one bitransition at every node, meaning the two disjoint pairs of consecutive edges of the trail at the node. There are three bitransitions at every node and the theorem below, equivalent to a result of Kotzig [19], states that we can forbid one of these and still have an allowed Eulerian trail. As we will show, this provides Hamiltonian cycles in the support of square points, used in Sect. 3 to prove our main result.

Theorem 3

[19] Let \(G=(V,E)\) be a 4-regular connected multigraph with a forbidden bitransition for every \(v\in V\). Then G has an Eulerian trail not using the forbidden bitransition of any node.

A square graph is defined as a pair (G, M) where \(G=(V,E)\) is a graph and M is a perfect matching of G such that the edges \(E{\setminus } M\) form squares. Note that G will be cubic and 2-edge-connected. We associate Boyd–Carr points to square graphs, where M is defined to be the set of 1-edges (in the associated square graphs both edges of a 2-edge-cut will be in M).

Lemma 2

A square graph (G, M) has a Hamiltonian cycle containing M.

Proof

Let \(G=(V,E)\). We assume G has at least two squares as the lemma is trivially true otherwise.

Suppose first that G has a square \(u_1u_2,u_2u_3,\) \(u_3u_4,u_4u_1\) in \(E{\setminus } M\), with a chord, say \(u_2u_4\), in M, that is, exactly the two edges \(au_1\) and \(u_3b\) \((a,b\in V)\) are leaving the set \(\{u_1,u_2,u_3,u_4\}\subseteq V\). In this case we can delete \(u_1,u_2,u_3,u_4\) from the graph and add the edge ab to G to form a new square graph \((\hat{G},\hat{M})\) with \(\hat{M} = M - u_2u_4 + ab\). From a Hamiltonian cycle of this reduced graph containing \(\hat{M}\) we obtain a Hamiltonian cycle of G containing M by deleting ab, and adding \(au_1,u_1u_2,u_2u_4,u_4u_3,u_3b\). We can thus suppose that G has no such square.

Contracting all squares of G, we obtain a 4-regular connected multigraph \(G^\prime =(V^\prime ,E^\prime )\) whose edges are precisely M and whose nodes are precisely the squares of \(G{\setminus } M\). To each contracted square C we associate the forbidden bitransition consisting of the pairs of edges of M incident with the diagonally opposite nodes of C in G, as shown in Fig. 1. By Theorem 3, there is an Eulerian trail K of \(G^\prime \) that does not use these forbidden bitransitions. The two pairs of consecutive edges in K at each node in \(G^\prime \) can then be completed by the perfect matching connecting their endpoints in the corresponding square in G, forming the desired Hamiltonian cycle.\(\square \)

Fig. 1
figure 1

Shrinking a square in G to node u; forbidden: \(\{(uv_1,uv_3),(uv_2,uv_4)\}\)

Full size image

As we will explain in Sect. 5, the above exhibited connection of Eulerian graphs with forbidden bitransitions can also be seen as a consequence of delta-matroids [2, 3] which have well-known optimization properties. We exploit this link and the background theory of delta matroids implicitly in Sect. 4, where we provide a direct self-contained algorithmic proof (with a polynomial-time, greedy algorithm) for a weighted generalization of Lemma 2. We then explicitly explain the connection to delta-matroids in Sect. 5. We content ourselves in this section by providing a simple, first application of Lemma 2 which shows a basic idea we will use in the proof of our main result in Sect. 3, without the additional difficulty of the more refined application.

Given a graph \(G=(V,E)\) and a value \(\lambda \), the everywhere  \(\lambda \) vector for G is the vector \(y \in \mathbb {R}^{E(K_{|V|})}\) for which \(y_e=\lambda \) for all edges \(e\in E\) and \(y_e=0\) for all the other edges in the complete graph \(K_{|V|}\). In Theorem 4 below we show that for any cubic 3-edge-connected graph with a Hamiltonian cycle, the everywhere 6 / 7 vector is in \(\mathcal {T}^{|V|}\). Since fundamental graphs are Hamiltonian (by Lemma 2 for Boyd–Carr, and by definition for Carr–Vempala), the theorem applies to their 3-edge-connected instances. Both classes of such 3-edge-connected graphs are also fundamental as was noted earlier (see the remark after the definition).

Theorem 4

If \(G=(V,E)\) is a cubic, 3-edge-connected Hamiltonian graph, then the everywhere 6 / 7 vector for G is in \(\mathcal {T}^{|V|}\).

Proof

Let H be a Hamiltonian cycle of G, and let \(M:=E{\setminus } H\) be the perfect matching complementary to H. Note that \(\chi ^H\) is the incidence vector of a tour, and we will use it in the convex combination for the everywhere 6 / 7 vector. It is a good choice in that it is a tour which contains the fewest edges possible, however it will need to be balanced with tours that do not use the edges in H very often in order to achieve our goal. To this end we consider the point \(x \in \mathbb {R}^{E(K_{|V|})}\) defined by \(x_e=1\) if \(e\in M\), \(x_e=1/2\) if \(e\in H\) and \(x_e=0\) otherwise. It is easily seen that x is in the subtour elimination polytope \(\mathcal {S}^{|V|}\), thus by Theorem 2, \(\frac{3}{2} x\in \mathcal {T}^{|V|}\).

Now take the convex combination of tours \(t:=\frac{3}{7}\chi ^H + \frac{4}{7} \frac{3}{2} x\). Then for edges \(e\in M\) we have \(t_e = 0 + \frac{4}{7}\frac{3}{2}=\frac{6}{7}\). For edges \(e\in H\) we have \(t_e =\frac{3}{7} + \frac{4}{7}\frac{3}{2}\frac{1}{2}=\frac{6}{7}\), and \(t_e = 0\) for all edges e not in G, finishing the proof. \(\square \)

Replacing Hamiltonian cycles by other, relatively small tours or convex combinations of tours in the proof of Theorem 4, one may get similar results weakening the Hamiltonicity condition. Such results are particularly interesting for general, cubic 3-edge-connected graphs. For such graphs the everywhere 1 vector is in \(\mathcal {T}^{|V|}\), as noticed in [22], where it is then asked whether the everywhere 8 / 9 vector belongs to \(\mathcal {T}^{|V|}\). These are the values one gets from Theorem 2 to Conjecture 2 respectively, applied to the everywhere 2 / 3 vector, feasible for \(\mathcal {S}^{|V|}\). Note that the analogous problem for the s–t path TSP has been solved [24].

The above possibility has been explored by Haddadan, Newman and Ravi [17], who proved that the everywhere 18 / 19 vector is in \(\mathcal {T}^{|V|}\), getting this constant below 1 for the first time, and with a polynomial-time algorithm. They replaced the Hamiltonian cycle in the proof of Theorem 4 by other “small tours”, defined with the help of the 2-factor provided by a result of Kaiser and Škrekovski [18] and by Boyd, Iwata, Takazawa [5] algorithmically. Even though their tours are not as small as a Hamiltonian cycle, these tours use the edges apparently in a more balanced way: this replacement leads to the mentioned improved uniform vector, below 1. They also note that the improved uniform vector immediately provides improvement upon the 3 / 2 upper bound on the integrality ratio for the more general node-weighted TSP, where every node v of a given graph \(G=(V,E)\) is given a weight \(f_v \in \mathbb {R}_+\), and the cost \(c_{uv}\) of an edge \(uv \in K_{|V|}\) is \(f_u + f_v\) if \(uv \in E\), and the cost of a shortest path in G otherwise.

Let us explain the relation of uniform covers and node-weights with the integrality ratio \(\textit{OPT}(c)/\textit{LP}(c)\) in a general setting, in order to make it easy to apply it in slightly different situations as well. Let \(G=(V,E)\) be a k-regular k-edge-connected graph with metric cost function \(c \in \mathbb {R}^{E(K_{|V|})}\). Note that the everywhere 2 / k vector for G is in \(\mathcal {S}^{|V|}\). We consider cost functions for which the everywhere 2 / k vector is also optimal for \(\textit{LP}(c)\), i.e. \(\textit{LP}(c) = \frac{2}{k}c(E)\). For example, this is true for the graph TSP metric c for G (to see this, note that its objective value is |V|, which is an obvious lower bound). Similarly, following ideas mentioned in [17], it can be seen that the everywhere 2 / k vector is optimal for \(\textit{LP}(c)\) for the more general node-weighted TSP. To see this, note that the constraints (2) of the subtour LP provide a lower bound of \(2 \sum _{v\in V} f_v =\frac{2}{k}c(E)\) for \(\textit{LP}(c)\). Now consider any cost function for which the everywhere 2 / k vector is optimal for \(\textit{LP}(c)\) and suppose we also have that the everywhere \(\lambda \) vector is in \(\mathcal {T}^{|V|}\). Then \(\textit{OPT}(c) \le \lambda c(E)\) and the integrality ratio \(\textit{OPT}(c)/LP(c) \le k\lambda /2\). (For \(k=3\) and \(\lambda <1\) this is indeed smaller than 3 / 2 and for \(\lambda = 18/19\) we get back the remark in [17] mentioned above.) Thus we obtain the following corollary of Theorem 4:

Corollary 1

Let \(G=(V,E)\) be a cubic 3-edge-connected Hamiltonian graph, or in particular a 3-edge-connected fundamental graph, with metric cost function \(c \in \mathbb {R}^{E(K_{|V|})}\) for which the everywhere 2 / 3 vector is optimal for \(\textit{LP}(c)\). Then \(\textit{OPT}(c)/\textit{LP}(c) \le \frac{9}{7}\).

2.2 Rainbow 1-trees

We now use matroid intersection to prove that the convex combination of incidence vectors of 1-trees that exists for any x in the subtour polytope can also satisfy an additional property. We use this in the proof of our main result in Sect. 3.

Given a graph \(G=(V,E)\), let every edge of G be given a colour. We call a 1-tree F of G a rainbow 1-tree if every edge of F has a different colour. Rainbow trees are discussed by Broersma and Li [6], where they note they are the common independent sets of two matroids, a fact combined here with Lemma 1 (i) to obtain the following theorem:

Theorem 5

Let \(x\in \mathcal {S}^n\) be \(\frac{1}{2}\)-integer, and let \(\mathscr {P}\) be any partition of the \(\frac{1}{2}\)-edges into pairs. Then x is in the convex hull of incidence vectors of 1-trees that each contain exactly one edge from each pair in \(\mathscr {P}\).

Proof

Let \(G_x = (V_n, E_x)\) be the support graph of x. Consider the partition matroid (cf. [21]) defined on \(E_x\) by the partition \(\mathscr {P}\cup \{\{e\} : e\in E_x,\) e is a 1-edge}. By Lemma 1, x is in the convex hull of incidence vectors of 1-trees in \(E_x\), which satisfy the basis axioms of a matroid as previously mentioned; since \(x(Q)=1\) for every class Q of the defined partition matroid, it is also in the convex hull of its bases. Thus by [21, Corollary 41.12d], which is a corollary of Edmonds’ matroid intersection theorem [11], x is in the convex hull of incidence vectors of the common bases of the two matroids. \(\square \)

3 Improved bounds for \(\frac{1}{2}\)-integer points

In this section we show that \(\frac{10}{7} x \in \mathcal {T}^n\) for all square points \(x\in \mathcal {S}^n\), and thus for all \(\frac{1}{2}\)-integer Boyd–Carr points x as well. We also analyse the possibility of a similar proof for Carr–Vempala points that would have the advantage of also implying that \(\frac{10}{7}x\in \mathcal {T}^n\) for all \(\frac{1}{2}\)-integer points \(x\in \mathcal {S}^n\), as we discuss at the end of this section. We begin by stating two properties we prove later to be sufficient to guarantee \(\frac{10}{7} x \in \mathcal {T}^n\) for any \(\frac{1}{2}\)-integer vector x in \(\mathcal {S}^n\):

  1. (A)

    The support graph \(G_x\) of x has a Hamiltonian cycle H.

  2. (B)

    Vector x is a convex combination of incidence vectors of 1-trees of \(G_x\) such that each 1-tree satisfies the following condition: it contains an even number of edges in every cut of \(G_x\) consisting of four \(\frac{1}{2}\)-edges in H.

We will use \(\chi ^H\) of (A) as part of the convex combination for \(\frac{10}{7} x\), which is globally good, since H has only n edges, but the \(\frac{1}{2}\)-edges of H have too high a value (equal to 1), contributing too much for the convex combination. To compensate for this, property (B) ensures that x is not only a convex combination of 1-trees, but these 1-trees are even for certain edge cuts \(\delta (S)\), allowing us to use a value essentially less than the \(\frac{x_e}{2}=\frac{1}{4}\) for \(\frac{1}{2}\)-edges e in H for the corresponding T-join. The details of how to ensure feasibility for the T-join polyhedron will be given in the proof of Theorem 6.

While conditions (A) and (B) may look at first sight difficult to meet, Lemma 2 shows that one can count on the bonus of the naturally arising properties: any square point x has a Hamiltonian cycle H that satisfies property (A), moreover it will contain all the 1-edges of \(G_x\). Together with the “rainbow 1-tree decomposition” of Theorem 5 this will imply (B) for square points. The reason we care about the somewhat technical property (B) instead of its more natural consequences is future research: in a new situation we may have to use the most general condition.

Lemma 3

Let x be any square point. Then x satisfies both (A) and (B).

Proof

If we replace the 1-paths in the support graph \(G_x\) by single 1-edges, then by Lemma 2 there is a Hamiltonian cycle for the new graph that contains all of the 1-edges, and thus \(G_x\) also has a Hamiltonian cycle H that contains all of its 1-edges. Thus point x satisfies property (A) . Moreover, since H contains all the 1-edges in \(G_x\), it follows that H contains a perfect matching from each square of \(G_x\).

Define \(\mathscr {P}\) to be the partition of the set of \(\frac{1}{2}\)-edges of \(G_x\) into pairs whose classes are the perfect matchings of squares. Then by Theorem 5, x is in the convex hull of incidence vectors of 1-trees that contain exactly one edge from each pair \(P\in \mathscr {P}\). Property (B) follows, since every cut C that consists of four \(\frac{1}{2}\)-edges of H is partitioned by two classes \(P_1,P_2\in \mathscr {P}\). (Indeed, we saw at the end of the first paragraph of this proof that a square met by H is met in a perfect matching.) Since \(P_1\) and \(P_2\) are met by exactly one edge of each tree of the constructed convex combination, C is met by exactly two edges of each tree. \(\square \)

Next we prove that properties (A) and (B) are sufficient to guarantee that \(\frac{10}{7} x \in \mathcal {T}^n\) for any \(\frac{1}{2}\)-integer point of \(\mathcal {S}^n\). Recall that properties (A) and (B) are more general than what we need for square points: the condition of the theorem we prove does not require that the Hamiltonian cycle of property (A) contains the 1-edges of \(G_x\), as Lemma 2 asserts for square points. We keep this generality of (A) and (B) to remain open to eventual posterior demands of future research.

Theorem 6

Let \(x\in \mathcal {S}^n\) be a \(\frac{1}{2}\)-integer point satisfying properties (A) and (B). Then \(\frac{10}{7} x \in \mathcal {T}^n\).

Proof

Let \(G_x=(V_n,E_x)\) be the support graph of x, and let H be any Hamiltonian cycle of \(G_x\), which exists according to (A). Let the 1-trees in the convex combination for property (B) be \(F_i\), \(i = 1, 2,\ldots ,k\), and for any 1-tree F of \(G_x\) let \(T_{F}\) be the set of odd degree nodes in the graph \((V_n,F)\). Consider the vector \(y\in \mathbb {R}^{E_n}\) defined as \(y:=\frac{2}{3}x - \frac{1}{6}\chi ^H\).

Claim For any 1-tree F of \(G_x\) which satisfies the condition of property (B), vector y is in the \(T_{F}\)-join polyhedron of \(K_n\).

To prove the claim, we show that y satisfies the constraints of the \(T_{F}\)-join polyhedron (6) of \(K_n\). Clearly \(y_e \ge 0\) for all \(e\in E_n\). Let C be a \(T_{F}\)-cut in \(K_n\). We must show \(y(C) \ge 1\). Note that \(|H \cap C|\ne 0\) is even, and \(H\subseteq E_x\).

  1. Case 1:

    \(|H \cap C|= 2\). Since \(x(C) \ge 2\) we have \(y(C) \ge 2(\frac{2}{3}) - 2(\frac{1}{6}) = 1\), as required.

  2. Case 2:

    \(|H \cap C| = 4\). Since \(x\in \mathcal {S}^n\), we have \(x(C) \ge 2\) and since x is \(\frac{1}{2}\)-integer the \(\frac{1}{2}\)-edges form edge-disjoint cycles, so x(C) is integer: \(x(C)\ge 3\), since \(x(C)=2\) would imply that C consists of the four edges of \(H \cap C\), and by (B) C is then not a \(T_{F}\)-cut; so \(y(C) \ge 3(\frac{2}{3}) - 4(\frac{1}{6}) \ge 1\).

  3. Case 3:

    \(|H \cap C|\ge 6\). Then for all \(e \in H \cap C\): \(y_e = \frac{2}{3} x_e - \frac{1}{6}\chi ^H_e \ge \frac{2}{3}(\frac{1}{2})-\frac{1}{6}=\frac{1}{6}\), so \(y(C)\ge 1\), which completes the proof of the claim.

According to the claim, for all \(i\in \{1,\ldots , k\}\) y majorates a convex combination of \(T_{F_i}\)-joins, and adding any one of these to \(\chi ^{F_i}\), we get tours. The convex combination of these tours is majorated by \(\chi ^{F_i} + y\), so \(\chi ^{F_i} + y \in \mathcal {T}^n\) for all \(i=1,\ldots ,k\), and therefore \(x +y \in \mathcal {T}^n\). Thus \(z:= \frac{1}{7}\chi ^H + \frac{6}{7}(x + y)= \frac{10}{7} x\) is also in \(\mathcal {T}^n\), which completes the proof. \(\square \)

Our main result follows from the above theorem:

Theorem 7

Let x be a square point. Then \(\frac{10}{7}x \in \mathcal {T}^n\).

Proof

By Theorem 6 it is enough to make sure that x satisfies properties (A) and (B), which is exactly the assertion of Lemma 3. \(\square \)

Since \(\frac{1}{2}\)-integer Boyd–Carr points are square points we have:

Corollary 2

If x is a \(\frac{1}{2}\)-integer Boyd–Carr point, then \(\frac{10}{7}x \in \mathcal {T}^n\).

Theorem 7 immediately implies the following optimization form of the above corollary:

Corollary 3

Let \(c\in \mathbb {R}^{E_n}\) be a metric cost function optimized by a square point x, i.e. \(cx = \textit{LP}(c)\). Then there exists a Hamiltonian cycle of cost at most \(\frac{10}{7} \textit{LP}(c)\) in \(K_n\).

Proof

We have \(\frac{10}{7} \textit{LP}(c)=\frac{10}{7} cx= c(\frac{10}{7} x)\ge \textit{OPT}_{\mathcal {T}^n}(c)\), where the last inequality follows from \(\frac{10}{7} x\) being a convex combination of tours by Theorem 7. As \(\textit{OPT}_{\mathcal {T}^n}(c) \ge \textit{OPT}(c)\) for metric costs, the result follows. \(\square \)

In the following section we show that the above existence theorems and their corollaries can also be accompanied with polynomial algorithms. We finish this section by showing that the integrality gap of square points is at least \(\frac{4}{3}\), providing new examples showing that Conjecture 1 cannot be improved.

Define a subclass of square points we call k-donuts, \(k\in \mathbb {Z}\), \(k\ge 2\): the support graph \(G_x=(V_n,E_x)\) consists of k \(\frac{1}{2}\)-squares arranged in a cyclic order, where the squares are joined by 1-paths, each of length k. In Fig. 2 the support graph of a 4-donut is shown. In the figure, dashed edges represent \(\frac{1}{2}\)-edges and solid edges represent 1-edges.

We define the cost of each edge in \(E_x\) to be 1, except for the pair of \(\frac{1}{2}\)-edges in each square that are opposite to one another, with one edge on the inside of the donut, and one on the outside, which are defined to have cost k (see the figure, where only edges of cost k are labelled, and all other edges in \(E_x\) have cost 1). The costs of other edges of \(K_n\) not in \(E_x\) are defined by the metric closure (cost of shortest paths in \(G_x\)). For these defined costs \(c^{(k)}\), we have \(\textit{OPT}(c^{(k)})= 4k^2 - 2k + 2\) and \(\textit{LP}(c^{(k)}) \le c^{(k)}x = 3k^2 + k\), thus \(\lim _{k\rightarrow \infty }\frac{\textit{OPT}(c^{(k)})}{\textit{LP}(c^{(k)})}\ge \frac{4}{3}\). Along with Theorem 7, this gives the following:

Corollary 4

The integrality gap for square points is at least \(\frac{4}{3}\) and at most \(\frac{10}{7}\).

Fig. 2
figure 2

Graph \(G_x\) for a k-donut x, \(k=4\)

Full size image

To conclude this section we briefly discuss the ideas used in creating the Boyd–Carr and Carr–Vempala fundamental classes and their ramifications for general \(\frac{1}{2}\)-integer points of \(\mathcal {S}^n\). In general, Boyd–Carr and Carr–Vempala points are obtained by starting with any \(x \in \mathcal {S}^n\) and applying a specific transformation to x to create a new point \(y \in \mathcal {S}^p, p>n\) which has the required form and properties for the fundamental class. Note that for the Boyd–Carr points that have been our focus, the transformation used from general vertices \(x\in \mathcal {S}^n\) to these Boyd–Carr points does not completely preserve the denominators. In particular, \(\frac{1}{2}\)-integer vertices of \(\mathcal {S}^n\) get transformed into Boyd–Carr points \(x^*\) with \(x^*_e\) values in \(\{1, \frac{1}{2}, \frac{3}{4}, \frac{1}{4}, 0\}\). However, for the Carr–Vempala points, it is clear from their construction in [8] that general \(\frac{1}{2}\)-integer vertices of \(\mathcal {S}^n\) lead to \(\frac{1}{2}\)-integer Carr–Vempala vertices. In fact we have the following theorem which, if Conjecture 3 is true, would provide a nice approach for proving Conjecture 2, since it is given for free that Carr–Vempala vertices satisfy property (A):

Theorem 8

If \(\rho x \in \mathcal {T}^n\) for each \(\frac{1}{2}\)-integer Carr–Vempala point \(x\in \mathcal {S}^n\), then \(\rho x \in \mathcal {T}^n\) for every \(\frac{1}{2}\)-integer point \(x \in \mathcal {S}^n\).

In light of these results and conjectures it seems worthwhile to study fundamental classes further and the role of \(\frac{1}{2}\)-integer points in them.

4 Related algorithms

In this section we show that some of the existence theorems stated in the previous sections can be accompanied by simple combinatorial algorithms that can be executed in polynomial time. The main result of this section is a polynomial-time algorithm for finding the Hamiltonian cycle of Corollary 3 in a completely elementary way. We point out that the bridge taking us to this result also leads to a polynomial-time algorithm for finding a minimum cost Hamiltonian cycle containing the M edges in a square graph (G, M), generalizing Lemma 2. It turns out that the greedy algorithm is the main ingredient of this algorithm, and delta-matroids are the structure behind this phenomenon. We give a short introduction to delta-matroids, their greedy algorithm and their connection to our results in Sect. 5. First we introduce the algorithms with direct proofs on our combinatorial objects below.

figure a

In the following theorem we show that algorithm (HAM) is well-defined and determines a Hamiltonian cycle containing M, moreover it is a minimum cost such Hamiltonian cycle. This is not difficult to prove directly along the same lines as the optimality of the greedy algorithm for optimal spanning trees.

Theorem 9

The output graph H produced by (HAM) for a square graph (G, M) is a Hamiltonian cycle of G containing M of minimum cost.

Proof

First we show that (HAM) is well-defined and does indeed output a Hamiltonian cycle H containing M. Clearly all degrees in H are two, thus it is enough to show that in iteration \(i\in \{1,\ldots , t\}\) of step 2 at least one of the two choices keeps the current graph H connected, and thus H is a Hamiltonian cycle. So suppose that at iteration i, \(H-C_i\) (edge-deletion) is not connected. Then it has at least two of the four arising nodes of degree 1 (the only nodes of odd degree after contracting the remaining squares) in each component. It follows that it has two components. If adding one of the two perfect matchings it is still not connected, then all edges of \(C_i\) are induced by one of the two components, so H is also not connected, a contradiction.

Next we show that H is a minimum cost Hamiltonian cycle containing M. Suppose for a contradiction that K is a Hamiltonian cycle of smaller cost containing M. Then there exists a square \(C_i\) for which K uses a different perfect matching than H and the cost of this perfect matching is strictly less than the one used by H. Let i be the smallest index for which this is true, and assume that over all minimum cost Hamiltonian cycles containing M, we chose K to be the one for which this i is as large as possible. By the algorithm, when we considered square \(C_i\), we know that removing the smaller cost perfect matching disconnected the graph (or it would have been chosen). Thus there must exist another square \(C_j\) crossing the cut formed by this disconnection for which K chooses a different perfect matching of \(C_i\) than H, and \(j < i\). By choice of index i, we know that the perfect matching used in \(C_j\) by K has cost greater than or equal to the one used by H. Now consider the new Hamiltonian cycle \(K^\prime \) obtained by taking K, and swapping the perfect matchings used by K in squares \(C_i\) and \(C_j\). We have \(c(K^\prime ) = c(K) + w_{C_i} - w_{C_j}\) and since \(w_{C_j} \ge w_{C_i}\) by the index ordering, we must have that \(K^\prime \) is another minimum cost Hamiltonian cycle. Again there must exist a square \(C_r\) for which \(K^\prime \) uses a different perfect matching than H and the cost of this perfect matching is strictly less than the one used by H, but by construction of \(K^\prime \) we have \(r>i\). But this contradicts our choice of K. \(\square \)

We now propose the following algorithm for finding a tour of relatively small cost for cost functions optimized at square points. It is in some ways a translation of Theorem 6 from the language of convex combinations into the context of optimizing an objective function (it can be considered to be the ‘derandomization’ of the proof of Theorem 6 where convex combinations are interpreted as mean values of random variables). The algorithm is similar to Christofides algorithm [9] in that it creates a tour by finding a minimum cost 1-tree and then adds a minimum cost T-join for the odd-degree nodes T in the 1-tree. However for our algorithm a Hamiltonian cycle is also required, as well as a 1-tree which satisfies additional properties.

figure b

We can now complete Corollary 3 with an algorithmic postulate, making use of some of the ideas used in the proof of Theorem 6:

Theorem 10

Let \(c\in \mathbb {R}^{E_n}\) be a metric cost function optimized by a square point x, \(cx = \textit{LP}(c)\). Then there exists a Hamiltonian cycle of cost at most \(\frac{10}{7} \textit{LP}(c)\) in \(K_n\) and (TOUR) can be used to find such a cycle in polynomial time.

Proof

Note that the algorithm (HAM) is polynomial, as are the algorithms referenced for steps 2 and 3 in (TOUR). Thus algorithm (TOUR) is a polynomial-time algorithm.

Let H be the Hamiltonian cycle of the support graph \(G_x\) that contains all of the 1-edges, provided algorithmically by (HAM), and let \(J^*\) be the tour of \(G_x\) determined in (TOUR). Note that the 1-tree \(F^*\) from step 2 of (TOUR) satisfies the condition of property (B), and thus by the claim in the proof of Theorem 6 we have \(y:=\frac{2}{3}x - \frac{1}{6}\chi ^H\) is in the \(T_{F^*}\)-join polyhedron (6) of \(K_n\) . Therefore the cost of the minimum cost \(T_{F^*}\)-join found in step 3 is at most cy. By Theorem 5, \(c(F^*)\le cx\), which gives \(c(J^*)\le cx + cy\). Thus

$$\begin{aligned} \min \left\{ c(H), c(J^*)\right\}\le & {} \frac{1}{7}c(H) + \frac{6}{7}c(J^*)\le \frac{1}{7}c(H) + \frac{6}{7} cx\\&+ \frac{6}{7} \left( \frac{2}{3} cx - \frac{1}{6} c(H)\right) = \frac{10}{7}LP(c) \end{aligned}$$

is the cost of a tour, and shortcutting this tour we get a Hamiltonian cycle of \(K_n\) not larger in cost. \(\square \)

Note that the above proof actually used less than what (HAM) produces: for (TOUR) it is sufficient to use any Hamiltonian cycle in \(G_x\) containing its 1-edges that can be found in polynomial time, not necessarily the optimal one! However, sharper or more general results may need the exact optimum here. This motivates us to sketch some details about delta-matroids that are in the background in the next section.

5 Delta-matroids

Throughout the previous sections the background role of delta-matroids has been mentioned. Indeed, square graphs (G, M) and their Hamiltonian cycles containing M lead naturally to 4-regular graphs and their Eulerian trails with one forbidden bitransition, which are known to form a delta-matroid due to Bouchet [2]. Knowing that the greedy algorithm in a general setting allowing negative weights is valid—and actually characterizes—delta-matroids, has led to defining the greedy algorithm for finding an optimal Hamiltonian cycle containing M.

Despite their role we have not actually used delta-matroids in the previous sections: the facts that we learnt from this connection could be easily proved directly, in an elementary way and therefore the preceding sections are self-contained. However, for a deeper understanding and possible further use, we sketch in this section the simple, but fruitful connection of our results to delta-matroids.

The family \(\mathscr {D}\ne \emptyset \) of subsets of a finite set S, or the pair \((S,\mathscr {D})\) is called a delta-matroid if the following symmetric exchange axiom (also called the 2-step axiom) is satisfied: For \(D_1, D_2\in \mathscr {D}\) and \(j\in D_1\varDelta D_2\) there exists \(k\in D_1\varDelta D_2\) such that \(D_1\varDelta \{j,k\}\in \mathscr {D}\). Note that \(k=j\) is possible, and we then naturally define \(\{j,j\}:=\{j\}\). The members of \(\mathscr {D}\) are called the feasible sets of the delta-matroid.

Delta-matroids were introduced by Bouchet, cf. [2]. For the introduction and the basics about them we follow [3].

A delta-matroid \((S,\mathscr {D})\) may have an exponential number of feasible sets, too many to be given explicitly. Fortunately, in order to work with delta-matroids we need less than giving all of its feasible sets as input. The basic and simple greedy algorithm already necessitates a solution of the following problem [3, (2.1)]: let \((S,\mathscr {D})\) be a delta-matroid, then for given (A, B) where \(A, B\subseteq S\), decide whether there exists \(D\in \mathscr {D}\) such that \(D\supseteq A\), \(D\cap B=\emptyset \). Let us call an oracle that solves this problem the extendability oracle for the given delta-matroid. (This is referred to as the “separation oracle” in [2].) This oracle can be executed in polynomial time for all the relevant applications, and we will have to check that this also holds for the delta matroid for which we need it.

Think about the set A as a set of elements chosen to be in the solution, and B the set of elements chosen not to be in the solution. Roughly, for an objective function \(c\in \mathbb {R}^S\), the greedy algorithm considers the elements of S in decreasing order of the absolute values and attempts to put a considered \(s\in S\) into A or B: If \(c(s)\ge 0\) and “it is possible” to be put in A, then it is put in A; if \(c(s)\le 0\) and “it is possible” to put it in B, then it is put in B. (“It is possible” means a YES answer of the extendibility oracle with the attempted update \(A\cup \{s\}\) of A or \(B\cup \{s\}\) of B. Note that the extendability of (A, B) implies that at least one of \((A\cup \{s\}, B)\), or \((A, B\cup \{s\})\) is also extendable.)

The following theorem is a generalization of Lemma 2 and therefore a direct proof of it. Given a square graph (G, M), let \(R=R(G)\subseteq E(G){\setminus } M\) be a reference set containing exactly one edge from each square of \(E(G){\setminus } M\); \(|R|=|V(G)|/4\). Let \(\mathscr {H}=\mathscr {H}(G)\) be the set of Hamiltonian cycles of G containing M.

Theorem 11

Let (G, M) be a square graph. Then \(\mathscr {H}\ne \emptyset \), and

$$\begin{aligned} \mathscr {D}:=\{H\cap R: H \in \mathscr {H}\} \end{aligned}$$

is a delta-matroid.

Proof

We have already seen earlier in Sect. 4 [see (HAM) and the proof of Theorem 9] that we can can replace, one by one, one after the other, the squares of G by one of their two perfect matchings and remain connected, and thus \(\mathscr {H}\ne \emptyset \).

In order to prove that \(\mathscr {D}\) is a delta-matroid, it is enough to check that for any two Hamiltonian cycles \(H_1\ne H_2\) of G that contain M, and any square C of G—M where \(H_1\) and \(H_2\) do not use the same perfect matching of C, either \(H_1\triangle C\) is also a Hamiltonian cycle or there exists a square D of G—M so that \(H_1\triangle C\triangle D\) is a Hamiltonian cycle.

To prove this, suppose \(H_1\triangle C\) is not a Hamiltonian cycle. It is still a 2-factor—subset of edges with all degrees equal to 2—with two components, with the cut \(Q\subseteq E(G)\) between the two components. Since \(H_2\) is connected, it contains a square D so that for one of the two perfect matchings of D: \(H_2\cap D \cap Q\ne \emptyset \). But then clearly, \(H_1\) and \(H_2\) do not use the same perfect matching of D, and we know \(H_1\triangle C\) is not connected. So by the claim \(H_1\triangle C \triangle D\) is again connected, and is thus a Hamiltonian cycle containing M. \(\square \)

Note that the above theorem is actually reproving Lemma 2 directly. In the proof of the lemma the contraction of the squares provided the correspondance between Hamiltonian cycles and Eulerian tours, where the two perfect matchings of each square are in bijection with the two bitransitions in the corresponding node of the contracted graph. Through this bijection, the set \(\mathscr {D}\) is the same as the family of feasible sets of Bouchet’s delta-matroid from Eulerian trails [2]. For the delta-matroid \(\mathscr {D}\) of the theorem the extendability oracle can be easily computed in polynomial time, and so Bouchet’s greedy algorithm [2, 3] is well defined for them. Note that algorithm (HAM) is indeed this greedy algorithm applied to the delta matroid \(\mathscr {D}\).