## Parameterized TSP: Beating the Average ∗

Gregory Gutin Royal Holloway, University of London e-mail: gutin@cs.rhul.ac.uk

Viresh Patel Queen Mary, University of London e-mail: viresh.patel@qmul.ac.uk

August 5, 2014

## Abstract

In the Travelling Salesman Problem (TSP), we are given a complete graph K n together with an integer weighting w on the edges of K n , and we are asked to find a Hamilton cycle of K n of minimum weight. Let h w ( ) denote the average weight of a Hamilton cycle of K n for the weighting w . Vizing (1973) asked whether there is a polynomialtime algorithm which always finds a Hamilton cycle of weight at most h w ( ). He answered this question in the affirmative and subsequently Rublineckii (1973) and others described several other TSP heuristics satisfying this property. In this paper, we prove a considerable generalisation of Vizing's result: for each fixed k , we give an algorithm that decides whether, for any input edge weighting w of K n , there is a Hamilton cycle of K n of weight at most h w ( ) -k (and constructs such a cycle if it exists). For k fixed, the running time of the algorithm is polynomial in n , where the degree of the polynomial does not depend on k (i.e., the generalised Vizing problem is fixed-parameter tractable with respect to the parameter k ).

## 1 Introduction

The Travelling Salesman Problem (TSP) is one of the most well-known and widely studied combinatorial optimisation problems. In this problem, we are

∗ GG's research was partially supported by Royal Society Wolfson Research Merit Award

given an n -vertex complete graph K n with weights on its edges and we are required to find a Hamilton cycle in K n of minimum total weight. In its full generality, TSP is not only NP-hard, but also NP-hard to approximate to within any constant factor. Therefore there has been much attention in developing approximation algorithms for restricted instances of TSP. In this paper, we consider general TSP, but rather than seeking a Hamilton cycle of minimum weight, we seek a Hamilton cycle that beats the average weight of all Hamilton cycles by some given value.

Let us fix some notation in order to state our result. As usual V ( G ) and E G ( ) denote the vertex and edge sets of a graph G . Let w be an integer edge weighting of K n , i.e. w : E K ( n ) → Z , and let G be a subgraph of K n . We write

