SIAM J. DISCRETE MATH.
Vol. 27, No. 2, pp. 918–939

c 2013 Society for Industrial and Applied Mathematics


FINDING 2-FACTORS CLOSER TO TSP TOURS IN CUBIC GRAPHS∗SYLVIA BOYD† , SATORU IWATA‡ , AND KENJIRO TAKAZAWA§
Abstract. In this paper we are interested in algorithms for finding 2-factors that cover certain
prescribed edge-cuts in bridgeless cubic graphs. Since a Hamilton cycle is a 2-factor covering alledge-cuts, imposing the constraint of covering those edge-cuts makes the obtained 2-factor closer toa Hamilton cycle. We present an algorithm for finding a minimum-weight 2-factor covering all the 3edge cuts in weighted bridgeless cubic graphs, together with a polyhedral description of such 2-factors
and that of perfect matchings intersecting all the 3-edge cuts in exactly one edge. We further give analgorithm for finding a 2-factor covering all the 3- and 4-edge cuts in bridgeless cubic graphs. Bothof these algorithms run in O(n3 ) time, where n is the number of vertices. As an application of thelatter algorithm, we design a 6/5-approximation algorithm for finding a minimum 2-edge-connectedspanning subgraph in 3-edge-connected cubic graphs, which improves upon the previous best ratioof 5/4. The algorithm begins with finding a 2-factor covering all 3- and 4-edge cuts, which is thebottleneck in terms of complexity, and thus it has running time O(n3 ). We then improve this timecomplexity to O(n2 log4 n) by relaxing the condition of the initial 2-factor and elaborating on thesubsequent processes.
Key words. bridgeless cubic graphs, minimum-weight 2-factor covering 3-edge cuts, polyhedral
description of 2-factors covering 3-edge cuts, 2-factor covering 3- and 4-edge cuts, minimum 2-edgeconnected spanning subgraphs
AMS subject classifications. 05C85, 05C70
DOI. 10.1137/110843514

1. Introduction. The classical theorem of Petersen [27] shows that any bridgeless cubic graph has a 2-factor. The aim of this paper is to provide algorithms forﬁnding 2-factors that cover certain prescribed edge-cuts in bridgeless cubic graphsand demonstrate their usefulness for developing approximation algorithms for related
NP-hard problems for such graphs. In section 3 we present a polyhedral descriptionof 2-factors covering all 3-edge cuts, as well as that of perfect matchings intersecting
all 3-edge cuts in exactly one edge, in bridgeless cubic graphs. In section 4 we give Algorithm W3Cut, which ﬁnds a minimum-weight 2-factor covering all 3-edge cuts in aweighted bridgeless cubic graph in O(n3 ) time, where n is the number of vertices, Notethat this represents the ﬁrst polynomial-time algorithm for this problem. In section 5
we give Algorithm 34Cut, which ﬁnds a 2-factor that covers all the 3- and 4-edge
cuts in bridgeless cubic graphs. This algorithm also runs in O(n3 ) time and represents
the ﬁrst polynomial-time algorithm for this problem. In section 6 we demonstrate theusefulness of our results by using them to facilitate a new 6/5-approximation algo∗ Received by the editors August 5, 2011; accepted for publication (in revised form) February 26,
2013; published electronically May 2, 2013.
http://www.siam.org/journals/sidma/27-2/84351.html† School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, ON K1N
6N5, Canada (sylvia@site.uottawa.ca). This author’s research was supported by the Natural Sciencesand Engineering Research Council of Canada.
‡ Department of Mathematical Informatics, University of Tokyo, Tokyo 113-8656, Japan (iwata@mist.i.u-tokyo.ac.jp). This author’s research was supported by the Kayamori Foundation of Informational Science Advancement.
§ Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan, andLaboratoire G-SCOP, Optimisation Combinatoire, 38031 Grenoble, France (takazawa@kurims.kyotou.ac.jp). This author’s research was supported by Grant-in-Aid for Young Scientists (B) 23700016,
JSPS Postdoctoral Fellowships for Research Abroad, and the TEOMATRO grant ANR-10-BLAN
0207 “New Trends in Matroids: Base Polytopes, Structure, Algorithms and Interactions.”

918

FINDING 2-FACTORS CLOSER TO TSP TOURS IN CUBIC GRAPHS

919

rithm for the problem of ﬁnding a minimum 2-edge-connected spanning subgraph ina 3-edge-connected cubic graph improving upon the previous best worst-case ratio of
5/4 for this problem [17, 18].
The problem of ﬁnding a 2-factor covering edge-cuts in a graph is closely related
to the problem of ﬁnding 2-factors of G which do not contain any cycles of prescribed
lengths (see [15] for an overview of what is known on this problem). We call a cycle oflength three a triangle and that of length four a square. In a bridgeless cubic graph G,
a 2-factor that covers all 3-edge cuts would form a triangle-free 2-factor, and, if G
is also 3-edge-connected, a 2-factor that covers all 3- and 4-edge cuts would form atriangle- and square-free 2-factor, unless G is K4 .
There exist polynomial-time algorithms for ﬁnding a minimum-weight trianglefree 2-factor in weighted subcubic graphs [16, 22, 31]. For general weighted graphs,
the complexity of this problem is unknown, while a polynomial-time algorithm forthe unweighted version of this problem is given in [14]. Polynomial-time algorithms
are known for ﬁnding a triangle- and square-free 2-factor in subcubic graphs [3, 15].
For general graphs, the complexity of this problem is also unknown. Moreover, Vornberger [31] showed that the problem of ﬁnding a minimum-weight triangle- and squarefree 2-factor is NP-hard, even in cubic graphs.
The algorithms for ﬁnding 2-factors which do not contain any cycles of length
three and/or four have proven useful in the design of approximation algorithms for
related NP-hard problems (cf. [1, 10, 26]). Surprisingly, despite being closely related
and thus also potentially useful, the problem of ﬁnding a 2-factor covering 3- and4-edge cuts has received very little attention in the literature. It can be deduced frompolyhedral results of Edmonds [9] that any bridgeless cubic graph has a 2-factor thatcovers all 3-edge cuts (see section 3), a fact which is shown in [19] and also shown andused in [5] to get the ﬁrst 4/3-approximation for graph-TSP. Furthermore, Kaiser
and Škrekovski [20] showed that any bridgeless cubic graph has a 2-factor covering all
3- and 4-edge cuts; however, their result is not algorithmic in nature (see section 5 formore details on this). Note that it is not always possible to ﬁnd a 2-factor covering
all 5-edge cuts in a bridgeless cubic graph (for example, consider the Petersen graph),or one that covers all 2-edge cuts, and the complexity of ﬁnding a minimum-weight2-factor covering all 3- and 4-edge cuts is currently not known.
Note that a 2-factor that covers all edge-cuts would form a Hamilton cycle. The
problem of ﬁnding a Hamilton cycle in bridgeless cubic graphs is known to be NPcomplete (see [24]). In the weighted case, a 2-factor found by Algorithm W3Cut
would provide a lower bound for the TSP in a bridgeless cubic graph. This lower
bound would be stronger than that provided by a minimum-weight 2-factor, or thatprovided by a minimum-weight triangle-free 2-factor.
Moreover, Algorithm 34Cut is useful for designing an approximation algorithm
for the TSP. By using our algorithm as a preprocess for the algorithm in [13] for
the TSP on the metric completion of 3-edge-connected cubic graphs, we can improve
the approximation ratio (3/2 − 5/389) to 7/5, which was further improved to 4/3
recently [5]. In another related paper, Aggarwal, Garg, and Gupta [1] prove 4/3
speciﬁcally for 3-edge-connected cubic graphs in a more elegant way. Their algorithm
begins by ﬁnding a triangle- and square-free 2-factor. However, their algorithm andproof could easily be both simpliﬁed and shortened by using our Algorithm 34Cut toinstead start with a 2-factor that covers all 3- and 4-edge cuts, as it would eliminate
the necessity of dealing with the cases of cycles of length ﬁve with chords.
In section 6 we further demonstrate the usefulness of Algorithm 34Cut by using
it to design a polynomial-time 6/5-approximation algorithm for the 2-edge-connected

920

SYLVIA BOYD, SATORU IWATA, AND KENJIRO TAKAZAWA

