arXiv:1703.03963v1 [] 11 Mar 2017

On Solving Travelling Salesman Problem with Vertex
Requisitions∗
Anton V. EREMEEV
Omsk Branch of Sobolev Institute of Mathematics SB RAS,
Omsk State University n.a. F.M. Dostoevsky
eremeev@ofim.oscsbras.ru
Yulia V. KOVALENKO
Sobolev Institute of Mathematics SB RAS,
julia.kovalenko.ya@yandex.ru

Received: / Accepted:
Abstract: We consider the Travelling Salesman Problem with Vertex Requisitions, where
for each position of the tour at most two possible vertices are given. It is known that
the problem is strongly NP-hard. The proposed algorithm for this problem has less time
complexity compared to the previously known one. In particular, almost all feasible instances
of the problem are solvable in O(n) time using the new algorithm, where n is the number of
vertices. The developed approach also helps in fast enumeration of a neighborhood in the
local search and yields an integer programming model with O(n) binary variables for the
problem.
Keywords: Combinatorial optimization, System of vertex requisitions, Local search, Integer
programming.
MSC: 90C59, 90C10.

1

INTRODUCTION

The Travelling Salesman Problem (TSP) is one of the well-known NP-hard combinatorial optimization problems [1]: given a complete arc-weighted digraph with n vertices, find
a shortest travelling salesman tour (Hamiltonian circuit) in it.
The TSP with Vertex Requisitions (TSPVR) was formulated by
A.I. Serdyukov in [2]: find a shortest travelling salesman tour, passing at i-th position
This research of the authors is supported by the Russian Science Foundation Grant (project no. 15-1110009).
∗

1

a vertex from a given subset X i , i = 1, . . . , n. A special case where |X i | = n, i = 1, . . . , n, is
equivalent to the TSP.
This problem can be interpreted in terms of scheduling theory. Consider a single machine
that may perform a set of operations X = {x1 , . . . , xn }. Each of the identical jobs requires
processing all n operations in such a sequence that the i-th operation belongs to a given
subset X i ⊆ X for all i = 1, . . . , n. A setup time is needed to switch the machine from
one operation of the sequence to another. Moreover, after execution of the last operation
of the sequence the machine requires a changeover to the first operation of the sequence to
start processing of the next job. The problem is to find a feasible sequence of operations,
minimizing the cycle time.
TSP with Vertex Requisitions where |X i | ≤ k, i = 1, . . . , n, was called k-TSP with
Vertex Requisitions (k-TSPVR) in [2]. The complexity of k-TSPVR was studied in [2]
for different values of k on graphs with small vertex degrees. In [3] A.I. Serdyukov proved
the NP-hardness of 2-TSPVR in the case of complete graph and showed that almost all
feasible instances of the problem are solvable in O(n2) time. In this paper, we propose an
algorithm for 2-TSPVR with time complexity O(n) for almost all feasible problem instances.
The developed approach also has some applications to local search and integer programming
formulation of 2-TSPVR.
The paper has the following structure. In Section 2, a formal definition of 2-TSPVR is
given. In Section 3, an algorithm for this problem is presented. In Section 4, a modification
of the algorithm is proposed with an improved time complexity and it is shown that almost
all feasible instances of the problem are solvable in time O(n). In Section 5, the developed
approach is used to formulate and enumerate efficiently a neighborhood for local search. In
Section 6, this approach allows to formulate an integer programming model for 2-TSPVR
using O(n) binary variables. The last section contains the concluding remarks.

2

PROBLEM FORMULATION AND ITS HARDNESS

