11institutetext:  School of Computer Science and Engineering, University of
Electronic Science and Technology of China, China, 11email<EMAIL_ADDRESS>22institutetext: Department of Applied Mathematics and Physics, Graduate
School of Informatics, Kyoto University, Japan, 22email:
<EMAIL_ADDRESS>
# An Exact Algorithm for TSP in Degree-$3$ Graphs via Circuit Procedure and
Amortization on Connectivity Structure ††thanks: Supported in part by Grant
60903007 of NSFC, China.

Mingyu Xiao 11 Hiroshi Nagamochi 22

###### Abstract

The paper presents an $O^{*}(1.2312^{n})$-time and polynomial-space algorithm
for the traveling salesman problem in an $n$-vertex graph with maximum degree
$3$. This improves the previous time bounds of $O^{*}(1.251^{n})$ by Iwama and
Nakashima and $O^{*}(1.260^{n})$ by Eppstein. Our algorithm is a simple
branch-and-search algorithm. The only branch rule is designed on a cut-circuit
structure of a graph induced by unprocessed edges. To improve a time bound by
a simple analysis on measure and conquer, we introduce an amortization scheme
over the cut-circuit structure by defining the measure of an instance to be
the sum of not only weights of vertices but also weights of connected
components of the induced graph.

Key words. Traveling Salesman Problem, Exact Exponential Algorithm, Graph
Algorithm, Connectivity, Measure and Conquer

##  1 Introduction

The traveling salesman problem (TSP) is one of the most famous and intensively
studied problems in computational mathematics. Many algorithmic methods have
been investigated to beat this challenge of finding the shortest route
visiting each member of a collection of $n$ locations and returning to the
starting point. The first $O^{*}(2^{n})$-time dynamic programming algorithm
for TSP is back to early 1960s. However, in the last half of a century no one
can break the barrier of $2$ in the base of the running time. To make steps
toward the long-standing and major open problem in exact exponential
algorithms, TSP in special classes of graphs, especially degree bounded
graphs, have also been intensively studied. Eppstein [5] showed that TSP in
degree-$3$ graphs (a graph with maximum degree $i$ is called a degree-$i$
graph) can be solved in $O^{*}(1.260^{n})$ time and polynomial space, and TSP
in degree-$4$ graphs can be solved in $O^{*}(1.890^{n})$ time and polynomial
space. Iwama and Nakashima [9] refined Eppstein’s algorithm for degree-$3$
graphs and improved the result to $O^{*}(1.251^{n})$ by showing that the worst
case in Eppstein’s algorithm will not always happen. Gebauer [8] designed an
$O^{*}(1.733^{n})$-time exponential-space algorithm for TSP in degree-$4$
graphs, which is improved to $O^{*}(1.716^{n})$ time and polynomial space by
Xiao and Nagamochi [13]. Bjorklund _et al._ [2] also showed TSP in degree
bounded graph can be solved in $O^{*}((2-\varepsilon)^{n})$ time, where
$\varepsilon>0$ depends on the degree bound only. There is a Monte Carlo
algorithm to decide a graph is Hamiltonian or not in $O^{*}(1.657^{n})$ time
[1]. For planar TSP and Euclidean TSP, there are sub-exponential algorithms
based on small separators [3].

In this paper, we present an improved deterministic algorithm for TSP in
degree-$3$ graphs, which runs in
$O^{*}(2^{{{3}\over{10}}n})=O^{*}(1.2312^{n})$ time and polynomial space. The
algorithm is simple and contains only one branch rule that is designed on a
cut-circuit structure of a graph induced by unprocessed edges. We will apply
the measure and conquer method to analyze the running time. Note that our
algorithm for TSP in degree-4 graphs in [13] is obtained by successfully
applying the measure and conquer method to TSP for the first time. However,
direct application of measure and conquer to TSP in degree-3 graphs may only
lead to an $O^{*}(1.260^{n})$-time algorithm. To effectively analyze our
algorithm, we use an amortization scheme over the cut-circuit structures by
setting weights to both vertices and connected components of the induced
graph.

##  2 Preliminaries

In this paper, a graph means an undirected edge-weighted graph with maximum
degree 3, which possibly has multiple edges, but no self-loops. Let $G=(V,E)$
be a graph with an edge weight. For a subset $V^{\prime}\subseteq V$ of
vertices and a subset $E^{\prime}\subseteq E$ of edges, the subgraphs induced
by $V^{\prime}$ and $E^{\prime}$ are denoted by $G[V^{\prime}]$ and
$G[E^{\prime}]$ respectively. We also use $\mathrm{cost}(E^{\prime})$ to
denote the total weight of edges in $E^{\prime}$. For any graph $G^{\prime}$,
the sets of vertices and edges in $G^{\prime}$ are denoted as $V(G^{\prime})$
and $E(G^{\prime})$ respectively. A graph consisting of a single vertex is
called trivial. A _cycle_ of length $l$ (also denoted as $l$-cycle) is a graph
with $l$ vertices $v_{i}$ and $l$ edges $v_{i}v_{i+1}$ ($i\in\\{1,2\dots,l\\}$
and $v_{l+1}=v_{1}$). An edge $v_{i}v_{j}$ ($|i-j|\geq 2$) between two
vertices in the cycle but different from the $l$ edges in it is called a chord
of the cycle. Two vertices in a graph are $k$-edge-connected if there are
$k$-edge-disjoint paths between them. A graph is $k$-edge-connected if every
pair of vertices in it are $k$-edge-connected. We treat a trivial graph as a
$k$-edge-connected graph for any $k\geq 1$. A Hamiltonian cycle is a cycle
through every vertex. Given a graph with an edge weight, the _traveling
salesman problem_ (TSP) is to find a Hamiltonian cycle of minimum total weight
in the edges.

###  2.1 Forced TSP

In some branch-and-search algorithms for TSP, we may branch on an edge in the
graph by including it to the solution or excluding it from the solution. In
this way, we need to maintain a set of edges that must be used in the
solution. We introduce the _forced traveling salesman problem_ as follows. An
instance is a pair $(G,F)$ of an edge-weighted undirected graph $G=(V,E)$ and
a subset $F\subseteq E$ of edges, called forced edges. A Hamiltonian cycle of
$G$ is called a tour if it passes though all the forced edges in $F$. The
objective of the problem is to compute a tour of minimum weight in the given
instance $(G,F)$. An instance is called infeasible if no tour exists. A vertex
is called _forced_ if there is a forced edge incident on it. For convenience,
we say that the _sign_ of an edge $e$ is 1 if $e$ is a forced edge and $0$ if
$e$ is an unforced edge. We use $\mathrm{sign}(e)$ to denote the sign of $e$.

###  2.2 $U$-graphs and $U$-components

We consider an instance $(G,F)$. Let $U=E(G)-F$ denote the set of unforced
edges. A subgraph $H$ of $G$ is called a _$U$ -graph_ if $H$ is a trivial
graph or $H$ is induced by a subset $U^{\prime}\subseteq U$ of unforced edges
(i.e., $H=G[U^{\prime}]$). A maximal connected $U$-graph is called a _$U$
-component_. Note that each connected component in the graph $(V(G),U)$ is a
$U$-component.

For a vertex subset $X$ (or a subgraph $X$) of $G$, let $\mathrm{cut}(X)$
denote the set of edges in $E=F\cup U$ between $X$ and $V(G)-X$, and denote
$\mathrm{cut}_{F}(X)=\mathrm{cut}(X)\cap F$ and
$\mathrm{cut}_{U}(X)=\mathrm{cut}(X)\cap U$. Edge set $\mathrm{cut}(X)$ is
also called a _cut_ of the graph. We say that an edge is _incident_ on $X$ if
the edge is in $\mathrm{cut}(X)$. The degree $d(v)$ of a vertex $v$ is defined
to be $|\mathrm{cut}(\\{v\\})|$. We also denote
$d_{F}(v)=|\mathrm{cut}_{F}(\\{v\\})|$ and
$d_{U}(v)=|\mathrm{cut}_{U}(\\{v\\})|$. A $U$-graph $H$ is $k$-pendent if
$|\mathrm{cut}_{U}(H)|=k$. A $U$-graph $H$ is called even (resp., odd) if
$|\mathrm{cut}_{F}(H)|$ is even (resp., odd). A $U$-component is 0-pendent.

In this paper, we will always keep every $U$-component 2-edge-connected. For
simplicity, we may regard a maximal path of forced edges between two vertices
$u$ and $v$ as a single forced edge $uv$ in an instance $(G,F)$, since we can
assume that $d_{F}(v)=2$ always implies $d(v)=2$ for any vertex $v$.

###  2.3 Circuits and blocks

We consider a nontrivial $U$-component $H$ in an instance $(G,F)$. A circuit
${\cal C}$ in $H$ is a maximal sequence $e_{1},e_{2},\ldots,e_{p}$ of edges
$e_{i}=u_{i}v_{i}\in E(H)$ $(1\leq i\leq p)$ such that for each $e_{i}\in{\cal
C}$ $(i\neq p)$, the next edge $e_{i+1}\in{\cal C}$ is given by a subgraph
$B_{i}$ of $H$ such that $\mathrm{cut}_{U}(B_{i})=\\{e_{i},e_{i+1}\\}$. See
Fig. 1 for an illustration. We say that each subgraph $B_{i}$ is a _block_
along ${\cal C}$ and vertices $v_{i}$ and $u_{i+1}$ are the endpoints of block
$B_{i}$. By the maximality of ${\cal C}$, we know that any two vertices in
each block $B_{i}$ are 2-edge-connected in the induced subgraph $G[B_{i}]$. It
is possible that a circuit in a 2-edge-connected graph $H$ may contain only
one edge $e=u_{1}v_{1}$. For this case, vertices $u_{1}$ and $v_{1}$ are
connected by three edge-disjoint paths in $H$ and the circuit is called
_trivial_ , where the unique block is the $U$-component $H$. Each nontrivial
circuit contains at least two blocks, each of which is a 2-pendent subgraph of
$H$. In our algorithm, we will consider only nontrivial circuits ${\cal C}$.
When $H$ is 2-edge-connected, there are $p\geq 2$ different blocks along a
nontrivial circuit ${\cal C}$, where $u_{1}$ and $v_{p}$ are in the same block
$B_{p}$ and $\mathrm{cut}_{U}(B_{p})=\\{e_{p},e_{1}\\}$. A block $B_{i}$ is
called trivial if $|V(B_{i})|=1$ and $d_{F}(v)=1$ for the only vertex $v$ in
it ($v$ is of degree 3 in $G$). A block $B_{i}$ is called reducible if
$|V(B_{i})|=1$ and $d_{F}(v)=0$ for the only vertex $v$ in it ($v$ is of
degree 2 in $G$). A block $B_{i}$ with $V(B_{i})=\\{v_{i}=u_{i+1}\\}$ is
either trivial or reducible in a 2-edge-connected graph.

Figure 1: A circuit in a 2-edge-connected graph $H$

We state more properties on circuits and blocks.

###### Lemma 1