spanning subgraph problem for 3-edge-connected cubic graphs. Given any unweighted
graph G, the 2-edge-connected spanning subgraph problem (henceforth 2EC) is the
problem of ﬁnding a 2-edge-connected spanning subgraph of G with as few edges
as possible. This problem is known to be MAX SNP-hard even for cubic graphs(see [8]) and has been widely investigated (see [18] for an overview). Krysta andAnil Kumar [23] designed a 21/16-approximation algorithm for cubic graphs, andCsaba, Karpinski, and Krysta [8] designed a (5/4 + )-approximation algorithm forsubcubic graphs. For 3-edge-connected cubic graphs, an algorithm achieving theapproximation ratio 5/4 was given by Huh [17]. For 2EC in general graphs, Vempala
and Vetta [30] and Jothi, Raghavachari, and Varadarajan [18] claimed to have 4/3- and5/4-approximation algorithms, respectively. A recent paper of Sebő and Vygen [29]contains, among other results, a 4/3-approximation algorithm for 2EC. Interestingly,
Vempala and Vetta [30] mentioned that in terms of possible improvements using theirapproach, achieving a worst-case ratio of 6/5 would seem to be a barrier, and thus
our algorithm that achieves this bound has some signiﬁcance.
For 2EC in 3-edge-connected cubic graphs, we present two algorithms, Algorithm Apx2EC and Algorithm FastApx2EC, both of which have approximation
ratio 6/5. Algorithm Apx2EC begins with a 2-factor covering all 3- and 4-edge
cuts found by Algorithm 34Cut. This preprocessing is the bottleneck of the complexity of the algorithm, and thus Algorithm Apx2EC has running time O(n3 ). In
Algorithm FastApx2EC, we make use of yet a third 2-factor algorithm we provide in this paper, which ﬁnds, in a given 3-edge-connected cubic graph, a 2-factor
which covers all 3-edge cuts and is square-free. Starting with this 2-factor has anadvantage: the algorithm to ﬁnd such a 2-factor is faster than Algorithm 34Cut,
and this allows us to improve the time complexity of our 6/5-approximation algorithm to O(n2 log4 n). However, this improvement comes at a cost: The resulting
6/5-algorithm is more complicated, and the proof of approximation is more diﬃcult(see section 7). So it seems that Algorithm 34Cut has deﬁnite advantages in thisregard.
A related approach for ﬁnding approximated 2EC solutions is to study the integrality gap α(2EC), which is the worst-case ratio between the optimal value for 2EC
and the optimal value for the linear programming relaxation of its associated weighted
problem, obtained by taking the metric completion. The value α(2EC) gives one measure of the quality of the lower bound provided by the linear programming relaxation.
Moreover, a polynomial-time constructive proof for the value α(2EC) would providean α(2EC)-approximation algorithm for 2EC. For the metric completion of 3-edgeconnected cubic graphs, Huh’s results [17] imply that α(2EC) is at most 5/4. In
section 6 we improve upon this and show that α(2EC) for this class of graphs is at
most 6/5. This is signiﬁcant, in that it has been conjectured that α(2EC) = 6/5 forgeneral weighted graphs; however, what is known is only that the integrality gap lies
somewhere between 6/5 and 3/2 for such graphs (see [2]).
The organization of this paper is summarized as follows. In section 2 we provide
some terminology and precise descriptions of the basic facts about 2-factors. A polyhedral description of 2-factors covering all 3-edge cuts in bridgeless cubic graphs isgiven in section 3. In section 4 we present Algorithm W3Cut, an algorithm for ﬁnding a minimum-weight 2-factor covering all 3-edge cuts in weighted bridgeless cubic
graphs. In section 5 we describe Algorithm 34Cut, an algorithm for ﬁnding a 2-factor
covering all 3- and 4-edge cuts in bridgeless cubic graphs. As an example of the usefulness of Algorithm 34Cut, in section 6 we give a 6/5-approximation algorithm for2EC in 3-edge-connected cubic graphs which runs in O(n3 ) time and show that 6/5 isFINDING 2-FACTORS CLOSER TO TSP TOURS IN CUBIC GRAPHS

921

an upper bound for α(2EC). Finally, in section 7 we give a faster O(n2 log4 n)-timealgorithm for the same problem with the same approximation ratio.
2. Preliminaries. In this section we provide precise deﬁnitions and notation
and a formal description of basic results which motivated our work. Let G = (V, E)
be a graph with vertex set V and edge set E. In general, unless stated otherwise,
we allow G to have multiedges (i.e., parallel edges) but no loops. We denote anedge with end vertices u and v by uv. We say that G is weighted if each edgee ∈ E is assigned a real weight ce . For any vertex subset S ⊆ V , let S̄ denote
V \ S and let δ(S) denote the set of edges connecting S and S̄. We denote |δ(S)|by d(S). For each vertex v ∈ V , δ({v}) and d({v}) are simply denoted by δ(v) andd(v), respectively. A graph in which d(v) = 3 for all v ∈ V is called cubic. For a
subgraph H of graph G, the vertex set and edge set of H are denoted by V (H) and
E(H), respectively. For S ⊆ V , we let γ(S) denote the set of edges with both ends
in S and let G[S] denote the subgraph of G induced by S, i.e., G[S] = (S, γ(S)).
For S ⊂ V , let G/S be the graph obtained by shrinking S into a single pseudovertex
vS . Note that we keep multiple copies of edges in such a contraction but remove
loops.
A matching is a set of vertex-disjoint edges. A matching M is called perfect ifevery vertex of G is incident to an edge in M . A 2-factor F is a set of edges F ⊆ Esuch that every vertex of G is incident to exactly two edges in F . Note that thecomplement of a 2-factor is a perfect matching in cubic graphs.
An edge subset D ⊆ E of the form D = δ(S) for some nonempty proper subset
S ⊂ V is called a cut. A cut D of cardinality k is called a k-edge cut if it is minimalin the sense that D does not contain any cut as a proper subset. A graph G is said
to be k-edge-connected if every cut of G has cardinality at least k. A graph without
any 1-edge cut is called bridgeless. We say that a subset F of E covers a cut D if
F ∩ D = ∅.
Petersen’s theorem [27] states that every bridgeless cubic graph contains a perfectmatching. Schönberger [28] proved the following strengthened form of Petersen’s
theorem.
Theorem 2.1 (Schönberger [28]). Let G = (V, E) be a bridgeless cubic (multi-)
graph with specified edge e∗ ∈ E. Then there exists a perfect matching of G that
contains e∗ .
A perfect matching containing a speciﬁed edge e∗ in a bridgeless cubic graph canbe found in O(n log4 n) time [4]. Taking the complement of the perfect matching in
Theorem 2.1 immediately gives the following corollary.
Corollary 2.2. Let G = (V, E) be a bridgeless cubic graph with specifiededge e∗ ∈ E. Then there exists a 2-factor of G that does not contain e∗ .
Kaiser and Škrekovski [20] proved a still stronger theorem, for which we will givean algorithmic proof in section 5.
Theorem 2.3 (Kaiser and Škrekovski [20]). Let G be a bridgeless cubic graphwith specified edge e∗ . Then there exists a 2-factor of G that covers all 3- and 4-edge
cuts and does not contain e∗ .
3. Polyhedral results. For any edge set F ⊆ E, the incidence vector of F isF
the vector χF ∈ RE deﬁned by χF= 0 for e ∈ E \ F . For any
e = 1 for e ∈ F and χe
Eedge set F ⊆ E and x ∈ R , let x(F ) denote the sum e∈F xe . Given a graph G,
the associated 2-factor polytope, P 2F (G), is the convex hull of all incidence vectorsof the 2-factors of G. In [9], Edmonds shows that P 2F (G) is given by the following
linear system:

922

SYLVIA BOYD, SATORU IWATA, AND KENJIRO TAKAZAWA(3.1)

x(δ(v)) = 2

for all v ∈ V,

(3.2)

x(X) − x(δ(S) \ X) ≤ |X| − 1

for all S ⊂ V ,X ⊆ δ(S), X a matching, |X| odd,

(3.3)

0 ≤ xe ≤ 1

for all e ∈ E.

In the following theorem, we extend this result by giving a linear description of
the convex hull of all incidence vectors of G covering all 3-edge cuts, denoted by
P 2F 3 (G).
Theorem 3.1. The polytope P 2F 3 (G) is given by the system of constraints (3.1)–(3.3) for the 2-factor polytope P 2F (G), with the addition of the following constraints:(3.4)

x(δ(S)) = 2

for all S ⊂ V , δ(S) a proper 3-edge cut of G.

Proof. Let P be the polytope deﬁned by the system of constraints (3.1)–(3.3) andconstraints (3.4). Clearly P 2F 3 (G) ⊆ P . To show that P ⊆ P 2F 3 (G) is also true (andthus complete the proof), we show that any x∗ ∈ P can be expressed as a convex
combination of incidence vectors of 2-factors that cover all 3-edge cuts of G.
Since x∗ ∈ P , we have that x∗ is also in P 2F (G) and thus can be expressed
as a convex combination of incidence vectors of 2-factors; i.e., there exist 2-factors
F1 , . . . , Fk of G and positive real numbers λ1 , . . . , λk such that
x∗ =

(3.5)

k

i=1

λi χFiandk

λi = 1.

i=1

Now consider any proper 3-edge cut δ(S) of G. Clearly χFi (δ(S)) ≤ 2 for i = 1, . . . , ksince a 2-factor will use 0 or 2 edges of a 3-edge cut. Since we also have that x∗ (δ(S)) =2, it follows from (3.5) that we must have χFi (δ(S)) = 2 for i = 1, . . . , k. Consequentlyx∗ is a convex combination of incidence vectors of 2-factors that cover all 3-edge cutsof G.
It is not diﬃcult to see that 23 χE ∈ P 2F 3 (G); in particular, P 2F 3 (G) = ∅ forbridgeless cubic graphs. Thus, the following existence theorem, which is a weakerstatement than Theorem 2.3, directly follows from Theorem 3.1.
Corollary 3.2. Let G = (V, E) be a bridgeless cubic graph with specifiededge e∗ ∈ E. Then there exists a 2-factor of G that covers all 3-edge cuts in G
and does not contain e∗ .
Similarly, we can obtain a polyhedral description of the convex hull of the incidence vectors of perfect matchings of G that intersect every 3-edge cut in exactly one
edge, which we denote by P P M3 (G). Given a graph G = (V, E), the associated perfectmatching polytope P P M (G) is the convex hull of all incidence vectors of the perfectmatchings of G and is given by the following linear system [9]:
(3.6)
(3.7)

x(δ(v)) = 1
x(δ(S)) ≥ 1

for all v ∈ V,
for all S ⊂ V , |S| odd,

(3.8)

xe ≥ 0for all e ∈ E.

Using this linear system, we have the following theorem, which can be proved similarly
to Theorem 3.1.
Theorem 3.3. The polytope P P M3 (G) is given by the system of constraints (3.6)–(3.8) for the perfect matching polytope P P M (G), with the addition of the following
constraints:(3.9)

x(δ(S)) = 1

for all S ⊂ V , δ(S) a proper 3-edge cut of G.

FINDING 2-FACTORS CLOSER TO TSP TOURS IN CUBIC GRAPHS

923