$$w ( G ) & \coloneqq \sum _ { e \in E ( G ) } w ( e ) \quad \text{ and } \quad w [ G ] \coloneqq \sum _ { e \in E ( G ) } | w ( e ) | \\ \intertext { n d w d f i n o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n of o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o t o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n t o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f O n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f O o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o r o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o ft o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o f o n o fs o n o f o n o f o n o f o n o f o n o fs o n o f o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n ofs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o f o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n ofs o n o fs o n ofs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n ofs o n o fs o n o f o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o f o n o fs o n ofs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o f o n o fs o n o f o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n ofs o n o fs o n o fs o n ofs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o fs o n o$$

and we define the density d = d w ( ) of w to be the average weight of an edge, i.e. d := w K ( n ) / ( ) n 2 . Note that E ( w H ( ˜ )) = dn , where ˜ H is a uniformly random Hamilton cycle of K n , and so there always exists a Hamilton cycle H ∗ satisfying w H ( ∗ ) ≤ dn .

Vizing [15] asked whether there is a polynomial-time algorithm which, given an integer edge weighting w of K n , always finds a Hamilton cycle H ∗ of K n satisfying w H ( ) ≤ dn . He answered this question in the affirmative and subsequently Rublineckii [14] described several other TSP heuristics satisfying this property. Such TSP heuristics including more recent ones are given in [10]. A natural question extending Vizing's question is the following: for each fixed k is there a polynomial-time algorithm which, given w , determines if there exists a Hamilton cycle H ∗ satisfying w H ( ∗ ) ≤ dn -k ? We give an affirmative answer to this question.

Theorem 1.1 There exists an algorithm which, given ( n, w, k ) as input, where n, k ∈ N and w : E K ( n ) → Z , determines whether there exists a Hamilton cycle H ∗ of K n satisfying

$$w ( H ^ { * } ) \leq d n - k$$

(and outputs such a Hamilton cycle if it exists) in time O k ( 3 )! + O k n ( 3 ) + O n ( 7 ) = f ( k n ) O (1) .

Note that our algorithm includes arithmetic operations which are assumed to take time O (1) and so our running times here and throughout are stated in the strong sense (see e.g. [8]). To obtain the running time in the weak sense, one simply multiplies by log M , where M := max e ∈ E K ( n ) | w e ( ) | for the input instance ( n, w, k ).

Theorem 1.1 immediately implies that the following NP-hard problem (which is essentially TSP) is fixed-parameter tractable 1 when parameterised by k .

Travelling Salesman Problem Below Average ( TSP BA )

Instance :

( n, w, k ), where n, k ∈ N and w : E K ( n ) → Z

Question

: Is there a Hamilton cycle H ∗ of K n satisfying w H ( ∗ ) ≤ dn - k ?

Theorem 1.1 is proved by applying a combination of probabilistic, combinatorial, and algorithmic techniques, some of which are inspired by [11]. The key step to proving Theorem 1.1 is Theorem 1.2 below, which characterises those weightings in which all Hamilton cycles have weight close to the average. We believe this result will have further applications.

Theorem 1.2 For any n, k ∈ N satisfying n &gt; 5000( k + 1) , and w : E K ( n ) → Z , in time O n ( 7 ) we can find either

- (a) A Hamilton cycle H ∗ of K n satisfying w H ( ∗ ) &lt; dn -k , or
- (b) A weighting w ∗ : E K ( n ) → Z and α ∈ Z satisfying w ∗ ( H ) = w H ( ) + α for all Hamilton cycles H of K n and w K [ n ] ≤ 4000 kn .

Note that since k is the parameter, it can be viewed as a constant, and so we may assume that n ≥ g k ( ) for any function g .

Related work The problem we consider in this paper falls into a class of problems introduced by Mahajan, Raman, and Sikdar [12]. The general framework is the following. Consider a combinatorial optimisation problem in which one is seeking a feasible solution of minimum (or maximum) value and suppose further that one is always guaranteed to find a feasible solution whose value is at most (or at least) some non-trivial (often tight) bound b (e.g. in our case, for any instance of TSP, one can always find a Hamilton cycle of weight at most dn where d is the average weight of an edge of K n ). One can then consider the problem, parameterised by k , of determining whether there exists a feasible solution of value at most b -k (or at least b + ). A variety k of techniques combining tools from linear algebra, the probabilistic method, Harmonic analysis, combinatorics and graph theory have been applied to such problems; see [9] for a survey. Here, we mention progress on only a small sample of such problems.

For the Maximum r -Satisfiability Problem, given a multiset of m clauses of size r , a straigtforward probabilistic argument shows that there exists a

1 For a recent introductions to parameterised algorithms and complexity, see monographs [3, 4].

truth assignment satisfying at least (2 r -1) m/ 2 r clauses and this is tight. Alon et al. [1] showed that one can decide in time O m ( ) + 2 O k ( 2 ) if there is a truth assignment satisfying at least ((2 r -1) m + k / ) 2 r clauses, where they used a combination of probabilistic, combinatorial and Harmonic analysis tools.

For the Max-Cut problem, the Edwards-Erd¨s bound [6, 7] states that o every connected graph on n vertices and m edges has a cut of size at least m 2 + n -1 4 and this is tight. Crowston, Jones, and Mnich [2] showed that it is fixed-parameter tractable to decide whether a given graph on n vertices and m edges has a cut of size at least m 2 + n -1 4 + k . This was later extended by Mnich et al. [13] to so-called λ -extendible properties ; as special cases of their result, they could extend the Max-Cut result above to the Max q -Colourable Subgraph problem and the Oriented Max Acyclic Digraph problem.

Organisation The rest of the paper is organised as follows. In the next section we set out the notation we use throughout. Section 3 gives a brief discussion of some the ideas that are used to prove Theorem 1.1 and Theorem 1.2. In Section 4, we show how standard derandomisation techniques can be applied to the Travelling Salesman Problem in preparation for Sections 5 and 6. Section 5 is dedicated to the proof of Theorem 1.2 and this is used in Section 6 to prove Theorem 1.1.

## 2 Notation and Terminology

In this section, for convenience, we collect some notation and terminology (mostly standard) that we shall use throughout.

Let G be a graph. The vertex set and edge set of G are denoted by V ( G ) and E G ( ) respectively and we write e G ( ) for the number of edges in G . A graph F is a subgraph of G written F ⊆ G if V ( F ) ⊆ V ( G ) and E F ( ) ⊆ E G ( ). We say F is a spanning subgraph of G if V ( F ) = V ( G ) and E F ( ) ⊆ E G ( ).

/negationslash

For X ⊆ V ( G ), we write X (2) for the set of all edges ab such that a, b ∈ X and a = . We write b G X [ ] for the graph induced by G on X and G -X for the graph obtained from G by deleting all vertices in X i.e. G -X := G V [ ( G ) \ X ]. For S ⊆ E G ( ), G -S is the graph obtained from G by deleting all the edges in S , i.e. G -S := ( V ( G , E G ) ( ) \ S ). If S ⊂ V ( G ) (2) then we write G ∪ S := ( V ( G , E G ) ( ) ∪ S ) (and we write G ∪ e rather than G ∪ { } e if S = { } e ). For disjoint subsets A, B of V ( G ), we write G A, B [ ] for the graph with vertex set A ∪ B and edge set { e = ab ∈ E G ( ) | a ∈ A, b ∈ B } . For a vertex v ∈ V ( G ), N G ( v ) denotes the set of neighbours of v in G and

d v ( G ) := | N G ( v ) | denotes the degree of v . The maximum and minimum degree of G is denoted by δ G ( ) and ∆( G ) respectively.

Apath P = v v 1 2 · · · v k is the graph with vertices v 1 . . . , v k and edges v v i i +1 for i = 1 , . . . , k -2. For a path P , we sometimes write v Pv 1 k for the same path to indicate that v 1 and v k are its end-vertices and we say v , . . . , v 2 k -1 are the internal vertices of P . The notation extends in the natural way for concatenated paths so that if v Pv 1 k and w Qw 1 /lscript are paths and x , . . . , x 1 t are vertices, then v Pv x 1 k 1 · · · x w Qw t 1 /lscript is the path v 1 · · · v x k 1 · · · x w t 1 · · · w /lscript . A cycle C = v 1 · · · v v k 1 is the graph with vertices v 1 . . . , v k and edges v v 1 k and v v i i +1 for i = 1 , . . . , k -2. We call it a k -cycle if it has k vertices. A cycle that is a spanning subgraph of a graph G is called a Hamilton cycle of G . As before, we can write a cycle as a concatenation of paths. A matching of G is a subgraph of G of maximum degree 1; a perfect matching of G is a spanning matching of G . The complete graph on n vertices is denoted by K n .

Repeating notation from the introduction, recall that an instance of TSP BA consists of a triple ( n, w, k ), where n, k ∈ N and w : E K ( n ) → Z . We sometimes drop the parameter k (when it is not relevant) and refer to instances ( n, w ). For a subgraph G of K n , we write

$$w ( G ) \coloneqq \sum _ { e \in E ( G ) } w ( e ) \quad \text{ and } \quad w [ G ] \coloneqq \sum _ { e \in E ( G ) } | w ( e ) |$$

and we define the density d = d n, w ( ) of ( n, w ) to be the average weight of an edge, i.e. d := w K ( n ) / ( ) n 2 .

## 3 Overview

We remark at the outset that the discussion in this section is not required to understand the sections that follow; some definitions will be repeated later.

Structural result The key step for the algorithm of Theorem 1.1 is the structural result, Theorem 1.2. In order to explain the idea behind its proof, let us recast Theorem 1.2 in the language of norms.

We say two instances ( n, w ) and ( n, w ′ ) of TSP BA are equivalent, written ( n, w ) ∼ ( n, w ′ ), if there exists some α ∈ Z such that w H ′ ( ) = w H ( ) + α for every Hamilton cycle H of K n . We define

$$\| ( n, w ) \| _ { 1 / \sim } \coloneqq \min \{ w ^ { \prime } [ K _ { n } ] \, \colon w ^ { \prime } \sim w \}.$$

For an instance ( n, w ) of density d , if k ∗ is such that dn -k ∗ is the weight of a minimum weight Hamilton cycle of K n , we define ‖ ( n, w ) ‖ HC := k ∗ . Then

the main substance of Theorem 1.2 is that the following inequality holds:

$$\| ( n, w ) \| _ { 1 / \sim } \leq 4 0 0 0 n \| ( n, w ) \| _ { \text{HC} }.$$

This is proved by considering a third parameter ‖ ( n, w ) ‖ 4 -cyc that is easily computed by examining the 4-cycles of K n . This parameter is introduced in Section 5, and in the same section we prove the two inequalities

$$\| ( n, w ) \| _ { 1 / \sim } \leq \frac { 4 0 0 0 } { n ^ { 2 } } \| ( n, w ) \| _ { 4 - \text{cyc} }$$

$$\frac { 1 } { n ^ { 3 } } \| ( n, w ) \| _ { 4 - \text{cyc} } & \leq \| ( n, w ) \| _ { \text{HC} },$$

which together prove (1).

We make some further remarks. Note that for fixed n , the set of instances ( n, w ) with the obvious notions of addition and scalar multiplication is the vector space R E K ( n ) . One can show that ∼ is an equivalence relation and the equivalence classes are translates of Z , the set of instances equivalent to the all-zero weighting, which turns out to be an ( n -1)-dimensional subspace of R E K ( n ) . Furthermore, each of ‖·‖ 1 / ∼ , ‖·‖ 4 -cyc , and ‖·‖ HC are pseudo-norms on R E K ( n ) and norms on the quotient space R E K ( n ) /Z . In particular, Z is precisely the set of instances ( n, w ) in which all Hamilton cycles have the same weight dn , where d is the density of ( n, w ).

Algorithmic result Once we have established the structural result Theorem 1.2, we can construct the algorithm of Theorem 1.1. Given ( n, w, k ), if Theorem 1.2 does not already give us the desired Hamilton cycle of weight at most dn -k , then we can find an equivalent instance ( n, w , k ′ ) with w K ′ [ n ] ≤ 4000 kn . If we can find a large matching in the graph of edges assigned a negative weight by w ′ then we can extend it (in a random way) to a desired Hamilton cycle of low weight. If such a matching does not exist, then one can easily conclude that all edges asigned a negative weight by w ′ are incident with only a small set (of size depending on k but independent of n ) of vertices. It turns out that, with this additional structure, one can in fact find the minimum weight Hamilton cycle for ( n, w ′ ) (and hence the minimum weight Hamilton cycle for ( n, w )) in FPT-time i.e. time f ( k n ) O (1) , where f is a function of k only.

## 4 Derandomisation

In this section we present some standard derandomisation arguments that we shall require later. First some notation.

We denote by H n the set of all Hamilton cycles of the complete graph K n . For any graph (or set of edges) G , let H G n := { H ∈ H n | G ⊆ H } . In general we shall denote by ˜ H a uniformly random element of H n , and by ˜ H G a uniformly random element of H G n .

We say a graph G ⊆ K n is a partial Hamilton cycle of K n if G is a spanning subgraph of some H ∈ H n ; thus G is either a Hamilton cycle or the union of vertex disjoint paths (where we allow a path to be a singleton vertex). A path consisting of a single vertex is called a trivial path , and a path on several vertices is called a non-trivial path . We shall use the following simple fact several times: if G is a partial Hamilton cycle with r non-trivial paths and s trivial paths then

$$| \mathcal { H } _ { n } ^ { G } | = 2 ^ { r - 1 } ( r + s - 1 )!.$$

For G a partial Hamilton cycle of K n , we denote by J G ( ) the set of edges in K n which join two paths of G together into a single path. If G is a Hamilton path, J G ( ) is defined to be the unique edge between the two ends of the path.

Lemma 4.1 Suppose we have a function X : H → n Q and for every partial Hamilton cycle G of K n , assume we can compute E ( X H ( ˜ G )) in time f ( n ) . Then for any given partial Hamilton cycle G ∗ , we can find in time O n f n ( 3 ( )) a Hamilton cycle H ∗ ∈ H G ∗ n such that X H ( ∗ ) ≤ E ( X H ( ˜ G ∗ )) .

Proof From the law of total expectation, we have

$$\mathbb { E } ( X ( \tilde { H } ^ { G } ) ) = \sum _ { e \in J ( G ) } \mathbb { P } ( e \in \tilde { H } ^ { G } ) \ \mathbb { E } ( X ( \tilde { H } ^ { G \cup e } ) ) \quad$$

and so we know there exists some e ∈ J G ( ) such that E ( X H ( ˜ G e ∪ )) ≤ E ( X H ( ˜ G )).

We construct H ∗ by adding edges one at a time to G ∗ as follows. Assume G ∗ has q edges for some q ≥ 0 and set G q := G ∗ . Assume we have constructed a partial Hamilton cycle G q ′ ⊇ G q with q ′ ≥ q edges satisfying E ( X H ( ˜ G q ′ )) ≤ E ( X H ( ˜ G q )). For each e ∈ J G ( q ′ ) we compute E ( X H ( ˜ G q ′ ∪ e )) and determine an edge e ∗ for which E ( X H ( ˜ G q ′ ∪ e ∗ )) ≤ E ( X H ( ˜ G q ′ )). This can be done in time O f n n ( ( ) 2 ). We set G q ′ +1 := G q ′ ∪ e ∗ . After at most n iterations of this process, we obtain a Hamilton cycle H ∗ satisfying the desired condition. The running time is therefore bounded by O f n n ( ( ) 3 ). /square

Lemma 4.2 Given any instance ( n, w ) and any partial Hamilton cycle G of K n , we can find in time O n ( 5 ) a Hamilton cycle H ∗ ∈ H G n such that w H ( ∗ ) ≤ E ( w H ( ˜ G )) .

Proof Apply the previous lemma. We can compute E ( w H ( ˜ G )) in time O n ( 2 ). Indeed, note that

$$\mathbb { E } ( w ( \tilde { H } ^ { G } ) ) = w ( G ) + \sum _ { e \in J ( G ) } \mathbb { P } ( e \in \tilde { H } ^ { G } ) w ( e ) \\ \hat { \ }. \,.$$

and using (4),

$$\mathbb { P } ( e \in \tilde { H } ^ { G } ) = \frac { | \mathcal { H } _ { n } ^ { G \cup e } | } { | \mathcal { H } _ { n } ^ { G } | } = \frac { 2 ^ { r ^ { \prime } - 1 } ( r ^ { \prime } + s ^ { \prime } - 1 )! } { 2 ^ { r - 1 } ( r + s - 1 )! },$$

where r, s are the numbers of non-trivial and trivial paths in G and r , s ′ ′ are the numbers of non-trival and trivial paths in G ∪ e . In fact it is not hard to see that if e ∈ J G ( ), then r + s = r ′ + s ′ +1, and so

$$\mathbb { P } ( e \in \tilde { H } ^ { G } ) = \frac { 2 ^ { r ^ { \prime } - r } } { r + s - 1 }.$$

Thus since | J G ( ) | = O n ( 2 ), we can compute E ( w H ( ˜ G )) in time O n ( 2 ) as required. /square

## 5 The structural result

Our aim in this section is to prove Theorem 1.2. In this section, an instance refers to a pair ( n, w ) where w : E K ( n ) → Z . Let us denote the set of 4-cycles of K n by C n . Given an instance ( n, w ) and a 4-cycle C = v v v v v 1 2 3 4 1 ∈ C n , we define the balance of C (with respect to ( n, w )) to be

$$\text{bal} _ { ( n, w ) } ( C ) = \text{bal} ( C ) \coloneqq | w ( v _ { 1 } v _ { 2 } ) + w ( v _ { 3 } v _ { 4 } ) - w ( v _ { 1 } v _ { 3 } ) - w ( v _ { 2 } v _ { 4 } ) |.$$

We say that C is balanced if bal( C ) = 0; otherwise we say C is unbalanced . For a set A ⊆ C n , we define

$$\text{bal} ( \mathcal { A } ) \coloneqq \sum _ { C \in \mathcal { A } } \text{bal} ( C ),$$

and we set

Our first lemma gives a polynomial-time witness to the inequality (3).

$$\| ( n, w ) \| _ { 4 - \text{cyc} } \coloneqq \text{bal} ( \mathcal { C } _ { n } ) = \sum _ { C \in \mathcal { C } _ { n } } \text{bal} ( C ). \\ \ n m a \text{ gives a nolvnomial-time witness to the maximal}$$

Lemma 5.1 For a given instance ( n, w ) and k ∈ Q , suppose ‖ ( n, w ) ‖ 4 -cyc ≥ kn 3 . Then there exists a Hamilton cycle H satisfying w H ( ) &lt; dn -k . Furthermore, we can find such a Hamilton cycle in time O n ( 7 ) .

Before we can prove this lemma, we require several preliminary results. Suppose H = v v 1 2 · · · v v n 1 is a Hamilton cycle of K n . Consider two edges e 1 = v v a b and e 2 = v v x y of K n , where without loss of generality a &lt; b , x &lt; y , and a &lt; x . We say e 1 and e 2 are crossing (relative to H ) if a &lt; x &lt; b &lt; y ; otherwise we say e 1 and e 2 are non-crossing. This is just the natural notion of crossing in a planar drawing of H e , 1 , and e 2 .

Proposition 5.2 Suppose H = v v 1 2 · · · v v n 1 is a Hamilton cycle of K n and suppose we have a function t : E K ( n ) → { 0 1 2 , , , . . . } . Then we can find T ∗ ⊆ E K ( n ) such that every pair of edges in T ∗ is non-crossing and t ( T ∗ ) ≥ t ( K n ) / (2 n ) . Furthermore, we can find T ∗ in time O n ( 2 ) .

Proof Let Q = { 3 4 , , . . . , 2 n } , and for each q ∈ Q , let E q = { v v i j ∈ E K ( n ) | i + j = q } . Observe that the sets ( E q ) q ∈ Q partition E K ( n ) and that for each fixed q ∈ Q each pair of edges in E q is non-crossing. Thus since

$$t ( K _ { n } ) & = \sum _ { q \in Q } t ( E _ { q } ), \\ \dots \psi \quad \slash \, \sum \, \dots \quad \slash \, \tau \succ \, \dots \, \slash \, \tau.$$

there is some q ∗ ∈ Q for which t ( E q ∗ ) ≥ t ( K n ) / Q | | ≥ t ( K n ) / 2 n . Set T ∗ = E q ∗ .

We can determine E q and t ( E q ) in time O n ( 2 ) and so we can determine T ∗ is time O n ( 2 ). /square

We introduce some more terminology. Let ( n, w ) be an instance and let H be a Hamilton cycle of K n . We say a 4-cycle C = v v v v v 1 2 3 4 1 of K n is embedded in H if either v v , v 1 2 3 v 4 ∈ E H ( ) or v v , v 2 3 4 v 1 ∈ E H ( ); note that if three edges of C are in H , then C is necessarily embedded in H . We say C is correctly embedded in H if E H ( ) /triangle E C ( ) forms a Hamilton cycle; note that this happens if and only if C is embedded in H , exactly two edges of C belong to H , and the other two edges of C are crossing relative to H . If C is an unbalanced 4-cycle and is embedded in H , we say it is heavily embedded in H if the edges of the heavier perfect matching of C appear in H . We write C ∗ n ( H ) for the set of 4-cycles heavily and correctly embedded in H . We define

The next lemma shows how a Hamilton cycle H can be locally improved using 4-cycles heavily and correctly embedded in it.

$$q ( H ) & \coloneqq \sum _ { C \in \mathcal { C } _ { n } ^ { * } ( H ) } \text{bal} ( C ). \\ \intertext { s h o w a H a m i l t o n } \ e v e l e \ H \ e a.$$

Lemma 5.3 Let ( n, w ) be an instance. Given a Hamilton cycle H of K n , there exists another Hamilton cycle H ′ such that w H ( ′ ) ≤ w H ( ) -( q H / n ( ) 2 ) , and we can find in it time O n ( 4 ) .

Proof Let e , . . . , e 1 n be the edges of H in order. Suppose C 1 and C 2 are 4-cycles that are correctly embedded in H , where e , e a b with a &lt; b are the edges of C 1 in H and e , e x y with x &lt; y are the edges of C 2 in H , and without loss of generality, assume a &lt; x . We say that C 1 and C 2 are crossing (relative to H ) if a &lt; x &lt; b &lt; y . If C 1 and C 2 are not crossing relative to H , we find that E H ( ) /triangle E C ( 1 ) /triangle E C ( 2 ) forms a Hamilton cycle. More generally, one can check that if C , . . . , C 1 r are all 4-cycles correctly embedded in H and no pair of these 4-cycles are crossing relative to H , then E H ( ) /triangle E C ( 1 ) /triangle · · · /triangle E C ( r ) forms a Hamilton cycle.

Consider an auxiliary complete graph K ◦ n with vertex set e , . . . , e 1 n and an auxiliary Hamilton cycle H ◦ = e e 1 2 · · · e n e 1 . For each edge e e x y of E K ( ◦ n ) \ E H ( ◦ ) let C xy be the unique 4-cycle of K n that is correctly embedded in H and satisfies E H ( ) ∩ E C ( ) = { e , e x y } . This correspondence is clearly bijective and crossing edges of K ◦ n (relative to H ◦ ) correspond to crossing 4-cycles of K n (relative to H ). Define t : E K ( ◦ n ) →{ 0 1 , , . . . } by

$$t ( e _ { x } e _ { y } ) = \begin{cases} \text{bal} ( C _ { x y } ) & \text{if $C_{xy}$ is heavily embedded in $H$;} \\ 0 & \text{otherwise,} \end{cases}$$

and note t ( K ◦ n ) = q H ( ). Applying Proposition 5.2, we can find a set of edges T ∗ ⊆ E K ( ◦ n ) which are pairwise non-crossing relative to H ◦ and satisfying t ( T ∗ ) &gt; q H / n ( ) 2 . By removing from T ∗ any edges assigned weight 0 by t , we may further assume that every edge in T ∗ is assigned a positive weight by t . The edges of T ∗ then correspond to 4-cycles C , . . . , C 1 r of K n that are heavily and correctly embedded in H such that no pair of these 4-cycles are crossing (relative to H ) and where bal( C 1 ) + · · · +bal( C r ) ≥ q H / n ( ) 2 . The time needed to find C , . . . , C 1 r is O n ( 2 ).

We construct a sequence of Hamilton cycles H , . . . , H 0 r , where H 0 = H and E H ( i ) = E H ( i -1 ) /triangle E C ( i ) (which takes time O r ( ) = O n ( )). We have w H ( i ) = w H ( i -1 ) -bal( C i ) since C i is heavily embedded in H i -1 . Hence setting H ′ = H r , we have

$$w ( H ^ { \prime } ) = w ( H ) - \text{bal} ( C _ { 1 } ) - \dots - \text{bal} ( C _ { r } ) \leq w ( H ) - ( q ( H ) / 2 n ), \\ \text{and the time required to construct } H ^ { \prime } \text{ is } O ( n ^ { 2 } ). & \Box$$

The previous lemma motivates our interest in the function q : H → n Z . We shall later apply Lemma 4.1 to q and for this we require the following straightforward proposition. We spell out the details for completeness.

Proposition 5.4 Let ( n, w ) be an instance and let G be a partial Hamilton cycle of K n . Then we can compute E ( q H ( ˜ G n )) in time O n ( 4 ) .

## Proof Note that

$$\mathbb { E } ( q ( \tilde { H } _ { n } ^ { G } ) ) & = \sum _ { C \in \mathcal { C } _ { n } } \mathbb { P } ( C \in \mathcal { C } _ { n } ^ { * } ( \tilde { H } ^ { G } ) ) \text{bal} ( C ), \\ \sigma \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \code \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \end{array}$$

and so it is sufficient to show how to compute P ( C ∈ C ∗ n ( ˜ H G )) in time O (1) for each C ∈ C n . This is intuitively clear, but slightly tedious to explain.

Clearly if C is balanced then P ( C ∈ C ∗ n ( ˜ H G )) = 0. So assume C = v v v v v 1 2 3 4 1 ∈ C n is unbalanced and that e 1 = v v 1 2 and e 2 = v v 3 4 are the edges of the heavier perfect matching of C . Then (using (4)) the probability p C, G ( ) that C is heavily embedded in ˜ H G is

$$p ( C, G ) = \mathbb { P } ( e _ { 1 }, e _ { 2 } \in \tilde { H } ^ { G } ) = \frac { | \mathcal { H } _ { n } ^ { G \cup \{ e _ { 1 }, e _ { 2 } \} } | } { | \mathcal { H } _ { n } ^ { G } | } = \frac { 2 ^ { r ^ { \prime } - 1 } ( r ^ { \prime } + s ^ { \prime } - 1 )! } { 2 ^ { r - 1 } ( r + s - 1 )! },$$

where r and s are the numbers of non-trivial and trivial paths in G and r ′ and s ′ are the numbers of non-trivial and trivial paths in G ∪ { e , e 1 2 } .

If e 1 and e 2 appear on different non-trivial paths of G ′ := G ∪ { e , e 1 2 } , say a P b 1 1 1 and a P b 2 2 2 , then P ( C ∈ C ∗ n ( ˜ H G )) = 1 2 p C, G ( ). To see this, we note that a Hamilton cycle H ∈ H G ′ n can take one of two forms depending on relative orientations of P 1 and P 2 on H . In one of these forms C is correctly embedded in H and in the other it is not. Thus C is correctly embedded in exactly half the Hamilton cycles of H G ′ n .

If e 1 and e 2 appear on the same non-trivial path of G ′ then either P ( C ∈ C ∗ n ( ˜ H G )) = p C, G ( ) or P ( C ∈ C ∗ n ( ˜ H G )) = 0 depending on the order of the vertices v , . . . , v 1 4 on the path. Hence we have shown how to compute P ( C ∈ C ∗ n ( ˜ H G )) in time O (1). /square

We are now ready to prove Lemma 5.1.

Proof (of Lemma 5.1) Let ˜ H be a uniformly random Hamilton cycle of K n and suppose C = v v v v v 1 2 3 4 1 is an unbalanced 4-cycle, with e 1 = v v 1 2 and e 2 = v v 3 4 the edges of its heavier perfect matching. Then the probability that C is heavily embedded in ˜ H is given by

$$\mathbb { P } ( e _ { 1 }, e _ { 2 } \in \tilde { H } ) = \frac { | \mathcal { H } _ { n } ^ { \{ e _ { 1 }, e _ { 2 } \} } | } { | \mathcal { H } _ { n } | } = \frac { 2 ( n - 3 )! } { ( n - 1 )! / 2 } = \frac { 4 } { ( n - 1 ) ( n - 2 ) } \geq \frac { 4 } { n ^ { 2 } }.$$

Now (as in the proof of Proposition 5.4) it is not too hard to see that the probability that C is heavily and correctly embedded in ˜ H is 1 2 P ( e , e 1 2 ∈ ˜ ) H ≥ 2 n 2 . Thus we have that

$$\mathbb { E } ( q ( \tilde { H } ) ) = \sum _ { C \in \mathcal { C } _ { n } } \mathbb { P } ( C \in \mathcal { C } _ { n } ^ { * } ( \tilde { H } ) ) \text{bal} ( C ) \geq \frac { 2 } { n ^ { 2 } } \| ( n, w ) \| _ { 4 - \text{cyc} } > 2 k n.$$

and so

$$\mathbb { E } ( w ( \tilde { H } ) - ( q ( \tilde { H } ) / 2 n ) ) < d n - k.$$

Thus there exists a Hamilton cycle H ∗ satisfying w H ( ∗ ) -( q H ( ∗ ) / 2 n ) &lt; dn -k . Furthermore we can find this Hamilton cycle in time O n ( 7 ). Indeed, by Lemma 4.1, it is sufficient to check that we can compute E ( w H ( ˜ G ) -( q H ( ˜ G ) / 2 n )) = E ( w H ( ˜ G )) -E ( q H ( ˜ G )) / 2 n in time O n ( 4 ) for every partial Hamilton cycle G . This holds since we can compute E ( w H ( ˜ G )) in O n ( 2 ) time by the proof of Lemma 4.2 and we can compute E ( q H ( ˜ G )) in time O n ( 4 ) by Proposition 5.4.

Finally, we apply Lemma 5.3 to H ∗ to obtain a Hamilton cycle H satisfying w H ( ) ≤ w H ( ∗ ) -( q H ( ∗ ) / 2 n ) &lt; dn -k as required. This takes time O n ( 4 ), so the total running time is O n ( 7 ). /square

Our next task is to prove (2) and give a polynomial-time witness for the inequality. Recall that two instances ( n, w ) and ( n, w ′ ) are equivalent if there exists some α ∈ Z such that w H ′ ( ) = w H ( ) + α for all Hamilton cycles of K n .

Lemma 5.5 Suppose ( n, w ) is an instance and 0 ≤ k ∈ Q with n &gt; 5000( k + 1) . If ‖ ( n, w ) ‖ 4 -cyc ≤ kn 3 then there exists an equivalent instance ( n, w ∗ ) satisfying w K ∗ [ n ] ≤ 4000 kn . Moreover, we can determine ( n, w ∗ ) in time O kn ( 5 ) .

After proving two preliminary results, we will prove Lemma 5.8, which states that if ‖ ( n, w ) ‖ 4 -cyc is small then there is an equivalent instance ( n, w ∗ ) in which most edges of K n are assigned weight 0. From this, we shall deduce Lemma 5.5.

Lemma 5.6 Suppose ( n, w ) is an instance and k ∈ Q with n &gt; 50 k such that ‖ ( n, w ) ‖ 4 -cyc ≤ kn 3 . Then there exists a set S of at most 16 kn edges of K n such that every 4 -cycle of K n -S is balanced. Moreover, we can find S in time O kn ( 5 ) .

Proof Note first that if ‖ ( n, w ) ‖ 4 -cyc ≤ kn 3 then there are at most kn 3 unbalanced 4-cycles.

Suppose C = v v v v v 1 2 3 4 1 is an unbalanced 4-cycle of K n and let ab be any edge of K n that is vertex disjoint from C . Then one of the following 4-cycles is unbalanced: av v ba 1 2 , bv v ab 2 3 , av v ba 3 4 , bv v ab 4 1 . Indeed, if not then we

have

$$w ( a b ) & = w ( a v _ { 1 } ) + w ( b v _ { 2 } ) - w ( v _ { 1 } v _ { 2 } ) \\ & = w ( b v _ { 2 } ) + w ( a v _ { 3 } ) - w ( v _ { 2 } v _ { 3 } ) \\ & = w ( a v _ { 3 } ) + w ( b v _ { 4 } ) - w ( v _ { 3 } v _ { 4 } ) \\ & = w ( b v _ { 4 } ) + w ( a v _ { 1 } ) - w ( v _ { 4 } v _ { 1 } ).$$

But then w v v ( 1 2 ) + w v v ( 3 4 ) = w v v ( 1 3 ) + w v v ( 2 4 ) and so C is a balanced 4-cycle, a contradiction. Hence we see that for every ab ∈ E K ( n -V ( C )), there exists an unbalanced 4-cycle C ′ which contains ab and shares an edge with C .

Now consider the greedy process where we start with G 0 := K n and we iteratively remove the edges of an arbitrary unbalanced 4-cycle C r from G r to obtain G r +1 ; thus G r has ( ) n 2 -4 r edges. This process must eventually stop, say with the graph G r ∗ that contains no unbalanced 4-cycles. Let q r be the number of unbalanced 4-cycles in G r . Then we have for all r &lt; r ∗ that

$$q _ { r + 1 } \leq q _ { r } - e ( G _ { r } - V ( C _ { r } ) ) \leq q _ { r } - \left ( \binom { n - 4 } { 2 } - 4 r \right ) ; \\. \quad. \quad. \,. \,. \,. \,. \quad. \quad. \quad. \quad..$$

the first inequality holds because, as observed above, for every ab ∈ E G ( r -V ( C r )), there exists an unbalanced 4-cycle of G r that contains ab and shares an edge with C r (and this 4-cycle is therefore absent from G r +1 ). We deduce that q r ≤ q 0 -r ( n -4 2 ) +4 ( ) r 2 . Since q 0 ≤ kn 3 , if r ∗ ≥ 4 kn , then

$$q _ { r ^ { * } } & \leq k n ^ { 3 } - 4 k n \binom { n - 4 } { 2 } + 4 \binom { 4 k n } { 2 } < 0, \\. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad.$$

where the last inequality holds for our choice of n large enough. Thus r ∗ ≤ 4 kn , and setting S to be the set of at most 16 kn edges removed from K n to obtain G r ∗ , we see that all 4-cycles of K n -S are balanced.

The proof is constructive and we can find S in time O kn ( 5 ): it takes time O n ( 4 ) to search for and remove an unbalanced 4-cycle and we do this at most 4 kn times, so the total running time is O kn ( 5 ). /square

The following proposition is straightforward, but we spell out the details for completeness.

Proposition 5.7 Suppose G is a graph on n vertices and at least ( ) n 2 -t edges for some 0 ≤ t ≤ ( ) n 2 . Then G has a connected component with at least ( ) n 2 -2 t edges.

Proof Let A ⊆ V ( G ) be a connected component of G with the maximum number of vertices. Then it must be the case that | A | ≥ n -1 -(2 t/n ); if not then ∆( G &lt; n ) -1 -(2 t/n ), which implies e G ( ) ≤ n ∆( G / ) 2 &lt; ( ) n 2 -t , a contradiction. Hence

$$e ( G [ A ] ) \geq e ( G ) - \binom { n - | A | } { 2 } \geq \binom { n } { 2 } - t - \binom { 1 + ( 2 t / n ) } { 2 } \geq \binom { n } { 2 } - 2 t, \\ \text{where the last inequality follows using that } \binom { n } { 2 } \geq t. & \Box$$

Next, we describe simple linear operations one can apply to an instance to obtain an equivalent instance. For a vertex v of K n we write I v : E K ( n ) → { 0 1 , } for the edge weighting of K n where I v ( e ) = 1 if v is an end-vertex of e , and I v ( e ) = 0 otherwise. Observe that if ( n, w ) is an instance and w ′ = w + λI v for some λ ∈ Z , then w H ′ ( ) = w H ( ) + 2 λ for all Hamilton cycles H of K n and both w and w ′ have the same balanced 4-cycles. More generally, given an integer λ v for each v ∈ V ( K n ), if where the last inequality follows using that ( ) 2

$$\sum _ { \substack { v \in V ( K _ { n } ) \\ \cdot } } \lambda _ { v } I _ { v } & & ( 6 ) \\. & \quad - & \quad.$$

then w H ′ ( ) = w H ( ) + 2 ∑ v λ v for all Hamilton cycles H of K n and so ( n, w ) and ( n, w ′ ) are equivalent instances. Note further that, as before, ( n, w ) and ( n, w ′ ) have the same balanced 4-cycles.

Lemma 5.8 Suppose ( n, w ) is an instance with k ∈ Q and n &gt; 65 k +3 . If ‖ ( n, w ) ‖ 4 -cyc ≤ kn 3 then there exists an equivalent instance ( n, w ∗ ) , where w ∗ ( e ) = 0 for all but at most 32 k n ( +1) edges e ∈ E K ( n ) . Moreover, we can determine ( n, w ∗ ) in time O kn ( 5 ) .

Proof From Lemma 5.6, in time O kn ( 5 ), we can find S ⊆ E K ( n ) of size at most 16 kn such all 4-cycles in K n -S are balanced. Write G := K n -S . Let v 0 be a vertex of maximum degree in G (so d G ( v 0 ) ≥ n -1 -32 k ). Consider the weighting of K n given by

$$w ^ { \prime } = w - \sum _ { u \in N _ { G } ( v _ { 0 } ) } w ( u v _ { 0 } ) I _ { u }.$$

Since w ′ takes the form of (6), we see ( n, w ) is equivalent to ( n, w ′ ).

We show that w ′ assigns the same weight, α say, to all but at most 32 kn + ( n -1) edges e ∈ E K ( n ). It is clear that w uv ′ ( 0 ) = 0 for every u adjacent to v 0 in G . Now for any vertex a ∈ V ( G ) \{ v 0 } = V ( K n ) \ { v 0 } , all edges incident to a in G (except possibly av 0 ) have the same weight: indeed,

/negationslash if ax, ay ∈ E G ( ) with x, y = v 0 , then axv ya 0 forms a balanced 4-cycle and so we must have that w ax ′ ( ) = w v y ′ ( 0 ) + w ax ′ ( ) = w v x ′ ( 0 ) + w ay ′ ( ) = w ay ′ ( ). This implies that w ′ assigns the same weight to every connected component of G -{ v 0 } : given two edges in the same component, there is a path from one edge to the other and each pair of incident edges have the same weight, so all edges on the path have the same weight.

Since G -{ v 0 } is an ( n -1)-vertex graph with at least ( n -1 2 ) -16 kn edges (and where ( n -1 2 ) ≥ 16 kn by our choice of n ), Proposition 5.7 implies there is a component A of G -{ v 0 } with at least ( n -1 2 ) -32 kn = ( ) n 2 -32 kn -( n -1) edges. Thus w ′ assigns the same weight, α say, to at least e G A ( [ ]) ≥ ( ) n 2 -32 kn -( n -1) edges of K n .

We set w ′′ := w ′ -α (i.e. we reduce w ′ by α for all edges of K n ). Thus ( n, w ′′ ) is equivalent to ( n, w ′ ) (and hence to ( n, w )) where w ′′ ( e ) = 0 for all but at most 32 kn +( n -1) edges e ∈ E K ( n ) and w ′′ ( e ) = -α for all edges e ∈ E G ( ) incident to v 0 . Setting w ∗ = w + αI v 0 , we have that ( n, w ∗ ) is equivalent to ( n, w ′′ ) (and hence to ( n, w )) with w ∗ ( e ) = 0 for all but at most 32 kn +( n -1) -d G ( v 0 ) ≤ 32 k n ( +1) edges e ∈ E K ( n ). So ( n, w ∗ ) satisfies the requirements of the lemma.

Finding w ∗ takes time O kn ( 5 ); the time is dominated by the time to find S . /square

We are now ready to prove Lemma 5.5.

Proof (of Lemma 5.5) By Lemma 5.8, we can find in time O kn ( 5 ) an instance ( n, w ′ ) equivalent to ( n, w ) such that w e ′ ( ) = 0 for all but at most 32 k n ( + 1) ≤ 50 kn edges of K n (for our choice of large n ).

/negationslash

Let F be the spanning subgraph of K n whose edge set consists of the edges e ∈ E K ( n ) for which w e ′ ( ) = 0. Define X = { v ∈ V ( K n ) : d F ( v ) ≥ n/ 4 } . Then | X n/ | 4 ≤ 2 ( e F ) ≤ 100 kn , and so | X | ≤ 400 k . We write X := V ( K n ) \ X .

For each x ∈ X define α x ∈ Q by

$$\alpha _ { x } \coloneqq \frac { 1 } { | \overline { X } | } \sum _ { v \in \overline { X } } w ^ { \prime } ( x v ) \quad \text{ and } \quad w ^ { * } \coloneqq w ^ { \prime } - \sum _ { x \in X } \lfloor \alpha _ { x } \rfloor I _ { x }. \\ \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{---} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad  \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \text{--} \quad \end{cases}$$

Thus ( n, w ∗ ) is equivalent to ( n, w ′ ) (since it takes the form of (6)) and hence to ( n, w ) and it is easy to check that we can compute ( n, w ∗ ) in O n ( 2 ) time. It remains for us to show that w K ∗ [ n ] ≤ 4000 kn . We shall show that w K ∗ [ n [ X ]] ≤ 2 kn and w K ∗ [ n [ X,X ]] ≤ 416 kn and w K ∗ [ n [ X ]] ≤ 3208 kn , proving the lemma.

/negationslash

Note that w ∗ ( e ) = w e ′ ( ) for all e ∈ X (2) . Define F ∗ to be the spanning subgraph of K n consisting of edges e for which w ∗ ( e ) = 0. For the rest of the proof, balance is with respect to ( n, w ∗ ), i.e. bal( ) = bal · ( n,w ∗ ) ( ). ·

/negationslash

Claim 1 We have w K ∗ [ n [ X ]] ≤ 2 kn .

/negationslash

Proof (of Claim 1) Consider e = xy ∈ E F ( ) ∩ X (2) = E F ( ∗ ) ∩ X (2) and define A xy to be the set of all 4-cycles uxyvu satisfying u, v ∈ X and ux, vy, uv ∈ E F ( ∗ ) ∩ X (2) , so w ∗ ( ux ) = w ∗ ( vy ) = w ∗ ( uv ) = 0. Note that for each C ∈ A xy , bal( C ) = | w ∗ ( xy ) . |

/negationslash

/negationslash

There are at least | X | -n/ 4 choices of u ∈ X such that ux ∈ E F ( ∗ ) and similarly | X | -n/ 4 -1 choices of v ∈ X such that vy ∈ E F ( ∗ ) and v = u . Amongst these choices of u, v , the number of possible choices where uv ∈ E F ( ∗ ) ∩ X (2) is at most | E F ( ) ∩ X (2) | ≤ e F ( ) ≤ 50 kn . Hence

$$| A _ { x y } | \geq ( | \overline { X } | - n / 4 - 1 ) ^ { 2 } - 5 0 k n \geq ( 3 n / 4 - 4 0 0 k - 1 ) ^ { 2 } - 5 0 k n \geq n ^ { 2 } / 2$$

where the last inequality follows by our choice of sufficiently large n . Now we have

$$\text{we have} \\ k n ^ { 3 } \geq \| ( n, w ^ { * } ) \| _ { 4 - \text{cyc} } \geq \text{bal} \left ( \bigcup _ { x y \in E ( F ^ { * } ) \cap X ^ { ( 2 ) } } A _ { x y } \right ) & \geq \sum _ { x y \in E ( F ^ { * } ) \cap \overline { X } ^ { ( 2 ) } } | w ^ { * } ( x y ) | | A _ { x y } | \\ & \geq ( n ^ { 2 } / 2 ) w ^ { * } [ K _ { n } [ \overline { X } ] ], \\. \quad. \quad. \quad. \quad. \quad.$$

$$\overline { \zeta } ] & \leq 2 k n. & \square$$