In a degree-$3$ graph, let $H$ be a 2-edge-connected $U$-component and ${\cal
C}$ be any circuit in it. For each block $B_{i}$ of ${\cal C}$, $B_{i}$ is not
trivial or reducible if and only if the two endpoints $v_{i}$ and $u_{i+1}$ of
it are two different vertices of degree $3$ in $H$.

###### Lemma 2

Each edge in a $2$-edge-connected $U$-component $H$ of a degree-$3$ graph is
contained in exactly one circuit. A partition of $E(H)$ into circuits can be
obtained in linear time.

_Proof._ It is known that the set of all minimum cuts (a set of $k$ edges in a
$k$-edge-connected multigraph is called a minimum cut if the graph becomes
disconnected by removing the $k$ edges) can be represented by a cactus
structure (cf. [11]). In particular, when the size of a minimum cut is two,
the cactus structure of minimum cuts can be obtained in linear time by
contracting each 3-edge-connected component (a maximal set of vertices every
two of which are 3-connected in the given graph) into a single vertex, and for
each cycle $C$ in the resulting graph, a pair of any two edges in $C$
corresponds to a minimum cut in the original graph [10]. In a 2-edge-connected
$U$-component $H$, (i) an edge $e\in E(H)$ forms a circuit ${\cal C}$ having
only one block if and only if $e$ is not in any minimum cut of $H$; and (ii) A
circuit ${\cal C}$ with at least two edges in $H$ corresponds to a cycle $C$
in the cactus structure. Based on the cactus structure, we can obtain a
partition of edge sets into circuits in linear time.

###  2.4 Branch-and-search algorithms

Our algorithm is a branch-and-search algorithm: we search the solution by
iteratively branching on the current instance into several smaller instances
until the current instance becomes trivial (or polynomially solvable). In this
paradigm, we will get a search tree. In each leaf of the search tree, we can
solve the problem directly. The size of the search tree is the exponential
part of the running time of the search algorithm. Let $\mu$ be a measure of
the instance (for graph problems, the measure can be the number of vertices or
edges in the graph and so on). Let $C(\mu)$ denote the maximum number of
leaves in the search tree generated by the algorithm for any instance with
measure $\mu$. We shall determine an upper bound on $C(\mu)$ by evaluating all
the branches. When we branch on an instance $(G,F)$ with $k$ branches such
that the $i$-th branch decreases the measure $\mu$ of $(G,F)$ by at least
$a_{i}$, we obtain the following recurrence

$C(\mu)\leq C(\mu-a_{1})+C(\mu-a_{2})+\cdots+C(\mu-a_{k}).$

Solving this recurrence, we get
$C(\mu)=[\alpha(a_{1},a_{2},\ldots,a_{k})]^{\mu}$, where
$\alpha(a_{1},a_{2},\ldots,a_{k})$ is the largest root of the function
$f(x)=1-\sum_{i=1}^{k}x^{-a_{i}}$. In this paper, we represent the above
recurrence by a vector $(a_{1};a_{2};\cdots;a_{k})$ of measure decreases,
called a branch vector (cf. [7]). In particular, when
$a_{i}=a_{i+1}=\cdots=a_{j}$ for some $i\leq j$, it may be written as
$(a_{1};a_{2};\cdots a_{i-1};[a_{i}]_{j-i+1};a_{j+1};\cdots;a_{k})$, and a
vector $([a]_{k})$ is simply written as $[a]_{k}$. When we compare two branch
vectors $\mathbf{b}=(a_{1};a_{2})$ $(a_{1}\leq a_{2})$ and
$\mathbf{b}^{\prime}=(a^{\prime}_{1};a^{\prime}_{2})$ such that “$a_{i}\leq
a^{\prime}_{i}$ $(i=1,2)$” or “$a^{\prime}_{1}=a_{1}-\varepsilon$ and
$a^{\prime}_{2}=a_{2}+\varepsilon$ for some $0\leq\varepsilon\leq
a_{2}-a_{1}$,” we only consider branch vector $\mathbf{b}$ in analysis, since
a solution $\alpha$ from $\mathbf{b}$ is not smaller than that from
$\mathbf{b}^{\prime}$ (cf. [7]). We say that $\mathbf{b}$ covers
$\mathbf{b}^{\prime}$ in this case.

##  3 Reductions based on small cuts

For some special cases, we can reduce the instance directly without branching.
Most of out reduction rules are based on the structures of small cuts in the
graph. In fact, we will deal with cuts of size $1,2,3$ and $4$.

###  3.1 Sufficient conditions for infeasibility

The parity condition on an instance is: (i) every $U$-component is even; and
(ii) the number of odd blocks along every circuit is even.

###### Lemma 3

An instance $(G,F)$ is infeasible if $G$ is not 2-edge-connected or it
violates the parity condition.

_Proof._ Since any tour is a 2-edge-connected spanning graph of $G$, it cannot
exist when $G$ is not 2-edge-connected. Since any tour is an Eulerian graph,
it cannot exist in any instance with an odd $U$-component. For a circuit which
has an odd number of odd blocks, we see that at least one odd block will be an
odd $U$-component in any way of including/deleting edges in the circuit.

###  3.2 Eliminable, reducible and parallel edges

The unique unforced edge incident on a 1-pendent $U$-graph is _eliminable_.
From parity condition (i), we can decide whether each eliminable edge need to
be included to $F$ or deleted from the graph just by depending on the parity
of $|\mathrm{cut}_{F}(H)|$.

For any subgraph $H$ of $G$ with $|\mathrm{cut}(H)|=2$, we call the unforced
edges in $\mathrm{cut}(H)$ reducible. From the connectivity condition and
parity condition (i), we see that all reducible edges need to be included to
$F$. In particular, any edge $uv$ incident to a vertex $v$ with $d(v)=2$ (or
with a neighbor $v^{\prime}$ with multiple edges of $vv^{\prime}\in F$ and
$vv^{\prime}\in U$) is reducible, since $uv\in\mathrm{cut}(X)$ and
$|\mathrm{cut}(X)|=2$ for $X=\\{v\\}$ (or $X=\\{v,v^{\prime}\\}$).

If there are multiple edges with the same endpoints $u$ and $v$, we can reduce
the instance in the following way preserving the optimality: If the graph has
only two vertices $u$ and $v$, solve the problem directly; else if there are
forced edges between $u$ and $v$, the problem is infeasible; and otherwise
remove all unforced edges between $u$ and $v$ except one with the smallest
weight.

###  3.3 Reductions based on 3-cuts and 4-cuts

###### Lemma 4

Let $(G,F)$ be an instance where $G$ is a graph with maximum degree 3. For any
subgraph $X$ with $|\mathrm{cut}(X)|=3$, we can replace $X$ with a single
vertex $x$ and update the three edges incident on $x$ preserving the
optimality of the instance.

_Proof._ Denote $\mathrm{cut}(X)$ by $\\{y_{1}x_{1},y_{2}x_{2},y_{3}x_{3}\\}$
with $x_{i}\in V(X)$ and $y_{i}\in V-V(X)$. We will replace $X$ and
$\mathrm{cut}(X)$ with a single vertex $x$ and three new edges $xy_{1},xy_{2}$
and $xy_{3}$. Let $G^{\prime}$ denote the new graph. We only need to decide
the weights and signs of edges $xy_{1},xy_{2}$ and $xy_{3}$ in $G^{\prime}$ to
satisfy the lemma. Let $I_{i}$ ($i=1,2,3$) denote the problem of finding a
path $P$ from $x_{i_{1}}$ to $x_{i_{2}}$ ($\\{i,i_{1},i_{2}\\}=\\{1,2,3\\}$)
of minimum total cost in $X$ that passes through all vertices and forced edges
in $X$. We say that $I_{i}$ _infeasible_ if it has no such path. We consider
the three problems $I_{i}$ ($i=1,2,3$). There are four possible cases. Case 1.
None of the three problems is feasible: We can see that the original instance
$(G,F)$ is also infeasible. In $G^{\prime}$, we let
$\mathrm{sign}(xy_{1})=\mathrm{sign}(xy_{2})=\mathrm{sign}(xy_{3})=1$. Since
the trivial $U$-component $\\{x\\}$ is odd, the new instance is infeasible by
Lemma 3. Case 2. Only one of the three problems, say $I_{j_{1}}$
($\\{j_{1},j_{2},j_{3}\\}=\\{1,2,3\\}$), is feasible: Let $S_{j_{1}}$ be an
optimal solution to $I_{j_{1}}$. Then there is a solution $S$ to $(G,F)$ such
that $S\cap E(X)=E(S_{j_{1}})$ (if $(G,F)$ is feasible). Therefore, in
$G^{\prime}$, we let $\mathrm{sign}(xy_{j_{2}})=\mathrm{sign}(xy_{j_{3}})=1$,
$\mathrm{sign}(xy_{j_{1}})=\mathrm{sign}(x_{j_{1}}y_{j_{1}})$,
$\mathrm{cost}(xy_{j_{2}})=\mathrm{cost}(x_{j_{2}}y_{j_{2}})+\mathrm{cost}(S_{j_{1}})$,
$\mathrm{cost}(xy_{j_{3}})=\mathrm{cost}(x_{j_{3}}y_{j_{3}})$ and
$\mathrm{cost}(xy_{j_{1}})=\mathrm{cost}(x_{j_{1}}y_{j_{1}})$. Case 3. Exactly
two of the three problems, say $I_{j_{1}}$ and $I_{j_{2}}$
($\\{j_{1},j_{2},j_{3}\\}=\\{1,2,3\\}$), are feasible: Let $S_{j_{1}}$ and
$S_{j_{2}}$ be an optimal solution to $I_{j_{1}}$ and $I_{j_{2}}$
respectively. Then there is a solution $S$ to $(G,F)$ such that either $S\cap
E(X)=E(S_{j_{1}})$ or $S\cap E(X)=E(S_{j_{2}})$. Therefore, in $G^{\prime}$,
we let $\mathrm{sign}(xy_{j_{3}})=1$,
$\mathrm{sign}(xy_{j_{1}})=\mathrm{sign}(x_{j_{1}}y_{j_{1}})$,
$\mathrm{sign}(xy_{j_{2}})=\mathrm{sign}(x_{j_{2}}y_{j_{2}})$,
$\mathrm{cost}(xy_{j_{3}})=\mathrm{cost}(x_{j_{3}}y_{j_{3}})$,
$\mathrm{cost}(xy_{j_{1}})=\mathrm{cost}(x_{j_{1}}y_{j_{1}})+\mathrm{cost}(S_{j_{2}})$
and
$\mathrm{cost}(xy_{j_{2}})=\mathrm{cost}(x_{j_{2}}y_{j_{2}})+\mathrm{cost}(S_{j_{1}})$.
Case 4. All of the three problems are feasible: Let $S_{1}$, $S_{2}$ and
$S_{3}$ be an optimal solution to $I_{1}$, $I_{2}$ and $I_{3}$ respectively.
In $G^{\prime}$, we let $\mathrm{sign}(xy_{i})=\mathrm{sign}(x_{i}y_{i})$ and
$\mathrm{cost}(xy_{i})=\mathrm{cost}(x_{i}y_{i})+{1\over
2}{\sum_{j=1}^{3}\mathrm{cost}(S_{j})}-\mathrm{cost}(S_{i})$ ($i=1,2,3$).
Straightforward computation can verify that with these setting $G^{\prime}$
will preserve the optimality.