4. Minimum-weight 2-factors covering the 3-edge cuts. In this section,
let G = (V, E) be a weighted bridgeless cubic graph with edge weights c ∈ RE . Recall
that G may have multiple edges but no loops, and |V | = n. We present an O(n3 )-timealgorithm for ﬁnding a minimum-weight 2-factor that covers all the 3-edge cuts in G.
Note that such a 2-factor always exists by Corollary 3.2.
The set of edges incident to each vertex forms a 3-edge cut, which is covered byevery 2-factor in G. To exclude this kind of trivially covered 3-edge cut, we call a
3-edge cut δ(S) proper if 2 ≤ |S| ≤ n − 2. Thus our goal is to ﬁnd a minimum-weight2-factor F of G that covers all proper 3-edge cuts in G.
The general approach is an adaptation of one used in [7], and it involves choosing
a proper 3-edge cut D = δ(S), ﬁnding a 2-factor F  in G/S covering all 3-edge cuts
and a 2-factor F ◦ in G/S̄ covering all 3-edge cuts such that F  and F ◦ use the sametwo edges of D, and then “gluing” them together. The fact that the resulting 2-factor
covers all 3-edge cuts in G is established by Lemma 4.1 below.
For the proof of this lemma, it is useful to note that for any graph G = (V, E), thefunction d(.) is symmetric submodular ; i.e., for every two sets A, B ⊆ V , the following
two properties hold:
(4.1)
(4.2)

d(A) + d(B) ≥ d(A ∪ B) + d(A ∩ B),
d(A) + d(B) ≥ d(A \ B) + d(B \ A).

For an edge subset F ⊆ E, we use δF (S) and dF (S) to denote F ∩ δ(S) and |F ∩ δ(S)|,respectively. Note that dF (.) is also symmetric submodular.
Lemma 4.1. Let D = δ(S) be a proper 3-edge cut of a bridgeless cubic graph G,F  be a 2-factor in G/S covering all 3-edge cuts, and F ◦ be a 2-factor in G/S̄ covering
all 3-edge cuts such that F  and F ◦ use the same two edges of D. Then F = F  ∪ F ◦is a 2-factor in G covering all proper 3-edge cuts in G.
Proof. Let δ(Z) be a proper 3-edge cut such that S and Z are crossing (i.e.,
S ∩ Z = ∅, S ∪ Z = V , S \ Z = ∅, and Z \ S = ∅). Since G is cubic, the fact thatd(S) = 3 implies that |S| is odd, and thus either |S ∩ Z| or |S \ Z| must be odd.
Assume without loss of generality that |S ∩ Z| is odd. Then |S ∪ Z| is also odd, andhence both d(S ∩ Z) and d(S ∪ Z) are odd. Since G is bridgeless, the submodular
property (4.1) implies that d(S ∩ Z) = 3 and d(S ∪ Z) = 3. Hence δ(S ∩ Z) is a 3-edge
cut in G/S̄ and δ(S ∪ Z) is a 3-edge cut in G/S, and it follows by the deﬁnition of F
that dF (S ∩ Z) = 2, dF (S ∪ Z) = 2, and dF (S) = 2, which implies dF (Z) ≥ 2 by the
submodular property (4.1) of dF (.).
The algorithm is described as follows.
Algorithm W3Cut
Input. A bridgeless cubic graph G = (V, E) with edge weights c ∈ RE .
Output. A minimum-weight 2-factor F in G covering all the 3-edge cuts in G.
Step 1. Find a proper 3-edge cut D = δ(S) of G such that no proper subset Y of
S forms a proper 3-edge cut δ(Y ) of G. If G does not contain any proper
3-edge cuts, then simply ﬁnd a minimum-weight 2-factor F in G.
Step 2. Let D = {e1 , e2 , e3 }. For i = 1, 2, 3, ﬁnd a minimum-weight 2-factor Fi◦ in
G/S̄ not containing edge ei . The existence of Fi◦ follows from Corollary 2.2,
and Fi◦ can be found by applying a minimum-weight 2-factor algorithm tothe graph obtained by deleting ei from G/S̄.
Step 3. For each 2-factor Fi◦ found in Step 2, let Li = c(γ(S) ∩ Fi◦ ). We assign anextra weight αi to each edge ei (i = 1, 2, 3) in G/S such that α1 + α2 = L3 ,

924

SYLVIA BOYD, SATORU IWATA, AND KENJIRO TAKAZAWA

α2 + α3 = L1 , and α3 + α1 = L2 . Deﬁne new edge weights c for the edgesof G/S by ce = ce for e ∈ γ(S̄) and ce = cei + αi for e = ei (i = 1, 2, 3).
Step 4. Now consider G/S, which is also a bridgeless cubic graph of smaller size
than G. Find a minimum-weight 2-factor F  covering all 3-edge cuts byrecursively applying the algorithm to G/S with weights c . Let ei∗ be theedge in D \ F  , and return F = F  ∪ Fi◦∗ .
The minimality of c(F ) in Step 4 is veriﬁed as follows. By the minimality of S,
one can apply Lemma 4.1, and hence F is a 2-factor in G covering all 3-edge cuts in G.
Let F̂ be any 2-factor in G that covers all 3-edge cuts in G and F̂  be a 2-factor in G/Sobtained from F̂ by shrinking S. Then we have that c(F̂ ) ≥ c (F̂  ) ≥ c (F  ) = c(F ).
Therefore the output F of Algorithm W3Cut has minimum weight among the 2factors covering all 3-edge cuts in G.
The time complexity T (n) of this algorithm is analyzed as follows. We have that
T (n) = T (n − l + 2) + 3T  (l) + f (n),where f (n) is the time complexity for ﬁnding a proper 3-edge cut δ(S) in G such thatno proper subset of S provides a proper 3-edge cut and T  (l) is that for solving theminimum-weight 2-factor problem in G/S̄ with l vertices. We obtain f (n) = O(n2 )as follows. We can assume that G is 3-edge-connected. (Otherwise, it suﬃces toﬁnd a 2-edge cut δ(U ) = {u1 v1 , u2 v2 }, where u1 , u2 ∈ U , and then ﬁnd a desired
proper 3-edge cut in two graphs: one is G[U ] plus edge u1 u2 and the other G[Ū ] plus
v1 v2 .) Now construct a directed graph by replacing every edge with two oppositely
directed edges and ﬁnd three edge-disjoint r-arborescences for a ﬁxed vertex r ∈ V .
We have three paths from r to v for every vertex v ∈ V \ {r}, which correspond to a
maximum r-v ﬂow. Then we know all 3-edge cuts separating r and v by decomposing
the residual graph into strongly connected components. Finding a 2-edge cut can bedone in O(n log n) time [12], ﬁnding three edge-disjoint r-arborescences in O(n log n)time [12], and decomposing the residual graphs for all vertices in V \ {r} in O(n2 )time, and thus we obtain f (n) = O(n2 ). Also, we have T  (l) = O(l2 log l) [11], andconsequently T (n) = O(n3 ).
Theorem 4.2. Algorithm W3Cut finds a minimum-weight 2-factor in G covering all the 3-edge cuts in O(n3 ) time.
Since the complement of a 2-factor in G is a perfect matching, the following is animmediate consequence of Theorem 4.2.
Corollary 4.3. Algorithm W3Cut finds a maximum-weight perfect matchingin G which intersects every 3-edge cut in G in exactly one edge in O(n3 ) time.
5. Finding 2-factors covering all the 3- and 4-edge cuts. In this section, let
G = (V, E) be a bridgeless cubic graph with n vertices. We present Algorithm 34Cut,an O(n3 )-time algorithm for ﬁnding a 2-factor that covers all the 3- and 4-edge cutsand does not contain a speciﬁed edge e∗ ∈ E, which provides a constructive proof for
Theorem 2.3. We also obtain an analogous result for the perfect matching of G whichis the complement of this 2-factor.
Once again, G may have multiple edges but no loops. Observe that a 4-edge
cut D = δ(S) with |S| = 2 is covered by every 2-factor. We call a 4-edge cut D = δ(S)proper if 3 ≤ |S| ≤ n − 3. Our goal is to ﬁnd a 2-factor F that covers all the proper3- and 4-edge cuts in G.
5.1. Covering 3-edge cuts. Our algorithm starts by ﬁnding a proper 3-edge
cut δ(S). We will discuss later in section 5.2 what to do if G is free from proper
3-edge cuts. Once an appropriate S is found, the algorithm decomposes G into G/SFINDING 2-FACTORS CLOSER TO TSP TOURS IN CUBIC GRAPHS

925