and so w K ∗ [ n [ X ]] ≤ 2 kn

Claim 2 We have w K ∗ [ n [ X,X ]] ≤ 416 kn .

/negationslash

/negationslash

Proof (of Claim 2) For each x ∈ X and ab ∈ X (2) with a = , let b A x,ab be the set of 4-cycles C = axbca with c ∈ X satisfying w ∗ ( ac ) = w ∗ ( bc ) = 0 (i.e. ac, bc ∈ E F ( ∗ ) ∩ X (2) = E F ( ) ∩ X (2) ). The number of choices for such a vertex c is thus at most

$$| \overline { X } | - 2 - d _ { F } ( a ) - d _ { F } ( b ) \geq n - 2 - 4 0 0 k - n / 4 - n / 4 \geq n / 4$$

/negationslash where the last inequality follows by our choice of sufficiently large n . Thus we have | A x,ab | ≥ n/ 4 for all x ∈ X and ab ∈ X (2) with a = b . Note also that, for all C ∈ A x,ab , we have bal( C ) = | w ∗ ( ax ) -w ∗ ( bx ) . |

Fix x ∈ X and let β x := | X | -1 ∑ v ∈ X w ∗ ( vx ), noting that β x = α x -/floorleft α x /floorright ∈ [0 , 1]. Write S + := { v ∈ X : w ∗ ( vx ) ≥ β x } and S -:= { v ∈ X : w ∗ ( vx ) ≤ β x } . Note for later that, since β x is the average of ( w ∗ ( vx )) v ∈ X , we have