2-TSP with Vertex Requisitions is formulated as follows.
Let G = (X, U)
be a complete arc-weighted digraph, where X = {x1 , . . . , xn } is the set of vertices,
U = {(x, y) : x, y ∈ X, x 6= y} is the set of arcs with non-negative arc weights ρ(x, y),
(x, y) ∈ U . Besides that, a system of vertex subsets (requisitions) X i ⊆ X, i = 1, . . . , n,
is given, such that 1 ≤ |X i | ≤ 2 for all i = 1, . . . , n.
Let F denote the set of bijections from Xn := {1, . . . , n} to X, such that f (i) ∈ X i , i =
1, . . . , n, for all f ∈ F . The problem consists in finding such a mapping f ∗ ∈ F that ρ(f ∗ ) =
n−1
P
min ρ(f ), where ρ(f ) =
ρ(f (i), f (i + 1)) + ρ(f (n), f (1)) for all f ∈ F . Later on the
f ∈F

i=1

symbol I is used for the instances of this problem.
Any feasible solution uses only the arcs that start in a subset X i and end in X i+1 for
some i ∈ {1, . . . , n} (we assume n + 1 := 1). Other arcs are irrelevant to the problem and we
assume that they are not given in a problem input I.
2-TSPVR is strongly NP-hard [3]. The proof of this fact in [3] is based on a reduction of
Clique problem to a family of instances of 2-TSPVR with integer input data, bounded by a

polynomial in problem length. Therefore, in view of sufficient condition for non-existence of
Fully Polynomial-Time Approximation Scheme (FPTAS) for strongly NP-hard problems [4],
the result from [3] implies that 2-TSPVR does not admit an FPTAS, provided that P6=NP.
The k-TSPVR with k ≥ 3 cannot be approximated with any constant or polynomial factor
of the optimum in polynomial time, unless P=NP, as follows from [5].

3

SOLUTION METHOD

Following the approach of A.I. Serdyukov [3], let us consider a bipartite graph Ḡ = (Xn , X, Ū)
where the two subsets of vertices of bipartition Xn , X have equal sizes and the set of edges
is Ū = {{i, x} : i ∈ Xn , x ∈ X i }. Now there is a one-to-one correspondence between the set
of perfect matchings W in the graph Ḡ and the set F of feasible solutions to a problem
instance I: Given a perfect matching W ∈ W of the form {{1, x1 }, {2, x2 }, . . . , {n, xn }}, this
mapping produces the tour (x1 , x2 , . . . , xn ).
An edge {i, x} ∈ Ū is called special if {i, x} belongs to all perfect matchings in the graph Ḡ.
Let us also call the vertices of the graph Ḡ special, if they are incident with special edges.
Supposing that Ḡ is given by the lists of adjacent vertices, the special edges and edges
that do not belong to any perfect matching in the graph Ḡ may be efficiently computed by
the Algorithm 1 described below. After that all edges, except for the special edges and those
adjacent to them, are slit into cycles. Note that the method of finding all special edges and
cycles in the graph Ḡ was not discussed in [3].
Algorithm 1. Finding special edges in the graph Ḡ
Step 1 (Initialization). Assign Ḡ′ := Ḡ.
Step 2. Repeat Steps 2.1-2.2 while it is possible:
Step 2.1 (Solvability test). If the graph Ḡ′ contains a vertex of degree 0 then problem I
is infeasible, terminate.
Step 2.2 (Finding a special edge). If the graph Ḡ′ contains a vertex z of degree 1, then
store the corresponding edge {z, y} as a special edge and remove its endpoints y and z from Ḡ′ .
Each edge of the graph Ḡ is visited and deleted at most once (which takes O(1) time).
The number of edges |Ū | ≤ 2n. So the time complexity of Algorithm 1 is O(n).
Algorithm 1 identifies the case when problem I is infeasible. Further we consider only
feasible instances of 2-TSPVR and bipartite graphs corresponding to them.
After the described preprocessing the resulting graph Ḡ′ is 2-regular (the degree of each
vertex equals 2) and its components are even cycles. The cycles of the graph Ḡ′ can be
computed in O(n) time using the Depth-First Search algorithm (see e.g. [6]). Note that there
are no other edges in the perfect matchings of the graph Ḡ, except for the special edges and
edges of the cycles in Ḡ′ . In what follows, q(Ḡ) denotes the number of cycles in the graph Ḡ
(and in the corresponding graph Ḡ′ ).
Each cycle j, j = 1, . . . , q(Ḡ), contains exactly two maximal (edge disjoint) perfect
matchings, so it does not contain any special edges. Every perfect matching in Ḡ is
uniquely defined by a combination of maximal matchings chosen in each of the cycles and the