Similar to Lemma 4, we can simplify a subgraph $X$ with $|\mathrm{cut}(X)|=4$.
However, there are many cases needed to consider. In fact, in our algorithms,
we only need to consider a special case.

We consider a subgraph $X$ with $|\mathrm{cut}_{F}(X)|=4$ and
$|\mathrm{cut}_{U}(X)|=0$. We want to reduce $X$. Denote $\mathrm{cut}(X)$ by
$\\{y_{1}x_{1},y_{2}x_{2},y_{3}x_{3},y_{4}x_{4}\\}$ with $x_{i}\in V(X)$ and
$y_{i}\in V-V(X)$, where $x_{i}\neq x_{j}$ $(1\leq i<j\leq 4)$. We define
$I_{i}$ ($i=1,2,3$) to be instances of the problem of finding two disjoint
paths $P$ and $P^{\prime}$ of minimum total cost in $X$ such that all vertices
and forced edges in $X$ appear in exactly one of the two paths, and one of the
two paths is from $x_{i}$ to $x_{4}$ and the other one is from $x_{j_{1}}$ to
$x_{j_{2}}$ ($\\{j_{1},j_{2}\\}=\\{1,2,3\\}-\\{i\\}$). We say that $I_{i}$
_infeasible_ if it has no solution.

A subgraph $X$ is _$4$ -cut reducible_ if $|\mathrm{cut}_{F}(X)|=4$,
$|\mathrm{cut}_{U}(X)|=0$, and at least one of the three problems
$I_{1},I_{2}$ and $I_{3}$ defined above is infeasible. We have the following
lemma to reduce the $4$-cut reducible subgraph.

###### Lemma 5

Let $(G,F)$ be an instance where $G$ is a graph with maximum degree 3. A
$4$-cut reducible subgraph $X$ can be replaced with one of the following
subgraphs $X^{\prime}$ with four vertices and
$|\mathrm{cut}_{F}(X^{\prime})|=4$ so that the optimality of the instance is
preserved:
(i) four single vertices $($i.e., there is no solution to this instance$)$;
(ii) a pair of forced edges; and
(iii) a 4-cycle with four unforced edges.

_Proof._ We consider the three problems $I_{i}$ ($i=1,2,3$). Since at least
one of them is infeasible, there are three possible cases. Case 1. None of the
three problems is feasible: We can see that the original instance $(G,F)$ is
also infeasible. Then we can replace $X$ with a graph containing only four
vertices $\\{x_{1},x_{2},x_{3},x_{4}\\}$ and no edge. Now $x_{1}$ becomes a
degree-1 vertex in the new graph and the new instance is infeasible. Case 2.
Only one of the three problems, say $I_{i_{0}}$ ($i_{0}\in\\{1,2,3\\}$), is
feasible: Let $S_{i_{0}}$ be an optimal solution to $I_{i_{0}}$. Then there is
a solution $S$ to $(G,F)$ such that $S\cap E(X)=E(S_{i_{0}})$. Therefore, we
can replace $X$ with a graph of four vertices $\\{x_{1},x_{2},x_{3},x_{4}\\}$
and two edges $x_{i}x_{4}$ and $x_{j_{1}}x_{j_{2}}$ in $G$ preserving the
optimality of the instance, where the costs of $x_{i_{0}}x_{4}$ and
$x_{j_{1}}x_{j_{2}}$ are the costs of the two paths in $S_{i_{0}}$. Note that
in the new instance after the replacement, the four vertices
$\\{x_{1},x_{2},x_{3},x_{4}\\}$ become degree-2 vertices and the two new edges
$x_{i}x_{4}$ and $x_{j_{1}}x_{j_{2}}$ should be included into $F$. Case 3. Two
of the three problems, say $I_{i_{1}}$ and $I_{i_{2}}$
($i_{1},i_{2}\in\\{1,2,3\\}$), are feasible: Let $S_{i_{1}}$ and $S_{i_{2}}$
be optimal solutions to $I_{i_{1}}$ and $I_{i_{2}}$ respectively. Then there
is a solution $S$ to $(G,F)$ such that $S\cap E(X)=E(S_{i_{1}})$ or $S\cap
E(X)=E(S_{i_{2}})$. Therefore, we can replace $X$ with a $4$-cycle
$x_{i_{1}}x_{4}x_{i_{2}}x_{j}$ preserving the optimality of the instance,
where $\\{j\\}=\\{1,2,3\\}-\\{i_{1},i_{2}\\}$, the costs of $x_{i_{1}}x_{4}$
and $x_{i_{2}}x_{j}$ are the costs of the two paths in $S_{i_{1}}$, and the
costs of $x_{4}x_{i_{2}}$ and $x_{j}x_{i_{1}}$ are the costs of the two paths
in $S_{i_{2}}$.

###### Lemma 6

Let $X$ be an induced subgraph of a degree-$3$ graph $G$ such that $X$
contains at most eight vertices of degree 3 in $G$. Then $X$ is $4$-cut
reducible if $|\mathrm{cut}_{F}(X)|=4$, $|\mathrm{cut}_{U}(X)|=0$, and $X$
contains at most two unforced vertices.

_Proof._ We only need to show that at least one of the three problem instances
$I_{1},I_{2}$ and $I_{3}$ (defined before Lemma 5) is infeasible. Assume that
no two edges in $\mathrm{cut}_{F}(X)$ meet at a same vertex in $X$, since
otherwise only one of $I_{1},I_{2}$ and $I_{3}$ is feasible. Also assume that
$X$ has no multiple edges or induced triangles, since otherwise $X$ can be
reduced to a smaller graph preserving its optimality. Note that $X$ contains
an even number $k$ of degree 3 vertices in $G$. Since $k=4$ (i.e., $|V(X)|=4$)
implies the lemma, we consider the case of $k=6,8$. When $k=6$, $X$ is either
a 6-cycle with a chord or a graph obtained from a 5-cycle with a chord by
subdividing the chord with a new vertex. In any case, we see that one of
$I_{1},I_{2}$ and $I_{3}$ is infeasible. Let $k=8$. In this case, there are
four vertices $u_{i}$ $(i=1,2,3,4)$ which are not incident to any of the four
edges in $\mathrm{cut}(B)=\mathrm{cut}_{F}(B)$, and two of them, say $u_{1}$
and $u_{2}$ are joined by a forced edge $u_{1}u_{2}\in F$ by the assumption on
the number of unforced vertices in $X$. Then we see that there are three
possible configurations for such an induced graph $X$ with no induced
triangles, and a straightforward inspection shows that none of them admits a
set of three feasible instances $I_{1},I_{2}$ and $I_{3}$.

Lemma 4 and Lemma 5 imply a way of simplifying some local structures of an
instance. However, it is not easy to find solutions to problems $I_{i}$ in the
above two lemmas. In our algorithm, we only do this replacement for $X$
containing no more than 10 vertices and then the corresponding problems
$I_{i}$ can be solved in constant time by a brute force search.

We define the operation of _$3$ /$4$-cut reduction_: If there a subgraph $X$
of $G$ with $|V(X)|\leq 10$ such that $|\mathrm{cut}(X)|=3$ or $X$ is $4$-cut
reducible, then we simplify the graph by replacing $X$ with a graph according
to Lemma 4 or Lemma 5. Note that a $3$/$4$-cut can be found in polynomial time
if it exists and then this reduction operation can be implemented in
polynomial time.

###  3.4 A solvable case and reduced graphs

A 3/4-cut reduction reduce the subgraph $X$ to a trivial graph except for the
last case of Lemma 5 where $X$ will become a 4-cycle. Eppstein has identified
a polynomially solvable case of forced TSP [5], which can deal with
$U$-components of 4-cycles.

###### Lemma 7

[5] If every $U$-component is a component of a 4-cycle, then a minimum cost
tour of the instance can be found in polynomial time.

Based on this lemma, we do not need to deal with $U$-components of 4-cycles in
our algorithms.

All above reduction rules can be applied in polynomial time. An instance
$(G,F)$ is called a _reduced_ instance if $G$ is 2-edge-connected, $(G,F)$
satisfies the parity condition, and has none of reducible edges, eliminable
edges and multiple edges, and the 3/4-cut reduction cannot be applied on it
anymore. Note that a reduced instance has no triangle, otherwise 3-cut
reduction would be applicable. An instance is called 2-edge-connected if every
$U$-component in it is 2-edge-connected. The initial instance
$(G,F=\emptyset)$ is assumed to be 2-edge-connected, otherwise it is
infeasible by Lemma 3. In our algorithm, we will guarantee that the input
instance is always 2-edge-connected, and we branch on a reduced graph to
search a solution.

##  4 The circuit procedure

The _circuit procedure_ is one of the most important operations in our
algorithm. The procedure will determinate each edge in a circuit to be
included into $F$ or to be deleted from the graph. It will be widely used as
the only branching operation in our algorithm.

#### Processing circuits:

_Determining_ an unforced edge means either including it to $F$ or deleting it
from the graph. When an edge is determined, the other edges in the same
circuit containing this edge can also be determined directly by reducing
eliminable edges. We call the series of procedures applied to all edges in a
circuit together as a _circuit procedure_. Thus, in the circuit procedure,
after we start to process a circuit ${\cal C}$ either by including an edge
$e_{1}\in{\cal C}$ to $F$ or by deleting $e_{1}$ from the graph, the next edge
$e_{i+1}$ of $e_{i}$ becomes an eliminable edge and we continue to determine
$e_{i+1}$ either by deleting it from the graph if block $B_{i}$ is odd and
$e_{i}=u_{i}v_{i}$ is included to $F$ (or $B_{i}$ is even and $e_{i}$ is
deleted); or by including it to $F$ otherwise. Circuit procedure is a
fundamental operation to build up our proposed algorithm. Note that a circuit
procedure determines only the edges in the circuit. During the procedure, some
unforced edges outside the circuit may become reducible and so on, but we do
not determine them in this execution.

###### Lemma 8

Let $H$ be a 2-edge-connected $U$-component in an instance $(G,F)$ and ${\cal
C}$ be a circuit in $H$. Let $(G^{\prime},F^{\prime})$ be the resulting
instance after applying circuit procedure on ${\cal C}$. Then
(i) each block $B_{i}$ of ${\cal C}$ becomes a 2-edge-connected $U$-component
in $(G^{\prime},F^{\prime})$; and
(ii) any other $U$-component $H^{\prime}$ than $H$ in $(G,F)$ remains
unchanged in $(G^{\prime},F^{\prime})$.

_Proof._ Since $H$ is 2-edge-connected, we know that each block $B_{i}$
induces a 2-edge-connected subgraph from $H$ according to the definition of
circuits. Hence $B_{i}$ will be a 2-edge-connected $U$-component in
$(G^{\prime},F^{\prime})$. Then we get (i). Since $H$ and $H^{\prime}$ are
vertex-disjoint and only edges in $H$ are determined, we see that (ii) holds.