$$\sum _ { v \in S ^ { + } } | w ^ { * } ( v x ) - \beta _ { x } | = \sum _ { v \in S ^ { - } } | w ^ { * } ( v x ) - \beta _ { x } | = \frac { 1 } { 2 } \sum _ { v \in \overline { X } } | w ^ { * } ( v x ) - \beta _ { x } |. \quad ( 7 )$$

We have

$$\text{We have} \\ \text{bal} \left ( \bigcup _ { a b \in \overline { X } ^ { ( 2 ) } } A _ { x, a b } \right ) & \geq \sum _ { a, b \in \overline { X } } | A _ { x, a b } | | w ^ { * } ( a x ) - w ^ { * } ( b x ) | \\ & \geq ( n / 4 ) \sum _ { \substack { a \in S ^ { + } \\ b \in S ^ { - } } } | w ^ { * } ( a x ) - w ^ { * } ( b x ) | \\ & = ( n / 4 ) \sum _ { \substack { a \in S ^ { + } \\ b \in S ^ { - } } } | w ^ { * } ( a x ) - \beta _ { x } | + | w ^ { * } ( b x ) - \beta _ { x } | \\ & \stackrel { ( \overline { \epsilon } ) } { = } ( n / 4 ) \left ( \frac { 1 } { 2 } ( | S ^ { - } | + | S ^ { + } | ) \sum _ { v \in X } | w ^ { * } ( v x ) - \beta _ { x } | \right ). \\ \text{Using that } | S ^ { + } | + | S ^ { - } | & \geq | \overline { X } | \text{ and } \beta _ { x } \in [ 0, 1 ], the last expression is bounded} \\ \text{below by}$$