graph G = ( X8, X, U )
1

x1

2

x2

3

x3

4

x4

5

x5

6

x6

7

x7

8

x8

cycle 1

special
edges

cycle 2

Figure 1: An instance I with n = 8 and system of vertex requisitions: X 1 = {x1 , x2 },
X 2 = {x1 , x2 }, X 3 = {x3 }, X 4 = {x3 , x4 }, X 5 = {x5 , x6 }, X 6 = {x6 , x7 }, X 7 = {x7 , x8 },
X 8 = {x6 , x8 }. Here the edges drawn in bold define one maximal matching of a cycle, and the
rest of the edges in the cycle define another one. The special edges are depicted by dotted lines.
The edges depicted by dashed lines do not belong to any perfect matching. The feasible solutions of the instance are f 1 = (x1 , x2 , x3 , x4 , x5 , x6 , x7 , x8 ), f 2 = (x1 , x2 , x3 , x4 , x5 , x7 , x8 , x6 ),
f 3 = (x2 , x1 , x3 , x4 , x5 , x6 , x7 , x8 ), f 4 = (x2 , x1 , x3 , x4 , x5 , x7 , x8 , x6 ).

set of all special edges (see Fig. 1). Therefore, 2-TSPVR is solvable by the following algorithm.
Algorithm 2. Solving 2-TSPVR
Step 1. Build the bipartite graph Ḡ, identify the set of special edges and cycles and find
all maximal matchings in cycles.
Step 2. Enumerate all perfect matchings W ∈ W of Ḡ by combining the maximal matchings of cycles and joining them with special edges.
Step 3. Assign the corresponding solution f ∈ F to each W ∈ W and compute ρ(f ).
Step 4. Output the result f ∗ ∈ F , such that ρ(f ∗ ) = min ρ(f ).
f ∈F

To evaluate the Algorithm 2, first note that maximal matchings in cycles are found easily
in O(n) time. Now |F | = |W| = 2q(Ḡ) so the time complexity of Algorithm 2 of solving
2-TSPVR is O(n2q(Ḡ) ), where q(Ḡ) ≤ ⌊ n2 ⌋ and the last inequality is tight.

4

IMPROVED ALGORITHM

In [3], it was shown that almost all feasible instances of 2-TSPVR have not more than n
feasible solutions and may be solved in quadratic time. To describe this result precisely, let
us give the following
Definition 1 [3] A graph Ḡ = (Xn , X, Ū) is called “good” if it satisfies the inequality
q(Ḡ) ≤ 1.1 ln(n).
Note that any problem instance I, which corresponds to a “good” graph Ḡ, has at most
2
< n0.77 feasible solutions.
Let χ̄n denote the set of “good” bipartite graphs Ḡ = (Xn , X, Ū ) , and let χn be the set
of all bipartite graphs Ḡ = (Xn , X, Ū ). The results of A.I. Serdyukov from [3] imply
1.1 ln n

Theorem 1 |χ̄n |/|χn | −→ 1 as n → ∞.
The proof of Theorem 1 from [3] is provided in the appendix for the sake of completeness.
According to the frequently used terminology (see e.g. [7]), this theorem means that almost
all feasible instances I have at most n0.77 feasible solutions and thus they are solvable in
O(n1.77 ) time by Algorithm 2.
Using the approach
from [8] we will now modify Algorithm 2 for solving 2-TSPVR in