and G/S̄. Note that both G/S and G/S̄ are bridgeless cubic graphs. Without loss ofgenerality, suppose that G/S contains e∗ . We then apply the algorithm recursively to
G/S to obtain a 2-factor F  covering all the 3- and 4-edge cuts in G/S and excludinge∗ . Let f and f  be the two edges in F  ∩δ(vS ). Again apply the algorithm recursively
to G/S̄ to obtain a 2-factor F ◦ with f, f  ∈ F ◦ covering all the 3- and 4-edge cutsin G/S̄. Then F = F ◦ ∪ F  forms a 2-factor in G. The algorithm terminates by
returning F .
Lemma 5.1. The output F of the above algorithm is a 2-factor in G covering all
the 3- and 4-edge cuts in G.
Proof. By Lemma 4.1, F covers all 3-edge cuts in G. So consider a 4-edge cut in
G. Let δ(Z) be a proper 4-edge cut such that S and Z are crossing. Since d(S) is odd
and G is cubic, it follows that |S| is odd, and thus either |S ∩ Z| or |S \ Z| is even.
Suppose without loss of generality that |S ∩Z| is even and |S \Z| is odd, which impliesd(S ∩ Z) is even and d(S \ Z) is odd. Since G is bridgeless, we have d(S ∪ Z) ≥ 2,
and thus d(S ∩ Z) ≤ 5 by the submodular property (4.1). Thus d(S ∩ Z) = 2 ord(S ∩ Z) = 4 holds.
Suppose d(S ∩ Z) = 2. Consider d(Z \ S). It must be even since |Z \ S| is even,and thus d(Z \ S) is either 2 or 4 by the submodular property (4.2). Since no proper
subset of δ(Z) forms a cut, we have d(Z \ S) + d(S ∩ Z) > d(Z). Thus d(Z \ S) = 4,
which implies d(S \ Z) = 3 by the submodular property (4.2). By the deﬁnition of F ,we have dF (Z \ S) ≥ 2, dF (S \ Z) ≥ 2, and dF (S) = 2. Thus we have dF (Z) ≥ 2 by
the submodular property (4.2) for dF (.).
If d(S ∩ Z) = 4, we have d(S ∪ Z) = 3 by the fact that |S ∪ Z| is odd andthe submodular property (4.1). By the deﬁnition of F , we have dF (S ∩ Z) ≥ 2,
dF (S ∪ Z) = 2, and dF (S) = 2, and we have dF (Z) ≥ 2 by the submodular property (4.1) for dF (.).
5.2. Covering 4-edge cuts. In this subsection, suppose that G is free fromproper 3-edge cuts. We now discuss how to ﬁnd a 2-factor covering all the 4-edge cutsin G and containing two speciﬁed edges f and f  incident to a vertex r ∈ V . If G
admits no proper 4-edge cut, then we ﬁnd an arbitrary 2-factor containing f and f by the algorithm in [4].
We now suppose that G has a proper 4-edge cut. Let D = δ(Y ) be a proper 4-edge
cut such that r ∈/ Y and no proper subset Z of Y provides a proper 4-edge cut δ(Z).
Suppose D = {e1 , e2 , e3 , e4 } with ej = uj vj , uj ∈ Y , and vj ∈ Ȳ for j = 1, 2, 3, 4.
Note that these end-vertices are all distinct since D is a proper cut, no proper subset
of D forms a cut, and G has no proper 3-edge cuts. Thus we cannot have both f
and f  belong to D. Construct the graph G/Ȳ . This graph is bridgeless and nearly
cubic in the sense that every vertex has degree three except for vȲ , which has degree
four. It follows from Corollary 2.2 that such a graph also admits a 2-factor, as will
be shown in the proof for Lemma 5.2 below. Let K be the family of pairs of edges in
D contained in 2-factors in G/Ȳ . Then H = (D, K) forms a graph with vertex set D
and edge set K.
Lemma 5.2. The graph H = (D, K) contains a square as a subgraph.
Proof. For each pair of distinct edges e ∈ D and e ∈ D, there exists a 2-factor
that contains e and does not contain e in G/Ȳ . To see this, split the vertex vȲ into
a pair of vertices t and t◦ connected by an additional edge e◦ in such a way that e
and e are incident to t and the remaining two edges in D are incident to t◦ . The
new edge e◦ does not form a 1-edge cut since no proper subset of D is a cut, andthus the resulting graph is a bridgeless cubic graph, which admits a 2-factor that does

926

SYLVIA BOYD, SATORU IWATA, AND KENJIRO TAKAZAWA

not contain e by Corollary 2.2. Contracting the new edge e◦ , we obtain the desired
2-factor in G/Ȳ . As a consequence, the degree of H is at least two at each e ∈ D.
This implies that H contains a square as a subgraph.
We now suppose without loss of generality that e1 e2 , e2 e3 , e3 e4 , and e4 e1 forma square in H. Then construct a graph G∗ = (W, E ∗ ) as follows. Construct G/Y ,and then split vY into a pair of vertices s1 and s2 connected by an additional edgee∗ in such a way that e1 and e3 are incident to s1 and e2 and e4 are incident to s2 .
Thus the vertex set W and the edge set E ∗ of G∗ are given by W = (V \ Y ) ∪ {s1 , s2 }and E ∗ = (E \ γ(Y )) ∪ {e∗ }. Note that G∗ is a bridgeless cubic graph which possibly
contains a proper 3-edge cut and is smaller in size than G. Apply the algorithm
recursively to obtain a 2-factor F ∗ covering all the 3- and 4-edge cuts in G∗ andcontaining the two speciﬁed edges f and f  .
We then split vȲ in G/Ȳ into two vertices t1 and t2 connected by an additionaledge e• in such a way that e1 and e3 are incident to t1 and e2 and e4 are incident to t2
to obtain a bridgeless cubic graph G• . Find a 2-factor F • such that F • ∩ D = F ∗ ∩ D
as follows: If |F ∗ ∩ D| = 4, then it suﬃces to ﬁnd a 2-factor in G• excluding e• . If
|F ∗ ∩ D| = 2, then the existence of F • follows from the construction of G∗ and G• ,and we have already obtained F • in the construction of H. Then F = F ∗ ∪ F • forms
a 2-factor in G. The following lemma establishes the correctness of our algorithm.
Lemma 5.3. The output F is a 2-factor covering all the 4-edge cuts in G.
Proof. Let δ(Z) be a proper 4-edge cut such that Y and Z are crossing.
Suppose d(Y ∩ Z) = 2, which implies that |Y ∩ Z| is even. Since both |Z| and|Y ∩ Z| are even, |Z \ Y | is even, and so is d(Z \ Y ). Thus by the submodular
property (4.2), d(Z \ Y ) is 2, 4, or 6. Since no proper subset of δ(Z) forms a cut, wehave d(Z \ Y ) + d(Y ∩ Z) > d(Z). Thus d(Z \ Y ) = 2. If d(Z \ Y ) = 6, then we haved(Y \ Z) = 2 by the submodular property (4.2), which is impossible since no proper
subset of δ(Y ) is a cut. Thus d(Z \ Y ) = 4 holds, and there exists exactly one edge
between Y ∩ Z and Z \ Y . Since dF (Z \ Y ) ≥ 2 by the deﬁnition of F , at least oneedge in F intersects δ(Z), which means Z is covered by F . Similarly, we may assertthat δ(Z) is covered by F if d(Y \ Z) = 2.
Suppose d(Y ∩ Z) = 3. Then Y ∩ Z must be a singleton, as G has no proper
3-edge cuts. Since Y and Z are proper 4-edge cuts, neither Y \ Z nor Z \ Y is asingleton. Note that |Y \ Z| and |Z \ Y | are odd, and so are d(Y \ Z) and d(Z \ Y ).
Therefore we have d(Y \ Z) ≥ 5 and d(Z \ Y ) ≥ 5, which provide a contradiction to(4.2). Thus we obtain d(Y ∩ Z) = 3. Similarly, we may assert that d(Y \ Z) = 3.
Finally, consider the remaining case of d(Y ∩ Z) = d(Y \ Z) = 4. Since noproper subset of Y provides a proper 4-edge cut, we have |Y ∩ Z| = |Y \ Z| =2. Then the induced subgraph G[Y ] = (Y, γ(Y )) forms a square with γ(Y ) ={u1 u2 , u2 u3 , u3 u4 , u4 u1 }. If |F ∗ ∩ D| = 2, then F • contains three edges from γ(Y ),and at least one of the three intersects δ(Z). If |F ∗ ∩ D| = 4, then e1 and e3 belong to
the same cycle in F ∗ , whereas u1 and u3 stay on diﬀerent sides of δ(Z). Thus there
must be an edge in F intersecting δ(Z).
5.3. Algorithm description and complexity analysis. The algorithm issummarized as follows.
Algorithm 34Cut
Input. A bridgeless cubic graph G = (V, E) and an edge e∗ ∈ E.
Output. A 2-factor in G covering all the 3- and 4-edge cuts in G and not containing e∗ .
Step 1. Find a proper 3-edge cut δ(S). If G has no proper 3-edge cut, then go to
Step 2. Otherwise, construct G/S and G/S̄, and let G/S contain e∗ . ApplyFINDING 2-FACTORS CLOSER TO TSP TOURS IN CUBIC GRAPHS

927

the algorithm recursively to obtain a 2-factor F  covering all the 3- and 4edge cuts in G/S and excluding e∗ . Let f, f  ∈ F  be the edges incident tovS . Then apply the algorithm recursively to G/S̄ to obtain a 2-factor F ◦ in
G/S̄ covering all the 3- and 4-edge cuts in G/S̄ and excluding the uniqueedge in δ(S) \ {f, f  }. Return F  ∪ F ◦ .
Step 2. Find a proper 4-edge cut D = δ(Y ) such that Y does not contain both endpoints of e∗ and no proper subset Z of Y provides a proper 4-edge cut δ(Z).
Then go to Step 3.
Step 3. For each pair of distinct edges e, e ∈ D, construct a graph G(e, e ) obtained
from G/Ȳ by splitting vȲ into a pair of vertices t and t◦ connected by anadditional edge e◦ in such a way that e and e are incident to t and theremaining two edges in D are incident to t◦ , and ﬁnd a 2-factor in G(e, e )excluding e◦ . Then go to Step 4.
Step 4. Construct G∗ as in section 5.2, according to the result in Step 3. Apply thealgorithm recursively to obtain a 2-factor F ∗ in G∗ covering all the 3- and4-edge cuts in G∗ and excluding e∗ , and then go to Step 5.
Step 5. Construct G• as in section 5.2, ﬁnd a 2-factor F • in G• such that F • ∩ D =F ∗ ∩ D, and then return F • ∪ F ∗ .
We analyze the time complexity T (n) of Algorithm 34Cut. The decomposition
into G/S and G/S̄ for a proper 3-edge cut δ(S) implies that T (n) = T (n1 ) + T (n2 ) +f (n), where f (n) is the time complexity for ﬁnding a proper 3-edge cut δ(S) in G
and n1 + n2 = n + 2. Note that f (n) = O(n2 ), as shown in section 4. By repeateddecomposition in Step 1, we obtain that
T (n) =kkT  (li ) + O(n3 ),i=1