$$\ast$$

Using that | S + | + | S -| ≥ | X | and β x ∈ [0 , 1], the last expression is bounded below by

$$( n | \overline { X } | / 8 ) \sum _ { v \in \overline { X } } ( | w ^ { * } ( v x ) | - 1 ) \geq ( n ^ { 2 } / 1 6 ) \sum _ { v \in \overline { X } } ( | w ^ { * } ( v x ) | - 1 )$$

for n sufficiently large. Finally, we have

$$\lambda \quad \rangle & \rangle \quad \rangle \quad \rangle \\ k n ^ { 3 } \geq \| ( n, w ) \| _ { 4 - \text{cycle} } & \geq \text{bail} \Big ( \bigcup _ { \substack { x \in X \\ a b \in \overline { X } ^ { ( 2 ) } } } A _ { x, a b } \Big ) \geq ( n ^ { 2 } / 1 6 ) \sum _ { \substack { x \in X \\ v \in \overline { X } } } ( | w ^ { * } ( v x ) | - 1 ) \\ & = ( n ^ { 2 } / 1 6 ) ( w ^ { * } [ K _ { n } [ X, \overline { X } ] ] - | X | | \overline { X } | ) \\ & \geq ( n ^ { 2 } / 1 6 ) ( w ^ { * } [ K _ { n } [ X, \overline { X } ] ] - 4 0 0 k n ), \\ & \quad -$$