q(Ḡ)
O q(Ḡ)2
+ n time. Let us carry out some preliminary computations before enumerating
all possible combinations of maximal matchings in cycles in order to speed up the evaluation
of objective function. We will call a contact between cycle j and cycle j ′ 6= j (or between
cycle j and a special edge) the pair of vertices (i, i + 1) (we assume n + 1 := 1) in the left-hand
part of the graph Ḡ, such that one of the vertices belongs to the cycle j and the other one
belongs to the cycle j ′ (or the special edge). A contact inside a cycle will mean a pair of
vertices in the left-hand part of a cycle, if their indices differ exactly by one, or these vertices
are (n, 1).
Consider a cycle j. If a contact (i, i + 1) is present inside this cycle, then each of the
two maximal matchings w 0,j and w 1,j in this cycle determines the i-th arc of a tour in the
graph G. Also, if the cycle j has a contact (i, i + 1) to a special edge, each of the two maximal
matchings w 0,j and w 1,j also determines the i-th arc of a tour in the graph G. For each of the
matchings w k,j , k = 0, 1, let the sum of the weights of arcs determined by the contacts inside
the cycle j and the contacts to special edges be denoted by Pjk .
If cycle j contacts to cycle j ′ , j ′ 6= j, then each combination of the maximal matchings
of these cycles determines the i-th arc of a tour in the graph G for any contact (i, i + 1)
between the cycles. If a maximal matching is chosen in each of the cycles, one can sum up
the weights of the arcs in G determined by all contacts between cycles j and j ′ . This yields
(0,0)
(0,1)
(1,0)
(1,1)
four values which we denote by Pjj ′ , Pjj ′ , Pjj ′ and Pjj ′ , where the superscripts identify
the matchings chosen in each of the cycles j and j ′ respectively.
(0,0)
(0,1)
(1,0)
(1,1)
Parameters Pj0 , Pj1 , Pjj ′ , Pjj ′ , Pjj ′ and Pjj ′ can be found as follows. Suppose that
intermediate values of Pj0 , Pj1 for j = 1, . . . , q(Ḡ) are stored in one-dimensional arrays of
(0,0)
(0,1)
(1,0)
(1,1)
size q(Ḡ), and intermediate values of Pjj ′ , Pjj ′ , Pjj ′ and Pjj ′ for j, j ′ = 1, . . . , q(Ḡ) are
stored in two-dimensional arrays of size q(Ḡ) × q(Ḡ). Initially, all of these values are assumed
to be zero and they are computed in an iterative way by the consecutive enumeration of pairs

of vertices (i, i + 1), i = 1, . . . , n − 1, and (n, 1) in the left-hand part of the graph Ḡ. When
we consider a pair of vertices (i, i + 1) or (n, 1), at most four parameters (partial sums) are
updated depending on whether the vertices belong to different cycles or to the same cycle, or
one of the vertices is special. So the overall time complexity of the pre-processing procedure
is O(q 2 (Ḡ) + n).
Now all possible combinations of the maximal matchings in cycles may be enumerated
using a Grey code (see e.g. [9]) so that the next combination differs from the previous one by
altering a maximal matching only in one of the cycles. Let the binary vector δ = (δ1 , . . . , δq(Ḡ) )
define assignments of the maximal matchings in cycles. Namely, δj = 0, if the matching w 0,j is
chosen in the cycle j; otherwise (if the matching w 1,j is chosen in the cycle j), we have δj = 1.
This way every vector δ is bijectively mapped into a feasible solution fδ to 2-TSPVR.
In the process of enumeration, a step from the current vector δ̄ to the next vector δ changes the maximal matching in one of the cycles j. The new value of objective function ρ(fδ ) may be computed via the current value ρ(fδ̄ ) by the formula ρ(fδ ) =
P
P
(δj ,δ ′ )
(δ̄j ,δ̄ ′ )
δ̄
δ
ρ(fδ̄ ) − Pj j + Pj j −
Pjj ′ j , where A(j) is the set of cycles contacting to
Pjj ′ j +
j ′ ∈A(j)

j ′ ∈A(j)

the cycle j. Obviously, |A(j)| ≤ q(Ḡ), so updating the objective function value for the next
solution requires O(q(Ḡ)) time, and the
 overall time complexity of the modified algorithm for