where k = O(n), i=1 li ≤ 2n, and T  (li ) is the time complexity for ﬁnding a 2-factor
covering all the 4-edge cuts in a bridgeless cubic graph on li vertices without proper
3-edge cuts. Furthermore, for T  (l), we have thatT  (l) = T (l1 + 2) + g(l2 + 2) + h(l),where l1 + l2 = l, g(l) is the time complexity for ﬁnding a 2-factor excluding a
speciﬁed edge in a bridgeless cubic graph with l vertices, and h(l) is that for ﬁnding
a proper 4-edge cut δ(Y ) such that no proper subset Z of Y provides a proper 4-edge
cut in a bridgeless cubic graph on n vertices without a proper 3-edge cut. We haveg(l) = O(l log4 l) [4], and we obtain h(l) = O(l2 ) as follows. We can assume thatthe graph has neither proper 3-edge cuts nor 2-edge cuts. Choose a vertex u, anddenote the edges incident to u by e1 , e2 , and e3 . For each edge f not adjacent to e1 ,contract e1 and f to vertices ve1 and vf , respectively, and ﬁnd four edge-disjoint paths
connecting ve1 and vf , which correspond to a maximum ve1 -vf ﬂow and can be foundin O(l) time [21, 25]. Then we know all 4-edge cuts separating e1 and f . In order toﬁnd 4-edge cuts including e1 , do the same procedures for e2 and e3 . Consequently,
we obtain h(l) = O(l2 ), T  (l) = O(l3 ), and T (n) = O(n3 ).
Theorem 5.4. Algorithm 34Cut finds a 2-factor in G covering all the 3- and4-edge cuts and not containing a specified edge e∗ ∈ E in O(n3 ) time.
Again taking the complement of the obtained 2-factor, we have the following.
Corollary 5.5. Algorithm 34Cut finds a perfect matching in G intersecting
every 3-edge cut in exactly one edge and every 4-edge cut in 0 or 2 edges and containing
a specified edge e∗ ∈ E in O(n3 ) time.

928

SYLVIA BOYD, SATORU IWATA, AND KENJIRO TAKAZAWA

We remark that Kaiser and Škrekovski’s original proof [20] for Theorem 2.3 is nota constructive one, while they also build upon a similar argument of gluing 2-factors.
In their proof, proper 4-edge cuts satisfying a speciﬁc property, not interlaced withany other proper 4-edge cut, in their terms, play a key role. Thus, in designing analgorithm based on their proof, one would need an eﬃcient subroutine for ﬁnding aproper 4-edge cut satisfying that property.
6. Approximating a minimum 2-edge-connected subgraph. In this section, we describe Algorithm Apx2EC, a 6/5-approximation algorithm for the 2-edgeconnected subgraph problem (2EC) for 3-edge-connected cubic graphs. This algorithm uses Algorithm 34Cut as a preprocess, ﬁnds a subgraph with at most 6n/5
edges containing two speciﬁed adjacent edges e1 , e2 ∈ E, and runs in O(n3 ) time. We
then discuss the integrality gap α(2EC) for 2EC and prove that it is at most 6/5 for
3-edge-connected cubic graphs. For clarity, we remark here that a 3-edge-connectedcubic graph has no multiple edges since multiple edges with multiplicity two would
provide a 2-edge cut, and those with multiplicity three imply that G has only those
three edges.
6.1. An approximation algorithm. A path is a sequence (v0 , e1 , v1 , . . . , ek ,vk ), where ei = vi−1 vi (i = 1, . . . , k) and v1 , . . . , vk are distinct. A path in agraph G is called a Hamilton path if it contains all vertices in G. A cycle is a sequence (v0 , e1 , v1 , . . . , ek , vk ), where ei = vi−1 vi (i = 1, . . . , k), v1 , . . . , vk−1 are distinct and v1 = vk . For a cycle C, an edge e ∈ E[C] \ E(C) is a chord of C. The sizeof a cycle C is deﬁned by the number of vertices in C and denoted by |C|. Where no
confusion arises, we often identify a path or a cycle Q with the subgraph consistingof the vertices and edges in Q. For convenience, for a subgraph H of G, δ(H) denotes
the set of edges connecting V (H) and V \ V (H). Also, we will use G[H] to denotethe subgraph induced by V (H).
The following lemma is an easy observation but plays a key role in our algorithm.
Lemma 6.1. Let G = (V, E) be a 2-edge-connected graph and C be a cycle in G
with at most two chords. Let V ∗ ⊆ V (C) be the set of vertices not incident to thechords. For any vertex v ∗ ∈ V ∗ , there is a Hamilton path in G[C] starting at v ∗ andending at some vertex u∗ ∈ V ∗ .
Proof. Denote the two vertices adjacent to v ∗ on C by i and j. We assume thati ∈ V ∗ and j ∈ V ∗ since the statement is obvious if i ∈ V ∗ or j ∈ V ∗ .
Suppose that C has a chord ij. If ij is the unique chord of C, then the statement
holds. Assume that C has another chord kl and the vertices in V ∗ appear in theorder of i, k, l, j on C. If l and j are adjacent on C, then G[C] has a Hamilton pathstarting at v ∗ , traversing j, ji, i, k, kl, l in this order and ending at a vertex between
k and l. If there are vertices between l and j on C, then G[C] has a Hamilton pathstarting at v ∗ , traversing j, ji, i, k, l in this order and ending at a vertex between jand l.
Suppose the chord ij does not exist. In this case, we have two chords, ik and jl.
Assume that the vertices in V ∗ appear in the order of i, k, l, j on C. Then G[C] hasa Hamilton path starting at v ∗ , traversing i, k, l, lj, j in this order and ending at avertex between j and l.
Assume that the vertices in V ∗ appear in the order of i, l, k, j on C. If k and l are
not adjacent on C, then G[C] has a Hamilton path starting at v ∗ , traversing i, l, lj, j, kin this order and ending at a vertex between k and l. If k and l are adjacent on C,
then there is at least one vertex between i and l or between j and k since otherwise
G has a 1-edge cut incident to v ∗ , which contradicts that G is 2-edge-connected.

FINDING 2-FACTORS CLOSER TO TSP TOURS IN CUBIC GRAPHS

929

Suppose, without loss of generality, that i and l are not adjacent. Then G[C] has a
Hamilton path starting at v ∗ , traversing i, ik, k, j, jl, l in this order and ending at avertex between i and l.
Note that the proof implies how to ﬁnd a desired Hamilton path in G[C].
To begin the algorithm, we apply Algorithm 34Cut to G to obtain a 2-factor F
which covers all the 3- and 4-edge cuts. The family of cycles in F is denoted by C.
The edges in E \ F , which form a perfect matching in G, are called the matchingedges. Observe that |C| ≥ 5 for each cycle C ∈ C. We say that a cycle C ∈ C is large
if |C| ≥ 10 and small if |C| ≤ 9. Note that all small cycles C have at most two chords
in G[C] unless C contains all vertices in G, and thus Lemma 6.1 can be applied tosuch cycles.
In the algorithm, we maintain a subgraph H satisfying the following properties:
1. H is 2-edge-connected;
2. V (H) is the union of the vertex set of a subfamily of the cycles in C; and3. |E(H)| ≤ 6|V (H)|/5.
The subgraph H is initially an arbitrary cycle in C and is augmented by adding
another subgraph H  . The algorithm terminates when V (H) = V .
In constructing H  , ﬁrst we choose an edge e = uv ∈ δ(H), where u ∈ V (H) andv ∈ V \ V (H), and let H  := ({u}, ∅). Here v belongs to a cycle C ∈ C which is notcontained in H. If C is a large cycle, then we add e and C to H  and continue togrow H  from an arbitrary matching edge f ∈ δ(C) \ {e}. If C is a small cycle, byLemma 6.1 there exists a Hamilton path P of G[C] starting at v and ending at somevertex w incident to a matching edge f ∈ δ(C) \ {e}. We call v and w the initialvertex and terminal vertex of P , respectively. Here we add e and P to H  and thencontinue to grow H  again from f , redeﬁning e := f and C as the cycle we reach at
the other end of f .
The above two procedures are applied when C is not contained in H or H  . If
we traverse e = uv to reach a cycle C ∈ C which is in H, then we have completed thegrowth of the subgraph H  , and we augment H with H  . If we traverse e = uv toreach a cycle C ∈ C with v ∈ C which has already been added to H  , then we add e
to H  and construct either a lollipop or a tadpole.
We construct a lollipop if C is a large cycle. A lollipop L is a subgraph consistingof the large cycle C plus the elements of H  added after C was added to H  . See
Figure 6.1 for an illustration. Then we continue to grow H  from a matching edge f ∈δ(L) \ E(H  ). Note that f always exists since G is 3-edge-connected.
We construct a tadpole if C is a small cycle. A tadpole T is a subgraph consistingof the Hamilton path P derived from C plus the elements of H  added after P wasadded to H  . For a tadpole T , we specify two subgraphs, the tail and the head. LetvC and wC be the initial and terminal vertices of P , respectively. The tail of T is a
subgraph of P , the path connecting vC and v. The head of T consists of the subgraphof P connecting v and wC and elements of T added to H  after P was added to H  .
See Figure 6.2 for an illustration. Then we continue to grow H  from a matchingedge connecting the head of T to V \ V (T ). The fact that there always exists such amatching edge will be proved in Lemma 6.2.
We call a cycle in C which does not belong to any lollipop or tadpole an independent cycle. If C is neither in H nor independent, then we construct a larger lollipop
or tadpole. If C is contained in a lollipop L, we construct a larger lollipop L̂, which
consists of L plus the elements of H  added after L was constructed. Then we continue
to grow H  from a matching edge in δ(L̂) \ E(H  ).

930

SYLVIA BOYD, SATORU IWATA, AND KENJIRO TAKAZAWA

Fig. 6.1. Construction of a lollipop L. The thick edges are the edges in L. The hexagon isa small cycle of size six, and the four circles indicate large cycles. (Some vertices and edges areomitted.)Fig. 6.2. Construction of a tadpole T . The thick edges are the edges in T . The hexagon isa small cycle of size six, and the three circles indicate large cycles. (Some vertices and edges areomitted.) The dotted thick edges form the tail of T , and the solid thick edges form the head of T .