We call a circuit _reducible_ if it contains at least one reducible edge. We
can apply the circuit procedure on a reducible circuit directly starting by
including a reducible edge to $F$. In our algorithm, we will deal with
reducible edges by processing a reducible circuit. When the instance becomes a
reduced instance, we may not be able to reduce the instance directly. Then we
search the solution by “branching on a circuit.” _Branching on a circuit
${\cal C}$ at edge $e\in{\cal C}$_ means branching on the current instance to
generate two instances by applying the circuit procedure to ${\cal C}$ after
including $e$ to $F$ and deleting $e$ from the graph respectively. Branching
on a circuit is the only branching operation used in our algorithm.

##  5 A simple algorithm based on circuit procedures

We first introduce a simple algorithm for forced TSP to show the effectiveness
of the circuit procedures. Improved algorithms are given in the next sections.

The simple algorithm contains only two steps: First reduce the instance until
it becomes a reduced one; and then select a $U$-component $H$ that is neither
trivial nor a 4-cycle and branch on a circuit ${\cal C}$ in $H$ such that at
least one block along ${\cal C}$ is trivial. Note that there is always a
circuit having a trivial block as long as the forced edge set $F$ is not
empty.

Here we use a traditional method to analyze the simple algorithm. It is
natural to consider how many edges can be added to $F$ in each operation of
the algorithm. The size of $F$ will not decrease by applying the reduction
rules. Let $r=n-|F|$ and $C(r)$ denote the maximum number of leaves in the
search tree generated by the algorithm for any instance with measure $r$. We
only need to consider the branching operation in the second step.

For convenience, we call a maximal sequence $P=\\{e_{1},e_{2},\ldots,e_{p}\\}$
of edges $e_{i}=u_{i}u_{i+1}\in E(H)$ $(1\leq i\leq p-1)$ a chain if all
vertices $u_{j}$ ($j=2,3,\ldots,p-1$) are forced vertices. In the definition
of the chain, we allow $u_{1}=u_{p}$. Observe that each chain is contained in
the same circuit. Since the selected circuit ${\cal C}$ has some trivial
block, we know that ${\cal C}$ contains at least one chain $P$ of size $\geq
2$. We distinguish two cases according to the size of $P$ being even or odd.

Case 1. $|P|$ is even: If all the blocks of ${\cal C}$ are trivial, then the
$U$-component $H$ containing ${\cal C}$ is a cycle of even length. Since $H$
cannot be a $4$-cycle, the length of cycle $H$ is at least $6$ (see Fig. 2(a)
for an illustration). In each branch, after processing the circuit ${\cal C}$,
we can include at least $3$ edges to $F$. This gives us branch vector

$\displaystyle(3;3).$ (1)

Next, we assume that ${\cal C}$ has a nontrivial block. We look at the worst
case where $P$ is of size 2 and ${\cal C}$ has only one nontrivial block (see
Fig. 2(b) for an illustration). Now ${\cal C}=P$. Let ${\cal
C}=\\{u_{1}v_{1},u_{2}v_{2}\\}$, where $v_{1}=u_{2}$. We branch on the circuit
at edge $u_{1}v_{1}$. In the branch of deleting $u_{1}v_{1}$, we include
$u_{2}v_{2}$ into $F$ . Furthermore, we can include the remaining two edges
incident on $u_{1}$ into $F$ by simply applying reduction rules. In the other
branch of including $u_{1}v_{1}$ into $F$, we will delete $u_{2}v_{2}$ and
include the other two edges incident on $v_{2}$ into $F$. We still can get
branch vector (1). Note that when ${\cal C}$ is not of the worst case, it is
not hard to verify that we may include more edges to $F$ and we can get a
branch vector covered by (1). We omit the details here, since the detailed
proof can also be derived from the analysis of the improved algorithm in the
next sections.

Figure 2: Three bottleneck cases in branching on a cirucuit ${\cal C}$: (a)
${\cal C}$ is a 6-cycle; (b) ${\cal C}$ is a chain $P$ of length 2; (c) ${\cal
C}$ is a chain $P$ of length 3.

Case 2. $|P|$ is odd: Now circuit ${\cal C}$ must contain at least one
nontrivial block, otherwise the instance violates the parity condition. We
also look at the worst case where $P$ is of size 3 (since $|P|\geq 2$) and
${\cal C}$ has only one nontrivial block (see Fig. 2(c) for an illustration).
Let ${\cal C}=\\{u_{1}v_{1},u_{2}v_{2},u_{3}v_{3}\\}$, where $v_{1}=u_{2}$ and
$v_{2}=u_{3}$. We branch on the circuit at edge $u_{1}v_{1}$. In the branch of
deleting $u_{1}v_{1}$, we will also delete $u_{3}v_{3}$ and include the
following five edges to $F$: $v_{2}u_{2}$, the remaining two edges incident on
$u_{1}$ and the remaining two edges incident on $v_{3}$ (note that since the
graph is reduced, $u_{1}$ and $v_{3}$ are not adjacent and then the five edges
are different to each other). In the other branch of including $u_{1}v_{1}$ to
$F$, we will delete $u_{2}v_{2}$ and include $u_{3}v_{3}$ to $F$. We can get
branch vector

$\displaystyle(5;2).$ (2)

When ${\cal C}$ is not of the worst case, we can reduce more edges and get (2)
at least.

Since $C(r)=1.260^{r}$ satisfies the two recurrences corresponding to (1) and
(2), we know that the simple algorithm can solve the TSP problem in an
$n$-vertex degree-3 graph in $O^{*}(1.260^{n})$ time, which achieves the same
running time bound of Eppstein’s algorithm for TSP3 in [5].

##  6 The measure and conquer method

The measure and conquer method, first introduced by Fomin, Grandoni and
Kratsch [6], is one of the most powerful tools to analyze exact algorithms. It
can obtain improved running time bound for many branching-and-search
algorithms without making any modification to the algorithms. Currently, many
best exact algorithms for NP-hard problems are based on this method. In the
measure and conquer method, we may set a weight of vertices in the instance
and use the sum $w$ of the total weight in the graph as the measure to
evaluate the running time. In the algorithm, the measure $w$ should satisfy
the _measure condition_ : (i) when $w\leq 0$ the instance can be solved in
polynomial time; (ii) the measure $w$ will never increase in each operation in
the algorithm; and (iii) the measure will decrease in each of the subinstances
generated by applying a branching rule. With these constraints, we may build
recurrences for the branching operations. Next, we introduce a way of applying
the measure and conquer method to the above simple algorithm.

The graph has three different vertex-weight. For each vertex $v$, we set its
vertex-weight $w(v)$ to be