q(Ḡ)
solving 2-TSPVR is O q(Ḡ)2
+n .
In view of Theorem 1 we conclude that using this modification of Algorithm 2 almost all
feasible instances of 2-TSPVR are solvable in O(n0.77 ln n + n) = O(n) time.

5

LOCAL SEARCH

A local search algorithm starts from an initial feasible solution. It moves iteratively from one
solution to a better neighboring solution and terminates at a local optimum. The number of
steps of the algorithm, the time complexity of one step, and the value of the local optimum
depend essentially on the neighborhood. Note that neighborhoods, often used for the classical
TSP (e.g. k-Opt, city-swap, Lin-Kernighan [10]), will contain many infeasible neighboring
solutions if applied to 2-TSPVR because of the vertex requisition constraints.
A local search method with a specific neighborhood for 2-TSPVR may be constructed
using the relationship between the perfect matchings in the graph Ḡ and the feasible solutions.
The main idea of the algorithm consists in building a neighborhood of a feasible solution to
2-TSPVR on the basis of a Flip neighborhood of the perfect matching, represented by the
maximal matchings in cycles and the special edges.
Let the binary vector δ = (δ1 , . . . , δq(Ḡ) ) denote the assignment of the maximal matchings
to cycles as above. The set of 2q(Ḡ) vectors δ corresponds to the set of feasible solutions by a
one-to-one mapping fδ . We assume that a solution fδ′ belongs to the Exchange neighborhood
of solution fδ iff the vector δ ′ is within Hamming distance 1 from δ, i.e. δ ′ belongs to the Flip
neighborhood of vector δ.
Enumeration of the Exchange neighborhood takes O(q 2 (Ḡ)) time if the preprocessing described in Section 4 is carried out before the start of the local search (without the preprocessing
it takes O(nq(Ḡ)) operations). Therefore, for almost all feasible instances I, the Exchange
neighborhood may be enumerated in O(ln2 (n)) time.

6

MIXED INTEGER LINEAR PROGRAMMING
MODEL

The one-to-one mapping between the maximal matchings in cycles of the graph Ḡ and feasible solutions to 2-TSPVR may be also exploited in formulation of a mixed integer linear
programming model.
Recall that Pj0 (Pj1 ) is the sum of weights of all arcs of the graph G determined by the
contacts inside the cycle j and the contacts of the cycle j with special edges, when the maximal
(k,l)
matching w 0,j (w 1,j ) is chosen in the cycle j, j = 1, . . . , q(Ḡ). Furthermore, Pjj ′ is the sum
of weights of arcs in the graph G determined by the contacts between cycles j and j ′ , if the
′
maximal matchings w k,j and w l,j are chosen in the cycles j and j ′ respectively, k, l = 0, 1,
j = 1, . . . , q(Ḡ) − 1, j ′ = j + 1, . . . , q(Ḡ). These values are computable in O(n + q 2 (Ḡ)) time
as shown in Section 4.
Let us introduce the following Boolean variables:

0, if matching w 0,j is chosen in the cycle j,
dj =
1, if matching w 1,j is chosen in the cycle j,
j = 1, . . . , q(Ḡ).
The objective function combines the pre-computed arc weights for all cycles, depending
on the choice of matchings in d = (d1 , . . . , dq(Ḡ) ):
q(Ḡ)−1 q(Ḡ)


X  (0,0)
(0,1)
Pjj ′ (1 − dj )(1 − dj ′ ) + Pjj ′ (1 − dj )dj ′

X
j=1

j ′ =j+1

q(Ḡ)−1 q(Ḡ)

+

X 

X

(1,0)
Pjj ′ dj (1

− dj ′ ) +

(1,1)
Pjj ′ dj dj ′

j ′ =j+1

j=1



(1)

q(Ḡ)

+

X
j=1


Pj0 (1 − dj ) + Pj1 dj → min,

dj ∈ {0, 1}, j = 1, . . . , q(Ḡ).

(2)