If C is contained in a tadpole T , then we construct a larger tadpole T̂ , which
consists of T and elements of H  added after T was constructed. The tail and headof T̂ are deﬁned as follows:• If the vertex v ∈ V (C) at which we come back to C is in the tail of T , then
the tail of T̂ is a subgraph of the tail of T , a path connecting v, and theinitial vertex of the Hamilton path providing the tail of T . The head of T̂ isa subgraph of H  consisting of edges in T not in the tail of T̂ and edges inH  added after T was constructed.
• If v is in the head of T , then the tail of T̂ is the same as that of T , and thehead of T̂ consists of the head of T and the elements of H  added after T wasconstructed.
Then we continue to grow H  from a matching edge connecting the head of T̂ andV \ V (T̂ ).

FINDING 2-FACTORS CLOSER TO TSP TOURS IN CUBIC GRAPHS

931

If a lollipop or a tadpole becomes contained in a larger lollipop or tadpole, thenwe remove the contained lollipops and tadpoles from our list of them. That is, we
handle only inclusionwise maximal lollipops and tadpoles.
Below is a full description of the algorithm.
Algorithm Apx2EC
Input. A 3-edge-connected cubic graph G = (V, E).
Output. A 2-edge-connected spanning subgraph H of G with at most 6|V |/5 edges.
Step 1. Apply Algorithm 34Cut to ﬁnd a 2-factor F of G covering all the 3- and4-edge cuts. Choose an arbitrary cycle C0 in F , set H := C0 , and then go
to Step 2.
Step 2. If V (H) = V , then return H. Otherwise, choose an arbitrary edge e =uv ∈ δ(H), where u ∈ V (H) and v ∈ V \ V (H), let H  be the graphconsisting of the single vertex u, and go to Step 3.
Step 3. Denote by C the cycle in F containing v. If C is not contained in H, then
go to Step 4. Otherwise, go to Step 5.
Step 4. Here, we have the following four cases:• If C is a large cycle not contained in H ∪ H  , then go to Step 4-1.
• If C is a small cycle not contained in H ∪ H  , then go to Step 4-2.
• If C is an independent large cycle in H  or is contained in a lollipop in
H  , then go to Step 4-3.
• If C is an independent small cycle in H  or is contained in a tadpole inH  , then go to Step 4-4.
Step 4-1. Add e and C to H  . That is, set V (H  ) := V (H  ) ∪ V (C) and E(H  ) :=E(H  ) ∪ E(C) ∪ {e}. Then choose an arbitrary edge f from δ(C) \ {e}, set
the vertex that is the end of f not in C to v, set e := f , and go to Step 3.
Step 4-2. Let P be a Hamilton path of G[C] starting at v (see Lemma 6.1), anddenote the terminal vertex of P by w. Add e and P to H  ; that is, set
V (H  ) := V (H  ) ∪ V (C) and E(H  ) := E(H  ) ∪ E(P ) ∪ {e}. Then let f
be the matching edge incident to w, set the vertex that is the other endof f to v, set e := f , and go to Step 3.
Step 4-3. Add e to H  , and construct a lollipop L. Remove any lollipops or tadpolescontained in L from the list of lollipops and tadpoles. Then choose anarbitrary edge f from δ(L) \ E(H  ), set the vertex that is the end of f not
in L to v, set e := f , and go to Step 3.
Step 4-4. Add e to H  , and construct a tadpole T . Remove any lollipops or tadpolesthat are part of T from the list of lollipops and tadpoles. Then choose anarbitrary edge f connecting the head of T to V \ V (T ), set the vertex thatis the end of f not in T to v, set e := f , and go to Step 3.
Step 5. Augment H by H  and e. That is, set V (H) := V (H) ∪ V (H  ) andE(H) := E(H) ∪ E(H  ) ∪ {e}. Then, go to Step 2.
What remains to be proven is that we can continue to grow H  from the head ofa tadpole in Step 4-4.
Lemma 6.2. In Step 4-4, there exists an edge connecting the head of the tadpole T
and V \ V (T ).
Proof. Denote the small cycle providing the tail of T by CT . Let Q = V (T ) \V (CT ) and R = V \ V (T ). Note that all edges in δ(CT ), δ(Q), and δ(R) are matchingedges.
Suppose that no edge connects the head of the tadpole T and V \ V (T ). Then
there are no edges between Q and R. Since G is 3-edge-connected and F covers all

932

SYLVIA BOYD, SATORU IWATA, AND KENJIRO TAKAZAWA

3- and 4-edge cuts, there are at least ﬁve edges between V (CT ) and Q and at least
ﬁve edges between V (CT ) and R. It follows that |CT | ≥ 10, which contradicts that
CT is a small cycle.
Step 1 takes O(n3 ) time (see Theorem 5.4). The other steps of the algorithm
collectively take O(n) time, and thus the total time complexity is O(n3 ). The approximation ratio follows from the following lemma.
Lemma 6.3. For an output H of Algorithm Apx2EC, it holds that |E(H)| ≤max{n, 6n/5 − 1}.
Proof. For n ≤ 9, the initial 2-factor which has all 3- and 4- edge cuts covered
must consist of just one cycle, and thus |E(H)| = n.
For n ≥ 10, partition the family C of cycles in F into two parts, L and S, where L
is the family of large cycles and S is that of small cycles. By construction, it is clearthat H contains at most 2(|C| − 1) edges from the matching edges E \ F . Moreover,
we use |C| edges from G[C] for a cycle C ∈ L, and |C| − 1 edges from G[C] for acycle C ∈ S, except possibly the initial cycle C0 —if it is a small cycle, then we use|C| edges from it. Thus, it follows that
|E(H)| ≤ n − (|S| − 1) + 2(|C| − 1) = n + |S| + 2|L| − 1 ≤ 6n/5 − 1.
The last inequality follows from the deﬁnition of small and large cycles, which implies
that n ≥ 5|S| + 10|L|.
As a consequence of the fact that n is a lower bound for 2EC, we obtain thefollowing theorem.
Theorem 6.4. Algorithm Apx2EC is a 6/5-approximation algorithm for 2EC in
3-edge-connected cubic graphs. More precisely, for a 3-edge-connected cubic graph G =(V, E), Algorithm Apx2EC finds a 2-edge-connected subgraph H of G with |E(H)| ≤6n/5 − 1 in O(n3 ) time.
We ﬁnally remark that it is possible to make the output subgraph H in Algorithm Apx2EC contain two speciﬁed adjacent edges.
Corollary 6.5. For a 3-edge-connected cubic graph G = (V, E) and two adjacent edges e1 , e2 ∈ E, one can find a 2-edge-connected subgraph H of G with
|E(H)| ≤ 6n/5 − 1 and {e1 , e2 } ⊆ E(H) in O(n3 ) time.
Proof. Let e1 , e2 ∈ E be adjacent at v ∈ V , and let e3 be the last edge in δ(v). In
Step 1 of Algorithm Apx2EC, we can apply Algorithm 34Cut so that the 2-factor F
does not contain e3 . If e1 and e2 belong to a large cycle in F , then it is clear that they
belong to the output subgraph. If they belong to a small cycle in F , then it suﬃces
to choose that small cycle to be the initial cycle in H.
6.2. The integrality gap for 2EC. In the weighted version of 2EC, which wedenote by W2EC, we are given a complete graph Kn = (V, E) with edge weights w ∈RE , and we wish to ﬁnd a 2-edge-connected spanning subgraph of Kn of minimum
weight. We can associate such a weighted problem with our 2EC problem for a given
graph G by taking the metric completion of G, which is the complete weighted graphobtained by assigning weight 1 to all edges of G, and letting each other edge haveweight equal to the length of a shortest path between its endpoints in G. We call thisweighted version of 2EC graph2EC . Note that the minimum size of a solution for2EC is equal to the minimum weight solution for its associated graph2EC problem(see [6]).
The integrality gap α(2EC) is the worst-case ratio between the optimal value for
2EC (i.e., its associated graph2EC) and the optimal value for the linear programming
relaxation of the integer programming formulation of the associated graph2EC. Since

FINDING 2-FACTORS CLOSER TO TSP TOURS IN CUBIC GRAPHS

933