. /square from which we obtain that w K ∗ [ n [ X,X ]] ≤ 416 kn

Claim 3 We have w K ∗ [ n [ X ]] ≤ 3208 kn .

Proof (of Claim 3) For each xy ∈ E F ( ∗ ) ∩ X (2) , define A xy to be the set of all 4-cycles of the form C = xyuvx , where u, v ∈ X . For fixed xy ∈ E F ( ∗ ) ∩ X (2) ,

we have

/negationslash

/negationslash

$$\text{we have} \\ \text{bal} ( A _ { x y } ) & = \sum _ { \substack { u, v \in \overline { X } \\ u \neq v } } | w ^ { * } ( x y ) + w ^ { * } ( w ) - w ^ { * } ( x v ) - w ^ { * } ( y u ) | \\ & \geq \left | \sum _ { \substack { u, v \in \overline { X } \\ u \neq v } } w ^ { * } ( x y ) + w ^ { * } ( u v ) - w ^ { * } ( x v ) - w ^ { * } ( y u ) \right | \\ & = \left | \overline { X } | ( | \overline { X } | - 1 ) w ^ { * } ( x y ) \ + \ 2 w ^ { * } ( K _ { n } [ \overline { X } ] ) \ - \ ( | \overline { X } | - 1 ) ( \beta _ { x } + \beta _ { y } ) | \overline { X } | \right | \\ & \geq | \overline { X } | ( | \overline { X } | - 1 ) | w ^ { * } ( x y ) | \ - \ 2 w ^ { * } [ K _ { n } [ \overline { X } ] ] \ - \ 2 | \overline { X } | ( | \overline { X } | - 1 ), \\ \text{where $\beta_{x}$, $\beta_{y} \in [0,1]$ are as defined in the previous claim. For our choice of} \\ \text{large $n$, $n$, we have $n/2<|\overline{X}|<n$ and so $n^2/8<|\overline{X}|(|\overline{X}|-1)\ <n^2$}. $Bv}$$