Let us define supplementary real variables in order to remove non-linearity of the objective
(k)
function: for k ∈ {0, 1} we assume that pj ≥ 0 is an upper bound on the sum of weights of
arcs in the graph Ḡ determined by the contacts of the cycle j, if matching w k,j is chosen in
this cycle, i.e. dj = k, j = 1, . . . , q(Ḡ) − 1.
Then the mixed integer linear programming model has the following form:
q(Ḡ)−1 

X

q(Ḡ)
(0)
pj

+

(1)
pj

j=1



+

X
j=1


Pj0 (1 − dj ) + Pj1 dj → min,
q(Ḡ)

q(Ḡ)
(0)
pj

≥

X

j ′ =j+1

(0,0)
Pjj ′

(1 − dj − dj ′ ) +

X

j ′ =j+1

(0,1)

Pjj ′ (dj ′ − dj ) ,

(3)

j = 1, . . . , q(Ḡ) − 1,
q(Ḡ)

q(Ḡ)
(1)
pj

≥

X

(4)

(1,0)
Pjj ′

j ′ =j+1

(dj − d ) +
j′

X

(1,1)

Pjj ′ (dj + dj ′ − 1) ,

j ′ =j+1

j = 1, . . . , q(Ḡ) − 1,

(5)

pj ≥ 0, k = 0, 1, j = 1, . . . , q(Ḡ) − 1,

(6)

dj ∈ {0, 1}, j = 1, . . . , q(Ḡ).

(7)

(k)

Note that if matching w 0,j is chosen for the cycle j in an optimal solution of problem (3)(0)
(1)
(7), then inequality (4) holds for pj as equality and pj = 0. Analogously, if matching w 1,j
(1)
(0)
is chosen for the cycle j, then inequality (5) holds for pj as equality and pj = 0. Therefore,
problems (1)-(2) and (3)-(7) are equivalent because a feasible solution of one problem corresponds to a feasible solution of another problem, and an optimal solution corresponds to an
optimal solution.
The number of real variables in model (3)-(7) is (2q(Ḡ) − 2), the number of Boolean
variables is q(Ḡ). The number of constraints is O(q(Ḡ)), where q(Ḡ) ≤ ⌊ n2 ⌋. The proposed
model may be used for computing lower bound of objective function or in branch-and-bound
algorithms, even if the graph Ḡ is not “good”.
Note that there are a number of integer linear programming models in the literature
on the classical TSP, involving O(n2 ) Boolean variables. Model (3)–(7) for 2-TSPVR has
at most ⌊ n2 ⌋ Boolean variables and for almost all feasible instances the number of Boolean
variables is O(ln(n)).

7

CONCLUSION

We presented an algorithm for solving 2-TSP with Vertex Requisitions, that reduces
the time complexity bound formulated in [3]. It is easy to see that the same approach is
applicable to the problem 2-Hamiltonian Path of Minimum Weight with Vertex
Requisitions, that asks for a Hamiltonian Path of Minimum Weight in the graph G, assuming the same system of vertex requisitions as in 2-TSP with Vertex Requisitions.
Using the connection to perfect matchings in a supplementary bipartite graph and some
preprocessing we constructed a MIP model with O(n) binary variables and a new efficiently
searchable Exchange neighborhood for problem under consideration.
Further research might address the existence of approximation algorithms with constant
approximation ratio for 2-TSP with Vertex Requisitions.

References
[1] Garey, M.R., Johnson, D.S.: Computers and intractability. A guide to the theory of NPcompleteness. W.H. Freeman and Company, San Francisco, CA (1979)
[2] Serdyukov, A.I.: Complexity of solving the travelling salesman problem with requisitions
on graphs with small degree of vertices. Upravlaemye systemi. 26, 73–82 (1985) (In Russian)