n is obviously a lower bound for the optimal value of the linear programming relaxation
for graph2EC, we obtain the following theorem, which is an immediate consequenceof Algorithm Apx2EC.
Theorem 6.6. The value of α(2EC) is at most 6/5 for 3-edge-connected cubic
graphs.
This result is signiﬁcant, in that it has been conjectured that the integrality gapα(W2EC) for general W2EC is 6/5, and, moreover, 6/5 is the best lower bound known
for α(W2EC) (see [2]). Previously, the best upper bound known for α(2EC) was 5/4,
which is implied by Huh’s algorithm in [17]. We remark that the best lower boundwe know for α(2EC) for bridgeless cubic graphs is 7/6 and for 3-edge connected cubic
graphs is 11/10.
7. A faster approximation algorithm. Let G = (V, E) be a 3-edge-connectedcubic graph with |V | = n. In this section, we describe an algorithm for ﬁnding a 2edge-connected spanning subgraph of G with at most 6n/5 edges in O(n2 log4 n) time.
In this algorithm, we begin with a 2-factor F which covers all the 3-edge cuts andconsists of cycles of size at least ﬁve (see section 7.2 for details). Note that this isa relaxed condition for the initial 2-factor F in Algorithm Apx2EC. This relaxation
improves the time complexity for ﬁnding F , which is the bottleneck part of the entire
algorithm, but makes the following procedures more involved.
We inherit the terminology from Algorithm Apx2EC. The family of cycles in F isdenoted by C. The edges in E \ F , which form a perfect matching in G, are called thematching edges. We say that a cycle C ∈ C is large if |C| ≥ 10 and small if |C| ≤ 9.
7.1. Diﬀerences from Algorithm Apx2EC. We basically execute the sameprocedures as in Algorithm Apx2EC. For the current initial 2-factor F , however,Lemma 6.2 fails due to the fact that F does not necessarily cover all 4-edge cuts. In
this subsection, we exhibit tricks which ensure that a tadpole T has a matching edge
connecting its head and V \ V (T ).
For a cycle C, let G − C denote the subgraph of G obtained by deleting G[C] andδ(C). If G − C is disconnected, then C is called a cut cycle. Let T be a tadpole, and
let C denote the small cycle providing the tail of T . If C is a cut cycle, then we do notknow whether there exists an edge connecting the head of T and V \ V (T ). In orderto ensure the existence of such an edge, we impose two new rules in constructing H.
In preparation for describing the rules, let us analyze the properties of small cut
cycles.
Lemma 7.1. A small cut cycle C ∈ C has the following properties:
1. G − C consists of exactly two components;
2. |C| = 8 or |C| = 9; and3. C has no chords.
Proof. Since G is 3-edge-connected and F covers all the 3-edge cuts, each component in G − C is connected to C by at least four edges in G. As C is a small cycle,
we have that |δ(C)| ≤ 9, which implies that the number of components in G − C is at
most two. Thus, we have that G − C consists of exactly two components and |C| iseight or nine. Furthermore, we have that |δ(C)| ≥ 8 and |C| ≤ 9, which implies that
C has no chords.
When we ﬁnd the initial 2-factor F and choose the initial cycle C0 , for each small
cut cycle C other than C0 , we label each edge in δ(C) as backward or forward. Denotethe component in G − C containing C0 by H0 and the other by H1 . We call thematching edges connecting H0 and C backward edges and those connecting H1 and C
forward edges. The lemma below immediately follows from Lemma 7.1.

934

SYLVIA BOYD, SATORU IWATA, AND KENJIRO TAKAZAWA

Fig. 7.1. Construction of a lollipop L by Trick 2. The thick edges are the edges in L. The
octagon is the small cut cycle C of size eight, and the three circles indicate large cycles. (Somevertices and edges are omitted.)

Lemma 7.2. For a small cut cycle C, the number of forward edges is four orfive.
One new rule is for the choice of a Hamilton path in G[C] for a small cut cycle C.
When we come to a small cycle C by traversing a matching edge e = uv with v ∈ V (C),we route a Hamilton path P in G[C] and leave C from a matching edge f ∈ δ(C). We
call this edge f as the leaving edge of P . Now, if C is a small cut cycle, Lemma 7.1
implies that G[C] has two Hamilton paths starting at v, which end at a vertex adjacent
to v on C. Here we impose a rule on the choice between these two Hamilton paths.
Trick 1. If at least one of the Hamilton paths has a backward leaving edge, thenchoose it. Otherwise, choose a Hamilton path whose leaving edge is closer
to a backward edge other than e on C than that of the other Hamilton path.
The other new rule is in construction of a tadpole. When we come back to asmall cut cycle C, we construct a lollipop instead of a tadpole if a certain conditionis satisﬁed.
Trick 2. Let uv, ij, kl ∈ δ(C) be matching edges used to come to C, leave C, andcome back to C, respectively, where v, i, k ∈ V (C). If i and k are adjacent on
the Hamilton path of G[C] contained in H  , then we construct a lollipop L
instead of the tadpole T as follows. The edge ik is deleted from H  , and vi
is added to H  . The vertex set of L is the same as that of T , and the edge
set of L is E(L) = (E(T ) \ {ik}) \ {vi}. See Figure 7.1 for an illustration.
Now we prove that the algorithm does not get stuck in leaving a tadpole from its
head.
Lemma 7.3. For a tadpole T , there exists an edge connecting the head of thetadpole T and V \ V (T ).
Proof. Suppose, to the contrary, that there exists no edge connecting the head ofa tadpole T and V \ V (T ). Denote the small cycle providing the tail of T by CT , thechosen Hamilton path of G[CT ] by P , and the matching edge used to come to CT at
the ﬁrst time by mT = uv, where v ∈ V (CT ). Here we have that CT is a small cut
cycle. Recall that H0 is the component in G − CT containing the initial cycle C0 and
H1 is the other component. Observe that the rest of the tadpole forms H1 , that is,
V (T ) \ V (CT ) = V (H1 ). (See Figure 7.2 for an illustration.)

FINDING 2-FACTORS CLOSER TO TSP TOURS IN CUBIC GRAPHS

935

Fig. 7.2. The path P , indicated by the thick line, and edge vi form the small cut cycle CT .
The subgraph of P connecting v and k is the tail of T .

Fig. 7.3. Shrinking a cycle of size four.

Denote the forward edge which is used to leave CT by ij and the forward edge
which is used to come back to CT to form the tadpole T by kl, where i, k ∈ V (CT )and j, l ∈ V (H1 ). By Trick 2, there exists at least one vertex between i and k on
P . Note that such a vertex p belongs to the head of T , and hence the matching edge
incident to p is a forward edge. This implies that P has at least two vertices between
i and a backward edge closest to i. By Trick 1, we have that the matching edges
incident to three vertices closest to v on P are forward edges. Therefore, CT has atleast six forward edges, which contradicts Lemma 7.2.
7.2. Finding the initial 2-factor. In this subsection, we describe how to ﬁnd
a 2-factor which covers all the 3-edge cuts and consists of cycles of size at least ﬁve ina 3-edge-connected cubic graph eﬃciently. If G is K4 , then any cycle of length foursuﬃces. Thus, in what follows we assume that G is not K4 .
First, take a maximal family Q of vertex-disjoint cycles of size four. Then we“shrink” each cycle Q ∈ Q in the following manner. Let Q = (v1 , e1 , v2 , e2 , v3 , e3 , v4 ,
e4 , v1 ). Delete all edges in E(Q), merge v1 and v3 into a single vertex s1 and v2 andv4 into another vertex s2 , and connect s1 and s2 by a new edge eQ . We refer to s1 , s2
as pseudovertices and eQ as a pseudoedge. See Figure 7.3 for an illustration. Denotethe graph obtained by shrinking every cycle in Q by G = (V  , E  ). Note that G
is a 2-edge-connected cubic graph. We also remark that a loop does not appear inthis procedure: if G has a loop attached to s1 , then v1 v3 ∈ E, and thus either V (Q)provides a 2-edge cut or V (G) = V (Q) holds. The former case contradicts that G is
3-edge-connected and the latter that G is not a K4 .
In G , we ﬁnd a 2-factor F  ⊆ E  which covers all the 3-edge cuts. More specifically, we describe a recursive algorithm to ﬁnd a 2-factor F  covering all the proper
3-edge cuts and excluding a speciﬁed edge e∗ in a 2-edge-connected cubic graph G .
If G has no proper 3-edge cut, then it suﬃces to ﬁnd an arbitrary 2-factor excluding e∗ , which can be done in O(n log4 n) time [4]. Suppose G has a proper 3-edge
cut D = δ(S). We construct two graphs, G /S and G /S̄. Without loss of generality,

936

SYLVIA BOYD, SATORU IWATA, AND KENJIRO TAKAZAWA

suppose that G /S contains e∗ . Then we apply the present algorithm recursively toG /S to obtain a 2-factor F ◦ covering all the 3-edge cuts and excluding e∗ in G /S.
Identify the unique edge e in D \ F ◦ . Then we again apply the present algorithm toG /S̄ recursively to obtain a 2-factor F • in G /S̄ covering all 3-edge cuts in G /S̄ andexcluding e. Now, by Lemma 4.1, F  = F ◦ ∪ F • is a 2-factor covering all the 3-edge
cuts in G .
In order to ﬁnd a proper 3-edge cut D in G , perform the following procedure.
Find an arbitrary 2-factor F  , and then contract each cycle in F  into a vertex toobtain a new graph G . Then ﬁnd an arbitrary 3-edge cut in G . Now if a 3-edge cut
in G is found, then it corresponds to a proper 3-edge cut in G . If G has no 3-edge
cut, then we can conclude that F  is a 2-factor covering all 3-edge cuts in G .
Then we unshrink all the pseudoedges sequentially to recover G. In unshrinking
a pseudoedge eQ , we extend F  by edges in E(Q) in the following manner.
Case 1 (eQ ∈ F  ). Denote the cycle in F  containing eQ by C. We choose the uniquetriple of edges in E(Q) which provides a cycle CQ of size |C| + 2.
Case 2 (eQ ∈ F  ).
Case 2.1. If s1 and s2 belong to the same cycle C in F  , then choose thepair of disjoint edges in E(Q) which provides a cycle CQ of size |C| + 2.
Case 2.2. If s1 and s2 belong to distinct cycles C1 and C2 in F  , then choose
any pair of disjoint edges in E(Q) to obtain a cycle CQ of size |C1 | +|C2 | + 2.
See Figure 7.4 for an illustration. In the end, we obtain a desired 2-factor F in G.
Lemma 7.4. The 2-factor F constructed as above covers all the 3-edge cuts andconsists of cycles of size at least five.
Proof. We ﬁrst prove that F consists of cycles of size at least ﬁve. By the deﬁnitionof G , F  does not contain a cycle of size less than ﬁve without pseudovertices. Let
eQ be a pseudoedge in G resulting from Q ∈ Q, and let GQ and FQ be the graphand 2-factor obtained from G and F  by unshrinking eQ , respectively. In Case 1,|CQ | < 5 implies that |C| = 2. Then we have that V (Q) provides a 2-edge cut
in G, which contradicts that G is 3-edge-connected. In Case 2.1, |CQ | < 5 again
implies that |C| = 2. Let Q = (v1 , e1 , v2 , e2 , v3 , e3 , v4 , e4 , v1 ). Then we have that
V (G) = {v1 , v2 , v3 , v4 } and E(G) = {e1 , e2 , e3 , e4 , e1 , e3 }, where e1 and e3 are paralleledges of e1 and e3 , respectively. Now {v1 , v2 } provides a 2-edge cut, which is acontradiction. In Case 2.2, |CQ | < 5 implies that |C1 | = |C2 | = 1, which contradicts
that G has no loops.
We now prove that FQ covers all the 3-edge cuts in GQ . Since F  covers all the
3-edge cuts in G , it suﬃces to consider 3-edge cuts in GQ containing edges in E(Q).
In both Cases 1 and 2, such an edge cut is covered by CQ . We inductively conclude
that F covers all the 3-edge cuts in G.
The procedures to ﬁnd the initial 2-factor are summarized as follows.
Procedure Ini2F
Input. A 3-edge-connected cubic graph G = (V, E).
Output. A 2-factor F ⊆ E in G which covers all the 3-edge cuts and consists ofcycles of size at least ﬁve.
Step 1. Let Q be a maximal family of vertex-disjoint cycles of size four. Shrink
each cycle Q ∈ Q to a pseudoedge eQ to obtain a 2-edge-connected cubic
graph G .
Step 2. Apply Procedure 3Cut below to obtain a 2-factor F  covering all the 3-edge
cuts in G .