$w(v)=\left\\{\begin{array}[]{cl}w_{3}=1&\mbox{if $d_{U}(v)=3$ }\\\
w_{3^{\prime}}&\mbox{if $d_{U}(v)=2$ and $d_{F}(v)=1$}\\\
0&\mbox{otherwise.}\end{array}\right.$

We will determine the best value of $w_{3^{\prime}}$ such that the worst
recurrence in our algorithm is best. Let $\Delta_{3}=w_{3}-w_{3^{\prime}}$.
For a subset of vertices (or a subgraph) $X$, we also use $w(X)$ to denote the
total vertex-weight in $X$.

Now we analyze the simple algorithm presented in Section 5 by using this
vertex-weight setting. Note that since we require that $w_{3}=1$, the total
vertex weight $w$ in the graph is not greater than the number $n$ of vertices
in the graph. We can get a running time bound related to $n$ if we get a
running time bound related to $w$. Here we only examine the three bottleneck
cases in Fig. 2.

When we branch on a circuit of 6-cycle in Fig. 2(a), in each branch, all the
six forced vertices will be reduced and then we can reduce $w$ by
$6w_{3^{\prime}}$. We get the following branching vector:

$\displaystyle[6w_{3^{\prime}}]_{2}.$ (3)

When we branch on a circuit of chain of length 2 in Fig. 2(b), in the branch
where $u_{1}v_{1}$ is included to $F$, $u_{2}v_{2}$ is deleted, and
$v_{2}v^{\prime}_{2}$ and $v_{2}v^{\prime\prime}_{2}$ are also included to $F$
by reduction rules, where $v^{\prime}_{2}$ and $v^{\prime\prime}_{2}$ are the
two neighbors of $v_{2}$ other than $u_{2}$. Then we can reduce $w$ by
$w_{3^{\prime}}$ from $v_{1}$, $\Delta_{3}$ from $u_{1}$, $w_{3}$ from
$v_{2}$, and $2\delta_{1}$ from $v^{\prime}_{2}$ and $v^{\prime\prime}_{2}$,
where $\delta_{1}\geq\min\\{\Delta_{3},w_{3^{\prime}}\\}$. The second branch
can be analyzed in a similar manner. We get

$\displaystyle[w_{3^{\prime}}+\Delta_{3}+w_{3}+2\delta_{1}]_{2}=[2+2\delta_{1}]_{2}.$
(4)

When we branch on a circuit of chain of length 3 in Fig. 2(c), in the branch
of including $u_{1}v_{1}$ to $F$, we reduce $w$ by $2\Delta_{3}$ from $u_{1}$
and $v_{3}$ and $2w_{3^{\prime}}$ from $v_{1}$ and $v_{2}$. In the other
branch, we can reduce $w$ by $2w_{3}$ from $u_{1}$ and $v_{3}$,
$2w_{3^{\prime}}$ from $v_{1}$ and $v_{2}$, and $4\delta_{1}$ from
$\\{u^{\prime}_{1},u^{\prime\prime}_{1},v^{\prime}_{3},v^{\prime\prime}_{3}\\}$,
where $u^{\prime}_{1}$ and $u^{\prime\prime}_{1}$ are the two neighbors of
$u_{1}$ other than $v_{1}$ and $v^{\prime}_{3}$ and $v^{\prime\prime}_{3}$ are
the two neighbors of $v_{3}$ other than $u_{3}$. We get

$\displaystyle(2;2w_{3}+2w_{3^{\prime}}+4\delta_{1}).$ (5)

We can verify that under that above three constraints, the best value of
$w_{3^{\prime}}$ is ${\frac{1}{2}}w_{3}=\frac{1}{2}$. With this setting, we
can see that (3) and (4) become (1), and (5) becomes (2). This also tells us
that the measure and conquer method cannot directly derive a better running
time bound of the simple algorithm. In the next section, we present a new
technique and show an improvement by combining the new technique with the
traditional measure and conquer method.

##  7 Amortization on connectivity structures

To improve the time bound by the above simple analysis, we need to use more
structural properties of the graph. Note that for the bottleneck case of Fig.
2(a), the above algorithm reduces all the vertices in this $U$-component. It
is impossible to improve by reducing more vertices (or edges) and so on. But
we also reduce the number of $U$-components by 1. This observation gives us an
idea of an amortization scheme over the cut-circuit structure by setting a
weight on each $U$-component in the graph.

In this method, each vertex in the graph receives a nonnegative weight as
shown in Section 6. We also set a weight (which is possibly negative, but
bounded from by a constant $c\geq 0$) to each $U$-component. Let $\mu$ be the
sum of all vertex weight and $U$-component weight. We will use $\mu$ to
measure the size of the search tree generated by our algorithm. The measure
$\mu$ will also satisfy the measure condition. Initially there is only one
$U$-component and $\mu<n+c$ holds. If we get a running time bound related to
$\mu$ for our algorithm, then we get a running time bound related to $n$.

A simple idea is to set the same weight to each nontrivial $U$-component. It
is possible to improve the previous best result by using this simple idea.
However, to get further improvement, in this paper, we set several different
component-weights. Our purpose is to distinguish some “bad” $U$-components,
which will be characterized as “critical” $U$-components.

An extension of a 6-cycle is obtained from a 6-cycle
$v_{1}v_{2}v_{3}v_{4}v_{5}v_{6}$ and a 2-clique $ab$ by joining them with two
independent edges $av_{i}$ and $bv_{j}$ ($i\neq j$). An extension of a 6-cycle
always has exactly eight vertices. A chord of an extension of a 6-cycle is an
edge between two vertices in it but different from the eight edges
$v_{1}v_{2},v_{2}v_{3},v_{3}v_{4},v_{4}v_{5},v_{5}v_{6},v_{6}v_{1},av_{i}$,
$bv_{j}$ and $ab$.

A subgraph $H$ of a $U$-component in an instance $(G,F)$ is _$k$ -pendent
critical_, if it is a 6-cycle or an extension of a 6-cycle with
$|\mathrm{cut}_{U}(H)|=k$ and $|\mathrm{cut}_{F}(H)|=6-k$ (i.e., $H$ has no
chord of unforced/forced edge). A $0$-pendent critical $U$-component is also
simply called a _critical graph_ or _critical $U$-component_. Fig. 3
illustrates two examples of critical graphs of extensions of a $6$-cycle.
Branching on a critical $U$-component may lead to a bottleneck recurrence in
our algorithm. So we set a different component-weight to this kind of
components to get improvement.

Figure 3: Extensions of a 6-cycle

For each $U$-component $H$, we set its component-weight $c(H)$ to be

$c(H)=\left\\{\begin{array}[]{cl}0&\mbox{if $H$ is trivial}\\\
-4w_{3^{\prime}}&\mbox{if $H$ is a 4-cycle}\\\ \gamma&\mbox{if $H$ is a
critical $U$-component}\\\ \delta&\mbox{otherwise,}\end{array}\right.$

where we set $c(H)=-4w_{3^{\prime}}$ so that $c(H)+w(H)=0$ holds for every
4-cycle $U$-component $H$.

We also require that the vertex-weight and component-weight satisfy the
following requirements

$\displaystyle 2\Delta_{3}\geq\gamma\geq\delta\geq\Delta_{3}\geq{1\over
2}w_{3},~{}w_{3^{\prime}}\geq{1\over
5}w_{3}~{}~{}\mathrm{and}~{}~{}\gamma-\delta\leq w_{3^{\prime}}.$ (6)

Under these constraints, we still need to decide the values of
$w_{3^{\prime}},\gamma$ and $\delta$ such that the time bound derived by the
worst recurrences in our algorithm will be minimized. In (6),
$2\Delta_{3}\geq\gamma$ is important, because it will be used to satisfy the
measure condition (ii). The other constraints in (6) are mainly used to
simplify some arguments and they will not become the bottleneck in our
analysis. Next, we first describe our simple algorithm.

##  8 The algorithm

A block is called a _normal block_ if it is none of trivial, reducible and
2-pendent critical. A normal block is _minimal_ if no subgraph of it is a
normal block along any circuit. Note that when $F$ is not empty, each
$U$-component has at least one nontrivial circuit. Our recursive algorithm for
forced TSP only contains two main steps:
1. First apply the reduction rules to a given instance until it becomes a reduced one; and
2. Then take any $U$-component $H$ that is neither trivial nor a 4-cycle (if no such $U$-component $H$, then the instance is polynomially solvable by Lemma 7), and branch on a nontrivial circuit ${\cal C}$ in $H$, where ${\cal C}$ is chosen so that
(1) no normal block appears along ${\cal C}$ (i.e., ${\cal C}$ has only
trivial and 2-pendent critical blocks) if this kind of circuit exist; and
(2) a minimal normal block $B_{1}$ in $H$ appears along ${\cal C}$ otherwise.

We use $\mu$ as the measure to analyze the size of the search tree in our
algorithm. It is easy to see that after applying the reduction rules on a
2-edge-connected instance, the resulting instance remains 2-edge-connected. By
this observation and Lemma 8, we can guarantee that an input instance is
always 2-edge-connected. Our analysis is based on this.

###  8.1 Basic properties of the measure

Before analyzing the time bound on our algorithm, we first give basic
properties of the measure $\mu$.

We show that the measure will not increase after applying any reduction
operation in an 2-edge-connected instance. Since an input instance is 2-edge-
connected, there is no eliminable edge. In fact, we always deal with
eliminable edges in circuit procedures. For reducible edges, we deal with them
during a process of a reducible circuit (including the reducible edges to $F$
and dealing with the resulting eliminable edges). We will show that $\mu$
never increases after processing a circuit. The measure $\mu$ will not
increase after deleting any unforced parallel edge. The following lemma also
shows that applying the $3$/$4$-cut reduction does not increase $\mu$.

###### Lemma 9

For a given instance,
(i) applying the $3$-cut reduction does not increase the measure $\mu$; and
(ii) applying the $4$-cut reduction on a $U$-component $X$ decreases the
measure $\mu$ by $w(X)+c(X)$.

_Proof._ It is easy to observe (i). Next we prove (ii). In the case where the
resulting graph consists of four single vertices or a pair of forced edges
after applying the $4$-cut reduction, the whole component $X$ is eliminated,
decreasing $\mu$ by $w(X)+c(X)$ and then the lemma holds. Otherwise the
resulting component, say $X^{\prime}$ is a $4$-cycle, where
$w(X^{\prime})+c(X^{\prime})=0$ according to our setting on the component-
weight of $4$-cycles, and $\mu$ again decreases by $w(X)+c(X)$.

Next we consider how much amount of measure decreases by processing a circuit.
We consider that the measure $\mu$ becomes zero whenever we find an instance
infeasible by Lemma 3. After processing a circuit ${\cal
C}=\\{e_{i}=u_{i}v_{i}\mid 1\leq i\leq p\\}$ in a $U$-component $H$, each
block $B_{i}$ along ${\cal C}$ becomes a new $U$-component, which we denote by
$\bar{B_{i}}$. We define the direct benefit $\beta^{\prime}(B_{i})$ from
$B_{i}$ to be the decrease in vertex-weight of the endpoints $v_{i}$ and
$u_{i+1}$ of $B_{i}$ minus the component-weight $c(\bar{B_{i}})$ in the new
instance after the circuit procedure. Immediately after the procedure, the
measure $\mu$ decreases by
$w(H)+c(H)-\sum_{i}(w(\bar{B_{i}})+c(\bar{B_{i}}))=c(H)+\sum_{i}\beta^{\prime}(B_{i})$.
After the circuit procedure, we see that the vertex-weights of endpoints of
each non-reducible and nontrivial block $B_{i}$ decreases by $\Delta_{3}$ and
$\Delta_{3}$ (or $w_{3}$ and $w_{3}$) respectively if $B_{i}$ is even, and by
$\Delta_{3}$ and $w_{3}$ (or $w_{3}$ and $\Delta_{3}$) respectively if $B_{i}$
is odd. Summarizing these, the direct benefit $\beta^{\prime}(B)$ from a block
$B$ is given by

$\beta^{\prime}(B)=\left\\{\begin{array}[]{cl}0&\mbox{if $B$ is reducible},\\\
w_{3^{\prime}}&\mbox{if $B$ is trivial},\\\
w_{3}\\!+\\!\Delta_{3}\\!-\\!\delta&\mbox{if $B$ is odd and nontrivial},\\\
\mbox{$2w_{3}-\delta$}&\mbox{if $B$ is even and non-reducible, and
$\mathrm{cut}_{U}(B)$ is deleted},\\\ \mbox{$2\Delta_{3}-\gamma$}&\mbox{if $B$
is $2$-pendent critical, and $\mathrm{cut}_{U}(B)$ is included in $F$},\\\
\mbox{$w(B)$}&\mbox{if $B$ is a $2$-pendent 4-cycle, and $\mathrm{cut}_{U}(B)$
is included in $F$},\\\ \mbox{$2\Delta_{3}-\delta$}&\mbox{otherwise (i.e., $B$
is even, non-reducible but not }\\\ &\mbox{~{} a $2$-pendent critical
$U$-graph or a $2$-pendent 4-cycle,}\\\ &\mbox{~{} and $\mathrm{cut}_{U}(B)$
is included to $F$).}\\\ \end{array}\right.$ (7)

By (6), we have that $\beta^{\prime}(B_{i})\geq 0$ for any type of block
$B_{i}$, which implies that the decrease
$c(H)+\sum_{i}\beta^{\prime}(B_{i})\geq c(H)\geq 0$ (where $H$ is not a
4-cycle) is in fact nonnegative, i.e., the measure $\mu$ never increases by
processing a circuit.

After processing a circuit ${\cal C}$, a reduction operation may be applicable
to some $U$-components $\bar{B}_{i}$ and we can decrease $\mu$ more by
reducing them. The _indirect benefit_ $\beta^{\prime\prime}(B)$ from a block
$B$ is defined as the amount of $\mu$ decreased by applying reduction rules on
the $U$-component $\bar{B}$ after processing the circuit. Since we have shown
that $\mu$ never increases by applying reduction rules, we know that
$\beta^{\prime\prime}(B)$ is always nonnegative. The _total benefit_
(_benefit_ , for short) from a block $B$ is

$\beta(B)=\beta^{\prime}(B)+\beta^{\prime\prime}(B).$

###### Lemma 10

After processing a circuit ${\cal C}$ in a $2$-edge-connected $U$-component
$H$ $($not necessary being reduced$)$ and applying reduction rules until the
instance becomes a reduced one, the measure $\mu$ decreases by

$c(H)+\sum_{i}\beta(B_{i}),$

where $B_{i}$ are the blocks along circuit ${\cal C}$.

The indirect benefit from a block depends on the structure of the block. In
our algorithm, we hope that the indirect benefit is as large as possible. Here
we prove some lower bounds on it for some special cases.

###### Lemma 11

Let $H$ be a $U$-component containing no induced triangle and ${\cal
C}^{\prime}$ be a reducible circuit in it such that there is exactly one
reducible block along ${\cal C}^{\prime}$. The measure $\mu$ decreases by at
least $2\Delta_{3}$ by processing the reducible circuit ${\cal C}^{\prime}$
and applying reduction rules.

_Proof._ By assumption, the reducible circuit has at least two blocks, one
reducible block $B_{1}$ and one non-reducible block $B_{2}$. (1) Assume that
every other block than $B_{1}$ along ${\cal C}^{\prime}$ is trivial. Then $H$
should be a cycle of length $k\geq 5$ (if $H$ is a 4-cycle, then there are
three odd blocks along ${\cal C}^{\prime}$ and we find the instance infeasible
by Lemma 3). There are $k-1\geq 4$ trivial blocks along ${\cal C}^{\prime}$.
After processing the circuit, the whole component $H$ will be eliminated
decreasing $\mu$ by at least $c(H)+w(H)\geq\delta+4w_{3^{\prime}}\geq
2\Delta_{3}$ (by (6)). (2) Otherwise, i.e., there is a block $B_{2}$ of more
than one vertex ($B_{2}$ is not trivial or reducible): (2-i)
$\mathrm{cut}_{U}(B_{2})$ is deleted in the circuit procedure: Then $\mu$
decreases by at least
$c(H)+\beta^{\prime}(B_{2})=\delta+(2w_{3}-\delta)=2w_{3}\geq 2\Delta_{3}$ by
(7). Hence assume that $\mathrm{cut}_{U}(B_{2})$ is included to $F$ in (2).
(2-ii) $B_{2}$ is not 2-pendent critical: Then the measure $\mu$ decreases by
at least $c(H)+\beta^{\prime}(B_{2})=\delta+(2\Delta_{3}-\delta)=2\Delta_{3}$.
The remaining case is that $B_{2}$ is 2-pendent critical and
$\mathrm{cut}_{U}(B_{2})$ is included to $F$. (2-iii) there are only two
blocks $B_{1}$ and $B_{2}$ along ${\cal C}^{\prime}$: By processing the
circuit ${\cal C}^{\prime}$, the two edges in
$\\{xz,yz\\}=\mathrm{cut}_{U}(B_{2})$ become forced edges. Since they are
incident on the single vertex $z$ in $B_{1}$, we can replace $xz$ and $yz$
with a single forced edge $xy$ and then $B_{2}$ becomes a 0-pendent 6-cycle or
extension of a 6-cycle with only one forced chord $xy$. After the circuit
procedure of ${\cal C}^{\prime}$, we can apply 4-cut reduction to the
0-pendent 6-cycle $B_{2}$ (by Lemma 6) and then this decreases $\mu$ by
$c(H)+\beta(B_{2})=\delta+w(B_{2})>2\Delta_{3}$ (by Lemma 9(ii)). (2-iv) there
is a pair of two trivial blocks $B_{3}$ and $B_{4}$ or a nontrivial and non-
reducible block $B_{5}$ along ${\cal C}^{\prime}$: Now we can decrease $\mu$
by at least $c(H)+\beta(B_{2})+\sum_{i\neq
2}\beta(B_{i})\geq\delta+(2\Delta_{3}-\gamma)+\min\\{2w_{3^{\prime}},(2\Delta_{3}-\delta)\\}\geq
2\Delta_{3}$ (by (6)).

In any case, the measure $\mu$ decreases by at least $2\Delta_{3}$.

###### Lemma 12

In the circuit procedure for a circuit ${\cal C}$ in a reduced instance, the
indirect benefit from a block $B$ along ${\cal C}$ satisfies

$\beta^{\prime\prime}(B)\geq\left\\{\begin{array}[]{clc}2\Delta_{3}&\mbox{if
$B$ is odd and nontrivial},&{\rm(i)}\\\ w(B)-\beta^{\prime}(B)&\mbox{if $B$ is
a $2$-pendent cycle or critical graph},&\\\ &\mbox{~{}~{}and
$\mathrm{cut}_{U}(B)$ is deleted},&{\rm(ii)}\\\ \delta&\mbox{if $B$ is even
but not reducible or a $2$-pendent}&\\\ &\mbox{~{}~{} cycle, and
$\mathrm{cut}_{U}(B)$ is deleted},&{\rm(iii)}\\\
0&\mbox{otherwise}.&{\rm(iv)}\\\ \end{array}\right.$

_Proof._ We will use $\bar{B}$ to denote the $U$-component resulting from $B$
after the circuit procession. Case (i): Since $B$ is odd, only one edge in
$\mathrm{cut}_{U}(B)$ is deleted (the other one is included to $F$) in the
circuit procession. Then there is exactly one vertex of degree 2 in $\bar{B}$,
which is the only reducible block along a circuit ${\cal C}^{\prime}$ in
$\bar{B}$. Since the original instance is reduced and contains no triangle, we
know that circuit ${\cal C}^{\prime}$ satisfies the condition in Lemma 11. By
processing ${\cal C}^{\prime}$ in $\bar{B}$, we can decrease $\mu$ by at least
$2\Delta_{3}$ by Lemma 11. Then we get $\beta^{\prime\prime}(B)\geq
2\Delta_{3}$. For case (ii), if $B$ is a $2$-pendent cycle, we can reduce the
whole $U$-component $\bar{B}$ after the circuit procedure, and then we have
$\beta^{\prime\prime}(B)=c(\bar{B})+w(\bar{B})$. Otherwise $B$ in (ii) is a
$2$-pendent critical graph and the 4-cut reduction can be applied to $\bar{B}$
by Lemma 6 since the two end vertices of edges in $\mathrm{cut}_{U}(B)$ will
be of degree 2 in $\bar{B}$ after $\mathrm{cut}_{U}(B)$ is deleted. Then we
still have $\beta^{\prime\prime}(B)=c(\bar{B})+w(\bar{B})$ by Lemma 9(ii).
Note that $\beta^{\prime}(B)=w(B)-w(\bar{B})-c(\bar{B})$ (by the definition of
$\beta^{\prime}(B)$). We get $\beta^{\prime\prime}(B)=w(B)-\beta^{\prime}(B)$.
For Case (iii), we will get at least one reducible circuit ${\cal C}^{\prime}$
in $\bar{B}$. Note that $\bar{B}$ has some vertex of degree 2 and cannot be a
critical graph. Hence $c(\bar{B})=\delta$. By processing the reducible circuit
${\cal C}^{\prime}$, we can decrease $\mu$ by at least
$c(\bar{B})+\sum_{i}\beta(B^{\prime}_{i})\geq c(\bar{B})=\delta$, where
$B^{\prime}_{i}$ are the blocks along ${\cal C}^{\prime}$. The inequality in
(iv) holds since we have proved that $\mu$ will never increase after applying
reduction rules.

##  9 The Analysis

Now we are ready to analyze our algorithm. In the algorithm, branching on a
circuit generates two instances $(G_{1},F_{1})$ and $(G_{2},F_{2})$. By Lemma
10, we get branch vector

$(c(H)+\sum_{i}\beta_{1}(B_{i});c(H)+\sum_{i}\beta_{2}(B_{i})),$

where $\beta_{j}(B)$, $\beta^{\prime}_{j}(B)$ and
$\beta^{\prime\prime}_{j}(B)$ denote the functions $\beta(B)$,
$\beta^{\prime}(B)$ and $\beta^{\prime\prime}(B)$ evaluated in
$(G_{j},F_{j})$, $j=1,2$ for clarifying how branch vectors are derived in the
subsequent analysis. We consider this branch vector for different cases. First
we analyze the easy case where the chosen circuit ${\cal C}$ has no normal
block. Then we analyze the somewhat complicated case where there is a minimal
normal block along ${\cal C}$.

###  9.1 Circuits with only trivial and $2$-pendent critical blocks

In this subsection, we assume that the chosen circuit ${\cal C}$ in a
$U$-component $H$ (not a 4-cycle) has only trivial and $2$-pendent critical
blocks. We consider the following three cases.

Case 1. All blocks along ${\cal C}$ are trivial blocks: Now $H$ should be a
cycle of even length $l\geq 6$. By (7) and Lemma 10, we know that in each
branch we can decrease $\mu$ by at least

$c(H)+\sum_{i}\beta(B_{i})\geq\left\\{\begin{array}[]{cl}\gamma+6w_{3^{\prime}}&\mbox{if
$l=6$ }\\\ \delta+8w_{3^{\prime}}&\mbox{if $l\geq 8$.}\end{array}\right.$

Then we get branch vectors

$\displaystyle[6w_{3^{\prime}}+\gamma]_{2}$ (8)

for $l=6$ and $[8w_{3^{\prime}}+\delta]_{2}$ for $l\geq 8$, which is covered
by (8). Note that (8) is tight for a circuit of 6-cycle in Fig. 2(a).

Case 2. There is only one 2-pendent critical block $B_{1}$ along ${\cal C}$:
Since $B_{1}$ is even, the number $r>0$ of trivial blocks (odd blocks) along
${\cal C}$ is also even by the parity condition. Note that if $r=2$ and
$B_{1}$ is 2-pendent 6-cycle then $H$ is a critical graph (an extension of a
6-cycle) and $c(H)=\gamma$. Otherwise $H$ is not critical and $c(H)=\delta$.
Then in the branch where $\mathrm{cut}_{U}(B_{1})$ is deleted, the decrease
$c(H)+\sum_{i}\beta(B_{i})$ of $\mu$ is at least
$c(H)+w(B_{2})+rw_{3^{\prime}}\geq\min\\{\gamma+(2w_{3}+4w_{3^{\prime}})+2w_{3^{\prime}},\delta+(4w_{3}+4w_{3^{\prime}})+2w_{3^{\prime}},\delta+(2w_{3}+4w_{3^{\prime}})+4w_{3^{\prime}}\\}=$

$\gamma+2w_{3}+6w_{3^{\prime}}.$

In the branch where $\mathrm{cut}_{U}(B_{1})$ is included to $F$, the decrease
$c(H)+\sum_{i}\beta(B_{i})$ of $\mu$ is at least

$\min\\{\gamma,\delta\\}+(2\Delta_{3}-\gamma)+2w_{3^{\prime}}=\delta+2w_{3}-\gamma.$

This gives branch vector

$\displaystyle(\gamma+2w_{3}+6w_{3^{\prime}};\delta+2w_{3}-\gamma).$ (9)

Case 3. There are at least two 2-pendent critical blocks $B_{1}$ and $B_{2}$
along ${\cal C}$: If $\mathrm{cut}_{U}(B_{2})$ is included to $F$ in the
branch where $\mathrm{cut}_{U}(B_{1})$ is deleted, then we can get branch
vector
$[c(H)+\beta(B_{1})+\beta(B_{2})]_{2}=[\delta+(2w_{3}+4w_{3^{\prime}})+(2\Delta_{3}-\gamma)]_{2}=[\delta+4w_{3}+2w_{3^{\prime}}-\gamma]_{2}$,
which is covered by (8). On the other hand, if $\mathrm{cut}_{U}(B_{2})$ is
also deleted in the branch where $\mathrm{cut}_{U}(B_{1})$ is deleted, we get
branch vector

$\displaystyle(\delta+2(2\Delta_{3}-\gamma);\delta+2(2w_{3}+4w_{3^{\prime}})).$
(10)

###  9.2 Circuits with a minimal normal block

In this subsection, we assume that the chosen circuit ${\cal C}$ in a
$U$-component $H$ has a minimal normal block $B_{1}$. Now $c(H)=\delta$ always
holds. We distinguish several cases to analyze the branch vectors.

Case 1. Block $B_{1}$ is odd: Circuit ${\cal C}$ has another odd block
$B_{2}$. By (7) we have
$\beta(B_{2})\geq\beta^{\prime}(B_{2})=\min\\{w_{3^{\prime}},w_{3}\\!+\\!\Delta_{3}\\!-\\!\delta\\}=w_{3^{\prime}}$
in each branch. For $B_{1}$, we have that
$\beta^{\prime}(B_{1})=w_{3}+\Delta_{3}-\delta$ and
$\beta^{\prime\prime}(B_{1})\geq 2\Delta_{3}$ by Lemma 12. In each branch,
$\mu$ decreases by at least
$c(H)+\sum_{i}\beta(B_{i})\geq\delta+\beta^{\prime}(B_{1})+\beta^{\prime\prime}(B_{1})+\beta(B_{2})\geq\delta+(w_{3}+\Delta_{3}-\delta)+2\Delta_{3}+w_{3^{\prime}}=4w_{3}-2w_{3^{\prime}}$.
Therefore, we can get branch vector

$\displaystyle[4w_{3}-2w_{3^{\prime}}]_{2}.$ (11)

Note that (11) is tight for a circuit of chain of length 2 in Fig. 2(b).

Next, we assume that $B_{1}$ is even. In the branch where
$\mathrm{cut}_{U}(B_{1})$ is included to $F$, we have that
$\beta^{\prime}_{1}(B_{1})=2\Delta_{3}-\delta$. In the other branch, we have
that $\beta^{\prime}_{2}(B_{1})=2w_{3}-\delta$. By branching on ${\cal C}$, we
get branch vector

$(\delta+\beta^{\prime}_{1}(B_{1})+\beta^{\prime\prime}_{1}(B_{1})+\xi_{1};\delta+\beta^{\prime}_{2}(B_{1})+\beta^{\prime\prime}_{2}(B_{1})+\xi_{2}),$

where $\xi_{j}=\sum_{i\neq 1}\beta_{j}(B_{i})\geq 0$ ($j\in\\{1,2\\}$),
$\beta^{\prime}_{1}(B_{1})=2\Delta_{3}-\delta$ and
$\beta^{\prime}_{2}(B_{1})=2w_{3}-\delta$. We here evaluate $\xi_{1}$ and
$\xi_{2}$. If all blocks other than $B_{1}$ along ${\cal C}$ are 2-pendent
critical, then we have that $\xi_{1}\geq 2\Delta_{3}-\gamma$ and
$\xi_{2}=\sum_{i\neq 1}w(B_{i})\geq w(B_{2})\geq 2w_{3}+4w_{3^{\prime}}$.
Otherwise,
$\xi_{1}\geq\min\\{2w_{3^{\prime}},w_{3}+\Delta_{3}-\delta,2\Delta_{3}-\delta\\}=2w_{3^{\prime}}$
and
$\xi_{2}\geq\min\\{2w_{3^{\prime}},w_{3}+\Delta_{3}-\delta,2w_{3}-\delta\\}=2w_{3^{\prime}}$.
We have the following two choices for $(\xi_{1},\xi_{2})$:

$\displaystyle(\xi_{1},\xi_{2})=(2\Delta_{3}-\gamma,2w_{3}+4w_{3^{\prime}})\ \
\ {\rm and}\ \ \ (2w_{3^{\prime}},2w_{3^{\prime}}).$ (12)

In what follows, we derive some lower bounds on
$\beta^{\prime\prime}_{1}(B_{1})$ and $\beta^{\prime\prime}_{2}(B_{1})$ by
examining the structure of $B_{1}$.

Let $\mathrm{cut}_{U}(B_{1})=\\{xv,yu\\}$, where $x$ and $y$ are in $B_{1}$.
Let $(G_{1},F_{1})$ and $(G_{2},F_{2})$ be the two resulting instances after
branching and processing the circuit ${\cal C}$, where $(G_{1},F_{1})$
corresponds to the branch where $\mathrm{cut}_{U}(B_{1})$ is included to $F$
and $(G_{2},F_{2})$ corresponds to the branch where $\mathrm{cut}_{U}(B_{1})$
is deleted. Let $x_{1}x$ and $x_{2}x$ (resp., $y_{1}y$ and $y_{2}y$) be the
two unforced edges incident on $x$ (resp., $y$) in $(G_{1},F_{1})$. Note that
$x_{1}x$ and $x_{2}x$ (resp., $y_{1}y$ and $y_{2}y$) will be in the same
circuit ${\cal C}_{x}$ (resp., ${\cal C}_{y}$) in $(G_{1},F_{1})$, since $x$
(resp., $y$) is a forced vertex now. See Fig. 4 for illustrations of the
structure of the edges incident to $x$ and $y$.

Figure 4: Illustrations of block $B_{1}$: (a) ${\cal C}_{x}\neq{\cal C}_{y}$;
(b) ${\cal C}_{x}={\cal C}_{y}$ and $x$ and $y$ are adjacent; (c) ${\cal
C}_{x}={\cal C}_{y}$ and $x$ and $y$ are not adjacent.

Case 2. Block $B_{1}$ is even and ${\cal C}_{x}$ and ${\cal C}_{y}$ are two
different circuits in $(G_{1},F_{1})$ (see Fig. 4(a)): Now ${\cal C}_{x}$ and
${\cal C}_{y}$ are two different circuits also in $(G_{2},F_{2})$. In the
branch where $\mathrm{cut}_{U}(B_{1})$ is deleted, we have
$\beta^{\prime\prime}_{2}(B_{1})\geq 4\Delta_{3}$ (by applying Lemma 11 to
${\cal C}_{x}$ and ${\cal C}_{y}$). Next we consider the other blocks along
${\cal C}$.

Case 2.1. There are at least two odd blocks $B_{2}$ and $B_{3}$ along ${\cal
C}$: By (7), $\beta_{1}(B_{i})\geq w_{3^{\prime}}$ and $\beta_{2}(B_{i})\geq
w_{3^{\prime}}$ ($i\in\\{2,3\\}$). Since
$c(H)+\sum_{i}\beta(B_{i})\geq\delta+\beta(B_{1})+\beta(B_{2})+\beta(B_{3})$,
we get branch vector

$\displaystyle(\delta+(2\Delta_{3}-\delta)+2w_{3^{\prime}};\delta+(2w_{3}-\delta)+4\Delta_{3}+2w_{3^{\prime}})=(2w_{3};6w_{3}-2w_{3^{\prime}}).$
(13)

Case 2.2. There is no odd block along ${\cal C}$: Let $B_{2}$ be the block
along ${\cal C}$ containing vertex $v$. Then $B_{2}$ is an even block such
that $\mathrm{cut}_{U}(B_{2})$ is also included to $F$ in the branch where
$\mathrm{cut}_{U}(B_{1})$ is included to $F$. Then
$c(H)+\sum_{i}\beta(B_{i})\geq\delta+\beta(B_{1})+\beta(B_{2})$. If $B_{2}$ is
not a 2-pendent critical block, then
$\beta^{\prime}_{1}(B_{2})=2\Delta_{3}-\delta$,
$\beta^{\prime}_{2}(B_{2})=2w_{3}-\delta$ and
$\beta^{\prime\prime}_{2}(B_{2})\geq\delta$ (by Lemma 12), and we get branch
vector

$\displaystyle(\delta+2(2\Delta_{3}-\delta);\delta+(2w_{3}-\delta)+4\Delta_{3}+2w_{3})=(4\Delta_{3}-\delta;4w_{3}+4\Delta_{3}).$
(14)

Otherwise $B_{2}$ is a 2-pendent critical block. Then
$\beta^{\prime}_{1}(B_{2})=2\Delta_{3}-\gamma$ and
$\beta_{2}(B_{2})=\beta^{\prime}_{2}(B_{2})+\beta^{\prime\prime}_{2}(B_{2})=w(B_{2})\geq
2w_{3}+4w_{3^{\prime}}$ (by (7) and Lemma 12). We get branch vector
$(\delta+(2\Delta_{3}-\delta)+(2\Delta_{3}-\gamma);\delta+(2w_{3}-\delta)+4\Delta_{3}+(2w_{3}+4w_{3^{\prime}}))$,
i.e.,

$\displaystyle(4\Delta_{3}-\gamma;8w_{3}).$ (15)

Case 3. Block $B_{1}$ is even and ${\cal C}_{x}={\cal C}_{y}$ in
$(G_{1},F_{1})$ (see Fig. 4(b),(c)): First of all, we consider
$\beta^{\prime\prime}_{1}(B_{1})$, $\beta^{\prime\prime}_{2}(B_{1})$ and
others. We look at the circuit ${\cal C}_{x}$ in $(G_{1},F_{1})$. Except
blocks $\\{x\\}$ and $\\{y\\}$, there are some other blocks along ${\cal
C}_{x}$. Note that each block $B^{\prime}$ along ${\cal C}_{x}$ should be a
trivial or 2-pendent critical block since $B_{1}$ is a minimal normal block.
We distinguish three cases by considering the number of critical blocks along
${\cal C}_{x}$.

Case 3.1. $B_{1}$ is a 2-pendent cycle of length $\ell$ (all blocks along
${\cal C}_{x}$ are trivial in $(G_{1},F_{1})$): Then $\ell$ is an even integer
with $\ell=4$ or $\ell\geq 8$ (since $B_{1}$ is even and non-critical). When
$\ell=4$, in both branches, we have
$\beta(B_{1})=w(B_{1})=2w_{3}+2w_{3^{\prime}}$. Then we can branch with a
branch vector $[c(H)+\beta(B_{1})]_{2}=[\delta+2w_{3}+2w_{3^{\prime}}]_{2}$
covered by (8). Next we assume that $\ell\geq 8$. Now we may get only
$\beta^{\prime}_{1}(B_{1})=2\Delta_{3}-\delta$ and
$\beta^{\prime\prime}_{1}(B_{1})\geq 0$ instead of
$\beta_{1}(B_{1})=w(B_{1})$. But it holds that
$\beta_{2}(B_{1})=w(B_{1})=2w_{3}+(\ell-2)w_{3^{\prime}}\geq
2w_{3}+6w_{3^{\prime}}$. We get branch vector

$\displaystyle(\delta+(2\Delta_{3}-\delta)+\xi_{1};\delta+(2w_{3}+6w_{3^{\prime}})+\xi_{2}).$
(16)

Case 3.2. There are only three blocks $\\{x\\}$, $\\{y\\}$ and $B^{\prime}$
along ${\cal C}_{x}$ in $(G_{1},F_{1})$, where $B^{\prime}$ is a 2-pendent
critical block: Now $x$ and $y$ are adjacent (see Fig. 4(b)). We assume that
$x_{2}=y$, $y_{2}=x$, and $x_{1},y_{1}\in B_{1}$. We look at $(G_{2},F_{2})$
wherein $x$ and $y$ are degree-2 vertices. After including edges $xy$,
$xx_{1}$ and $yy_{1}$ to $F$, $B^{\prime}$ becomes a $4$-cut reducible graph
by Lemma 6. Then $\mu$ decreases by $w(B^{\prime})$ after applying the 4-cut
reduction. Then we know that
$\beta_{2}(B_{1})=w(B_{1})=w(x)+w(y)+w(B^{\prime})\geq
4w_{3}+4w_{3^{\prime}}$. Therefore, we get branch vector

$(\delta+(2\Delta_{3}-\delta)+\xi_{1};\delta+(4w_{3}+4w_{3^{\prime}})+\xi_{2}),$

which is covered by (16).

Case 3.3. $B_{1}$ is not a 2-pendent cycle and there are more than three
blocks along ${\cal C}_{x}$ in $(G_{1},F_{1})$: Then there is a nontrivial and
nonreducible block $B^{\prime}_{1}$ along ${\cal C}_{x}$ in $(G_{1},F_{1})$,
where $B^{\prime}_{1}$ is a 2-pendent critical block since $B_{1}$ is a
minimal normal block. For this case, we only get the following branch vector
by branching on ${\cal C}$:
$(\delta+(2\Delta_{3}-\delta)+\xi_{1};\delta+(2w_{3}-\delta)+\beta^{\prime\prime}_{2}(B_{1})+\xi_{2})=$

$\displaystyle(2\Delta_{3}+\xi_{1};2w_{3}+\beta^{\prime\prime}_{2}(B_{1})+\xi_{2}).$
(17)

In fact, the branch vector (17) in Case 3.3 can be the bottleneck in the
analysis of our algorithm. However, in $(G_{1},F_{1})$, circuit ${\cal C}_{x}$
is a circuit with only trivial and 2-pendent critical blocks. In our
algorithm, circuit ${\cal C}_{x}$ will be one of the circuits for the next
branching, and it will never be destroyed until we branch on it. In fact,
branching on ${\cal C}_{x}$ proves a branch vector better than (17). For the
purpose of analysis, we derive a branch vector for the three branches, i.e.,
the branching on ${\cal C}$ followed by the branching on ${\cal C}_{x}$ in
$(G_{1},F_{1})$ in the branch of including $\mathrm{cut}_{U}(B_{1})$ into $F$.

In Case 3.3, we see that: either ($a$) ${\cal C}_{x}$ has at least two trivial
blocks $B^{\prime}_{2}$ and $B^{\prime}_{3}$ different from $\\{x\\}$ and
$\\{y\\}$ (since the number of odd blocks is even); or ($b$) all blocks other
than $\\{x\\}$ and $\\{y\\}$ are 2-pendent critical.

Case ($a$): There is also a 2-pendent critical block $B^{\prime}_{1}$ along
${\cal C}_{x}$ (since $B_{1}$ is not a 2-pendent cycle). In $(G_{2},F_{2})$,
we can see that $\beta^{\prime\prime}_{2}(B_{1})\geq
c(B_{1})+w(B^{\prime}_{2})+w(B^{\prime}_{3})=\delta+2w_{3^{\prime}}$ (since
$B^{\prime}_{2}$ and $B^{\prime}_{3}$ are trivial blocks). In $(G_{1},F_{1})$,
by branching on ${\cal C}_{x}$, we can get branch vector
$(c(B_{1})+\beta_{1}(\\{x\\})+\beta_{1}(\\{y\\})+\sum_{i=1}^{3}\beta_{1}(B^{\prime}_{i});c(B_{1})+\beta_{2}(\\{x\\})+\beta_{2}(\\{y\\})+\sum_{i=1}^{3}\beta_{2}(B^{\prime}_{i}))=(\delta+4w_{3^{\prime}}+(2\Delta_{3}-\gamma);\delta+4w_{3^{\prime}}+(2w_{3}+4w_{3^{\prime}}))=$

$(\delta+2w_{3}+2w_{3^{\prime}}-\gamma;\delta+2w_{3}+8w_{3^{\prime}}).$

By combining it with (17) and taking
$\beta^{\prime\prime}_{2}(B_{1})=\delta+2w_{3^{\prime}}$, we get branch vector

$\displaystyle(2\Delta_{3}\\!+\\!\xi_{1}\\!\\!+\\!(\delta\\!+\\!2w_{3}\\!+\\!2w_{3^{\prime}}\\!-\\!\gamma);2\Delta_{3}\\!+\\!\xi_{1}\\!\\!+\\!(\delta\\!+\\!2w_{3}\\!+\\!8w_{3^{\prime}}\\!);2w_{3}\\!+\\!\delta\\!+\\!2w_{3^{\prime}}\\!+\\!\xi_{2}).~{}~{}~{}~{}$
(18)

Case ($b$): There are at least two 2-pendent critical blocks $B^{\prime}_{1}$
and $B^{\prime}_{2}$ along ${\cal C}_{x}$ (since there are at least four
blocks among ${\cal C}_{x}$). In $(G_{2},F_{2})$, we may get only
$\beta^{\prime\prime}_{2}(B_{1})\geq\delta$. In $(G_{1},F_{1})$, by branching
on ${\cal C}_{x}$, at least we can get branch vector

$(\delta+2w_{3^{\prime}}+2(2\Delta_{3}-\gamma);\delta+2w_{3^{\prime}}+2(2w_{3}+4w_{3^{\prime}}).$

By combining it with (17) and taking $\beta^{\prime\prime}_{2}(B_{1})=\delta$,
we get branch vector

$\displaystyle(2\Delta_{3}\\!+\\!\xi_{1}\\!+\\!(\delta\\!+\\!4w_{3}\\!-\\!2w_{3^{\prime}}\\!-\\!2\gamma);2\Delta_{3}\\!+\\!\xi_{1}\\!+\\!(\delta\\!+\\!4w_{3}\\!+\\!10w_{3^{\prime}});2w_{3}\\!+\\!\delta\\!+\\!\xi_{2}).$
(19)

Finally, by replacing $\xi_{1}$ and $\xi_{2}$ in (16), (18) and (19)
respectively with the bounds in (12), we get the following six branch vectors

$\displaystyle(4\Delta_{3}-\gamma;\delta+4w_{3}+10w_{3^{\prime}}),$ (20)
$\displaystyle(2w_{3};\delta+2w_{3}+8w_{3^{\prime}}),$ (21)
$\displaystyle(\delta+6w_{3}-2w_{3^{\prime}}-2\gamma;\delta+6w_{3}+4w_{3^{\prime}}-\gamma;\delta+4w_{3}+6w_{3^{\prime}}),$
(22)
$\displaystyle(\delta+4w_{3}+2w_{3^{\prime}}-\gamma;\delta+4w_{3}+8w_{3^{\prime}};\delta+2w_{3}+4w_{3^{\prime}}),$
(23)
$\displaystyle(\delta+8w_{3}-6w_{3^{\prime}}-3\gamma;\delta+8w_{3}+6w_{3^{\prime}}-\gamma;\delta+4w_{3}+4w_{3^{\prime}}),$
(24)

and

$\displaystyle(\delta+6w_{3}-2w_{3^{\prime}}-2\gamma;\delta+6w_{3}+10w_{3^{\prime}};\delta+2w_{3}+3w_{3^{\prime}}).$
(25)

###  9.3 Overall analysis

A quasiconvex program is obtained from (6) and 13 branch vectors (from (8) to
(15) and from (20) to (25)) in our analysis. There is a general method to
solve quasiconvex programs [4]. For our quasiconvex program, we observe a
simple way to solve it. We look at (8) and (11). Note that
$\min\\{6w_{3^{\prime}}+\gamma,4w_{3}-2w_{3^{\prime}}\\}$ under the constraint
$2\Delta_{3}\geq\gamma$ gets the maximum value at the time when
$6w_{3^{\prime}}+\gamma=4w_{3}-2w_{3^{\prime}}$ and $2\Delta_{3}=\gamma$. We
get $w_{3^{\prime}}={1\over 3}$ and $\gamma={4\over 3}$. With this setting, we
can verify that when $\delta\in[1.2584,1.2832]$, all branch vectors other than
(8) and (11) in our quasiconvex program will not be the bottleneck. We get a
time bound $O^{*}(\alpha^{\mu})$ with $\alpha=2^{3\over 10}<1.2312$ by setting
$w_{3^{\prime}}={1\over 3}$,$\gamma={4\over 3}$ and $\delta\in[1.2584,1.2832]$
for our problem. The bottlenecks in the analysis are (8), (11) and
$2\Delta_{3}\geq\gamma$ in (6).

###### Theorem 9.1

TSP in an $n$-vertex graph $G$ with maximum degree 3 can be solved in
$O^{*}(1.2312^{n})$ time and polynomial space.

##  10 Concluding Remarks

In this paper, we have presented an improved exact algorithm for TSP in
degree-3 graphs. The basic operation in the algorithm is to process the edges
in a circuit by either including an edge in the circuit to the solution or
excluding it from the solution. The algorithm is analyzed by using the measure
and conquer method and an amortization scheme over the cut-circuit structure
of graphs, wherein we introduce not only weights of vertices but also weights
of $U$-components to define the measure of an instance.

The idea of amortization schemes introducing weights on components may yield
better bounds for other exact algorithms for graph problems if how
reduction/branching procedures change the system of components is successfully
analyzed.

## References

  * [1] Bjorklund, A.:  Determinant sums for undirected Hamiltonicity.  In: Proc. 51st Annual IEEE Symp. on Foundations of Computer Science (2010) 173-182
  * [2] Bjorklund, A., Husfeldt, T., Kasaki, P. and Koivisto, M.:  The travelling salesman problem in bounded degree graphs.  In: ICALP 2008, LNCS 5125 (2008) 198-209
  * [3] Dorn, F., Penninkx, E., Bodlaender, H. L., and Fomin, F. V.:  Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions.  Algorithmica 58(3) (2010) 790-810
  * [4] Eppstein, D.: Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms. ACM Trans. on Algorithms 2(4) (2006) 492-509
  * [5] Eppstein, D.:  The traveling salesman problem for cubic graphs.  J. Graph Algorithms and Applications 11(1) (2007) 61-81
  * [6] Fomin, F., Grandoni, F., Kratsch, D. Measure and Conquer: Domination - A Case Study, ICALP Springer-Verlag LNCS 3580 (2005), pp. 191–203.
  * [7] Fomin, F. V., Kratsch, D.: Exact Exponential Algorithms, Springer (2010)
  * [8] Gebauer, H.:  Finding and enumerating Hamilton cycles in 4-regular graphs.  Theoretical Computer Science 412(35) (2011) 4579-4591
  * [9] Iwama, K. and Nakashima, T.:  An improved exact algorithm for cubic graph TSP.  In: COCOON 2007. LNCS 4598 (2007) 108-117
  * [10] Nagamochi, H., Ibaraki, T.: A linear time algorithm for computing 3-edge-connected components in multigraphs, J. of Japan Society for Industrial and Applied Mathematics, 9(2) (1992) 163-180
  * [11] Nagamochi, H., Ibaraki, T.: Algorithmic Aspects of Graph Connectivities, Encyclopedia of Mathematics and Its Applications, Cambridge University Press (2008)
  * [12] Woeginger, G. J.:  Exact algorithms for NP-hard problems: A survey.  In: Combinatorial Optimization. LNCS 2570 (2003) 185-207
  * [13] Xiao, M. and Nagamochi, H.:  An improved exact algorithm for TSP in degree-$4$ graphs.  In: COCOON 2012. LNCS 7434 (2012) 74-85