[3] Serdyukov, A.I.: On travelling salesman problem with prohibitions. Upravlaemye systemi.
17, 80–86 (1978) (In Russian)
[4] Garey, M.R., Johnson, D.S.: Strong NP-completeness results: Motivation, examples, and
implications. Journal of the ACM. 25, 499–508 (1978)
[5] Serdyukov A.I.: On finding Hamilton cycle (circuit) problem with prohibitions. Upravlaemye systemi. 19, 57–64 (1979) (In Russian)
[6] Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd
edition. MIT Press (2001)
[7] Chvatal, V.: Probabilistic methods in graph theory. Annals of Operations Research. 1,
171–182 (1984)
[8] Eremeev, A., Kovalenko, J.: Optimal recombination in genetic algorithms for combinatorial optimization problems: Part II. Yugoslav Journal of Operations Research. 24 (2),
165-186 (2014)
[9] Reingold, E.M., Nievergelt, J., Deo, N.: Combinatorial algorithms: Theory and Practice.
Englewood Cliffs, Prentice-Hall (1977)
[10] Kochetov, Yu. A.: Computational bounds for local search in combinatorial optimization.
Computational Mathematics and Mathematical Physics. 48 (5), 747-763 (2008)
[11] Feller, W.: An Introduction to Probability Theory and Its Applications. Vol. 1. John
Wiley & Sons, New York, NY (1968)
[12] Riordan, J.: An Introduction to Combinatorial Analysis. John Wiley & Sons, New York,
NY (1958)

APPENDIX
Note that A.I. Serdyukov in [3] used the term block instead of term cycle, employed in Section 3
of the present paper. A block was defined in [3] as a maximal (by inclusion) 2-connected
subgraph of graph Ḡ with at least two edges. However, in each block of the graph Ḡ, the
degree of every vertex equals 2 (otherwise F = Ø because the vertices of degree 1 do not
belong to blocks and the vertex degrees are at most 2 in the right-hand part of Ḡ). So, the
notions block and cycle are equivalent in the case of considered bipartite graph Ḡ. We use the
term block in the proof of Theorem 1 below, as in the original paper [3], in order to avoid a
confusion of cycles in Ḡ with cycles in permutations of the set {1, . . . , n}.
Theorem 1 [3] |χ̄n |/|χn | −→ 1 as n → ∞.
Proof. Let Sn be the set of all permutations of the set {1, . . . , n}. Consider a random
permutation s from Sn . By ξ(s) denote the number of cycles in permutation s. It is known
n
P
1
and the
(see e.g. [11]) that the expectation E[ξ(s)] of random variable ξ(s) is equal to
i
i=1

variance V ar[ξ(s)] equals

n
P

i=1

i−1
.
i2

Let S̄n denote the set of permutations from Sn , where the

number of cycles is at most 1.1 ln(l). Then, using Chebychev’s inequality [11], we get
|S̄n |/|Sn | −→ 1 as n → ∞.

(8)

Now let Sn′ denote the set of permutations from Sn , which do not contain the cycles of
(i)
length 1, and let Sn be the set of permutations from Sn , which contain a cycle with element
i, i = 1, . . . , n. Using the principle of inclusion and exclusion [12], we obtain
|Sn \

Sn′ |

=