where β , β x y ∈ [0 , 1] are as defined in the previous claim. For our choice of large n , we have n/ 2 ≤ | X | ≤ n and so n / 2 8 ≤ | X | ( | X | -1) ≤ n 2 . By Claim 1, we have w K ∗ [ n [ X ] ≤ 2 kn ≤ n 2 . Putting this together, the final expression above is at most 1 8 n 2 | w ∗ ( xy ) | -4 n 2 . Finally

$$k n ^ { 3 } \geq \| ( n, w ^ { * } ) \| _ { 4 - \text{cyc} } & \geq \text{bal} ( \bigcup _ { x y \in X ^ { ( 2 ) } } A _ { x y } ) \geq \sum _ { x y \in X ^ { ( 2 ) } } \frac { 1 } { 8 } n ^ { 2 } | w ^ { * } ( x y ) | - 4 n ^ { 2 } \\ & \geq ( n ^ { 2 } / 8 ) w ^ { * } [ K _ { n } [ X ] ] - 4 ( 4 0 0 k ) ^ { 2 } n ^ { 2 } \\ & \geq ( n ^ { 2 } / 8 ) w ^ { * } [ K _ { n } [ X ] ] - 4 0 0 k n ^ { 3 },$$

where the last inequality holds by the choice of large n . Rearranging shows that w K ∗ [ n [ X ]] ≤ 3208 kn . /square

This completes the proof of the lemma.

$$\Box$$

We can now combine Lemma 5.1 and Lemma 5.5 to prove the main result of this section, Theorem 1.2.

Proof (of Theorem 1.2) Given an instance ( n, w ) and k ∈ N with n &gt; 5000( k +1), if ‖ ( n, w ) ‖ 4 -cyc ≥ kn 3 then by Lemma 5.1, in time O n ( 7 ), we can find a Hamilton cycle H of K n satisfying w H ( ) &lt; dn -k . If ‖ ( n, w ) ‖ 4 -cyc ≤ kn 3 then in time O kn ( 5 ) = O n ( 7 ), we can find an equivalent instance ( n, w ′ ) satisfying w K ′ [ n ] ≤ 4000 kn . /square

## 6 Algorithms

In this section we prove Theorem 1.1. Let ( n, w, k ) be an instance of TSP BA and let X ⊆ V ( K n ). An ( X )-partial Hamilton cycle of K n is any spanning

subgraph G of K n that can be obtained by taking a Hamilton cycle of K n and deleting all its edges that lie in E K ( n [ X ]).

Suppose G is a spanning subgraph of K n . It is not hard to see that G is an ( X )-partial Hamilton cycle of K n if and only if

- (a) G consists of vertex disjoint paths P , . . . , P 1 r for some r (where we allow trivial paths);
- (b) every x ∈ X is an internal vertex of some P i ;
- (c) no edge of E K ( n [ X ]) is present in G .

For X ⊆ V ( K n ), we define X := V ( K n ) \ X .

Lemma 6.1 Let ( n, w, k ) be an instance of TSP BA and let X ⊆ V ( K n ) with t := | X | . We can find an ( X ) -partial Hamilton cycle of K n of minimum weight in time O t ( 3 )! + O t n ( 3 ) .

Proof For each a ∈ X , let y , y a 1 a 2 , . . . be an ordering of the vertices of X such that w ay ( a 1 ) ≤ w ay ( a 2 ) ≤ . . . . For each ab ∈ X (2) , let y ab 1 , y ab 2 , . . . be an ordering of the vertices of X such that w ay ( ab 1 ) + w by ( ab 1 ) ≤ w ay ( ab 2 ) + w by ( ab 2 ) ≤ . . . .

For each positive integer /lscript , define

$$Y _ { \ell } ^ { 1 } ( X ) \coloneqq & \bigcup _ { a \in X } \bigcup _ { i = 1 } ^ { \ell } \{ y _ { i } ^ { a } \} \subseteq \overline { X } \text{ and } Y _ { \ell } ^ { 2 } ( X ) \coloneqq \bigcup _ { a b \in X ^ { ( 2 ) } } \bigcup _ { i = 1 } ^ { \ell } \{ y _ { i } ^ { a b } \} \subseteq \overline { X } \\ \dots \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{  } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{\ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text$$

and define

$$M _ { \ell } ^ { 1 } ( X ) \coloneqq \bigcup _ { a \in X } \bigcup _ { i = 1 } ^ { \ell } \{ a y _ { i } ^ { a } \} \text{ and } M _ { \ell } ^ { 2 } ( X ) \coloneqq \bigcup _ { a b \in X ^ { ( 2 ) } } \bigcup _ { i = 1 } ^ { \ell } \{ a y _ { i } ^ { a b }, b y _ { i } ^ { a b } \}. \\ - \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \,.$$

Finally, let Y := Y 1 2 +1 t ( X ) ∪ Y 2 2 +1 t ( X ) and let M := M 1 2 +1 t ( X ) ∪ M 2 2 +1 t ( X ).

Claim 1 Suppose G is an ( X )-partial Hamilton cycle of K n of minimum weight. Subject to this, assume further that | E G ( X,X ) \ M | is minimised. Then E G ( X,X ) ⊆ M . Note that in particular, this implies that the nontrivial paths of G all lie in X ∪ Y .

/negationslash

Proof (of Claim 1) Suppose rs ∈ E G ( X,X ) with r ∈ X and s ∈ X but rs ∈ M . Since G is an ( X )-partial Hamilton cycle, we have | N G ( s ) | = 1 2 , and N G ( s ) ⊆ X (since G has no edges in E K ( n [ X ]). Let N G ( s ) = { r, r ′ } , where r = r ′ if | N G ( s ) | = 1.

Let A be the set of all x ∈ X satisfying N G ( x ) &gt; 0; then | A | ≤ 2 | X | = 2 t since N G ( x ) ⊆ X for all x ∈ X and d G ( x ) = 2 for all x ∈ X . Note also that, for every a ∈ X \ A , the graph G ′ obtained by deleting the edges rs, r s ′ and replacing them with the edges ra, r a ′ is an ( X )-partial Hamilton cycle.

/negationslash

/negationslash

Suppose | N G ( s ) | = 1. Pick any i ∈ [2 t + 1] such that y r i ∈ A (this is possible since | A | ≤ 2 ) and replace t rs with ry r i in G to form G ′ . Then G ′ is an ( X )-partial Hamilton cycle, and w G ( ′ ) ≤ w G ( ) since w ry ( r i ) ≤ w rs ( ) (by the definition of y r i ). However | E G ′ ( X,X ) \ M &lt; E | | G ( X,X ) \ M | (since rs ∈ M and ry r i ∈ M ), a contradiction.

/negationslash

/negationslash

Suppose | N G ( s ) | = 2. Pick any i ∈ [2 t + 1] such that y rr ′ i ∈ A (this is possible since | A | ≤ 2 ) and replace t rs, r s ′ with ry rr ′ i , r y ′ rr ′ i in G to form G ′ . Then G ′ is an ( X )-partial Hamilton cycle, and w G ( ′ ) ≤ w G ( ) since w ry ( rr ′ i ) + w r y ( ′ rr ′ i ) ≤ w rs ( ) + w r s ( ′ ) (by the definition of y rr ′ i . However | E G ′ ( X,X ) \ M &lt; E | | G ( X,X ) \ M | (since rs, r s ′ ∈ M and ry rr ′ i , r y ′ rr ′ i ∈ M ), a contradiction. /square

By Claim 1, in order to find an X -partial Hamilton cycle of K n of minimum weight, it is sufficient to find an ( X )-partial Hamilton cycle of K X Y n [ ∪ ] of minimum weight. We can do this in time O t ( 3 )! + O t n ( 3 ) by brute force as follows.

We first determine Y ; this can be done in time O t n ( 3 ) since Y has size at most O t ( 3 ). We find all Hamilton cycles of K X n [ ∪ Y ], which takes time O X ( | | + | Y | )! = O t ( 3 )!. For each such Hamilton cycle, we delete its edges in Y (2) to obtain an ( X )-partial Hamilton cycle H ′ and we determine w H ( ′ ) (this takes time O t ( 3 ) O t ( 3 )! = O t ( 3 )!). We find the ( X )-partial Hamilton cycle of K X n [ ∪ Y ] of minimum weight, and its non-trivial paths form the non-trivial paths of an ( X )-partial Hamilton cycle of K n of minimum weight. /square

Given an instance ( n, w, k ) of TSP BA , we define the subgraph K + w (resp. K -w , K 0 w ) of K n to have vertex set V ( K n ) and to have edge set consisting of the edges assigned a positive (resp. negative, zero) weight by w .

Lemma 6.2 Suppose that ( n, w, k ) is an instance of TSP BA and X ⊆ V ( K n ) with | X | = t satisfies the following properties:

- (a) w e ( ) ≥ 0 for all e ∈ E K ( n [ X ]) ;
- (b) δ K ( 0 w [ X ]) ≥ 1 2 | X | +4 t .

Then we can find a minimum weight Hamilton cycle H ∗ of K n in time O t ( 3 )! + O t n ( 3 + n 3 ) .

Proof In time O t ( 3 )! + O t n ( 3 ), we can find an ( X )-partial Hamilton cycle G ∗ of K n of minimum weight. Let P , . . . , P 1 r be the non-trivial paths of G ∗ and note that r ≤ t . Let a , b i i ∈ X be the end-points of P i and let e i = a b i i .

Let X ′ be the set of internal vertices of P , . . . , P 1 r . Thus X ⊆ X ′ and it is not hard to see that | X ′ | ≤ 2 | X | = 2 . t Thus

$$\delta ( K _ { w } ^ { 0 } [ \overline { X ^ { \prime } } ] ) \geq \delta ( K _ { w } ^ { 0 } [ \overline { X } ] ) - | \overline { X } \, \sum \overline { X ^ { \prime } } | & \geq \delta ( K _ { w } ^ { 0 } [ \overline { X } ] ) - 2 t \geq \frac { 1 } { 2 } | \overline { X } | + 4 t - 2 t \\ & \geq \frac { 1 } { 2 } | \overline { X ^ { \prime } } | + 2 t \geq \frac { 1 } { 2 } | \overline { X ^ { \prime } } | + \frac { 3 } { 2 } r.$$

By an algorithmic version of Dirac's Theorem (see e.g. [11] Lemma 5.11), we can find, in time O n ( 3 ), a Hamilton cycle H of K 0 w [ X ′ ] ∪ { e , . . . , e 1 r } that contains all the edges e , . . . , e 1 r . Replacing each edge e i with the path P i gives a Hamilton cycle H ∗ of K n , which we claim has minimum weight.

Indeed, let H be any Hamilton cycle of K n . Let G be obtained from H by deleting all the edges of H in X (2) ; thus G is an ( X )-partial Hamilton cycle, so w G ( ∗ ) ≤ w G ( ). Note also by condition (i) that w H X ( [ ]) ≥ 0, whereas by construction w H ( ∗ [ X ]) = 0. Therefore

$$w ( H ) = w ( G ) + w ( H [ \overline { X } ] ) \geq w ( G ^ { * } ) + w ( H ^ { * } [ \overline { X } ] ) = w ( H ^ { * } )$$

∗ . /square showing that H is a minimum weight Hamilton cycle of K n

Finally we can prove Theorem 1.1.

Proof (of Theorem 1.1) We assume n &gt; ck for a sufficiently large constant c ; otherwise we can find a Hamilton cycle of minimum weight by brute force. We describe the steps of the algorithm and give the running time in brackets.

- 1. Given ( n, w, k ), by Theorem 1.2, either we can output a Hamilton cycle H ∗ satisfying w H ( ∗ ) &lt; dn -k (and we are done) or we we can find an equivalent instance ( n, w , k ′ ) where w K ′ [ n ] ≤ 4000 kn . (time O n ( 7 ))
- 2. Find a maximum matching Q of K -w ′ , the subgraph of K n containing the edges assigned a negative weight w ′ . Let q be the number of edges of Q and set d ′ := w K ′ ( n ) / ( ) n 2 . (time O n ( 3 ); see [5] for a polynomial-time maximum matching algorithm)
- 3. If q &gt; 10 5 k then E ( w H ′ ( ˜ Q )) ≤ d n ′ -k (see Claim 1) and so by Lemma 4.2, we can find a Hamilton cycle H ∗ of K n in time O n ( 5 ) satisfying w H ′ ( ∗ ) ≤ E ( w H ′ ( ˜ Q )) ≤ d n ′ -k and hence w H ( ∗ ) ≤ dn -k . We output H ∗ and stop. (time O n ( 5 ))

- 4. If q ≤ 10 5 k , then construct the set X ⊆ V ( K n ) such that X = V ( Q ) ∪ { v ∈ V ( K n ) | d K + w ′ ( v ) ≥ 1 4 n } . (time O n ( 2 ))
- 5. Using the properties of X proved in Claim 2, we can apply Lemma 6.2 to ( n, w , k ′ ) , X to find a Hamilton cycle of minimum weight in K n (w.r.t. w ′ ). If w H ′ ( ∗ ) ≤ d n ′ -k then output H ∗ and note w H ( ∗ ) ≤ dn -k . Otherwise we conclude there is no Hamilton cycle beating the average by at least k . (time O k ( 3 )! + O k n ( 3 + n 3 ))

Claim 1 If q &gt; 10 5 k then E ( w H ′ ( ˜ Q )) ≤ d n ′ -k .

Proof (of Claim 1) If q &gt; 10 5 k we have

$$\dots \dots \dots \dots \dots \dots \dots \\ \mathbb { E } ( w ^ { \prime } ( \tilde { H } ^ { Q } ) ) & = w ^ { \prime } ( Q ) + \sum _ { e \in J ( Q ) } \mathbb { P } ( e \in \tilde { H } ^ { Q } ) w ^ { \prime } ( e ) \\ & \leq - 1 0 ^ { 5 } k + ( 4 / ( n - 2 ) ) \sum _ { e \in J ( Q ) } w ^ { \prime } ( e ) \\ & \leq - 1 0 ^ { 5 } k + ( 4 / ( n - 2 ) ) 4 0 0 0 k n \\ & \leq - 5 0 0 0 0 k, \\. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad.$$

where we have used that w Q ′ ( ) ≤ -q (since Q ⊆ K -w ′ ) and P ( e ∈ ˜ H Q ) ≤ 4 / n ( -2) (using (5)) for the first inequality and where we have used that w K ′ [ n ] ≤ 4000 kn for the second inequality, and that n is large for the third inequality. Note also that

$$d ^ { \prime } n - k = \binom { n } { 2 } ^ { - 1 } w ^ { \prime } ( K _ { n } ) n - k \geq - 4 0 0 0 k \frac { n } { n - 1 } - k & \geq - 5 0 0 0 0 k \\ & \geq \mathbb { E } ( w ^ { \prime } ( \tilde { H } ^ { Q } ) ),$$

where the we have used that n is large enough for the second inequality. This gives the desired result. /square

Claim 2 For the set X defined in Step 4, we have

$$( \mathbf a ) \ t \coloneqq | X | \leq 3 \cdot 1 0 ^ { 5 } k ;$$

- (b) w e ′ ( ) ≥ 0 for all e ∈ E K ( n [ X ]);

$$( c ) \ \delta ( K _ { w ^ { \prime } } ^ { 0 }$$

Proof (of Claim 2) (a) We have X = V ( Q ) ∪ S where S := { v ∈ V ( K n ) | d K + w ′ ( v ) ≥ 1 4 n } . We show that | S | ≤ 10 5 k and since | V ( Q ) | ≤ 2 q ≤ 2 · 10 5 k , we have | X | ≤ 3 · 10 5 k as required.

Observe that

$$\frac { 1 } { 4 } n | S | \leq 2 e ( K _ { w$$

which implies | S | ≤ 32000 k ≤ 10 5 k , as required.

(b) follows from the construction of X , since X contains all vertices of a maximum matching from the graph of negatively weighted edges.

To prove (c) observe that for each x ∈ X

$$\begin{array} {$$

where the last inequality holds for n large enough. /square

This completes the proof of the theorem.

/square

## 7 Concluding Remarks

We believe that an analogue of our result ought to hold for the Asymmetric Travelling Salesman Problem. Formally, let ↔ K n denote the complete directed graph on n vertices, so that there are two edges, one in each direction, between each pair of vertices.

Asymmetric Travelling Salesman Problem Below Average ( ATSP BA )

↔

K n )?

$$\begin{array} { c } I n s t a n c e \colon & ( n$$

Problem 7.1 Is ATSP BA fixed parameter tractable when parameterised by k ?

We believe the answer to this question is yes. However, several of the methods in this paper do not generalise in a straightforward way to directed graphs, so we expect that several new ideas will be needed to solve the problem above.

## References

| [1]   | N. Alon, G. Gutin, E.J. Kim, S. Szeider and A. Yeo, Solving MAX-SAT Above a Tight Lower Bound. Algorithmica 61 (2011), 638-655.                                                                                    |
|-------|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [2]   | R. Crowston, M. Jones, and M. Mnich, Max-cut parameterized above the Edwards-Erd¨s o bound, Proc ICALP 2012, Part I, Lect. Notes Comput. Sci. 7391 (2012), 242-253.                                                |
| [3]   | M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk and S. Saurabh, Parameterized Algorithms , Springer, to appear.                                                              |
| [4]   | G. Downey and M. R. Fellows, Fundamentals of Parameterized Com- plexity , Springer 2013.                                                                                                                           |
| [5]   | J. Edmonds, Maximum matching and a polyhedron with 0 , 1-vertices, Journal of Research of the National Bureau of Standards 69B (1965), 125-130.                                                                    |
| [6]   | C. S. Edwards, Some extremal properties of bipartite subgraphs, Cana- dian Journal of Mathematics 25 (1973), 475-483.                                                                                              |
| [7]   | C. S. Edwards, An improved lower bound for the number of edges in a largest bipartite subgraph, In Recent advances in graph theory , (1975), 167-181.                                                              |
| [8]   | M. Gr¨tschel, o L´szl´ a o Lov´sz, a Alexander Schrijver, Complexity, Oracles, and Numerical Computation (book chapter), Geometric Algorithms and Combinatorial Optimization , 21-45, (1988).                      |
| [9]   | G. Gutin and A. Yeo, Constraint satisfaction problems parameterized above or below tight bounds: a survey. In Fellows Festschrift, Lect. Notes Comput. Sci. 7370 (2012), 257-286.                                  |
| [10]  | G. Gutin, A. Yeo and A. Zverovitch, Exponential neighborhoods and domination analysis for the TSP. In The Traveling Salesman Problem and its variations (G. Gutin and A. Punnen, eds.), Springer, (2002), 223-256. |
| [11]  | D. K¨hn, u D. Osthus and V. Patel, A domination algorithm for { 0 , 1 } - instances of the Travelling Salesman Problem, submitted.                                                                                 |
| [12]  | M. Mahajan, V. Raman, and S. Sikdar, Parameterizing above or below guaranteed values, J Comput System Sci 75 (2009), 137-153.                                                                                      |

- [13] M. Mnich, G. Philip, S. Saurabh and O. Suchy, Beyond Max-Cut: λ -extendible properties parameterised above the Poljak-Turz´ ık bound, J Comput System Sci 80 (2014), 1384-1403.
- [14] V.I. Rublineckii, Estimates of the accuracy of procedures in the Traveling Salesman Problem, Numer Math Comput Tech 4 (1973), 18-23 (in Russian).
- [15] V.G. Vizing, Values of the target functional in a priority problem that are majorized by the mean value, Kibernetika , Kiev 5 (1973), 76-78 (in Russian).
Gregory Gutin Viresh Patel
Parameterized TSP: Beating the Average
In the Travelling Salesman Problem (TSP), we are given a complete graph $K_n$
together with an integer weighting $w$ on the edges of $K_n$, and we are asked
to find a Hamilton cycle of $K_n$ of minimum weight. Let $h(w)$ denote the
average weight of a Hamilton cycle of $K_n$ for the weighting $w$. Vizing
(1973) asked whether there is a polynomial-time algorithm which always finds a
Hamilton cycle of weight at most $h(w)$. He answered this question in the
affirmative and subsequently Rublineckii (1973) and others described several
other TSP heuristics satisfying this property. In this paper, we prove a
considerable generalisation of Vizing's result: for each fixed $k$, we give an
algorithm that decides whether, for any input edge weighting $w$ of $K_n$,
there is a Hamilton cycle of $K_n$ of weight at most $h(w)-k$ (and constructs
such a cycle if it exists). For $k$ fixed, the running time of the algorithm is
polynomial in $n$, where the degree of the polynomial does not depend on $k$
(i.e., the generalised Vizing problem is fixed-parameter tractable with respect
to the parameter $k$).