FINDING 2-FACTORS CLOSER TO TSP TOURS IN CUBIC GRAPHS

937

Fig. 7.4. Unshrinking a pseudoedge. Thick edges are in F  and F . The three patterns indicate
Cases 1, 2.1, and 2.2, respectively. In Case 2.2, it is also possible to add e2 and e4 to F  instead ofe1 and e3 .

Procedure 3Cut
Step 2.1. Find an arbitrary 2-factor F  in G , and contract each cycle in
F  into a single vertex to obtain a new graph G .
Step 2.2. Find an arbitrary 3-edge cut in G . If no 3-edge cut exists, return
F .
Step 2.3. Let D = δ(S) be a proper 3-edge cut in G which corresponds tothe 3-edge cut in G found in Step 2.2. Construct G × S andG × S̄. Apply Procedure 3Cut to G × S recursively to obtaina 2-factor F ◦ covering all the 3-edge cuts. Let e be the uniqueedge in D \ F ◦ , and again apply Procedure 3Cut to G × S̄ toobtain a 2-factor F • covering all the 3-edge cuts and excluding
e. Return F  = F ◦ ∪ F • .
Step 3. Unshrink all the pseudoedges eQ sequentially to obtain a desired 2-factor F .
Denote the time complexity of Procedure Ini2F by T (n). Then we have that
T (n) = T (n1 ) + T (n2 ) + f (n),where n1 and n2 denote the number of vertices in G × S and G × S̄, respectively, and f (n) denotes the time complexity for ﬁnding a proper 3edge cut D in a cubic graph with n vertices. Note that ﬁnding Q can bedone in O(n) time. As stated above, for ﬁnding a proper 3-edge cut D, it
suﬃces to ﬁnd a 2-factor in G and a 3-edge cut in G . The former can

938

SYLVIA BOYD, SATORU IWATA, AND KENJIRO TAKAZAWA

be done in O(n log4 n) time [4] and the latter in O(n log n) [12] by trying
to ﬁnd four edge-disjoint arborescences in a digraph obtained by replacing
each edge by two oppositely directed edges. Consequently, we have thatf (n) = O(n log4 n) and T (n) = O(n2 log4 n).
By combining Procedure Ini2F and the argument in section 7.1, we obtain Algorithm FastApx2EC.
Theorem 7.5. Algorithm FastApx2EC finds a 6/5-approximate solution for2EC in 3-edge-connected cubic graphs in O(n2 log4 n) time.
REFERENCES[1] N. Aggarwal, N. Garg, and S. Gupta, A 4/3-Approximation for TSP on Cubic 3-EdgeConnected Graphs, http://arxiv.org/abs/1101.5586 (2011).
[2] A. Alexander, S. Boyd, and P. Elliott-Magwood, On the Integrality Gap of the 2-Edge
Connected Subgraph Problem, Technical Report TR-2006-04, SITE, University of Ottawa,
Ottawa, Canada, 2006.
[3] K. Bérczi and L. A. Végh, Restricted b-matchings in degree-bounded graphs, in Integer Programming and Combinatorial Optimization, Lecture Notes in Comput. Sci. 6080, Springer,
Berlin, 2010, pp. 43–56.
[4] T. C. Biedl, P. Bose, E. D. Demaine, and A. Lubiw, Eﬃcient algorithms for Petersen’smatching theorem, J. Algorithms, 38 (2001), pp. 110–134.
[5] S. Boyd, R. Sitters, S. van der Ster, and L. Stougie, TSP on cubic and subcubic graphs,
in Integer Programming and Combinatorial Optimization, Lecture Notes in Comput. Sci.
6655, Springer, Heidelberg, 2011, pp. 65–77.
[6] J. Cheriyan, A. Sebő, and Z. Szigeti, Improving on the 1.5-approximation of a smallest
2-edge connected spanning subgraph, SIAM J. Discrete Math., 14 (2001), pp. 170–180.
[7] G. Cornuéjols, D. Naddef, and W. Pulleyblank, The traveling salesman problem in graphswith 3-edge cutsets, J. ACM, 32 (1985), pp. 383–410.
[8] B. Csaba, M. Karpinski, and P. Krysta, Approximability of dense and sparse instances ofminimum 2-connectivity, TSP and path problems, in Proceedings of the Thirteenth Annual
ACM-SIAM Symposium on Discrete Algorithms, 2002, pp. 74–83.
[9] J. Edmonds, Maximum matching and a polyhedron with 0, 1-vertices, J. Res. Nat. Bur. Standards, Sect. B, 69 (1965), pp. 125–130.
[10] D. Fotakis and P. Spirakis, Graph properties that facilitate travelling, Electron. Colloq.
Comput. Complex., 31 (1998), pp. 1–18.
[11] H. N. Gabow, Data structures for weighted matching and nearest common ancestors with linking, in Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms,
1990, pp. 434–443.
[12] H. N. Gabow, A matroid approach to ﬁnding edge connectivity and packing arborescences, J.
Comput. Systems Sci., 50 (1995), pp. 259–273.
[13] D. Gamarnik, M. Lewenstein, and M. Sviridenko, An improved upper bound for the TSP
in cubic 3-edge-connected graphs, Oper. Res. Lett., 33 (2005), pp. 467–474.
[14] D. Hartvigsen, Extensions of Matching Theory, Ph.D. thesis, Carnegie Mellon University,
Pittsburgh, PA, 1984.
[15] D. Hartvigsen and Y. Li, Maximum cardinality simple 2-matchings in subcubic graphs, SIAM
J. Optim., 21 (2011), pp. 1027–1045.
[16] D. Hartvigsen and Y. Li, Polyhedron of triangle-free simple 2-matchings in subcubic graphs,
Math., Program., 138 (2013), pp. 43–82.
[17] W. T. Huh, Finding 2-edge connected spanning subgraphs, Oper. Res. Lett., 32 (2004), pp. 212–216.
[18] R. Jothi, B. Raghavachari, and S. Varadarajan, A 5/4-approximation algorithm for minimum 2-edge-connectivity, in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003, pp. 725–734.
[19] T. Kaiser, D. Král’, and S. Norine, Unions of perfect matchings in cubic graphs, Electron.
Notes Discrete Math., 22 (2005), pp. 341–345.
ˇ[20] T. Kaiser and R. Skrekovski,
Cycles intersecting edge-cuts of prescribed sizes, SIAM J.
Discrete Math., 22 (2008), pp. 861–874.
[21] D. R. Karger and M. S. Levine, Finding maximum ﬂows in undirected graphs seems easierthan bipartite matching, in Proceedings of the Thirtieth Annual ACM Symposium on
Theory of Computing, 1998, pp. 69–78.

FINDING 2-FACTORS CLOSER TO TSP TOURS IN CUBIC GRAPHS

939[22] Y. Kobayashi, A simple algorithm for ﬁnding a maximum triangle-free 2-matching in subcubic
graphs, Discrete Optim., 7 (2010), pp. 197–202.
[23] P. Krysta and V. S. Anil Kumar, Approximation algorithms for minimum size 2-connectivity
problems, in Proceedings of the Eighteenth Annual Symposium on Theoretical Aspects ofComputer Science, 2001, pp. 431–442.
[24] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, eds., The Traveling
Salesman Problem—A Guided Tour of Combinatorial Optimization, Wiley, Chichester,1985.
[25] H. Nagamochi and T. Ibaraki, A linear-time algorithm for ﬁnding a sparse k-connectedspanning subgraph on a k-connected graph, Algorithmica, 7 (1992), pp. 583–596.
[26] C. Papadimitriou and M. Yannakakis, The traveling salesman problem with distances one
and two, Math. Oper. Res., 18 (1993), pp. 1–11.
[27] J. Petersen, Die Theorie der regulären graphen, Acta Math., 15 (1891), pp. 193–220.
[28] T. Schönberger, Ein Beweis des Petersenschen Graphensatzes, Acta Litt. Sci. Szeged, 7(1934–1935), pp. 51–57.
[29] A. Sebő and J. Vygen, Shorter Tours by Nicer Ears: 7/5-Approximation for Graphic
TSP, 3/2 for the Path Version, and 4/3 for Two-Edge-Connected Subgraphs,
http://arxiv.org/abs/1201.1870 (2012).
[30] S. Vempala and A. Vetta, Factor 4/3 approximations for minimum 2-connected subgraphs,
in Approximation Algorithms for Combinatorial Optimization, Lecture Notes in Comput.
Sci. 1913, Springer, Berlin, 2000, pp. 262–273.
[31] O. Vornberger, Easy and Hard Cycle Covers, preprint, Universität Paderborn, Paderborn,
Germany, 1980.