[

Sn(i)

1≤i≤n

X

Sn(i)

1≤i6=j6=k≤n

\

Sn(j)

\

=

n
X

Sn(i) −

i=1

X

1≤i6=j≤n

Sn(i)

\

Sn(j) +

Sn(k) − . . . = n! − Cn2 (n − 2)! + Cn3 (n − 3)! − . . . ≤
n! n!
2
2
+
= n! = |Sn |.
2
6
3
3

Therefore,

1
|Sn′ | ≥ |Sn |.
3

(9)

Combining (8) and (9), we get
|S̄n′ |/|Sn′ |

3|Sn′ \S̄n′ |
3|Sn \S¯n |
|Sn′ \S̄n′ |
≥
1
−
≥
1
−
−→ 1,
=1−
|Sn′ |
|Sn |
|Sn | n→+∞

(10)

where S̄n′ = Sn′ ∩ S¯n .
The values |χ̄n | and |χn \χ̄n | may be bounded, using the following approach. We assign
any permutation s ∈ Sl′ , l ≤ n, a set of bipartite graphs χn (s) ⊂ χn as follows. First of
all let us assign an arbitrary set of n − l edges to be special. Then the non-special vertices {i1 , i2 , . . . , il } ⊂ Xn of the left-hand part, where ij < ij+1 , j = 1, . . . , l − 1, are now
partitioned into ξ(s) blocks, where ξ(s) is the number of cycles in permutation s. Every
cycle (t1 , t2 , . . . , tr ) in permutation s corresponds to some sequence of vertices with indices
{it1 , it2 , . . . , itr } belonging to the block associated with this cycle. Finally, it is ensured that
for each pair of vertices {itj , itj+1 }, j = 1, . . . , r − 1, as well as for the pair {itr , it1 }, there
exists a vertex in the right-hand part X which is adjacent to both vertices of the pair. Except
for special edges and blocks additional edges are allowed in graphs from class χn (s). These
edges are adjacent to the special vertices of the left-hand part such that the degree of any
vertex of the left-hand part is not greater than two. Moreover, additional edges should not
lead to creating new blocks.
There are n! ways to associate vertices of the left-hand part to vertices of the righthand part, therefore the number of different graphs from class χn (s), s ∈ Sl′ , l ≤ n, is
|χn (s)| = Cnl 2ξn!
h(n, l), where function h(n, l) depends only on n and l, and ξ1 (s) is the
1 (s)
number of cycles of length two in permutation s. Division by 2ξ1 (s) is here due to the fact
that for each block that corresponds to a cycle of length two in s, there are two equivalent
ways to number the vertices in its right-hand part.

Let s = c1 c2 . . . cξ(s) be a permutation from set Sl′ , represented by cycles ci , i = 1, . . . , ξ(s),
and let cj be an arbitrary cycle of permutation s of length at least three, j = 1, . . . , ξ(s).
Permutation s may be transformed into permutation s1 ,
s1 = c1 c2 . . . cj−1 c−1
j cj+1 . . . cξ(s),

(11)

by reversing the cycle cj . Clearly, permutation s1 induces the same subset of bipartite graphs
in class χn as the permutation s does. Thus any two permutations s1 and s2 from set Sl′ ,
l ≤ n, induce the same subset of graphs in χn , if one of these permutations may be obtained
from the other one by several transformations of the form (11). Otherwise the two induced
subsets of graphs do not intersect. Besides that χn (s1 ) ∩ χn (s2 ) = ∅ if s1 ∈ Sl′1 , s2 ∈ Sl′2 ,
l1 6= l2 .
On one hand, if s ∈ S̄l′ , l ≤ n, then χn (s) ⊆ χ̄n . On the other hand, if s ∈ S̃l′ := Sl′ \S̄l′ ,
l < n, then either χn (s) ⊆ χ̄n or, alternatively, χn (s) ⊆ χn \χ̄n may hold. Therefore,
|χ̄n | ≥

n X
X
l=2 s∈S̄l′

≥

n
X

|S̄l′ |

·

l=2

|χn \χ̄n | ≤

n!
Cnl ξ1 (s) ξ(s)−ξ1 (s) h(n, l)
2
2

n!
Cnl 1.1ln(l) h(n, l)
2
n
X

l=⌊1.1ln(n)⌋

Now assuming ψ(n) =

X

s∈S̃l′

max

l=⌊1.1ln(n)⌋,...,n

n
X

≥

n!
Cnl ξ(s)
2

=

n X
X

Cnl

l=2 s∈S̄l′

|S̄l′ | · Cnl

l=⌊1.1ln(n)⌋

≤

n
X

n!
h(n, l) ≥
2ξ(s)
n!

21.1ln(l)

|S̃l′ | · Cnl

l=⌊1.1ln(n)⌋

(12)

h(n, l),

n!
21.1ln(l)

h(n, l).

(13)

|S̃l′ |/|S̄l′ | and taking into account (12), (13) and (10),

we obtain
|χn \χ̄n |
≤ ψ(n) → 0 as n → +∞.
|χ̄n |
Finally, the statement of the theorem follows from (14). Q.E.D.

(14)

