# Smoothed Complexity of SWAP in Local Graph Partitioning

Xi Chen
Columbia University
<EMAIL_ADDRESS>Supported by NSF IIS-1838154, CCF-2106429 and
CCF-2107187. Chenghao Guo
MIT
<EMAIL_ADDRESS>Supported by NSF TRIPODS program award DMS-2022448 and by
NSF Career Award CCF-1940205, CCF- 2131115. Emmanouil V. Vlatakis-Gkaragkounis
University California, Berkeley
<EMAIL_ADDRESS>Supported by Postdoctoral FODSI Simons-Fellowship.
Mihalis Yannakakis
Columbia University
<EMAIL_ADDRESS>Supported by NSF CCF-2107187 and CCF-2212233.

###### Abstract

We give the first quasipolynomial upper bound $\phi n^{\text{polylog}(n)}$ for
the smoothed complexity of the SWAP algorithm for local Graph Partitioning
(also known as Bisection Width), where $n$ is the number of nodes in the graph
and $\phi$ is a parameter that measures the magnitude of perturbations applied
on its edge weights. More generally, we show that the same quasipolynomial
upper bound holds for the smoothed complexity of the 2-FLIP algorithm for any
binary Maximum Constraint Satisfaction Problem, including local Max-Cut, for
which similar bounds were only known for $1$-FLIP. Our results are based on an
analysis of cycles formed in long sequences of double flips, showing that it
is unlikely for every move in a long sequence to incur a positive but small
improvement in the cut weight.

##  1 Introduction

_Local search_ has been a powerful machinery for a plethora of problems in
combinatorial optimization, from the classical Simplex algorithm for linear
programming to the gradient descent method for modern machine learning
problems, to effective heuristics (e.g. Kernighan-Lin) for basic combinatorial
problems such as the Traveling Salesman Problem and Graph Partitioning. A
local search algorithm begins with an initial candidate solution and then
follows a path by iteratively moving to a better neighboring solution until a
local optimum in its neighborhood is reached. The quality of the obtained
solutions depends of course on how rich is the neighborhood structure that is
explored by the algorithm. Local search is a popular approach to optimization
because of the general applicability of the method and the fact that the
algorithms typically run fast in practice. In contrast to their empirical fast
convergence, however, many local search algorithms have exponential running
time in the worst case due to delicate pathological instances that one may
never encounter in practice. To bridge this striking discrepancy, Spielman and
Teng [1] proposed the framework of _smoothed analysis_ , a hybrid of the
classical worst-case and average-case analyses. They used it to provide
rigorous justifications for the empirical performance of the Simplex algorithm
by showing its smoothed complexity to be polynomial. Since then, the smoothed
analysis of algorithms and problems from combinatorial optimization [2, 3, 4],
among many other research areas such as numerical methods [5, 6, 4, 7],
machine learning [8, 9, 10, 11] and algorithmic game theory[12, 13, 14, 15],
has been studied extensively .

In this paper we study the smoothed complexity of local search algorithms for
the classical problem of _Graph Partitioning_ (also known as _Bisection Width_
in the literature). In the problem we are given edge weights $X=(X_{e}:e\in
E_{2n})$ of a complete graph $K_{2n}=(V_{2n},E_{2n})$ with $X_{e}\in[-1,1]$,
and the goal is to find a _balanced_ partition $(U,V)$ of $V_{2n}$ into two
equal-size subsets $U$ and $V$ to minimize the weight of the corresponding cut
(i.e., the sum of weights of edges with one node in $U$ and the other node in
$V$). Graph Partitioning has been studied extensively, especially in practice.
It forms the basis of divide and conquer algorithms and is used in various
application domains, for example in laying out circuits in VLSI. It has also
served as a test bed for algorithmic ideas [16].

Given its NP-completeness [17], heuristics have been developed to solve Graph
Partitioning in practice. A commonly used approach is based on local search:
starting with an initial balanced partition, local improvements on the cut are
made iteratively until a balanced partition that mimimizes the cut within its
_neighborhood_ is reached. The simplest neighborhood is the SWAP neighborhood,
where two balanced partitions are neighbors if one can be obtained from the
other by swapping two nodes, one from each part. A locally optimal solution
under the SWAP neighborhood can be found naturally by the SWAP algorithm,
which keeps swapping two nodes as long as the swap improves the cut. A more
sophisticated neighborhood structure, which yields much better locally optimal
solutions in practice, is that of the Kernighan-Lin (KL) algorithm which
performs in each move a sequence of swaps [18].

These local search algorithms for Graph Partitioning typically converge fast
in practice. (For a thorough experimental analysis of their performance, and
comparison with simulated annealing, regarding both the quality of solutions
and the running time, see [16].) In contrast, it is also known that the worst-
case complexity is exponential. (Finding a locally optimal solution for Graph
Partitioning under the sophisticated Kernighan-Lin neighborhood, and even
under the SWAP neighborhood is complete in PLS [19, 20]. The hardness
reductions give instances on which these algorithms take exponential time to
converge.) _This significant gap in our understanding motivates us to work on
the smoothed complexity of the SWAP algorithm for Graph Partitioning in this
paper._

We work on the full perturbation model, under which edge weights are drawn
independently from a collection of distributions
$\mathcal{X}=(\mathcal{X}_{e}:e\in E_{2n})$. Each $\mathcal{X}_{e}$ is
supported on $[-1,1]$, and has its density function bounded from above by a
parameter $\phi>0$. Our goal is to understand the expected number of steps the
SWAP algorithm takes, as a function of $n$ and $\phi$, against any edge weight
distributions $\mathcal{X}$.111Note that any upper bound under the full
perturbation model applies to the alternative, simpler model where an
adversary commits to a weight $w_{e}$ for each edge and then all edge weights
are perturbed independently by a random noise $\mathcal{Z}_{e}$ (for example,
drawn uniformly from a small interval), i.e. the weights are
$\mathcal{X}_{e}=w_{e}+\mathcal{Z}_{e}$. The parameter $\phi$ in the full
perturbation model is a bound on the pdf of the perturbations
$\mathcal{Z}_{e}$. Note that the SWAP algorithm, similar to the Simplex
algorithm, is a family of algorithms since one can implement it using
different pivoting rules, deterministic or randomized, to pick the next pair
of nodes to swap when more than one pairs can improve the cut. We would like
to establish upper bounds that hold for any implementation of the SWAP
algorithm.

###  1.1 Related work: Smoothed analysis of 1-FLIP for Max-Cut

There has not been any previous analysis on SWAP under the smoothed setting,
as far as we are aware. In contrast, much progress has been made on the
smoothed analysis of the  _1-FLIP algorithm for Max-Cut_ [21, 22, 23, 24, 25].
The major challenge for the analysis of SWAP, as we discuss in more details in
Section 1.3, is to overcome substantial new obstacles posed by the richer
neighborhood structure of SWAP, which are not present in the simpler _$1$
-change neighborhood_ behind $1$-FLIP.

Recall in Max-Cut, we are given edge weights $X=(X_{e}:e\in E_{n})$ of a
complete graph $K_{n}=(V_{n},E_{n})$ with $X_{e}\in[-1,1]$ and the goal is to
find a (_not necessarily balanced_) partition of $V_{n}$ to maximize the cut.
222Since we allow weights in $[-1,1]$, maximizing the cut is the same as
minimizing the cut after negating all edge weights. Hence the only difference
of Max-Cut, from Graph Partitioning, is that the partition does not have to be
balanced. The simplest neighborhood structure for local search on Max-Cut is
the so-called _$1$ -change neighborhood_, where two partitions are neighbors
if one can be obtained from the other by moving a single node to the other
side. The $1$-FLIP algorithm finds such a locally optimal solution by keeping
moving nodes, one by one, as long as each move improves the cut. For the
structured perturbation model, where a graph $G$ (not necessarily a complete
graph) is given and only weights of edges in $G$ are perturbed, [22] showed
that the expected number of steps $1$-FLIP takes to terminate is at most $\phi
n^{\log n}$. Subsequently, the bound was improved by [23] to
$\smash{\phi\cdot\text{poly}(n)}$ for the full perturbation model, with
further improvements in [24] on the polynomial part of $n$. The upper bound of
[22] for the structured model was recently improved to $\smash{\phi
n^{\sqrt{\log n}}}$ in [25].

###  1.2 Our Contributions

We present the first smoothed analysis of the SWAP algorithm for Graph
Partitioning. Our main result for SWAP is a quasipolynomial upper bound on its
expected running time: 333We did not make an attempt to optimize the constant
$10$ in the polylog exponent.

######  Theorem 1.1.

Let $\mathcal{X}=(\mathcal{X}_{e}:e\in E_{2n})$ be distributions of edge
weights such that each $\mathcal{X}_{e}$ is supported on $[-1,1]$ and has its
density function bounded from above by a parameter $\phi>0$. Then with
probability at least $1-o_{n}(1)$ over the draw of edge weights
$X\sim\mathcal{X}$, any implementation of SWAP takes at most $\phi
n^{O(\log^{10}n)}$ steps to terminate.

The proof of Theorem 1.1 for SWAP is based on techniques we develop for a more
challenging problem: the smoothed analysis of _$2$ -FLIP for Max-Cut_.
Starting with an initial partition (not necessarily balanced), in each round,
$2$-FLIP can move either one node (like $1$-FLIP) or two nodes (not
necessarily in different parts) as long as the cut is improved. If we restrict
the algorithm to only use double flips in every move, then we call this
variant pure 2-FLIP. Feasible moves in SWAP are clearly feasible in pure
2-FLIP as well but not vice versa. Thus, an improving sequence of SWAP in the
Graph Partitioning problem is also an improving sequence of pure 2-FLIP in the
Max-Cut problem on the same instance.

We do not make again any assumption on the pivoting rule used by 2-FLIP (i.e.,
which move is selected in each step if there are multiple improving moves),
except that if both single and double flips are allowed, then the algorithm
never moves a pair of nodes when moving only one of the two nodes would yield
a better cut. Clearly, any reasonable implementation of 2-FLIP satisfies this
property. Our main result on 2-FLIP is a similar quasipolynomial upper bound
on its expected running time. The same result holds also for any
implementation of the pure 2-FLIP algorithm that performs only 2-flips. This
is the first smoothed analysis of $2$-FLIP:

######  Theorem 1.2.

Let $\mathcal{X}=(\mathcal{X}_{e}:e\in E_{n})$ be distributions of edge
weights such that each $\mathcal{X}_{e}$ is supported on $[-1,1]$ and has its
density function bounded from above by a parameter $\phi>0$. Then with
probability at least $1-o_{n}(1)$ over the draw of edge weights
$X\sim\mathcal{X}$, any implementation of the $2$-FLIP algorithm takes at most
$\phi n^{O(\log^{10}n)}$ steps to terminate.

A more general class of problems that is related to Max-Cut is the class of
Maximum Binary Constraint Satisfaction Problems (MAX 2-CSP). In a general
Max-2CSP, the input consists of a set of Boolean variables and a set of
weighted binary constraints over the variables; the problem is to find an
assignment to the variables that maximizes the weight of the satisfied
constraints. Max-Cut is the special case when every constraint is a $\neq$
(XOR) constraint. Other examples are Max 2SAT and Max Directed Cut (i.e., the
Max Cut problem on weighted directed graphs). More generally, in a Binary
Function Optimization Problem (BFOP), instead of binary constraints the input
has a set of weighted binary functions on the variables, and the objective is
to find an assignment that maximizes the sum of the weights of the functions
(see Section 7 for the formal definitions). It was shown in [25] that the
results for $1$-FLIP for Max-Cut generalize to all Max 2-CSP and BFOP
problems. We prove that this is the case also with 2-FLIP.

We say an instance of Max 2-CSP or BFOP is complete if it includes a
constraint or function for every pair of variables.

######  Theorem 1.3.

Let $I$ be an arbitrary complete instance of a MAX 2-CSP (or BFOP) problem
with $n$ variables and $m$ constraints (functions) with independent random
weights in $[-1,1]$ with density at most $\phi>0$. Then, with probability at
least $1-o_{n}(1)$ over the draw of the weights, any implementation of 2-FLIP
takes at most $m\phi n^{O(\log^{10}n)}$ steps to terminate.

For all the aforementioned problems, by controlling the tail-bound of the
failure probability, we can strengthen our analysis to derive the same bound
for the expected number of steps needed to terminate as in the standard
smoothed analysis prototype (See Corollary 3.5).

###  1.3 Our Approach

Here, we give an overview of our proof approach, focusing on the analysis of
the $2$-FLIP algorithm for Max-Cut (Theorem 1.2). Many details are omitted in
this subsection, to help the reader get an overall view of some of the key
ideas and the structure of the proof. Note that 2-FLIP clearly subsumes
1-FLIP, since it explores a much larger neighborhood structure. For example, a
2-FLIP algorithm could apply improving 1-flips as long as possible, and only
when the partition is locally optimal with respect to the 1-flip neighborhood
apply an improving 2-flip. Therefore, the complexity (whether smoothed or
worst-case) of 2-FLIP is clearly at least as large as the complexity of
1-FLIP, and could potentially be much larger. Similarly, the analysis of
2-FLIP has to subsume the analysis of 1-FLIP, but it needs to address many
more challenges, in view of the larger space of possible moves in each step
(quadratic versus linear). In a sense, it is analogous to the difference
between a two-dimensional and a one-dimensional problem.

First, let’s briefly review the approach of previous work [22] on the simpler
1-FLIP problem. Since the edge weights are in $[-1,1]$, the weight of any cut
is in $[-n^{2},n^{2}]$. For the execution of the FLIP algorithm to be long, it
must have many moves where the gain in the cut weight is very small, in
$(0,\epsilon]$ for some small $\epsilon>0$. It is easy to see that any single
move by itself has small probability ($\phi\epsilon$) of this being the case.
If different moves were uncorrelated, then the probability that a sequence
increases the weight of the cut by no more than $\epsilon$ would go down
exponentially with the length of the sequence. Of course, different moves are
correlated. However, the same effect holds if the improvements of the moves
are linearly independent in the following sense. For any sequence of the FLIP
algorithm, the _improvement vector_ of one move is the vector indexed by the
edges with entries in $\\{-1,0,1\\}$ indicating whether each edge is added or
removed from the cut as a result of the move. Most work along this line of
research is based on the following fact (see Corollary 2.1 for the formal
statement): If the rank of the set of improvement vectors is rank, then the
sequence has improvement at most $\epsilon$ with probability at most
$(\phi\epsilon)^{\textsf{rank}}$. On the other hand, if all sequences with
length at most $\Theta(n)$ have an improvement of at least $\epsilon$, then
the number of steps of FLIP is bounded by
$\Theta(n)\cdot(2n^{2}/\epsilon)=\text{poly}(n)/\epsilon$, as the total
improvement cannot exceed $2n^{2}.$ So a natural approach is to union bound
over all possible sequences of length $\Theta(n)$ and all $2^{n}$ possible
initial configurations, which yields a probability upper bound of
$2^{n}n^{\Theta(n)}(\phi\epsilon)^{\textsf{rank}}$.

Getting a quasi-polynomial complexity bound using the union bound above
requires the rank of any sequence of length $\Theta(n)$ to be at least
$\Omega(n/\log n)$. However, this is not always true (consider, e.g., a
sequence in which only $n^{0.1}$ distinct nodes moved). One key idea of [22]
is to avoid union bound over all initial configurations and only union bound
over initial configurations of _active_ nodes (nodes that move at least once
in the sequence) by looking at _arcs_. An arc is defined to be two adjacent
moves of the same node. By taking the sum of improvement vectors of the two
moves of an arc, edges that involve inactive nodes are cancelled, so the union
bound over sequences of length $\ell$ becomes
$2^{\ell}n^{\ell}(\phi\epsilon)^{\textsf{rank}_{\textsf{arcs}}}$.

To lower bound the rank of arcs of sequence $S$,
$\textsf{rank}_{\textsf{arcs}}(S)$, they proved it is at least half of the
number of nodes that appear more than once in the sequence, denoted
$V_{2}(S)$. The essential combinatorial claim made by [22] is that for any
sequence of length $\Omega(n)$, there exists a substring of length $\ell$ with
$V_{2}(S)$ at least $\Omega(\ell/\log n)$. This can be shown by bucketing arcs
by length into buckets $[2^{i},2^{i+1})$ and picking the largest bucket as
length of the substring. On average, a random substring would contain
$\Omega(\ell/\log n)$ arcs with similar length, and therefore,
$\Omega(\ell/\log n)$ arcs with distinct nodes. The similar idea is used in
Case 1 of our Section 6 to handle 1-moves (moves that flip a single node).

Now let’s return to the case of the 2-FLIP algorithm. A step now can move two
nodes at the same time, and this fact poses qualitatively new challenges to
the proof framework. Now we have to deal not just with sets (e.g., the set of
nodes that move more than once) but instead with relations (graphs). Define an
_auxiliary graph_ $H$ for the sequence of moves that contains $K_{n}$ as
vertices and an edge for each 2-move of the sequence. If we still want to
eliminate the influence of inactive nodes in the improvement vector by summing
or subtracting two moves as in the 1-FLIP case, the moves have to contain the
_exact_ same pair of nodes. This happens too sparsely in the improving
sequence of 2-FLIP to provide enough rank. To this end, we generalize the
notion of arcs to _cycles_. A cycle is a set of 2-moves of the sequence whose
corresponding edges form a cycle in $H$. But not all cycles of $H$ are useful.
We are interested only in cycles for which there is a linear combination of
the improvement vectors of the moves of the cycle that cancels all edges of
$K_{n}$ that involve an inactive node (i.e., the corresponding entry in the
linear combination is 0); these are the cycles that are useful to the rank and
we call them _dependent cycles_.

So the goal is to find a substring $S$ of length $\ell$ where we can lower
bound $\textsf{rank}_{\textsf{cycles}}(S)$ by $\ell/\text{polylog}(n)$. The
ideal case would be the case where all nodes have $O(\text{polylog}(n))$ but
at least $2$ appearances in the substring, i.e., all nodes have degree between
2 and $O(\text{polylog}(n))$ in $H$. In this case, we can repeat the following
process to find enough cycles. Find a dependent cycle in $H$, pick an edge in
$K_{n}$ that is non-zero in the improvement vector of the cycle (we call this
the _witness_ of the cycle) and delete both nodes of the witness from $H$.
This way the improvement vector of cycles of $H$ we pick in the future will
not contain witnesses from previous cycles, and improvement vectors of cycles
we pick would form a triangular matrix that has full rank. Since any node has
$O(\text{polylog}(n))$ degree in $H$, each iteration deletes
$O(\text{polylog}(n))$ edges. So the process can be repeated at least
$\Omega(\ell/\text{polylog}(n))$ times.

However, it is not hard to construct sequences with polynomial length, such
that any substring consists mostly of moves involving one high-degree node
(with degree even $\Omega(\ell)$) and one degree-$1$ node, so deleting the
high-degree node would have a significant impact on the graph and the process
can only repeat for a few rounds and lead to a few cycles. So the challenge is
to run a similar process, but reuse high-degree nodes carefully without
repeating witnesses found in previous cycles. Suppose we find a cycle $C$ with
witness edge $(u,v)$. To avoid including the edge in another cycle
$C^{\prime}$, a sufficient condition is that: (1) $u$ is not included in
$C^{\prime}$. (2) For any two adjacent edges (edges in $H$, not $K_{n}$) of
$v$ in $C^{\prime}$, $u$ never moved between the two corresponding moves of
the edges. To meet condition 1, we can delete $u$ from $H$. To meet condition
2, we can make multiple copies of $v$ in $H$ where each copy corresponds to
moves in $S$ where $u$ doesn’t move between them. We call this operation
_splitting_ since the new graph is generated by deleting and splitting the
original $H$. The new graph after splitting is denoted by _splitted auxiliary
graph_. Our algorithm for finding a large number of linearly independent
cycles can be described as repeatedly performing the following process. Find a
cycle in the splitted auxiliary graph with witness $(u,v)$ by a tree-growing
argument, delete $u$ and split the graph by creating multiple copies of $v$.
We have to choose carefully the witness edges $(u,v)$ and do the splitting, so
that the number of nodes does not proliferate in this process.

Compared to the original auxiliary graph, the number of edges deleted and the
number of new nodes introduced is proportional to the degree of $u$, so the
number of cycles for a sequence of length $\ell$ we can find in the algorithm
is bounded by $\ell/deg(u)$. To find $\ell/poly(\log n)$ cycles, we need a
window where decent amount of moves involve a node $u$ that has $deg(u)$
bounded by $poly(\log n)$. The existence of such window in an arbitrary
sequence that is long enough can be proven via a sophisticated bucketing and
counting argument.

The overall argument then for 2-FLIP is that, given a sufficiently long
sequence of improving moves (specifically, of length $n\cdot poly(\log n))$),
we can find a window (a substring) such that the rank of the arcs and cycles
in the window is within a $poly(\log n)$ factor of the length of the window.
As a consequence, with high probability the weight of the cut improves by a
nontrivial amount $\epsilon$ (1/quasi-polynomial) during this window. This can
happen at most $n^{2}/\epsilon$ times, hence the length of the execution
sequence of 2-FLIP is at most quasi-polynomial.

###  1.4 Organization of the paper.

The rest of the paper is organized as follows. Section 2 gives basic
definitions of the problems and the smoothed model, defines the central
concepts of arcs and cycles, their improvement vectors, and proves a set of
basic lemmas about them that are used throughout in the subsequent analysis.
Section 3 states the main lemma on the existence of a nice window in the move
sequence such that the arcs and cycles in the window have high rank, and shows
how to derive the main theorem from this lemma. Sections 4 and 5 prove the
main lemma in the case that all the moves are 2-moves (this is the more
challenging case). First we show in Section 4 the existence of a nice window
(in fact a large number of nice windows, since this is needed in the general
case) such that many moves in the window have the property that both nodes of
the move appear a substantial number of times in the window (at least
polylog$(n)$ times), and one of them does not appear too many times (at most a
higher polylog$(n)$). In Section 5 we show how to find in such a nice window a
large number of cycles whose improvement vectors are linearly independent.
Section 6 extends the proof of the main lemma to the general case where the
sequence of moves generated by 2-FLIP contains both 1- and 2-moves. Finally,
in Section 7 we extend the results to the class of Maximum Binary Constraint
Satisfaction and Function Optimization problems.

##  2 Preliminaries

We write $[n]$ to denote $\\{1,\ldots,n\\}$. Given two integers $a\leq b$, we
write $[a:b]$ to denote $\\{a,\ldots,b\\}$. Given
$\gamma,\gamma^{\prime}\in\\{\pm 1\\}^{n}$ we use $d(\gamma,\gamma^{\prime})$
to denote the Hamming distance between $\gamma$ and $\gamma^{\prime}$, i.e.,
the number of entries $i\in[n]$ such that $\gamma_{i}\neq\gamma_{i}^{\prime}$.

###  2.1 Local Max-Cut and the FLIP Algorithm

Let $K_{n}=(V_{n},E_{n})$ with $V_{n}=[n]$ be the complete undirected graph
over $n$ nodes. Given edge weights $X=(X_{e}:e\in E_{n})$ with
$X_{e}\in[-1,1]$, the _$k$ -local Max-Cut problem_ is to find a partition of
$V_{n}$ into two sets $V_{1}$ and $V_{2}$ such that the weight of the
corresponding cut (the sum of weights of edges with one node in $V_{1}$ and
the other in $V_{2}$) cannot be improved by moving no more than $k$ nodes to
the other set. Formally, the objective function of our interest is defined as
follows: Given any _configuration_ $\gamma\in\\{\pm 1\\}^{n}$ (which
corresponds to a partition $V_{1},V_{2}$ with $V_{1}=\\{u\in
V_{n}:\gamma(u)=-1\\}$ and $V_{2}=\\{u\in V_{n}:\gamma(u)=1\\}$), the
objective function is

$\textsf{obj}_{X}(\gamma):=\sum_{(u,v)\in
E_{n}}{X_{(u,v)}}\cdot\mathbf{1}\big{\\{}\gamma(u)\neq\gamma(v)\big{\\}}=\frac{1}{2}\sum_{(u,v)\in
E_{n}}X_{(u,v)}\cdot\big{(}1-\gamma(u)\gamma(v)\big{)}.$ (1)

Our goal is to find a configuration $\gamma\in\\{\pm 1\\}^{n}$ that is a
$k$-local optimum, i.e.,
$\textsf{obj}_{X}(\gamma)\geq\textsf{obj}_{X}(\gamma^{\prime})$ for every
configuration $\gamma^{\prime}\in\\{\pm 1\\}^{n}$ with Hamming distance no
more than $k$ from $\gamma$.

A simple local search algorithm for $k$-Local Max-Cut is the following
$k$-FLIP algorithm:

_Start with some initial configuration $\gamma=\gamma_{0}\in\\{\pm 1\\}^{n}$.
While there exists a configuration $\gamma^{\prime}$
with $d(\gamma^{\prime},\gamma)\leq k$ such that
$\emph{{obj}}_{X}(\gamma^{\prime})>\emph{{obj}}_{X}(\gamma)$, select one such
configuration $\gamma^{\prime}$ (according
to some pivoting criterion), set $\gamma=\gamma^{\prime}$ and repeat, until no
such configuration $\gamma^{\prime}$ exists. _

The execution of $k$-FLIP on $K_{n}$ with edge weights $X$ depends on both the
initial configuration $\gamma_{0}$ and the pivoting criterion used to select
the next configuration in each iteration. The larger the value of $k$, the
larger the neighborhood structure that is being explored, hence the better the
quality of solutions that is expected to be generated. However, the time
complexity of each iteration grows rapidly with $k$: there are $\Theta(n^{k})$
candidate moves, and with suitable data structures we can determine in
$O(n^{k})$ if there is an improving move and select one. Thus, the algorithm
is feasible only for small values of $k$. For $k=1$, it is the standard FLIP
algorithm. Here we are interested in the case $k=2$. We will not make any
assumption on the pivoting criterion in our results, except that we assume
that the algorithm does not choose to flip in any step two nodes when flipping
only one of them would produce a strictly better cut. This is a natural
property satisfied by any reasonable implementation of 2-FLIP. For example,
one approach (to optimize the time of each iteration) is to first check if
there is an improving 1-flip ($n$ possibilities), and only if there is none,
proceed to search for an improving 2-flip ($O(n^{2})$ possibilities). Clearly
any implementation that follows this approach satisfies the above property.
Also, the greedy approach, that examines all $O(n^{2})$ possible 1-flips and
2-flips and chooses one that yields the maximum improvement, obviously
satisfies the above property.

Our results hold also for the variant of 2-FLIP that uses only 2-flips (no
1-flips). We refer to this variant as Pure 2-FLIP.

###  2.2 Graph Partitioning and the SWAP Algorithm

In the Graph Partitioning (or Bisection Width) problem, we are given a graph
$G$ on $2n$ nodes with weighted edges; the problem is to find a partition of
the set $V$ of nodes into two equal-sized subsets $V_{1},V_{2}$ to minimize
the weight of the cut.444Since the weights can be positive or negative, there
is no difference between maximization and minimization. The Graph Partitioning
problem is usually stated as a minimization problem. As in the Max Cut
problem, in this paper we will assume the graph is complete and the edge
weights are in $[-1,1]$. A simple local search algorithm is the SWAP
algorithm: Starting from some initial partition $(V_{1},V_{2})$ with $n$ nodes
in each part, while there is a pair of nodes $u\in V_{1},v\in V_{2}$ whose
swap (moving to the other part) decreases the weight of the cut, swap $u$ and
$v$. We do not make any assumption on the pivoting rule, i.e. which pair is
selected to swap in each iteration if there are multiple pairs whose swap
improves the cut. At the end, when the algorithm terminates it produces a
locally optimal balanced partition, i.e. one that cannot be improved by
swapping any pair of nodes. The SWAP algorithm is clearly a restricted version
of Pure 2-FLIP (restricted because the initial partition is balanced, and in
each step the 2-flip must involve two nodes from different parts of the
partition).

The SWAP algorithm is the simplest local search algorithm for the Graph
Partitioning problem, but it is a rather weak one, in the sense that the
quality of the locally optimal solutions produced may not be very good. For
this reason, more sophisticated local search algorithms have been proposed and
are typically used, most notably the Kernighan-Lin algorithm [18], in which a
move from a partition to a neighboring partition involves a sequence of swaps.
If a partition has a profitable swap, then Kernighan-Lin (KL) will perform the
best swap; however, if there is no profitable swap then KL explores a sequence
of $n$ greedy steps, selecting greedily in each step the best pair of nodes to
swap that have not changed sides before in the current sequence, and if this
sequence of swaps produces eventually a better partition, then KL moves to the
best such partition generated during this sequence. A related variant, to
reduce the time cost of each iteration, was proposed by Fiduccia and Matheyses
[26]. This idea of guided deep neighborhood search is a powerful method in
local search that was introduced first in the [18] paper of Kernighan and Lin
on Graph Partitioning, and was applied subsequently successfully to the
Traveling Salesman Problem and other problems.

###  2.3 Smoothed Analysis

We focus on the $2$-FLIP algorithm from now on. Under the smoothed complexity
model, there is a family $\mathcal{X}=(\mathcal{X}_{e}:e\in E_{n})$ of
probability distributions, one for each edge in $K_{n}=(V_{n},E_{n})$. The
edge weights $X=(X_{e}:e\in E_{n})$ are drawn independently with
$X_{e}\sim\mathcal{X}_{e}$. We assume that each $\mathcal{X}_{e}$ is a
distribution supported on $[-1,1]$ and its density function is bounded from
above by a parameter $\phi>0$. (The assumption that the edge weights are in
$[-1,1]$ is no loss of generality, since they can be always scaled to lie in
that range.) Our goal is to bound the number of steps the $2$-FLIP algorithm
takes to terminate when running on $K_{n}$ with edge weights
$X\sim\mathcal{X}$, in terms of $n$ and the parameter $\phi$.

###  2.4 Move Sequences

We introduce some of the key definitions that will be used in the smoothed
analysis of $2$-FLIP.

A _move sequence_ $\mathcal{S}=(\mathcal{S}_{1},\ldots,\mathcal{S}_{\ell})$ is
an $\ell$-tuple for some $\ell\geq 1$ such that $\mathcal{S}_{i}$ is a subset
of $V_{n}$ of size either one or two. We will refer to the $i$-th move in
$\mathcal{S}$ as a _$1$ -move_ if $|\mathcal{S}_{i}|=1$ and a _$2$ -move_ if
$|\mathcal{S}_{i}|=2$, and write $\textsf{len}(\mathcal{S}):=\ell$ to denote
its length. Additionally, let $\emph{$1$-move}(\mathcal{S})$ and
$\emph{$2$-move}(\mathcal{S})$ denote the corresponding subsequence of single
flip or double flips correspondingly. We say a node $u\in V_{n}$ is _active_
in $\mathcal{S}$ if $u$ appears in $\mathcal{S}_{i}$ for some $i$, and is
_inactive_ otherwise. We write $V(\mathcal{S})\subseteq V_{n}$ to denote the
set of active nodes in $\mathcal{S}$.

Given $\gamma_{0}\in\\{\pm 1\\}^{n}$ as the initial configuration, a move
sequence $\mathcal{S}=(\mathcal{S}_{1},\ldots,\mathcal{S}_{\ell})$ naturally
induces a sequence of configurations
$\gamma_{0},\gamma_{1},\ldots,\gamma_{\ell}\in\\{\pm 1\\}^{n}$, where
$\gamma_{i+1}$ is obtained from $\gamma_{i}$ by flipping the nodes in
$\mathcal{S}_{i+1}$. We say $(\gamma_{0},\mathcal{S})$ is _improving_ with
respect to edge weights $X$ if

$\textsf{obj}_{X}(\gamma_{i})>\textsf{obj}_{X}(\gamma_{i-1}),\quad\text{for
all $i\in[\ell]$}$

and is _$\epsilon$ -improving_ with respect to edge weights $X$, for some
$\epsilon>0$, if

$\textsf{obj}_{X}(\gamma_{i})-\textsf{obj}_{X}(\gamma_{i-1})\in(0,\epsilon],\quad\text{for
all $i\in[\ell]$.}$

For each $i\in[\ell]$, the change
$\textsf{obj}_{X}(\gamma_{i})-\textsf{obj}_{X}(\gamma_{i-1})$ from the $i$-th
move $\mathcal{S}_{i}$ can be written as follows:

  1. 1.

When $\mathcal{S}_{i}=\\{u\\}$,

$\textsf{obj}_{X}(\gamma_{i})-\textsf{obj}_{X}(\gamma_{i-1})=\sum_{w\in
V_{n}:w\not=u}\gamma_{i-1}(w)\gamma_{i-1}(u)X_{(u,w)}.$ (2)

Figure 1: Example of a _1-move_ , showing edges in the cut only.

  2. 2.

When $\mathcal{S}_{i}=\\{u,v\\}$,

$\textsf{obj}_{X}(\gamma_{i})-\textsf{obj}_{X}(\gamma_{i-1})=\sum_{w\in
V_{n}:w\not\in\\{u,v\\}}(\gamma_{i-1}(w)\gamma_{i-1}(u)X_{(w,u)}+\gamma_{i-1}(w)\gamma_{i-1}(v)X_{(w,v)}).$
(3)

Figure 2: Example of a _2-move_ , showing edges in the cut only.

For each $i\in[\ell]$, we write $\textsf{imprv}_{\gamma_{0},\mathcal{S}}(i)$
to denote the improvement vector in $\\{0,\pm 1\\}^{E_{n}}$ such that

$\textsf{obj}_{X}(\gamma_{i})-\textsf{obj}_{X}(\gamma_{i-1})=\textsf{imprv}_{\gamma_{0},\mathcal{S}}(i)\cdot
X.$ (4)

Next, let $E(\mathcal{S})$ denote the set of edges $(u,v)\in E_{n}$ such that
both $u$ and $v$ are active in $\mathcal{S}$. We write
$\textsf{imprv}_{\gamma_{0},\mathcal{S}}^{*}(i)\in\\{0,\pm
1\\}^{E(\mathcal{S})}$ to denote the projection of
$\textsf{imprv}_{\gamma_{0},\mathcal{S}}(i)$ on entries that correspond to
edges in $E(\mathcal{S})$. We note that
$\textsf{imprv}_{\gamma_{0},\mathcal{S}}^{*}(i)$ only depends on the initial
configuration of active nodes $V(S)$ in $\gamma_{0}$. Given a (partial)
configuration $\tau_{0}\in\\{\pm 1\\}^{V(S)}$ of $V(S)$, we let

$\textsf{imprv}_{\tau_{0},\mathcal{S}}(i):=\textsf{imprv}^{*}_{\gamma_{0},\mathcal{S}}(i)\in\\{0,\pm
1\\}^{E(\mathcal{S})},$

where $\gamma_{0}\in\\{\pm 1\\}^{n}$ is an arbitrary (full) configuration that
is an extension of $\tau_{0}$. (To aid the reader we will always use $\gamma$
to denote a full configuration and $\tau$ to denote a partial configuration in
the paper.)

Note that if $\mathcal{S}$ is a sequence of moves generated by an execution of
the 2-FLIP algorithm then $\mathcal{S}$ must be improving, because every move
must increase the weight of the cut and therefore every $1-$ or $2-$ move is
improving. On the other hand, if every move in $\mathcal{S}$ increases the cut
weight by no more than $\epsilon$ then we can not directly guarantee that
after $poly(|\mathcal{S}|,n,1/\epsilon)$ steps the algorithm would certainly
terminate. From probabilistic perspective, in order to provide a smoothed
upper bound on the running time of 2-FLIP method, it suffices to show that it
is exponentially small probability for every move in a long enough sequence to
incur only a $o(1/poly(n))$ improvement in our objective.

Indeed, in an idealized scenario where the improvements of different moves of
a sequence were disentangled, the event for a linear-length sequence to be at
most $\epsilon-$improving would have exponentially small probability.
Unfortunately, going back to the 2-FLIP algorithm, there could be improving
steps that are strongly correlated (as an extreme situation there could be two
flips with almost the same improvement vector). Thus, as one may expect the
probability exponential decay holds only for linearly independent
$\textsf{imprv}_{\tau_{0},\mathcal{S}}(\cdot)$, introducing the necessity of
analysis of the
$\textsf{rank}\left(\\{\textsf{imprv}_{\tau_{0},\mathcal{S}}(i)|i\in\mathcal{S}^{\prime}\\}\right)$,
for some neatly chosen subset $\mathcal{S}^{\prime}$ of moves from the
sequence $\mathcal{S}$.

######  Corollary 2.1 ([22]).

Let $X_{1},...,X_{m}$ be independent real random variables and let
$f_{i}:\mathbb{R}\to[0,\phi]$ for some $\phi>0$ denote the density of $X_{i}$
for each $i\in[m]$. Additionally, let $\mathcal{C}$ be a collection of k not
necessarily linearly independent integer row vectors, namely
$\mathcal{C}=\\{V_{1},\cdots,V_{k}\\}$. Then it holds that for any interval
$I\subset\mathbb{R}$

$\Pr[F_{\epsilon}]=\Pr\left[\bigcap_{i\in[k]}\\{V_{i}\cdot X\in
I\\}\right]\leq(\phi\textsf{len}(I))^{\textsf{rank}(\mathcal{C})}$

However, one standard issue, which typically occurs with the direct usage of
improvement vectors of sequence’s moves, is their dependence also on the
initial configuration $\gamma$ of inactive nodes that do not appear in the
sequence $\mathcal{S}$. Their number may be much larger than the rank of the
active nodes, and thus considering all their possible initial values in a
union-bound will overwhelm the probability $(\phi\epsilon)^{r}$. For these
reasons, in the literature [22, 24, 25] more complex combinatorial structures
have been proposed, like pairs of (consecutive) moves of the same node.
Interestingly, for the case of 2-FLIP, new challenges have to be overcome due
to the 2-move case. To alleviate these harnesses, we introduce the idea of
dependent cycles whose role will be revealed in the case that our sequence
abounds with 2-moves.

###  2.5 Arcs and Cycles

######  Definition 2.2.

An _arc_ $\alpha$ in a move sequence
$\mathcal{S}=(\mathcal{S}_{1},\ldots,\mathcal{S}_{\ell})$ is an ordered pair
$(i,j)$ with $i<j\in[\ell]$ such that
$\mathcal{S}_{i}=\mathcal{S}_{j}=\\{u\\}$ for some node $u\in V_{n}$ and for
any $i<k<j$, $\mathcal{S}_{k}\not=\\{u\\}$.

Let $\tau_{0}\in\\{\pm 1\\}^{V(\mathcal{S})}$ be a configuration of active
nodes in $\mathcal{S}$, and let $\tau_{0},\tau_{1},\ldots,\tau_{\ell}\in\\{\pm
1\\}^{V(\mathcal{S})}$ be the sequence of configurations induced by
$\mathcal{S}$, i.e., $\tau_{i}$ is obtained from $\tau_{i-1}$ by flipping
nodes in $\mathcal{S}_{i}$. We make the following observation:

######  Lemma 2.3.

For any configuration $\gamma_{0}\in\\{\pm 1\\}^{n}$ that is an extension of
$\tau_{0}$, letting $\gamma_{0},\gamma_{1},\ldots,\gamma_{\ell}\in\\{\pm
1\\}^{n}$ be the sequence of configurations induced by $\mathcal{S}$ and
letting
$w[u,i,j]:=\gamma_{i}(u)\cdot\emph{{imprv}}_{\gamma_{0},\mathcal{S}}(i)-\gamma_{j}(u)\cdot\emph{{imprv}}_{\gamma_{0},\mathcal{S}}(j)$,
we have that

$(w[u,i,j]_{e})_{e\in
E_{n}}=\begin{cases}(\tau_{i}(u)\cdot\emph{{imprv}}_{\tau_{0},\mathcal{S}}(i)-\tau_{j}(u)\cdot\emph{{imprv}}_{\tau_{0},\mathcal{S}}(j))_{e}&\text{
for every entry $e\in E(\mathcal{S})$,}\\\ 0&\text{ otherwise.}\end{cases}$

for any arbitrary choice of $u\in V(\mathcal{S})$.

Motivated by Lemma 2.3, we define for an arc $\alpha=(i,j)$ of a node $u$,

$\textsf{imprv}_{\tau_{0},\mathcal{S}}(\alpha):=\tau_{i}(u)\cdot\textsf{imprv}_{\tau_{0},\mathcal{S}}(i)-\tau_{j}(u)\cdot\textsf{imprv}_{\tau_{0},\mathcal{S}}(j)\in\mathbb{Z}^{E(\mathcal{S})}.$
(5)

Let $\textsf{arcs}(\mathcal{S})$ denote the set of all arcs in $\mathcal{S}$.
We will be interested in the rank of

$Q_{\textsf{arcs}}:=\Big{\\{}\textsf{imprv}_{\tau_{0},\mathcal{S}}(\alpha):\alpha\in\textsf{arcs}(\mathcal{S})\Big{\\}}$
(6)

It is easy to show that the rank does not depend on the choice of $\tau_{0}$
so we will denote it by $\textsf{rank}_{\textsf{arcs}}(\mathcal{S})$.

######  Lemma 2.4.

The rank of the set of vectors in (6) does not depend on the choice of
$\tau_{0}$.

######  Definition 2.5.

A _cycle_ $C$ in a move sequence
$\mathcal{S}=(\mathcal{S}_{1},\ldots,\mathcal{S}_{\ell})$ is an ordered tuple
$C=(c_{1},\ldots,c_{t})$ for some $t\geq 2$ such that $c_{1},\cdots c_{t}$ are
distinct, and $\mathcal{S}_{c_{j}}=\\{u_{j},u_{j+1}\\}$ for all $j\in[t-1]$
and $\mathcal{S}_{c_{t}}=\\{u_{t},u_{1}\\}$ for some nodes
$u_{1},\ldots,u_{t}\in V_{n}$. (Every $\mathcal{S}_{c_{j}}$ is a $2$-move. The
same vertex may appear in multiple $\mathcal{S}_{c_{j}}$’s).

######  Definition 2.6.

Given a configuration $\tau_{0}\in\\{\pm 1\\}^{V(\mathcal{S})}$, we say a
cycle $C=(c_{1},\ldots,c_{t})$ in $\mathcal{S}$ is _dependent_ with respect to
$\tau_{0}$ if there exists $b\in\\{\pm 1\\}^{t}$ such that

$\text{For all $j\in[t-1]$ we have that
}b_{j}\cdot\tau_{c_{j}}(u_{j+1})+b_{j+1}\cdot\tau_{c_{j+1}}(u_{j+1})=0\text{
and }b_{t}\cdot\tau_{c_{t}}(u_{1})+b_{1}\cdot\tau_{c_{1}}(u_{1})=0,$

where $\tau_{0},\tau_{1},\ldots,\tau_{\ell}$ are configurations induced by
$\mathcal{S}$ starting from $\tau_{0}$.

We note that such a vector $b$, if it exists, it has the form
$b=b_{1}\cdot\left(1,\cdots,(-1)^{k-1}{\prod_{i\in[2:k]}\tau_{c_{i-1}}(u_{i})}{\tau_{c_{i}}(u_{i})},\cdots\right)^{\top}$
and hence it is unique if we further require $b_{1}=1$. After elimination of
the above equations, we see the following equivalent criterion:

######  Remark 2.7 (Dependence Criterion).

A cycle $C$ is _dependent_ $\Leftrightarrow$
$(-1)^{t}=\tau_{c_{t}}(u_{1})\tau_{c_{1}}(u_{1})\cdot{\prod_{i=2}^{t}\tau_{c_{i-1}}(u_{i})}{\tau_{c_{i}}(u_{i})}.$

We will refer to the unique vector $b\in\\{\pm 1\\}^{t}$ as the _cancellation
vector_ of $C$. Notice that whether a cycle $C$ in $\mathcal{S}$ is dependent
or not actually does not depend on the choice of $\tau_{0}$.

######  Lemma 2.8.

If a cycle $C$ of $\mathcal{S}$ is dependent with respect to some
$\tau_{0}\in\\{\pm 1\\}^{V(\mathcal{S})}$ using $b$ as its cancellation
vector, then it is dependent with respect to every configuration
$\tau_{0}^{\prime}\in\\{\pm 1\\}^{V(\mathcal{S})}$ using the same $b$ as its
cancellation vector.

As a result, we can refer to cycles of $\mathcal{S}$ as dependent cycles
without specifying a configuration $\tau_{0}$; the same holds for cancellation
vectors. Next we prove a lemma that is similar to Lemma 2.3 for arcs:

######  Lemma 2.9.

Let $C=(c_{1},\ldots,c_{t})$ be a dependent cycle of $\mathcal{S}$ and let $b$
be its cancellation vector. Then for any configurations $\tau_{0}\in\\{\pm
1\\}^{V(\mathcal{S})}$ and $\gamma_{0}\in\\{\pm 1\\}^{n}$ such that
$\gamma_{0}$ is an extension of $\tau_{0}$, letting
$w[C]:=\sum_{j\in[t]}b_{j}\cdot\emph{{imprv}}_{\gamma_{0},\mathcal{S}}(c_{j}),$
we have that

$(w[C]_{e})_{e\in
E_{n}}=\begin{cases}(\sum_{j\in[t]}b_{j}\cdot\emph{{imprv}}_{\tau_{0},\mathcal{S}}(c_{j}))_{e}&\text{
for every entry $e\in E(\mathcal{S})$,}\\\ 0&\text{ otherwise.}\end{cases}$

Given $\tau_{0}\in\\{\pm 1\\}^{V(\mathcal{S})}$ and a dependent cycle $C$ of
$\mathcal{S}$ with $b$ as its cancellation vector, we define

$\textsf{imprv}_{\tau_{0},\mathcal{S}}(C):=\sum_{j\in[t]}b_{j}\cdot\textsf{imprv}_{\tau_{0},\mathcal{S}}(c_{j}).$
(7)

Let $\textsf{cycles}(\mathcal{S})$ denote the set of all dependent cycles in
$\mathcal{S}$. We will be interested in the rank of

$Q_{\textsf{cycles}}:=\Big{\\{}\textsf{imprv}_{\tau_{0},\mathcal{S}}(C):C\in\textsf{cycles}(\mathcal{S})\Big{\\}}$
(8)

Similarly we note that the rank does not depend on the choice of $\tau_{0}$ so
we denote it by $\textsf{rank}_{\textsf{cycles}}(\mathcal{S})$.

######  Lemma 2.10.

The rank of the set of vectors in (8) does not depend on the choice of
$\tau_{0}$.

For the sake of readability we defer the proofs of initial configuration
invariance for the rank of improvement vectors of arcs and cycles to Appendix
B. Having defined the sets of $\textsf{arcs}(\mathcal{S})$ and
$\textsf{cycles}(\mathcal{S})$, we conclude this section by showing that for a
fixed parameter $\epsilon>0$, a move sequence $\mathcal{S}$ and an initial
configuration $\tau_{0}\in\\{\pm 1\\}^{V(\mathcal{S})}$, if either
$\textsf{rank}_{\textsf{arcs}}(\mathcal{S})$ or
$\textsf{rank}_{\textsf{cycles}}(\mathcal{S})$ is high, then most likely (over
$X\sim\mathcal{X}$) $(\gamma_{0},\mathcal{S})$ is not $\epsilon$-improving for
every $\gamma_{0}\in\\{\pm 1\\}^{n}$ that is an extension of $\tau_{0}$.

######  Lemma 2.11.

Let $\epsilon>0$. With probability at least

$1-\left(2\textsf{len}(\mathcal{S})\cdot\phi\epsilon\right)^{\max\big{(}\emph{{rank}}_{\emph{{arcs}}}(\mathcal{S}),\hskip
1.42271pt\emph{{rank}}_{\emph{{cycles}}}(\mathcal{S})\big{)}}$

over $X\sim\mathcal{X}$, we have that $(\gamma_{0},\mathcal{S})$ is not
$\epsilon$-improving for every $\gamma_{0}\in\\{\pm 1\\}^{n}$ that is an
extension of $\tau_{0}$.

###### Proof.

Let $\mathcal{E}_{moves}$ be the event of a given $(\gamma_{0},\mathcal{S})$
being $\epsilon$-improving with respect to edge weights $X$, for some fixed
$\epsilon>0$:

$\mathcal{E}_{moves}:\left\\{\textsf{imprv}_{\gamma_{0},\mathcal{S}}(i)\cdot
X\in(0,\epsilon],\quad\text{for all $i\in[\ell]$}\right\\}$

where $\textsf{imprv}_{\gamma_{0},\mathcal{S}}(i)$ correspond to the
improvement vector of $\mathcal{S}_{i}$ move(See (2),(3)). Now, notice that
the improvement vector of an arc (See (5)) or of a dependent cycle (See (7))
can be written as the $\\{-1,0,1\\}$ sum of all the improvement vectors of
either 1 or 2-moves in $\mathcal{S}$. Thus, we define the corresponding event
for cycles and arcs for a given sequence $(\gamma_{0},\mathcal{S})$ with
respect to edge weights $X$:

$\mathcal{E}_{arcs/cycles}:\left\\{\textsf{imprv}_{\gamma_{0},\mathcal{S}}(\beta)\cdot
X\in[-\textsf{len}(\mathcal{S})\epsilon,\textsf{len}(\mathcal{S})\epsilon],\quad\text{for
any
$\beta\in\textsf{arcs}(\mathcal{S})/\textsf{cycles}(\mathcal{S})$}\right\\}$

So it is easy to see that $\mathcal{E}_{moves}$ implies
$\mathcal{E}_{arcs/cycles}$, or equivalently
$\Pr[\mathcal{E}_{moves}]\leq\min\\{\Pr[\mathcal{E}_{arcs}],\Pr[\mathcal{E}_{cycles}]\\}$.
Thus, by leveraging Corollary 2.1 for vectors in $Q_{\textsf{arcs}}$ and
$Q_{\textsf{cycles}})$, we get that:

$\Pr[\text{$(\gamma_{0},\mathcal{S})$ being an $\epsilon$-improving
sequence}]\leq\left(2\textsf{len}(\mathcal{S})\cdot\phi\epsilon\right)^{\max\big{(}\emph{{rank}}_{\emph{{arcs}}}(\mathcal{S}),\hskip
1.42271pt\emph{{rank}}_{\emph{{cycles}}}(\mathcal{S})\big{)}}$

This finishes the proof of the lemma.∎

##  3 Main Lemma and the Proof of Theorem 1.2 and Theorem 1.1

We start with the definition of _valid_ move sequences:

######  Definition 3.1.

We say a move sequence
$\mathcal{S}=(\mathcal{S}_{1},\ldots,\mathcal{S}_{\ell})$ is _valid_ if it
satisfies the following property: For every $i<j\in[\ell]$, at least one node
$w\notin\mathcal{S}_{i}$ appears an odd number of times in
$\mathcal{S}_{i},\ldots,\mathcal{S}_{j}$.

######  Lemma 3.2.

The move sequence generated by 2-FLIP (or by pure 2-FLIP), for any pivoting
rule and any instance, is valid .

###### Proof.

Let $\mathcal{S}$ be a move sequence generated by 2-FLIP (or pure 2-FLIP). If
there are two moves $\mathcal{S}_{i},\mathcal{S}_{j}$, $i\leq j$, such that no
node appears an odd number of times in
$\mathcal{S}_{i},\dots,\mathcal{S}_{j}$, then the configurations before
$\mathcal{S}_{i}$ and after $\mathcal{S}_{j}$ are the same, contradicting the
fact that all the moves increase the weight of the cut. Therefore, the set $O$
of nodes that appear an odd number of times in
$\mathcal{S}_{i},\dots,\mathcal{S}_{j}$ is nonempty. Suppose that $i<j$ and
$O\subseteq\mathcal{S}_{i}$. If $O=\mathcal{S}_{i}$, then the set of nodes
that appear an odd number of times in
$\mathcal{S}_{i+1},\dots,\mathcal{S}_{j}$ would be empty, a contradiction to
the above property. Therefore, $O\neq\mathcal{S}_{i}$.

In the case of pure 2-FLIP, since all moves are 2-flips, $O$ has even size,
and hence $O\neq\emptyset$ and $O\neq\mathcal{S}_{i}$ imply the claim.

In the case of 2-FLIP, $O\neq\emptyset$, $O\neq\mathcal{S}_{i}$ and
$O\subseteq\mathcal{S}_{i}$ imply that $\mathcal{S}_{i}$ has size 2, say
$\mathcal{S}_{i}=\\{u,v\\}$ and $O=\\{u\\}$ or $O=\\{v\\}$. If $O=\\{u\\}$
then the configuration $\gamma_{j}$ differs from $\gamma_{i-1}$ only in that
node $u$ is flipped. Thus, at configuration $\gamma_{i-1}$, flipping node $u$
results in configuration $\gamma_{j}$ which has strictly greater cut than the
configuration $\gamma_{i}$ that results by flipping the pair $\\{u,v\\}$,
contradicting our assumption about 2-FLIP. A similar argument holds if
$O=\\{v\\}$. In either case we have a contradiction to
$O\subseteq\mathcal{S}_{i}$. The claim follows. ∎

Given a move sequence $\mathcal{S}$, a _window_ $W$ of $\mathcal{S}$ is a
substring of $\mathcal{S}$, i.e., $W=(\mathcal{S}_{i},\ldots,\mathcal{S}_{j})$
for some $i<j\in[\ell]$ (so $W$ itself is also a move sequence). Our main
technical lemma below shows that every long enough valid move sequence has a
window $W$ such that either $\textsf{rank}_{\textsf{arcs}}(W)$ or
$\textsf{rank}_{\textsf{cycles}}(W)$ is large relative to $\textsf{len}(W)$.

######  Lemma 3.3.

Let $\mathcal{S}$ be a valid move sequence with $\emph{{len}}(\mathcal{S})\geq
n\log^{10}n$. Then $\mathcal{S}$ has a window $W$ such that

$\max\Big{(}\emph{{rank}}_{\emph{{arcs}}}(W),\emph{{rank}}_{\emph{{cycles}}}(W)\Big{)}\geq\Omega\left(\frac{\emph{{len}}(W)}{\log^{10}n}\right).$
(9)

We prove Lemma 3.3 when $\mathcal{S}$ consists of $2$-moves only in Section 4
and 5, and then generalize the proof to work with general move sequences in
Section 6. Assuming Lemma 3.3, we use it to establish our main theorem,
restated below:

See 1.2

###### Proof.

Let $\epsilon>0$ be specified as follows:

$\epsilon:=\frac{1}{\phi n^{c_{1}\log^{10}n}}$

for some large enough constant $c_{1}>0$ to be specified later. We write
$\mathcal{F}$ to denote the following event on the draw of edge weights
$X\sim\mathcal{X}$:

> Event $\mathcal{F}$: For every move sequence $W$ of length at most
> $n\log^{10}n$ such that (letting $a>0$ be the constant hidden in (9))
>
>
> $\max\Big{(}\textsf{rank}_{\textsf{arcs}}(W),\textsf{rank}_{\textsf{cycles}}(W)\Big{)}\geq\frac{a}{\log^{10}n}\cdot\textsf{len}(W).$
> (10)
>
> and every configuration $\gamma_{0}\in\\{\pm 1\\}^{n}$, $(\gamma_{0},W)$ is
> not $\epsilon$-improving with respect to $X$.

We break the proof of the theorem into two steps. First we show that
$\mathcal{F}$ occurs with probability at least $1-o_{n}(1)$. Next we show that
when $\mathcal{F}$ occurs, any implementation of $2$-FLIP must terminate in at
most $\phi n^{O(\log^{10}n)}$ many steps.

For the first step, we apply Lemma 2.11 on every move sequence $W$ of length
at most $n\log^{10}n$ that satisfies (10) and every configuration
$\tau_{0}\in\\{\pm 1\\}^{V(W)}$. It then follows from a union bound that
$\mathcal{F}$ occurs with probability at least

$1-\sum_{\ell\in[n\log^{10}n]}n^{2\ell}\cdot
2^{2\ell}\cdot(\ell\phi\epsilon)^{\frac{a\ell}{\log^{10}n}}=1-\sum_{\ell\in[n\log^{10}n]}\left((2n)^{\frac{2\log^{10}n}{a}}\cdot\ell\phi\epsilon\right)^{\frac{a\ell}{\log^{10}n}}=1-o_{n}(1),$

where the factor $n^{2\ell}$ is an upper bound for the number of $W$ of length
$\ell$ and $2^{2\ell}$ is an upper bound for the number of configurations
$\tau_{0}$ since $|V(W)|\leq 2\ell$. The last equation follows by setting the
constant $c_{1}$ sufficiently large.

For the second step, we assume that the event $\mathcal{F}$ occurs, and let
$\gamma_{0},\ldots,\gamma_{N}\in\\{\pm 1\\}^{n}$ be a sequence of $N$
configurations that is the result of the execution of some implementation of
$2$-FLIP under $X$. Let $\mathcal{S}=(\mathcal{S}_{1},\ldots,\mathcal{S}_{N})$
denote the move sequence induced by $\gamma_{0},\ldots,\gamma_{N}$. So
$(\gamma_{0},\mathcal{S})$ is improving with respect to edge weights $X$. By
Lemma 3.2, $\mathcal{S}$ is a valid sequence.

We use the event $\mathcal{F}$ to bound the length of $\mathcal{S}$. Because
of $\mathcal{F}$ and that $\mathcal{S}$ is a valid move sequence, it follows
from Lemma 3.3 that the objective function gets improved by at least
$\epsilon$ for every $n\log^{10}n$ consecutive moves in $\mathcal{S}$. Given
that the objective function lies between $[-n^{2},n^{2}]$, we have

$\textsf{len}(\mathcal{S})\leq n\log^{10}n\cdot\frac{2n^{2}}{\epsilon}\leq\phi
n^{O(\log^{10}n)}.$ (11)

This finishes the proof of the theorem. ∎

######  Corollary 3.4.

Under the same setting of Theorem 1.2, the same result holds for Pure 2-FLIP.

###### Proof.

The only property of the sequence of moves used in the proof of Theorem 1.2 is
that it is a valid sequence, and this property holds for Pure 2-FLIP as well.
∎

Notice that by twining the constant $c_{1}$ in the exponent, we can control
the tail-bound of the failure probability. Thus, we can strengthen our proof
to get the same bound for the expected number of steps needed to terminate as
in the standard smoothed analysis prototype :

######  Corollary 3.5.

Under the same setting of Theorem 1.2, any implementation of the 2-FLIP
algorithm (or Pure 2-FLIP) takes at most $\phi n^{O\left(\log^{10}n\right)}$
many steps to terminate on expectation.

###### Proof.

We let $\mathcal{F}_{\epsilon}$ denote the event $\mathcal{F}$ in the proof of
Theorem 1.2 with a specified $\epsilon>0$. Let $\epsilon_{0}=1/\left(\phi\cdot
n^{c_{1}\log^{10}n}\right)$, where $c_{1}>0$ is a constant to be fixed
shortly. For any $\epsilon<\epsilon_{0}$, we have that

$\displaystyle\Pr[\lnot\mathcal{F}_{\epsilon}]$
$\displaystyle\leq\sum_{\ell\in[n\log^{10}n]}n^{2\ell}\cdot
2^{2\ell}\cdot(\ell\phi\epsilon)^{\max\Big{(}\emph{{rank}}_{\emph{{arcs}}}(W),\emph{{rank}}_{\emph{{cycles}}}(W)\Big{)}}\leq\sum_{\ell\in[n\log^{10}n]}n^{2\ell}\cdot
2^{2\ell}\cdot(\ell\phi\epsilon\cdot\frac{\epsilon_{0}}{\epsilon_{0}})^{\lceil\frac{a\ell}{\log^{10}n}\rceil}$
$\displaystyle\leq\sum_{\ell\in[n\log^{10}n]}n^{2\ell}\cdot
2^{2\ell}\cdot\left(\ell\phi\epsilon_{0}\right)^{\lceil\frac{a\ell}{\log^{10}n}\rceil}\cdot(\frac{\epsilon}{\epsilon_{0}})^{\lceil\frac{a\ell}{\log^{10}n}\rceil}\leq\sum_{\ell\in[n\log^{10}n]}\frac{1}{n^{3}}\left(\frac{\epsilon}{\epsilon_{0}}\right)^{\lceil\frac{a\ell}{\log^{10}n}\rceil}\leq\frac{\epsilon}{c_{2}n\epsilon_{0}}$

where $c_{1}=2+6/a$ (letting $a>0$ be the constant hidden in (9)) and
$c_{2}=10^{8}$. From the proof of Theorem 1.2, conditionally to the event
$\mathcal{F}_{\epsilon}$ for any $\epsilon\leq\epsilon_{0}$,
$\textsf{len}(\mathcal{S})\leq
L(\epsilon):=\tfrac{2n^{3}\log^{10}n}{\epsilon}$. Notice that for any
$\epsilon(\rho):=\epsilon_{0}/\rho$, $L(\epsilon(\rho))=\rho L(\epsilon_{0})$.
Thus, the probability that $\textsf{len}(\mathcal{S})$ is larger than
$cL(\epsilon)$ for any $\rho\geq 1$ is

$\Pr[\textsf{len}(\mathcal{S})>\rho L(\epsilon)]\leq\Pr[\lnot
F_{\epsilon_{0}/\rho}]\leq\frac{1/\rho}{c_{2}\cdot n}.$

Note that $L$ is always trivially bounded by the total number of
configurations, $2^{n}$. Therefore, we have

$\displaystyle\mathbb{E}[\textsf{len}(\mathcal{S})]$
$\displaystyle=\sum_{s=1}^{2^{n}}\Pr[\textsf{len}(\mathcal{S})\geq
s]\leq\sum_{s=1}^{\lceil L(\epsilon_{0})\rceil}\Pr[L\geq s]+\sum_{s=\lceil
L(\epsilon_{0})\rceil}^{2^{n}}\Pr[L\geq s]\leq L(\epsilon_{0})+\sum_{s=\lceil
L(\epsilon_{0})\rceil}^{2^{n}}\Pr[L\geq s]$ $\displaystyle\leq
L(\epsilon_{0})+\sum_{s=\lceil
L(\epsilon_{0})\rceil}^{2^{n}}\Pr[L\geq\tfrac{s}{L(\epsilon_{0})}\cdot
L(\epsilon_{0})]\leq L(\epsilon_{0})+\sum_{s=\lceil
L(\epsilon_{0})\rceil}^{2^{n}}\frac{L(\epsilon_{0})/s}{c_{2}n}=O(n)\cdot
L(\epsilon_{0})=\phi n^{O(\log^{10}n)}.\vspace{0.1cm}$

This finishes the proof of Corollary 3.5. ∎

The same results hold for the Graph Partitioning problem and the SWAP
neighborhood.

See 1.1

###### Proof.

Every move sequence $\mathcal{S}$ generated by SWAP (for any pivoting rule,
any weights, and any initial balanced partition) is also a legal move sequence
for Pure 2-FLIP on the same instance, except that the sequence may be
incomplete for Pure 2-FLIP, that is, the final partition may not be locally
optimal for Pure 2-FLIP, since there may be a 2-move (but not a swap) that
improves the weight of the cut (the resulting partition would not be
balanced), and Pure 2-FLIP would continue and produce a longer sequence.
Hence, the number of steps of SWAP is upper bounded by the number of steps of
Pure 2-FLIP, and thus it is at most $\phi n^{O\left(\log^{10}n\right)}$ with
probability $1-o_{n}(1)$, as well as in expectation. ∎

##  4 Windows in a Valid Sequence of $2$-Moves

We will start with the proof of Lemma 3.3 for the case when $\mathcal{S}$
consists of $2$-moves only in Section 4 and 5, and generalize it to deal with
general move sequences in Section 6.

We start with a combinatorial argument about sets and subsequences of $[N]$,
where $N=poly(n)$ for any polynomial at $n$. Let $I$ be a subset of $[N]$ with
$|I|\geq\log^{10}n$. Intuitively, later in this section $I$ will be chosen to
be the set $I_{u}$ representing the appearances of some frequently appeared
active node $u\in V(\mathcal{S})$ in a move sequence $\mathcal{S}$. We will
write $\textsf{order}(i)$ to denote the order of $i\in I$. In other words, the
smallest index in $I$ has order $1$ and the largest index in $I$ has order
$|I|$. To give an example if $I=\\{2,5,9,11\\}$ then
$\textsf{order}(2)=1,\textsf{order}(5)=2$ and so on. Let $\delta=0.01$. We
start by quantifying how much large windows centered around an index $i\in I$
should be to cover the majority of a set $I$. Afterwards, we present the
combinatorial lemmas about subset $I$.

######  Definition 4.1.

Let $I\subseteq[N]$. We say an index $i\in I$ is _$\ell$ -good_ for some
positive integer $\ell$ if

$\Big{[}i-\lceil(1+2\delta)L^{\prime}\rceil:i+\lceil(1+2\delta)L^{\prime}\rceil\Big{]}\subseteq[N],\quad\text{where
$L^{\prime}=\lceil(1+\delta)^{\ell-1}\rceil$}$

and $I$ satisfies

$\Big{|}I\cap[i-L^{\prime}:i+L^{\prime}]\Big{|}\geq\log^{3}n\quad\text{and}\quad\Big{|}I\cap\Big{[}i-\lceil(1+2\delta)L^{\prime}\rceil:i+\lceil(1+2\delta)L^{\prime}\rceil\Big{]}\Big{|}\leq\log^{7}n.$
(12)

If there exists no such constant $\ell$, we call the corresponding index
_bad_.

$i$$L^{\prime}$$W=$$\underbrace{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ }$$\underbrace{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
}$$i$$L^{\prime}$$W^{\prime}=$$\underbrace{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }$$\underbrace{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \
}$$\lceil(1+2\delta)L^{\prime}\rceil$$\lceil(1+2\delta)L^{\prime}\rceil$
Figure 3: Two examples of windows whose intersection in $I$ is between
$[\log^{3}n,\log^{7}n]$.

######  Remark 4.2.

Some motivation behind the definition 4.1: When $i\in I$ is $\ell$-good
(letting $L=L^{\prime}+\lceil(1+2\delta)L^{\prime}\rceil+1$ and
$L^{\prime}=\lceil(1+\delta)^{\ell-1}\rceil$), it implies that all the
$\lceil(1+2\delta)L^{\prime}\rceil-L^{\prime}\geq 2\delta
L^{\prime}=\Omega(L)$555Indeed, by definition
$L=L^{\prime}+1+\lceil(1+2\delta)L^{\prime}\rceil\leq
2((1+\delta)L^{\prime}+1)\leq 2((1+\delta)L^{\prime}+1)\leq
2(2+\delta)L^{\prime}$, since $L^{\prime}\geq 1$ windows $W$ of length $L$,
i.e., those start at
$i-\lceil(1+2\delta)L^{\prime}\rceil,\ldots,i-L^{\prime}$, satisfy

$i\in W,\quad\big{|}I\cap
W\big{|}\geq\log^{3}n\quad\text{and}\quad\big{|}I\cap W\big{|}\leq\log^{7}n.$

######  Remark 4.3.

By definition 4.1, $\ell$ can get at most $\log_{1+\delta}N=\Theta(\log n)$,
for any $N=poly(n)$.

######  Lemma 4.4.

Suppose $I$ is a subset of $[N]$ with $|I|\geq{\log^{8}n}$. Then at least a
$(1-O(1/\log n))$-fraction of $i\in I$ is $\ell_{i}$-good for some nonnegative
integer $\ell_{i}$.

###### Proof.

We start by defining an $\ell_{i}$ for each $i\in I$ (except for the smallest
$\lceil\log^{7}n\rceil$ indices and the largest $\lceil\log^{7}n\rceil$
indices in $I$, which are negligible since $|I|\geq\log^{8}n$) and then show
that most $i\in I$ is $\ell_{i}$-good. Let $I^{\prime}$ be the subset of $I$
after removing the smallest $\lceil\log^{7}n\rceil$ indices and the largest
$\lceil\log^{7}n\rceil$ indices in $I$. For each $i\in I^{\prime}$, let

  * •

$j\in I^{\prime}$ be the index in $I^{\prime}$ of order
$\textsf{order}(i)-\lfloor\log^{7}n/2\rfloor+1$,

  * •

$k\in I^{\prime}$ be the index in $I^{\prime}$ of order
$\textsf{order}(i)+\lfloor\log^{7}n/2\rfloor-1$.

  * •

$\Delta$ be the minimum distance between index $i$ and indices $j,k$,
$\Delta=\min(i-j,k-i)$ and

  * •

$\ell_{i}$ be the largest integer such that
$\lceil(1+2\delta)\cdot(1+\delta)^{\ell_{i}-1}\rceil\leq\Delta-2$.

Using the fact that for any real positive number $x$, it holds that
$0\leq\lceil(1+2\delta)\cdot\lceil x\rceil\rceil-\lceil(1+2\delta)\cdot
x\rceil\leq 2$, we get that:

$\begin{cases}\lceil(1+2\delta)\cdot\lceil(1+\delta)^{\ell_{i}-1}\rceil\rceil\leq\Delta\\\
\lceil(1+2\delta)\cdot(1+\delta)^{\ell_{i}}\rceil>\Delta-2\end{cases}.$

For the rest of the proof, let
$L_{i}^{\prime}=\lceil(1+\delta)^{\ell_{i}-1}\rceil$. It follows from the
choice of $\ell_{i}$ that

$\displaystyle\big{|}I\cap[i-\lceil(1+2\delta)L_{i}^{\prime}\rceil:i+\lceil(1+2\delta)L_{i}^{\prime}\rceil]\big{|}$
$\displaystyle\leq 2(\lfloor\log^{7}n/2\rfloor-1)+1\leq\log^{7}n$ (13)
$\displaystyle\big{|}I\cap[i-\lceil(1+\delta)\cdot(1+2\delta)L_{i}^{\prime}\rceil:i+\lceil(1+\delta)\cdot(1+2\delta)L_{i}^{\prime}\rceil]\big{|}$
$\displaystyle\geq(\lfloor\log^{7}n/2\rfloor-1)+1-4$ (14)

For (14), we use the observation that left-hand side is larger than
$\big{|}I\cap[i-(\Delta-2):i+(\Delta-2)]\big{|}\geq\big{|}I\cap[i-\Delta:i+\Delta]\big{|}-4$.
Using $(1+\delta)(1+2\delta)\leq 1+4\delta$ with $\delta=0.01$, the second
inequality implies

$\big{|}I\cap[i-\lceil(1+4\delta)L_{i}^{\prime}\rceil:i+\lceil(1+4\delta)L_{i}^{\prime}\rceil]\big{|}\geq\lfloor\log^{7}n/2\rfloor-4.$
(15)

On the other hand, (13) implies that $i\in I^{\prime}$ is $\ell_{i}$-good
unless

$\big{|}I\cap[i-L_{i}^{\prime}:i+L_{i}^{\prime}]\big{|}\leq\log^{3}n.$ (16)

Assume now for a contradiction that the number of $i\in I^{\prime}$ that are
bad is at least $|I|/\log n$. Additionally, for any possible exponent
$\ell\in[\log_{1+\delta}N]$, let $\mathcal{R}_{\ell}$ be the set of the
indices $i$ that are not $\ell$-good:

$\mathcal{R}_{\ell}:=\\{i\in I^{\prime}\text{ s.t }i\text{ is not
}\ell-\text{good}\\}\text{ \&
}\ell^{*}=\displaystyle\mathop{\operatorname{argmax}}_{\ell\in[\log_{1+\delta}N]}|\mathcal{R}_{\ell}|$

Then, it holds that

$|\mathcal{R}_{\ell^{*}}|\geq\frac{|I|/\log
n}{\log_{1+\delta}N}=\Omega(|I|/\log^{2}n),$

where we use the facts that $|I|\geq{\log^{8}n}$ and $N=poly(n)$. We define
then $L^{*}=\lceil(1+\delta)^{{\ell^{*}}-1}\rceil$ and for each
$\rho\in\mathcal{R}_{\ell^{*}}$ we let

$B_{\rho}=\big{(}I\cap[\rho-\lceil(1+4\delta)L^{*}\rceil,\rho-L^{*}]\big{)}\cup\big{(}I\cap[\rho+L^{*},\rho+\lceil(1+4\delta)L^{*}\rceil]\big{)}.$

Note now that when an index $i$ is not $\ell$-good, we have from (16) and (15)
that

$\displaystyle\Big{|}\big{(}I\cap[i-\lceil(1+4\delta)L_{i}^{\prime}\rceil:i-L_{i}^{\prime}]\big{)}\cup\big{(}I\cap[i+L_{i}^{\prime}:i+\lceil(1+4\delta)L_{i}^{\prime}\rceil]\big{)}\Big{|}$
$\displaystyle\geq\lfloor\log^{7}n/2\rfloor-4-\log^{3}n=\Omega(\log^{7}n).$

Hence, we have that $|B_{\rho}|\geq\Omega(\log^{7}n)$ for every
$\rho\in\mathcal{R}_{\ell^{*}}$ and thus,

$\sum_{\rho\in\mathcal{R}_{\ell^{*}}}|B_{\rho}|\geq\Omega\left(\frac{|I|}{\log^{2}n}\right)\cdot\Omega(\log^{7}n)=\Omega\big{(}|I|\log^{5}n\big{)}.$

On the other hand, we can prove the following claim:

######  Claim 4.5.

For any $i\in I$, the number of $\rho\in\mathcal{R}_{\ell^{*}}$ such that
$i\in B_{\rho}$ is at most $O(\log^{3}n)$.

It follows then from the claim that

$\text{ For any $i\in I$, we get }|\\{\rho\in\mathcal{R}_{\ell^{*}}\big{|}i\in
B_{\rho}\\}|=O(\log^{3}n)\Rightarrow\sum_{\rho\in\mathcal{R}_{\ell^{*}}}|B_{\rho}|\leq|I|\cdot
O(\log^{3}n),$

which leads to a contradiction. ∎

###### Proof of Claim 4.5.

Fix any $i\in I$. Let us assume then that $\rho$ be a
$\rho\in\mathcal{R}_{\ell^{*}}$ such that $i\in B_{\rho}$. We prove that the
number of $\rho\in\mathcal{R}_{\ell^{*}}$ with $\rho>i$ and $i\in B_{\rho}$ is
at most $O(\log^{3}n)$; the case with $\rho<i$ is symmetric. If no such $\rho$
exists then the claim is trivially true. Hence, let’s assume that such one
exists with $\rho>i$. Given that $i\in B_{\rho}$, we have that
$i\in[\rho-\lceil(1+4\delta)L^{*}\rceil,\rho-L^{*}]$ and we also have

$\big{|}I\cap[\rho-L^{*},\rho+L^{*}]\big{|}\leq\log^{3}n.$ (17)

On the other hand, every other $\rho^{\prime}\in\mathcal{R}_{\ell^{*}}$ that
satisfies $\rho^{\prime}>i$ and $i\in B_{\rho^{\prime}}$ also has the property
that $i\in[\rho^{\prime}-\lceil(1+4\delta)L^{*}\rceil,\rho^{\prime}-L^{*}]$
and thus, $\rho^{\prime}\in[i+L^{*},i+\lceil(1+4\delta)\rceil L^{*}].$ But
combining this with $i\in[\rho-(1+4\delta)L^{*},\rho-L^{*}]$ we have

$\rho^{\prime}\leq
i+\lceil(1+4\delta)L^{*}\rceil\leq\rho+\lceil(1+4\delta)L^{*}\rceil-L^{*}$

and

$\rho^{\prime}\geq i+L^{*}\geq\rho-\lceil(1+4\delta)L^{*}\rceil+L^{*}.$

So
$\rho^{\prime}\in[\rho-\lceil(1+4\delta)L^{*}\rceil+L^{*},\rho+\lceil(1+4\delta)L^{*}\rceil-L^{*}]\subseteq[\rho-L^{*},\rho+L^{*}]$
and by (17) the number of such $\rho^{\prime}$ is no more than $\log^{3}n$. ∎

Now we return to work on our problem and an arbitrary move sequence
$\mathcal{S}=(\mathcal{S}_{1},\ldots,\mathcal{S}_{N})$. Let $W$ be a window
(move sequence) of $\mathcal{S}$. For each active node $u\in V(W)$, we write
$\\#_{W}(u)$ to denote the number of occurrences of $u$ in $W$. The main
result in this section is the following lemma:

######  Lemma 4.6.

Let $\mathcal{S}$ be a move sequence of length $N=n\log^{10}n$ that consists
of $2$-moves only. There exists a positive integer $L$ such that $\mathcal{S}$
has at least $\Omega((N-L+1)/\log n)$ many windows $W=(W_{1},\ldots,W_{L})$ of
length $L$ such that at least $\Omega(L/\log n)$ moves $W_{i}=\\{u,v\\}$ of
$W$ satisfy

$\log^{3}n\leq\\#_{W}(u)\leq\log^{7}n\quad\text{and}\quad\\#_{W}(v)\geq\log^{3}n$
(18)

###### Proof.

For each node $u\in V(\mathcal{S})$ we write $I_{u}\subseteq[N]$ to denote the
set of $i\in[N]$ with $u\in\mathcal{S}_{i}$. We say the $i$-th move
$\mathcal{S}_{i}=\\{u,v\\}$ is $\ell$-good for some positive integer $\ell$ if
$i$ is $\ell_{1}$-good in $I_{u}$ and $i$ is $\ell_{2}$-good in $I_{v}$ for
some positive integers $\ell_{1},\ell_{2}$ such that
$\ell=\max(\ell_{1},\ell_{2})$.

Let $\mathcal{S}_{i}=\\{u,v\\}$. Then we consider the following cases:

  1. 1.

Either $|I_{u}|$ or $|I_{v}|$ is smaller than $\log^{8}n$: Given that no more
than $n\log^{8}n$ moves can contain a vertex that appears less than
$\log^{8}n$ times in the sequence, we have the number of such $i$ is at most

$n\log^{8}n=o(N/\log n);$

  2. 2.

$|I_{u}|,|I_{v}|\geq\log^{8}n$ but either $u$ is not $\ell_{1}$-good for any
$\ell_{1}$ or $v$ is not $\ell_{2}$-good for any $\ell_{2}$: By Lemma 4.4, the
number of such $i$ is at most (using $\sum_{u}|I_{u}|=2N$)

$\sum_{u:|I_{u}|\geq\log^{8}n}\frac{|I_{u}|}{\log n}\leq\frac{2N}{\log n}.$

  3. 3.

Otherwise, $\mathcal{S}_{i}$ is $\ell$-good by setting
$\ell=\max(\ell_{1},\ell_{2})$.

Thus, the number of $i\in[N]$ such that the $\mathcal{S}_{i}$ is $\ell$-good
for some $\ell$ is at least $(1-3/\log n)N$.

Given that $\ell$ is at most $O(\log N)=O(\log n)$, there exists a positive
integer $\ell$ such that the number of moves in $\mathcal{S}$ that are
$\ell$-good is at least $\Omega(N/\log n)$. Let
$L^{\prime}=\lceil(1+\delta)^{\ell-1}\rceil$ and

$L=L^{\prime}+\big{\lceil}(1+2\delta)L^{\prime}\big{\rceil}+1.$

For any move $\mathcal{S}_{i}=\\{u,v\\}$ that is $\ell$-good, it is easy to
verify that there are $\Omega(L)$ windows $W$ of length $L$ that contain $i$
and satisfy (18) (See Remark 4.2) .

Let’s pick a window $W$ of $\mathcal{S}$ of size $L$ uniformly at random; note
that there are $N-L+1$ many such windows in total. Let $X$ be the random
variable that denotes the number of moves in $W$ that satisfy (18). Given that
the number of moves that are $\ell$-good is at least $\Omega(N/\log n)$, we
have

$\textbf{E}\big{[}X\big{]}\geq\Omega\left(\frac{N}{\log
n}\right)\cdot\frac{\Omega(L)}{N}=\Omega\left(\frac{L}{\log n}\right).$

Let $a$ be the constant hidden above. Given that we always have $X\leq L$, we
have

$\Pr\left[X\geq\frac{aL}{2\log n}\right]\geq\frac{a}{2\log n}$ (19)

since otherwise,

$\textbf{E}\big{[}X\big{]}\leq\frac{a}{2\log n}\cdot L+\left(1-\frac{a}{2\log
n}\right)\cdot\frac{aL}{2\log n}<\frac{aL}{\log n}.$

a contradiction. The lemma then follows directly from (19). ∎

##  5 Finding Cycles

Let $\mathcal{S}=(\mathcal{S}_{1},\ldots,\mathcal{S}_{N})$ be a valid move
sequence of length $N=n\log^{10}n$ that consists of $2$-moves only. By Lemma
4.6, $\mathcal{S}$ has a window $W=(W_{1},\ldots,W_{L})$ of length $L$ such
that the number of moves in $W$ that satisfy (18) is at least $\Omega(L/\log
n)$. We show in this section that such a $W$ satisfies

${\textsf{rank}}_{{\textsf{cycles}}}(W)=\Omega\left(\frac{L}{\log^{10}n}\right).$
(20)

This will finish the proof of Lemma 3.3 when $\mathcal{S}$ consists of
$2$-moves only.

To this end, let $\tau_{0}\in\\{\pm 1\\}^{V(W)}$ be the configuration with
$\tau_{0}(u)=-1$ for all $u\in V(W)$ so that we can work on vectors
$\textsf{imprv}_{\tau_{0},W}(i)$ and $\textsf{imprv}_{\tau_{0},W}(C)$ for
dependent cycles of $W$ (at the same time, recall from Lemma 2.10 that
$\textsf{rank}_{\textsf{cycles}}(W)$ does not depend on the choice of
$\tau_{0}$). Let $\tau_{0},\ldots,\tau_{L}$ denote the sequence of
configurations induced by $W$.

Next, let us construct an auxiliary graph $H=(V(W),E)$, where every move
$W_{i}=\\{u,v\\}$ adds an edge between $u$ and $v$ in $E$. Note that we allow
parallel edges in $H$ so $|E|=L$ and $\\#_{W}(u)$ is exactly the degree of $u$
in $H$. There is also a natural one-to-one correspondence between cycles of
$W$ and cycles of $H$. The following lemma shows the existence of a nice
looking bipartite graph in $H$:

######  Lemma 5.1.

There are two disjoint sets of nodes $V_{1},V_{2}\subset V(W)$ and a subset of
edges $E^{\prime}\subseteq E$ such that

  1. 1.

Every edge in $E^{\prime}$ has one node in $V_{1}$ and the other node in
$V_{2}$;

  2. 2.

$|V_{1}\cup V_{2}|=O(L/\log^{3}n)$ and $|E^{\prime}|=\Omega(L/\log n)$;

  3. 3.

$\\#_{W}(u)\leq\log^{7}n$ for every node $u\in V_{1}$.

###### Proof.

Let $V$ be the set of vertices $v$ such that $\\#_{W}(v)\geq\log^{3}n$. We
start our proof with the size of $V$:

$|V|\log^{3}n\leq|V|\min_{v\in V}\\#_{W}(u)=|V|\min_{v\in
V}\mathop{\operatorname{deg}_{H}}(v)\leq\sum_{v\in
V}\mathop{\operatorname{deg}_{H}}(v)=2|E(H)|\leq 2L.$

We further partition $V$ into $V_{\ell}$ and $V_{h}$ such that $V_{\ell}$
contains those in $V$ with $\\#_{W}(v)\leq\log^{7}n$ and $V_{h}$ contains
those with $\\#_{W}(v)>\log^{7}n$. By Lemma 4.6 we can assume the number of
edges incident to at least one vertex in $V_{\ell}$ (that is edges in
$V_{\ell}\times V_{\ell}\cup V_{\ell}\times V_{h}$) is at least $\Omega(L/\log
n)$. Suppose we construct $V_{1}$ and $V_{2}$ by randomly put each node in
$V_{\ell}$ in $V_{1}$ or $V_{2}$ and put all nodes in $V_{h}$ in $V_{2}$. Any
edge in $V_{\ell}\times V_{\ell}$ or $V_{\ell}\times V_{h}$ is between $V_{1}$
and $V_{2}$ with $1/2$ probability. Thus
$\mathbb{E}[\text{EdgesInCut}(V_{1},V_{2})]=|E|/2=\Omega(L/\log n)$. Thus, by
standard probabilistic argument, there exist at least one assignment of
$V_{\ell}$ to $V_{1}$ and $V_{2}$ such that at least half of the edges in
$V_{\ell}\times V_{\ell}\cup V_{\ell}\times V_{h}$ are included. Hence, we get
a bipartite graph between $V_{1}$ and $V_{2}$ with at least $\Omega(L/\log n)$
edges, and any node $v$ in $V_{1}$ satisfies
$\log^{3}n\leq\\#_{W}(v)\leq\log^{7}n$. Notice that since $V=|V_{1}\cup
V_{2}|=|V_{\ell}\cup V_{h}|$, we get that $|V_{1}\cup V_{2}|=O(L/\log^{3}n)$.
∎

Recall the definition of dependent cycles of $W$ (and their cancellation
vectors) from Section 2. Since we only care about the rank of vectors induced
by dependent cycles, we give the following definition which classify each edge
of $H$ into two types and then use it to give a sufficient condition for a
cycle of $W$ to be dependent:

######  Definition 5.2.

We say the $i$-th move $W_{i}=\\{u,v\\}$ of $W$ is of the same sign if
$\tau_{i}(u)=\tau_{i}(v)$, and is of different signs if
$\tau_{i}(u)\neq\tau_{i}(v)$.

######  Lemma 5.3.

Let $C=(c_{1},\ldots,c_{t})$ be a cycle of $W$ and assume that $t$ is even. If
all of $W_{c_{1}},\ldots,W_{c_{t}}$ are of different signs, then $C$ is a
dependent cycle; If all of $W_{c_{1}},\ldots,W_{c_{t}}$ are of the same sign,
then $C$ is a dependent cycle of $W$.

###### Proof.

Recall the Dependence Criterion (Remark 2.7)

$\text{ $C$ is a dependent cycle of $W$
}\Leftrightarrow(-1)^{t}=\tau_{c_{t}}(u_{1})\tau_{c_{1}}(u_{1})\cdot{\prod_{i=2}^{t}\tau_{c_{i-1}}(u_{i})}{\tau_{c_{i}}(u_{i})}$

If all of $W_{c_{1}},\ldots,W_{c_{t}}$ are of different signs, then
$\tau_{c_{j}}(u_{j})\tau_{c_{j}}(u_{j+1})=\tau_{c_{t}}(u_{1})\tau_{c_{t}}(u_{t})=-1$,
and the above expression equals to $(-1)^{t}=(-1)^{t}$. If all of
$W_{c_{1}},\ldots,W_{c_{t}}$ are of the same sign, then
$\tau_{c_{j}}(u_{j})\tau_{c_{j}}(u_{j+1})=\tau_{c_{t}}(u_{1})\tau_{c_{t}}(u_{t})=1$,
the above expression is also $1=(-1)^{t}$, which holds since $t$ is even. ∎

We assume in the rest of the proof that at least half of edges in $E^{\prime}$
are of the same sign; the case when at least half of $E^{\prime}$ are of
different signs can be handled similarly. Let $E^{\prime\prime}$ be the subset
of $E^{\prime}$ that consists of edges of the same sign, with
$|E^{\prime\prime}|\geq|E^{\prime}|/2$. In the following discussion, cycles in
$E^{\prime\prime}$ always refer to cycles that do not use the same edge twice
(parallel edges are counted as different edges, since they correspond to
different moves in the window $W$).

The aforementioned discussion leads to the following corollary which reduces
the existence of dependent cycle of $W$ to a simple cycle in auxiliary graph
$H$:

######  Corollary 5.4.

Since every cycle in a bipartite graph has even length, every cycle in
$E^{\prime\prime}$ corresponds to a dependent cycle of $W$. For convenience,
given any cycle $C$ of $E^{\prime\prime}$ we will write
$\textsf{imprv}_{\tau_{0},W}(C)$ to denote the vector of its corresponding
dependent cycle of $W$.

We first deal with the case when $E^{\prime\prime}$ contains many parallel
edges:

######  Lemma 5.5.

Let $D$ be the subset of nodes in $V_{1}$ that have parallel edges in
$E^{\prime\prime}$. Then $\textsf{rank}_{\textsf{cycles}}(W)\geq|D|/2.$

###### Proof.

We prove the lemma even if the sequence contains both 1-moves and 2-moves so
that we can use it also in the general case in the next section. We note first
that if $S_{i}=\\{u,v\\}$, $S_{j}=\\{u,v\\},i<j$ are two moves that involve
the same two nodes, then there is at least one node $z\neq u,v$ that appears
an odd number of times between the two moves. This follows from the definition
of a valid move sequence.

We will construct a set $Q$ of at least $|D|/2$ 2-cycles, where each 2-cycle
consists of two parallel edges in $E^{\prime\prime}$. We use the following
procedure.
1\. While there is a 2-cycle $(u,v)$ with $u\in D$, $v\in V_{2}$, such that
some node $z\neq u$ of $V_{1}$ moves an odd number of times between the two
$\\{u,v\\}$ moves of the 2-cycle, pick any such 2-cycle $(u,v)$ and add it to
our set $Q$, pick any such node $z\neq u$ that moves an odd number of times
between the two $\\{u,v\\}$ moves, and delete $u$ and $z$ from $D$ (if $z$ is
in $D$).
2\. Suppose now that there are no more 2-cycles as in step 1. While $D$ is not
empty, let $u$ be any remaining node in $D$, take any two incident parallel
edges $\\{u,v\\}$ in $E^{\prime\prime}$, add the corresponding 2-cycle to $Q$,
and delete $u$ from $D$.

Firstly, notice that for every new entry at $Q$ in the procedure, we delete at
most 2 nodes from $D$. Hence, this procedure will generate clearly a set $Q$
of at least $|D|/2$ 2-cycles. Let
$(u_{1},v_{1}),(u_{2},v_{2}),\ldots,(u_{k},v_{k})$ be the sequence of 2-cycles
selected, where the first $d$ were selected in step 1, and the rest in step 2.
The nodes $u_{i}$ are distinct, while the nodes $v_{i}$ may not be distinct.
For each $i=1,\ldots,d$, let $z_{i}$ be the node in $V_{1}$ that appears an
odd number of times between the two $\\{u_{i},v_{i}\\}$ moves that was
selected by the algorithm. Note that node $z_{i}\neq u_{j}$ for all $j\geq i$,
since $z_{i}$ was deleted from $D$ when $u_{j}$ was selected. For each
$i=d+1,\ldots,k$, let $z_{i}$ be any node, other than $u_{i},v_{i}$, that
appears an odd number of times between the two $\\{u_{i},v_{i}\\}$ moves. Then
$z_{i}$ is not in $V_{1}$ because in step 2 there are no odd nodes in $V_{1}$.
For each $i=1,\ldots,k$, we view the edge $\\{u_{i},z_{i}\\}$ of the complete
graph as a witness for the 2-cycle $(u_{i},v_{i})$.

Consider the matrix with columns corresponding to the selected 2-cycles
$(u_{i},v_{i})$, $i=1,\ldots,k$, and rows corresponding to the witness edges
$\\{u_{i},z_{i}\\}$. The entry for the corresponding witness edge
$\\{u_{i},z_{i}\\}$ is nonzero. Indeed, by definition 2.6,
$\textsf{imprv}_{\tau_{0},W}(C=(u_{i},v_{i}))_{\\{u_{i},z_{i}\\}}=-b_{1}(\tau_{c_{1}}(u_{i})\tau_{c_{1}}(z_{i}))-b_{2}(\tau_{c_{2}}(u_{i})\tau_{c_{2}}(z_{i}))$

$\text{ and }\begin{cases}\tau_{c_{1}}(z_{i})=-\tau_{c_{2}}(z_{i})\\\ b_{1}=1\
\&\ b_{2}=-\tau_{c_{1}}(v_{i})\tau_{c_{2}}(v_{i})\\\
\tau_{c_{m}}(v_{i})=\tau_{c_{m}}(u_{i}),\text{ for }m\in\\{1,2\\}\
\end{cases}\text{ which yields
}\textsf{imprv}_{\tau_{0},W}(C=(u_{i},v_{i}))_{\\{u_{i},z_{i}\\}}=2\cdot\tau_{c_{1}}(z)\neq
0.$

Consider the column for a 2-cycle $(u_{i},v_{i})$ selected in step 1. The
entry for any other witness edge $\\{u_{j},z_{j}\\}$ with $j<i$ is 0 because
$u_{j},z_{j}\neq u_{i},v_{i}$. (The entries for witness edges
$\\{u_{j},z_{j}\\}$ with $j>i$ could be nonzero.)

Consider the column for a 2-cycle $(u_{i},v_{i})$ selected in step 2. The
entry for any witness edge $\\{u_{j},z_{j}\\}$ from step 1 (i.e. with $j\leq
d$) is 0 because $u_{j},z_{j}\neq u_{i},v_{i}$. The entry for any witness edge
$\\{u_{j},z_{j}\\}$ from step 2 (i.e. with $j>d$) is also 0 because (1)
$u_{j}\neq u_{i},v_{i}$, (2) $z_{j}\notin V_{1}$ hence $z_{j}\neq u_{i}$, and
(3), even if $z_{j}=v_{i}$, all nodes of $V_{1}$ –hence also $u_{j}$ –occur an
even number of times between the two $\\{u_{i},v_{i}\\}$ moves, therefore the
entry for $\\{u_{j},v_{i}\\}$ is 0.

$\footnotesize\begin{cases}\mathcal{M}^{\text{[step 1]}}_{1\to
d}=\begin{bmatrix}\textsf{imprv}_{\tau_{0},W}(C_{1})_{\\{x_{1},y_{1}\\}}\neq
0&0&0\\\ *&\ddots&\vdots\\\
*&*&\textsf{imprv}_{\tau_{0},W}(C_{d})_{\\{x_{d},y_{d}\\}}\neq
0\end{bmatrix}\\\ \\\ \footnotesize\mathcal{M}^{\text{[step 2]}}_{d+1\to
k}=\operatorname{\mathop{diag}_{t\in(d+1)\to
k}}(\footnotesize\textsf{imprv}_{\tau_{0},W}(C_{t})_{\\{x_{t},y_{t}\\}}\neq
0)\end{cases}\Rightarrow\footnotesize\mathcal{M}=\begin{bmatrix}\mathcal{M}^{\text{[step
1]}}_{1\to d}&\mbox{\bf 0}\\\ *&\mathcal{M}^{\text{[step 2]}}_{d+1\to
k}\end{bmatrix}$

Thus, the matrix with columns corresponding to the selected 2-cycles
$(u_{i},v_{i})$ and rows corresponding to their witness edges
$\\{u_{i},z_{i}\\}$ is a lower triangular matrix with non-zero diagonal
entries. It follows that the columns are linearly independent. ∎

As a result, it suffices to deal with the case when $|D|$ is $o(L/\log^{8}n)$.
Let $E^{*}$ denote the subset of edges obtained from $E^{\prime\prime}$ after
deleting all nodes of $D$ and their incident edges. The remaining bipartite
graph has no parallel edges. Then we have

$|E^{*}|\geq|E^{\prime\prime}|-|D|\cdot\log^{7}n=\Omega(L/\log n).$

We list all properties of the bipartite graph $H^{*}=(V_{1}\cup V_{2},E^{*})$
we need as follows:

  1. 1.

$H^{*}$ is a bipartite graph with no parallel edges;

  2. 2.

$|V_{1}\cup V_{2}|\leq O(L/\log^{3}n)$ and $|E^{*}|\geq\Omega(L/\log n)$; and

  3. 3.

$\\#_{W}(u)\leq\log^{7}n$ for every node $u\in V_{1}$.

  4. 4.

Every edge $e=\\{u,v\\}\in E^{*}$ corresponds to a move $W_{i}=\\{u,v\\}$
which is of the same sign.

Recall that $E(W)$ denotes the set of edges in $K_{n}$ which have both nodes
in $V(W)$. These edges are indices of
$\textsf{imprv}_{\tau_{0},\mathcal{S}}(i)$ and
$\textsf{imprv}_{\tau_{0},\mathcal{S}}(C)$ for a given dependent cycle $C$ of
$W$. Our main lemma is the following:

######  Lemma 5.6.

Fix an arbitrary $s\in[0:L/\log^{10}(n)]$. Assume additionally that there
exists a set of edges
$\mathcal{E}_{s}=\\{\\{x_{1},y_{1}\\},\cdots\\{x_{s},y_{s}\\}\\}\subseteq
E(W)$ such that $x_{i}\in V_{1}$ for all $i\in[s]$. Then there exists a cycle
$C$ in $H^{*}$ and an edge $\\{u,v\\}\in E(W)$ with $u\in
V_{1}\setminus\\{x_{1},y_{1},\ldots,x_{s},y_{s}\\}$ such that

$\Big{(}\emph{{imprv}}_{\tau_{0},W}(C)\Big{)}_{\\{u,v\\}}\neq
0\quad\text{and}\quad\Big{(}\emph{{imprv}}_{\tau_{0},W}(C)\Big{)}_{\\{x_{i},y_{i}\\}}=0,\quad\text{for
all $i\in[s]$.}$ (21)

###### Proof of (20) Assuming Lemma 5.6.

Start with $\mathcal{E}_{s=0}=\emptyset$, For integer $s$ going from $0$ to
$\lfloor L/\log^{10}n\rfloor$, using Lemma 5.6, find cycle $C_{s+1}$ and an
edge $\\{u,v\\}$ satisfying (21), let
$\mathcal{E}_{s+1}=\mathcal{E}_{s}\cup\\{x_{s+1},y_{s+1}\\}=\\{u,v\\}$ and
repeat the above process.

In the end, we get a set of cycles $C_{1},\cdots,C_{k}$ where $k=\lfloor
L/\log^{10}n\rfloor$. And for any $j\in[k]$, we have

$\Big{(}\emph{{imprv}}_{\tau_{0},W}(C_{j})\Big{)}_{\\{x_{j},y_{j}\\}}\neq
0\quad\text{and}\quad\Big{(}\emph{{imprv}}_{\tau_{0},W}(C_{j})\Big{)}_{\\{x_{i},y_{i}\\}}=0,\quad\text{for
all $i\in[j-1]$.}$

Let $\mathcal{M}$ be the $k\times k$ square matrix where
$\mathcal{M}_{ij}=\Big{(}\emph{{imprv}}_{\tau_{0},W}(C_{j})\Big{)}_{\\{x_{i},y_{i}\\}}$.

$\footnotesize\mathcal{M}=\begin{bmatrix}\textsf{imprv}_{\tau_{0},W}(C_{1})_{\\{x_{1},y_{1}\\}}\neq
0&0&0&\cdots&0\\\ *&\textsf{imprv}_{\tau_{0},W}(C_{2})_{\\{x_{2},y_{2}\\}}\neq
0&0&\cdots&0\\\
\vdots&*&\textsf{imprv}_{\tau_{0},W}(C_{3})_{\\{x_{3},y_{3}\\}}\neq
0&\cdots&0\\\ \vdots&\vdots&*&\ddots&0\\\
*&*&*&*&\textsf{imprv}_{\tau_{0},W}(C_{k})_{\\{x_{k},y_{k}\\}}\neq
0\end{bmatrix}$

As we can see, the matrix is lower triangular with non-zero diagonal entries,
so it has full rank $k$. Note that $\mathcal{M}$ is a submatrix of the matrix
formed by taking $\emph{{imprv}}_{\tau_{0},W}(C_{j})$ as column vectors,
therefore we have $\textsf{rank}_{\textsf{cycles}}(W)\geq k\geq L/\log^{10}n.$
∎

###  5.1 Proof of Lemma 5.6

Given a cycle $C$ in $H^{*}$, we say $\\{u,v\\}\in E(W)$ is a _witness_ of $C$
if

$\left(\textsf{imprv}_{\tau_{0},W}(C)\right)_{\\{u,v\\}}\neq 0.$

So the goal of Lemma 5.6 is to find a cycle $C$ of $H^{*}$ such that none of
$(u_{i},v_{i})\in\mathcal{E}_{s}$ are witnesses of $C$ and at the same time,
$C$ has a witness edge $\\{u,v\\}$ with $u$ being a new node in $V_{1}$ not
seen in $\mathcal{E}_{s}$ before. The proof consists of two steps. First we
introduce a so-called _split auxiliary graph_ $G$ using $H^{*}$ and
$\mathcal{E}_{s}$, by deleting certain nodes and creating extra copies of
certain nodes in $H^{*}$. We show in Lemma 5.7 that certain simple cycles in
$G$ correspond to cycles in $H^{*}$ that don’t have any edge in
$\mathcal{E}_{s}$ as witnesses. Next we show in Lemma 5.9 how to find such a
simple cycle in $G$ that has a new witness $(u,v)$ such that $u\in V_{1}$ and
does not appear in $\mathcal{E}_{s}$.

Let $\mathsf{wit}_{1}(\mathcal{E}_{s})$ be the set of $u\in V_{1}$ that appear
in $\mathcal{E}_{s}$ and let $\mathsf{wit}_{2}(\mathcal{E}_{s})$ be the set of
$v\in V_{2}$ that appear in $\mathcal{E}_{s}$. For each
$v\in\mathsf{wit}_{2}(\mathcal{E}_{s})$, we write
$\mathsf{wit}_{1}(v)\neq\emptyset$ to denote the set of nodes
$u\in\mathsf{wit}_{1}(\mathcal{E}_{s})$ such that $(u,v)\in\mathcal{E}_{s}$,
and let $k_{v}$ denote the number of moves in $W$ that involve at least one
node in $\mathsf{wit}_{1}(v)$. We have
$k_{v}\leq|\mathsf{wit}_{1}(v)|\cdot\log^{7}n$ since $\\#_{W}(u)\leq\log^{7}n$
for all $u\in V_{1}$. Below, we give an example of such an auxiliary graph:

$u_{5}$$u_{6}$$u_{7}$$u_{8}$$v_{B}$$W_{2}$$W_{4}$$W_{6}$$W_{8}$$\text{Let
}W=(W_{1},\cdots,W_{11},\cdots)$$\text{Let
}\mathcal{E}_{s=3}=\\{\\{u_{1},v_{A}\\},\\{u_{2},v_{A}\\},\\{u_{3},v_{A}\\}\\}$$\mathsf{wit}_{1}(\mathcal{E}_{s=3})=\\{u_{1},u_{2},u_{3}\\}$$\begin{array}[]{l}\mathsf{wit}_{2}(\mathcal{E}_{s=3})=\\{v_{A}\\}\\\
\mathsf{wit}_{1}(v_{A})=\\{u_{1},u_{2},u_{3}\\}\\\ k_{v_{A}}=(1+3+4)\ =\
8\end{array}$$V_{1}$$V_{2}$$u_{5}^{(0)}$$u_{7}^{(0)}$$u_{8}^{(0)}$$C(v_{A})$$v_{B}^{(0)}$$W_{7}$$W_{2}$$W_{4}$$W_{6}$$W_{8}$$G\left(H^{*},\mathcal{E}_{s=3}\right)$$W_{10}$$W_{10}$$u_{5}^{(0)}$$u_{4}^{(0)}$$v_{A}^{(0)}$$v_{A}^{(1)}$$v_{A}^{(2)}$$v_{A}^{(3)}$$v_{A}^{(4)}$$v_{A}^{(8)}$$v_{A}^{(7)}$$v_{A}^{(6)}$$v_{A}^{(5)}$$V^{\prime}_{2}$$V^{\prime}_{1}$$C(v_{B})$$u_{1}$$u_{2}$$u_{3}$$u_{4}$$v_{A}$$W_{1}$$W_{9}$$W_{3}$$W_{7}$$\\#_{W}(u_{1})=1$$\\#_{W}(u_{2})=3$$\\#_{W}(u_{3})=4$$W_{5}$$H^{*}$$\vdots$$\vdots$$\vdots$$\vdots$

Figure 4: An exemplifying case of an auxiliary graph $H^{*}$ and splitting
graph $G(H^{*},\mathcal{E}_{s})$

We now define our split auxiliary (bipartite) graph $G$. We start with its set
of nodes $V_{1}^{\prime}\cup V_{2}^{\prime}$:

  1. 1.

$V_{1}^{\prime}=V_{1}\setminus\mathsf{wit}_{1}(\mathcal{E}_{s})$; and

  2. 2.

$V_{2}^{\prime}=\cup_{v\in V_{2}}C(v),$ where $C(v)=\\{v^{(0)}\\}$ if
$v\notin\mathsf{wit}_{2}(\mathcal{E}_{s})$ and
$C(v)=\\{v^{(0)},v^{(1)},\ldots,v^{(k_{v})}\\}$ if
$v\in\mathsf{wit}_{2}(\mathcal{E}_{s})$.

So we deleted nodes $\mathsf{wit}_{1}(\mathcal{E}_{s})$ from $V_{1}$ and
replaced each node $v\in\mathsf{wit}_{2}(\mathcal{E}_{s})$ by $k_{v}+1$ new
nodes. Next we define the edge set $E(G)$ of $G$. Every move $W_{i}=\\{u,v\\}$
in $W$ that corresponds to an edge $(u,v)$ in $H^{*}$ with $u\in
V_{1}\setminus\mathsf{wit}_{1}(\mathcal{E}_{s})$ and $v\in V_{2}$ will add an
edge in $G$ as follows:

  1. 1.

If $v\notin\mathsf{wit}_{2}(\mathcal{E}_{s})$, then we add $(u,v^{(0)})$ to
$G$; and

  2. 2.

Otherwise $(v\in\mathsf{wit}_{2}(\mathcal{E}_{s})$), letting
$\mu_{i}\in[0:k_{v}]$ be the number of moves before $W_{i}$ that contain at
least one node in $\mathsf{wit}_{1}(v)$ (note that $W_{i}$ does not contain
$\mathsf{wit}_{1}(v)$; actually $W_{i}$ cannot contain
$\mathsf{wit}_{1}(\mathcal{E}_{s})$), we add $(u,v^{(\mu_{i})})$ to $G$.

Therefore, every edge in $G$ corresponds to a move in $W$ which corresponds to
an edge in $H^{*}$ that does not contain a node in
$\mathsf{wit}_{1}(\mathcal{E}_{s})$. It is clear that each simple cycle of $G$
corresponds to a cycle of $H$, which in turn corresponds to a dependent cycle
of $W$ (Since we assume w.l.o.g that all edges of auxiliary graph, and its
split one, correspond to moves of the same sign ( See Corollary 5.4) ). So
$\textsf{imprv}_{\tau_{0},W}(C)$ is well defined for simple cycles $C$ of $G$.
Our motivation for constructing and working on $G$ is because of the following
lemma:

######  Lemma 5.7.

Let $C$ be a simple cycle of $G$. Then none of the edges in $\mathcal{E}_{s}$
is a witness of $C$.

###### Proof.

Let $e=\\{u,v\\}\in\mathcal{E}_{s}$ and
$u\in\mathsf{wit}_{1}(\mathcal{E}_{s})$. By the definition of $G$, $u$ has no
copy in $G$. So $u$ does not appear on the cycle. Let $C$ be a cycle in $G$
with nodes
$(w_{1}^{(i_{1})},w_{2}^{(i_{2})},\cdots,w_{t}^{(i_{t})},w_{1}^{(i_{1})})$ (we
use $w_{j}^{(0)}$ to denote $w_{j}$ for $w_{j}\in V_{1}^{\prime}$ ). If the
cycle does not contain any vertex in $C(v)$, then
$\textsf{imprv}_{\tau_{0},W}(C)_{e}=0$. Now suppose the cycle contains nodes
in $C(v)$, specifically, $w_{j_{1}}=\cdots=w_{j_{m}}=v$. Let the corresponding
cycle $C$ on $W$ be $c_{1},\cdots,c_{t}$ where $W_{c_{i}}=\\{w_{i},w_{i+1}\\}$
if $i<t$ and $W_{c_{t}}=\\{w_{t},w_{1}\\}$, and let $b$ be the cancellation
vector of $C$. We can write down the value of the improvement vector on edge
$e$.

$\displaystyle\begin{split}\textsf{imprv}_{\tau_{0},W}(C)_{e}&=\sum_{k=1}^{m}\left(b_{j_{k}-1}\textsf{imprv}_{\tau_{0},W}(c_{j_{k}-1})_{e}+b_{j_{k}}\textsf{imprv}_{\tau_{0},W}(c_{j_{k}})_{e}\right)\\\
&=-\sum_{k=1}^{m}\left(b_{j_{k}-1}\tau_{c_{j_{k}-1}}(v)\tau_{c_{j_{k}-1}-1}(u)+b_{j_{k}}\tau_{c_{j_{k}}}(v)\tau_{c_{j_{k}}-1}(u)\right)\end{split}$
(22)

By the construction of $G$, $u$ doesn’t appear in any move between $c_{j_{k}}$
and $c_{j_{k}-1}$ (otherwise, in $G$, the edge corresponding to
$W_{c_{j_{k}}}$ and edge corresponding to $W_{c_{j_{k}}-1}$ wouldn’t be
connected to $w_{j_{k}}^{(i_{j_{k}})}$ with the same $i_{j_{k}}$.(For an
illustative explanation, see Figure 5 & 6) ) So
$\tau_{c_{j_{k}-1}-1}(u)=\tau_{c_{j_{k}}-1}(u)$. By definition of cancellation
vector,

$b_{j_{k}-1}\tau_{c_{j_{k}-1}}(v)+b_{j_{k}}\tau_{c_{j_{k}}}(v)=0.$

So each term in (22) is 0, and $\textsf{imprv}_{\tau_{0},W}(C)_{e}=0$.

$C(v_{A})$$v_{A}^{(0)}$$v_{A}^{(1)}$$v_{A}^{(2)}$$v_{A}^{(3)}$$v_{A}^{(4)}$$v_{A}^{(8)}$$v_{A}^{(7)}$$v_{A}^{(6)}$$v_{A}^{(5)}$$u_{1}$$u_{2}$$u_{3}$$\mathsf{wit}_{1}(\mathcal{E}_{s=3})$$u_{4}^{(0)}$$W_{7}$$W_{12}$$u_{12}^{(0)}$$\vdots$$\vdots$

Figure 5: Following the example of Figure 7, $u_{4}^{(0)}$ and $u_{11}^{(0)}$
can not close cycle, since $u_{3}\in W_{9}$ and
$u_{3}\in\mathsf{wit}_{1}(v_{A})$ and appears between $W_{7}$ and $W_{12}$.
Thus, $u_{4}^{0}$ and $u_{11}^{0}$ fail to make a cycle due to the
intervention of a node in $u_{3}\in\mathsf{wit}_{1}(v_{A})$.

$C(v_{A})$$v_{A}^{(0)}$$v_{A}^{(1)}$$v_{A}^{(2)}$$v_{A}^{(3)}$$v_{A}^{(4)}$$v_{A}^{(8)}$$v_{A}^{(7)}$$v_{A}^{(6)}$$v_{A}^{(5)}$$u_{1}$$u_{2}$$u_{3}$$\mathsf{wit}_{1}(\mathcal{E}_{s=3})$$u_{18}^{(0)}$$W_{18}$$W_{12}$$u_{12}^{(0)}$$\vdots$$\vdots$

Figure 6: Again by the example of Figure 7, since $u_{12}^{(0)}$ and
$u_{18}^{(0)}$ achieved to form a cycle with moves $W_{12}=\\{u_{12},v_{A}\\}$
and $W_{18}=\\{u_{18},v_{A}\\}$, we know from our construction that none of
$\mathsf{wit}_{1}(v_{A})$ appear in the sub-window $W_{13}\cdots W_{17}$.

∎

To finish the proof, it suffices now to find a simple cycle $C$ of $G$ that
has a witness $(u,v)\in E(W)$ with one of its vertices $u\in V_{1}^{\prime}$.
We start by checking that all conditions for $H^{*}$ still hold for $G$. It is
clear that $G$ is a bipartite graph with no parallel edges. By the definition
of $\mathsf{wit}_{1}(v)$ for each $v\in\mathsf{wit}_{2}(\mathcal{E}_{s})$, we
have $\sum_{v\in\mathsf{wit}_{2}(\mathcal{E}_{s})}|\mathsf{wit}_{1}(v)|\leq
2s$, also $|\mathsf{wit}_{1}(\mathcal{E}_{s})|\leq 2s$. The number of nodes
$|V_{1}^{\prime}\cup V_{2}^{\prime}|$ in $G$ is at most

$\displaystyle
O(L/\log^{3}n)+\sum_{v\in\mathsf{wit}_{2}(\mathcal{E}_{s})}k_{v}\leq
O(L/\log^{3}n)+\sum_{v\in\mathsf{wit}_{2}(\mathcal{E}_{s})}|\mathsf{wit}_{1}(v)|\cdot\log^{7}n=O(L/\log^{3}n).$

where the last equality used that $s\leq L/\log^{10}n$. The number of edges in
$G$ is at least

$\Omega(L/\log
n)-|\mathsf{wit}_{1}(\mathcal{E}_{s})|\cdot\log^{7}n=\Omega(L/\log n).$

Let’s work on another preprocessing of $G$ to simplify the proof. Note that
the average degree of nodes in $G$ is at least
$\Omega\left({\footnotesize(L/\log
n)/(L/\log^{3}n)}\right)=\Omega(\log^{2}n)$. The following simple lemma shows
that one can clean up $G$ to get a bipartite graph $G^{*}$ such that every
node has degree at least $100\log n$ and the number of edges in $G^{*}$
remains to be $\Omega(L/\log n)$:

######  Lemma 5.8.

There is a bipartite graph $G^{*}=(V_{1}^{*}\cup V_{2}^{*},E(G^{*}))$ with
$V_{1}^{*}\subseteq V_{1}^{\prime}$, $V_{2}^{*}\subseteq V_{2}^{\prime}$ and
$E(G^{*})\subseteq E(G)$ such that every node in $G^{*}$ has degree at least
$100\log n$ and $|E(G^{*})|=\Omega(L/\log n)$.

###### Proof.

Keep deleting nodes in $G$ with degree less than $100\log n$ one by one (and
its adjacent edges) until no such nodes exist. The number of edges we delete
during the whole process is no more than

$(|V_{1}^{\prime}|+|V_{2}^{\prime}|)\cdot 100\log n\leq O(L/\log^{2}n).$

So the remaining graph (which trivially has minimum degree at least $100\log
n$) has at least $\Omega(L/\log n)$ many edges. ∎

Let us list the properties of $G^{*}=(V_{1}^{*}\cup V_{2}^{*},E(G^{*}))$ we
will use in the rest of the proof:

  1. 1.

$V_{1}^{*}\subseteq
V_{1}^{\prime}=V_{1}\setminus\mathsf{wit}_{1}(\mathcal{E}_{s})$ and
$V_{2}^{*}\subseteq V_{2}^{\prime}$ so each node in $V_{2}^{*}$ is in $C(v)$
for some $v\in V_{2}$.

  2. 2.

The degree of any node is at least $100\log n$; and

  3. 3.

For any $u\in V_{1}^{*}$ and $v\in V_{2}$, the number of neighbors of $u$ in
$V_{2}^{*}\cap C(v)$ is at most one.

  4. 4.

$E(G^{*})$ has no parallel edges, $|E(G^{*})|\geq\Omega(L/\log n)$ and
w.l.o.g. each edge in $E(G^{*})$ correspond to a move of same sign.

We prove the following lemma to finish the proof:

######  Lemma 5.9.

Let $u\in V_{1}^{*}$ and $v\neq v^{\prime}\in V_{2}^{*}$ such that
$(u,v^{(j)}),(u,v^{\prime(j^{\prime})})\in E(G^{*})$ for some $j$ and
$j^{\prime}$, and the corresponding moves $W_{i}=\\{u,v\\}$ and
$W_{i^{\prime}}=\\{u,v^{\prime}\\}$ in $W$ are not consecutive666 It is worth
mentioning, that $V_{2}^{*}$ always includes at least two vertices which are
copies from different initial nodes $v,v^{\prime}$. Indeed, if $G^{*}$ was
actually a star graph around $V_{2}^{*}=\\{v^{*}\\}$, then $\Omega(L/\log
n)=E(G^{*})=\Theta(V(G^{*}))=O(L/\log^{3}n)$, which leads to a contradiction.
Additionally, notice that $v^{(j)}$ and $v^{\prime(j^{\prime})}$ correspond to
different nodes in the initial graph, otherwise the initial auxiliary graph
$H^{*}$ would have parallel edges. . Then, the graph $G^{*}$ has a simple
cycle $C$ such that $C$ has a witness $e=\\{u,w\\}\in E(W)$ with $w\in
V_{1}^{*}$.

###### Proof.

We begin with a simple sufficient condition for a simple cycle of $G^{*}$ to
satisfy the above condition.

First, let $u\in V_{1}^{*}$ and $v\neq v^{\prime}\in V_{2}^{*}$ such that
$(u,v^{(j)}),(u,v^{\prime(j^{\prime})})\in E(G^{*})$ for some $j$ and
$j^{\prime}$, and the corresponding moves $W_{i}=\\{u,v\\}$ and
$W_{i^{\prime}}=\\{u,v^{\prime}\\}$ in $W$ are not consecutive. Assume that
$i<i^{\prime}$ without loss of generality; then $i+1<i^{\prime}$. The
following claim shows that there must be a node $w\notin\\{u,v,v^{\prime}\\}$
that moves an odd number times in $W_{i+1},\ldots,W_{i^{\prime}-1}$:

######  Claim 5.10.

There is a node $w\notin\\{u,v,v^{\prime}\\}$ that appears in an odd number of
moves in $W_{i+1},\ldots,W_{i^{\prime}-1}$.

###### Proof.

This follows from the fact that $W$ is a valid move sequence. We distinguish
two cases.

If $v^{\prime}$ appears an even number of times in
$W_{i+1},\ldots,W_{i^{\prime}-1}$, then use the condition of validity on the
subsequence $W_{i},\ldots,W_{i^{\prime}-1}$: there is at least one node
$w\notin W_{i}=\\{u,v\\}$ that appears an odd number of times in
$W_{i},\ldots,W_{i^{\prime}-1}$. Since $w\notin W_{i}$, node $w$ appears an
odd number of times in $W_{i+1},\ldots,W_{i^{\prime}-1}$. Hence $w\neq
v^{\prime}$ and thus $w\notin\\{u,v,v^{\prime}\\}$ and the claim follows.

If $v^{\prime}$ appears an odd number of times in
$W_{i+1},\ldots,W_{i^{\prime}-1}$, then $v^{\prime}$ appears an even number of
times in $W_{i},\ldots,W_{i^{\prime}}$. Use the condition of validity on the
subsequence $W_{i},\ldots,W_{i^{\prime}}$: there is at least one node $w\notin
W_{i}=\\{u,v\\}$ that appears an odd number of times in
$W_{i},\ldots,W_{i^{\prime}}$. Then $w\neq v^{\prime}$, and since also
$w\notin W_{i}=\\{u,v\\}$, it follows that $w$ appears an odd number of times
in $W_{i+1},\ldots,W_{i^{\prime}-1}$ and the claim follows again. ∎

We remark that Claim 5.10 holds even when $W$ is a mixture of $1$-moves and
$2$-moves. This will be important when we deal with the general case in
Section 6.

We write $w^{*}(u,v^{(j)},v^{\prime(j^{\prime})})\in V(W)$ to denote such a
node $w$ promised in the above claim (if more than one exist pick one
arbitrarily). The next claim gives us a sufficient condition for a simple
cycle $C$ of $G^{*}$ to satisfy the condition of the lemma:

######  Claim 5.11.

Let

$C=u_{1}v_{1}^{(j_{1})}u_{2}v_{2}^{(j_{2})}\cdots u_{k}v_{k}^{(j_{k})}u_{1}$

be a simple cycle of $G^{*}$ for some nonnegative integers
$j_{1},\ldots,j_{k}$. Suppose for some $i\in[k]$ we have that
$w:=w^{*}(u_{i},v_{i-1}^{(j_{i-1})},v_{i}^{(j_{i})})\in V(W)$ does not appear
in $C$ (where $v_{i-1}^{(j_{i-1})}$ denotes $v_{k}^{(j_{k})}$ if $i=1$), i.e.,
$w\notin\\{u_{1},\ldots,u_{k},v_{1},\ldots,v_{k}\\}$, then $(u_{i},w)\in E(W)$
must be a witness of $C$.

###### Proof.

Let the corresponding cycle in $W$ be $(c_{1},\cdots,c_{2k})$, edge
$\\{u_{l},v_{l}^{(j_{l})}\\}$ corresponds to move $c_{2l-1}$ and edge
$(v_{l}^{(j_{l})},u_{l+1})$ corresponds to $c_{2l}$ (when $l=k$, $u_{l+1}$
denotes $u_{1}$). Let $b$ be its cancellation vector. Recall

$\Big{(}\textsf{imprv}_{\tau_{0},W}(C)\Big{)}_{\\{w,u_{i}\\}}=\sum_{l=1}^{2k}b_{l}\Big{(}\textsf{imprv}_{\tau_{0},W}(c_{l})\Big{)}_{\\{w,u_{i}\\}}.$

Since $w$ does not appear in $C$,
$\Big{(}\textsf{imprv}_{\tau_{0},W}(c_{l})\Big{)}_{\\{w,u_{i}\\}}\neq 0$ only
when $u_{i}\in W_{c_{l}}$, i.e., when $l=2i-2$ or $l=2i-1$ (if $i=1$, it is
$l=2k$ or $l=1$). So

$\Big{(}\textsf{imprv}_{\tau_{0},W}(C)\Big{)}_{\\{w,u_{i}\\}}=-b_{2i-2}\tau_{c_{2i-2}}(u_{i})\tau_{c_{2i-2}}(w)-b_{2i-1}\tau_{c_{2i-1}}(u_{i})\tau_{c_{2i-1}}(w).$

By the definition of $w^{*}$, $w$ moved odd number of times between move
$c_{2i-2}$ and $c_{2i-1}$. So $\tau_{c_{2i-2}}(w)=-\tau_{c_{2i-1}}(w)$. Also,
by property $4$ of $G^{*}$, Corollary 5.4 and the definition of a dependent
cycle, $b_{2i-2}\tau_{c_{2i-2}}(u_{i})+b_{2i-1}\tau_{c_{2i-1}}(u_{i})=0$. So

$\Big{(}\textsf{imprv}_{\tau_{0},W}(C)\Big{)}_{\\{w,u_{i}\\}}=-2b_{2i-2}\tau_{c_{2i-2}}(u_{i})\tau_{c_{2i-2}}(w)\neq
0.$

This finishes the proof of the claim. ∎

Finally we prove the existence of a simple cycle $C$ of $G^{*}$ that satisfies
the condition of the above claim. To this end, we first review a simple
argument which shows that any bipartite graph with $n$ nodes and minimum
degree at least $100\log n$ must have a simple cycle. Later we modify it to
our needs.

The argument goes by picking an arbitrary node in the graph as the root and
growing a binary tree of $\log n$ levels as follows:

  1. 1.

In the first round we just add two distinct neighbors of the root in the graph
as its children.

  2. 2.

Then for each round, we grow the tree by one level by going through its
current leaves one by one to add two children for each leaf. For each leaf $u$
of the current tree we just pick two of its neighbors in the graph that do not
appear in ancestors of $u$ and add them as children of $u$. Such neighbors
always exist since the tree will have no more than $\log n$ levels and each
node has degree at least $100\log n$ in the graph.

Given that there are only $n$ nodes in the graph, there must be a node that
appears more than once in the tree at the end. Let’s consider the first moment
when we grow a leaf by adding one child (labelled by $u$) and $u$ already
appeared in the tree. Note that the two nodes labelled by $u$ are not related
in the tree since we maintain the invariant that the label of a node does not
appear in its ancestors. Combining paths from these two nodes to the first
node at which the two paths diverge, we get a simple cycle of the graph.

We now adapt the above argument to prove the existence of a simple cycle $C$
of $G^{*}$ that satisfies the condition of Claim 5.11 by building a binary
tree of $2\log n$ levels as follows. We start with an arbitrary node
$u_{\textsf{root}}\in V_{1}^{*}$ as the root of the tree and expand the tree
level by level, leaf by leaf, as follows:

  1. 1.

Case $1$: The leaf we would like to grow is labelled a node $u\in V_{1}^{*}$.
In this case we add two children as follows. Let $u_{1}v_{1}^{(j_{1})}\cdots
u_{k-1}v_{k-1}^{(j_{k-1})}u$ be the path from the root ($u_{1}$) to $u$ in the
tree, where $u_{1},\ldots,u_{k-1},u\in V_{1}^{*}$ and
$v_{1}^{(j_{1})},\ldots,v_{k-1}^{(j_{k-1})}\in V_{2}^{*}$. We pick two
neighbors $v^{(j)},v^{\prime(j^{\prime})}$ of $u$ in $G^{*}$ with distinct
$v,v^{\prime}\in V_{2}$ as its children in the tree. We would like $v$ and
$v^{\prime}$ to satisfy the following two properties: (1) $v$ and $v^{\prime}$
do not lie in $\\{v_{1},v_{2},\cdots,v_{k-1}\\}$, (2) $v$ and $v^{\prime}$ are
different from $w^{*}(u_{i},v_{i}^{(j_{i})},v_{i}^{\prime(j_{i}^{\prime})})$
for every $i=1,\ldots,k-1$, where $v_{i}^{\prime(j_{i}^{\prime})}$ denotes the
other child of $v_{i}$ in the tree and (3) the move corresponding to
$\\{u,v^{(j)}\\}$ in $W$ and the move corresponding to
$\\{u,v^{\prime(j^{\prime})}\\}$ in $W$ are not consecutive moves. The
existence of $v^{(j)}$ and $v^{\prime(j^{\prime})}$ that satisfy (1), (2) and
(3) follows trivially from the fact that every node (in particular, $u$ here)
has degree at least $100\log n$ in $G^{*}$. Indeed, to satisfy (2) and (3),
for each time we may reject at most 2 possible leafs. Given that the tree will
only grow for $2\log n$ levels –the half of times with $V_{1}^{*}$ leafs and
the rest half with $V_{2}^{*}$ –, we have $k\leq\log n$ and there are at most
$2k\leq 2\log n$ edges of $u$ that need to be avoided. Moreover, no two edges
from $u$ go two the same $C(v)$ for some $v\in V_{2}$ (Because we don’t allow
parallel edges).

  2. 2.

Case $2$: The leaf we would like to grow is labelled a node $v^{(j)}\in
V_{2}^{*}$. In this case we just add one neighbor $u\in V_{1}^{*}$ of
$v^{(j)}$ as its only child. Let $u_{1}v_{1}^{(j_{1})}\cdots
v_{k-1}^{(j_{k-1})}u_{k}v^{(j)}$ be the path from the root to $v^{(j)}$. We
pick a neighbor $u\in V_{1}^{*}$ of $v^{(j)}$ in $G^{*}$ that satisfies (1)
$u\notin\\{u_{1},\cdots,u_{k}\\}$ and (2) $u$ is different from
$w^{*}(u_{i},v_{i}^{(j_{i})},v_{i}^{\prime(j_{i}^{\prime})})$ for every
$i=1,\ldots,k-1$ and $u$ is different from
$w^{*}(u_{k},v^{(j)},v^{\prime(j^{\prime})})$, where
$v_{i}^{\prime(j_{i}^{\prime})}$ denotes the other child of $u_{i}$ and
$v_{i}^{\prime(j_{i}^{\prime})}$ denotes the other child of $u_{k}$ in the
tree. The existence of such $u$ follows from the same argument as Case 1.

Given that the tree has $2\log n$ levels and there are only $n$ nodes, there
must be a node that appears more than once in the tree at the end, and let’s
consider the first moment when we grow a leaf by adding a child and the same
node already appeared in the tree. Similarly we trace the two paths and let
$u\in V_{1}^{*}$ be the node where the two paths diverge; note that given the
construction of the tree, this node must be a node in $V_{1}^{*}$, given that
nodes in $V_{2}^{*}$ only have one child in the tree. On the one hand, the way
we construct the tree makes sure that combining the two paths leads to a
simple cycle $C$ of $G^{*}.$ On the other hand, let
$v^{(j)},v^{\prime(j^{\prime})}\in V_{2}^{*}$ be the two children of $u$
(which are next to $u$ on the cycle). Then it is easy to verify that
$w^{*}(u,v^{(j)},v^{\prime(j^{\prime})})$ does not appear on the cycle we just
found.

This ends the proof of the lemma. ∎

$u_{8}=u_{5}$$v^{\prime(j^{\prime}_{{}^{\prime}7})}_{7}$$v_{7}^{(j_{7})}$$v^{\prime(j^{\prime}_{6})}_{6}$$v_{6}^{(j_{6})}$$u_{7}$$u_{6}$$u_{5}$$u_{4}$$v^{\prime(j^{\prime}_{{}^{\prime}5})}_{5}$$v_{5}^{(j_{5})}$$v^{\prime(j^{\prime}_{4})}_{4}$$v_{4}^{(j_{4})}$$v^{\prime(j^{\prime}_{3})}_{3}$$v_{3}^{(j_{3})}$$v^{\prime(j^{\prime}_{2})}_{2}$$v_{2}^{(j_{2})}$$u_{3}$$u_{2}$$v^{\prime\left(j_{1}^{{}^{\prime}}\right)}_{1}$$v_{1}^{(j_{1})}$$u_{1}=u_{\mathsf{root}}$

Figure 7: Example of Finding-Cycle Process.

##  6 General Case

We prove Lemma 3.3 for the general case. Let
$\mathcal{S}=(\mathcal{S}_{1},\ldots,\mathcal{S}_{N})$ be a valid move
sequence of length $N=n\log^{10}n$ that consists of both $1$-moves and
$2$-moves. We will consider two cases and deal with them separately: (1) the
number of $1$-moves in $\mathcal{S}$ is at least $N/\log^{5}n$; and (2) the
number of $1$-moves is at most $N/\log^{5}n$.

###  6.1 Case $1$

We consider the case when there are at least $N/\log^{5}n$ many $1$-moves. In
this case we show that there is a window $W$ of $\mathcal{S}$ such that
$\textsf{rank}_{\textsf{arcs}}(W)$ is large. The arguments used in this case
are similar to those used in [27, 24, 13]. Given a window $W$ of
$\mathcal{S}$, we write $V_{2}(W)$ to denote the set of nodes $u\in V(W)$ such
that at least two $1$-moves in $W$ are $\\{u\\}$.

######  Lemma 6.1.

There is a window $W$ of $\mathcal{S}$ such that

$|V_{2}(W)|=\Omega\left(\frac{\emph{{len}}(W)}{\log^{6}n}\right).$

###### Proof.

Any 1-move that is not the first 1-move of the vertex generates a new arc of
$\mathcal{S}$, so the total number of arcs is at least
$|\textsf{arcs}(\mathcal{S})|\geq N/\log^{5}n-n.$ Define the length of an arc
$\alpha$ $(i,j)$, $\textsf{len}(\alpha)$, to be $j-i$. Partition all arcs
based on their length, for any integer $i$ that $0\leq
i\leq\lfloor\log_{2}N\rfloor$, define

$\textsf{arcs}_{i}(\mathcal{S}):=\Big{\\{}\alpha:\alpha\in\textsf{arcs}(\mathcal{S}),\
\textsf{len}(\alpha)\in[2^{i},2^{i+1})\Big{\\}}.$

Since
$\sum_{i=0}^{\lfloor\log_{2}N\rfloor}|\textsf{arcs}_{i}(\mathcal{S})|\geq
N/\log^{5}n-n$, there exists $i^{*}$ such that

$|\textsf{arcs}_{i^{*}}(\mathcal{S})|\geq\frac{N/\log^{5}n-n}{\log_{2}N+1}\geq\frac{N}{10\log^{6}n}.$

Let $W_{r}^{\prime}$ be a window of length $2^{i^{*}+2}$ starting at a
uniformly random position in $\\{-2^{i^{*}+2}+1,\cdots,N\\}$, and
$W_{r}=W_{r}^{\prime}\cap[N]$. For any arc
$\alpha\in\textsf{arcs}_{i^{*}}(\mathcal{S})$, there are
$\textsf{len}(W_{r}^{\prime})-\textsf{len}(\alpha)$ possible starting points
for $W_{r}$ to contain $\alpha$. So

$\Pr[\alpha\in\textsf{arcs}(W_{r})\big{]}\geq\frac{\textsf{len}(W_{r}^{\prime})-\textsf{len}(\alpha)}{N+2^{i^{*}+2}-1}\geq\frac{2^{i^{*}+1}}{N+2^{i^{*}+2}}.$

From linearity of expectation, and $2^{i^{*}+2}\leq 4N$,

${\rm I}\kern-1.79993pt{\rm
E}\big{[}|\textsf{arcs}_{i^{*}}(W_{r})|\big{]}\geq|\textsf{arcs}_{i^{*}}(\mathcal{S})|\cdot\frac{2^{i^{*}+1}}{N+2^{i^{*}+2}}\geq\frac{2^{i^{*}+1}}{50\log^{6}n}\geq\frac{\textsf{len}(W_{r})}{100\log^{6}n}.$

We can pick $W$ so that
$|\textsf{arcs}_{i^{*}}(W)|\geq{\textsf{len}(W)}/{100\log^{6}n}$. By
definition of an arc, any vertex in one of the arcs in
$\textsf{arcs}_{i^{*}}(W)$ must be in $V_{2}(W)$. On the other hand, any arc
$\alpha\in\textsf{arcs}_{i^{*}}(W)$ has length at least
$2^{i^{*}}\geq\textsf{len}(W)/4$. So any vertex can have at most 4 arcs in
$\textsf{arcs}_{i^{*}}(W)$. We have

$V_{2}(W)\geq\text{\\# vertices in
}\textsf{arcs}_{i^{*}}(W)\geq|\textsf{arcs}_{i^{*}}(W)|/4\geq\frac{\textsf{len}(W)}{400\log^{6}n}$

This finishes the proof of the lemma. ∎

######  Lemma 6.2.

We have $\emph{{rank}}_{\emph{{arcs}}}(W)\geq\Omega(|V_{2}(W)|)$.

###### Proof.

Let $u_{1},u_{2},\cdots,u_{k}$ be the vertices in $V_{2}(W)$, and
$\alpha_{j}=(s_{j},e_{j})$ be the arc of $u_{j}$ formed by its first and
second 1-move. Since sequence $W$ is a valid move sequence, there exists a
vertex $v_{j}\not=u_{j}$ that moved odd number of times between $s_{j}$ and
$e_{j}$, i.e., $\tau_{s_{j}-1}(v_{j})=-\tau_{e_{j}-1}(v_{j})$. Pick an
arbitrary such $v_{j}$ for each $j$. Take a subset $U$ of $V_{2}(W)$ by the
following process:

  * •

$V\leftarrow V_{2}(W)$

  * •

$U\leftarrow\emptyset$

  * •

For $j$ from 1 to $k$, if $u_{j}\in V$, $V\leftarrow
V\backslash\\{u_{j},v_{j}\\}$, $U\leftarrow U\cup\\{u_{j}\\}$.

In each step we delete at most two element from $V$ and add one element to
$U$, so $|U|\geq|V_{2}(W)|/2$. Let
$U=\\{u_{i_{1}},u_{i_{2}},\cdots,u_{i_{m}}\\}$, ordered by the sequence they
are added. By the process, for any $u_{i_{j}}\in U$, and any $j^{\prime}>j$,
$v_{i_{j^{\prime}}}\not=u_{i_{j}}$.

Recall

$\textsf{imprv}_{\tau_{0},W}(\alpha_{i_{j}})_{(u_{i_{j}},v_{i_{j}})}=-\tau_{s_{i_{j}}-1}(v_{i_{j}})+\tau_{e_{i_{j}}-1}(v_{i_{j}})=2\tau_{e_{i_{j}}-1}(v_{i_{j}})\not=0.$

And for any $j^{\prime}>j$, $u_{i_{j}}\not=u_{i_{j}}$,
$v_{i_{j^{\prime}}}\not=u_{i_{j}}$, so
$\textsf{imprv}_{\tau_{0},W}(\alpha_{i_{j^{\prime}}})_{(u_{i_{j}},v_{i_{j}})}=0$.
Consider the matrix formed by taking the $j-$th column to be
$\textsf{imprv}_{\tau_{0},W}(\alpha_{i_{j}})$. The row indexed by
$(u_{i_{j}},v_{i_{j}})$ would be of the form

$(\underbrace{*,*,\cdots,*,}_{\text{$j-1$ unknown
numbers}}2\tau_{e_{i_{j}}-1}(v_{i_{j}})\not=0,0,\cdots,0).$

This means the matrix has a lower triangular square submatrix of size at least
$m\geq|V_{2}(W)|/2$. So we have
$\textsf{rank}_{\textsf{arcs}}(W)\geq|V_{2}(W)|/2$. ∎

###  6.2 Case $2$

Let $\mathcal{S}$ be a valid move sequence of length $N$ with no more than
$N/\log^{5}n$ many $1$-moves. Let $W$ be a window of $\mathcal{S}$. We write
$\\#_{W}(u)$ to denote the number of moves (including both $1$-moves and
$2$-moves) that $u$ appears in $W$, and write $\\#_{W}^{2}(u)$ to denote the
number of $2$-moves that $u$ appears in $W$.

We start by showing a lemma similar to Lemma 4.6 in Section 4.

######  Lemma 6.3.

Let $\mathcal{S}$ be a valid move sequence of length $N=n\log^{10}n$ with no
more than $N/\log^{5}n$ many $1$-moves. Then there exists a window $W$ of
$\mathcal{S}$ such that at least $\Omega(\emph{{len}}(W)/\log n)$ many moves
of $W$ are $2$-moves $W_{i}=\\{u,v\\}$ that satisfy

$\log^{3}n\leq\\#^{2}_{W}(u)\leq\\#_{W}(u)\leq
2\log^{7}n\quad\text{and}\quad\\#^{2}_{W}(v)\geq\log^{3}n$ (23)

###### Proof.

We would like to apply Lemma 4.6 (which works on move sequences that consist
of $2$-moves only). To this end, we let $\mathcal{S}^{\prime}$ be the move
sequence obtained from $\mathcal{S}$ by removing all its $1$-moves. Let
$N^{\prime}:=\textsf{len}(\mathcal{S}^{\prime})\geq(1-1/\log^{5}n)N$. Applying
Lemma 4.6 on $\mathcal{S}^{\prime}$,777Note that $\mathcal{S}^{\prime}$ has
length not exactly $N$ but $(1-1/\log^{5}n)N$ but the statement of Lemma 4.6
still holds. there must exist a positive integer $L$ and among the
$N^{\prime}-L+1$ windows $W^{\prime}$ of $\mathcal{S}^{\prime}$ of length $L$,
at least $\Omega(1/\log n)$-fraction of them satisfy that $\Omega(L/\log n)$
many $2$-moves $\\{u,v\\}$ in it satisfy

$\log^{3}n\leq\\#^{2}_{W^{\prime}}(u)\leq\log^{7}n\quad\text{and}\quad\\#^{2}_{W^{\prime}}(v)\geq\log^{3}n.$
(24)

Let’s denote these windows of $\mathcal{S}^{\prime}$ by
$W_{1}^{\prime},\ldots,W_{s}^{\prime}$ for some
$s=\Omega((N^{\prime}-L+1)/\log n)$. For each $W_{i}^{\prime}$ we let
$\mathcal{S}_{k_{i}}$ (or $\mathcal{S}_{\ell_{i}}$) to denote the move in
$\mathcal{S}$ that corresponds to the first (or last, respectively) move in
$W_{i}^{\prime}$, and let $W_{i}$ denote the window
$(\mathcal{S}_{k_{i}},\ldots,\mathcal{S}_{\ell_{i}})$ of $\mathcal{S}$.

If $L\geq N^{\prime}/2$, we can just take $W$ to be $W_{1}$. We note that the
number of $2$-moves in $W_{1}$ that satisfy (24) is at least $\Omega(L/\log
n)=\Omega(\textsf{len}(W_{1})/\log n)$ given that $L\geq N^{\prime}/2$. On the
other hand, the number of $u\in V(W_{1})$ that appears in at least $\log^{7}n$
$1$-moves of $W_{1}$ is at most $(N/\log^{5}n)/\log^{7}n=O(N/\log^{12}n)$.
Thus, the number of $2$-moves $\\{u,v\\}$ in $W_{1}$ that satisfy (24) but not
$\\#_{W_{1}}(u)\leq 2\log^{7}n$ is at most

$\log^{7}n\cdot O\left(\frac{N}{\log^{12}n}\right)=o\left(\frac{L}{\log
n}\right).$

So we assume below that $L<N^{\prime}/2$.

We claim that $W_{i}$ can satisfy the condition of the lemma if
$\textsf{len}(W_{i})\leq(1+1/\log^{2}n)L$. To see this is the case, we note
that the number of nodes $u\in W_{i}$ that appears in at least $\log^{7}n$
many $1$-moves is at most $(L/\log^{2}n)/\log^{7}n=O(L/\log^{9}n)$. Thus, the
number of $2$-moves $\\{u,v\\}$ in $W_{i}$ that satisfy (24) but not
$\\#_{W_{i}}(u)\leq 2\log^{7}n$ is at most

$\log^{7}n\cdot O\left(\frac{N}{\log^{9}n}\right)=o\left(\frac{L}{\log
n}\right).$

So it suffices to show that
$\textsf{len}(W_{i})\leq(1+1/\log^{2}n)\cdot\textsf{len}(W_{i}^{\prime})$ for
some window $W_{i}$. Assume this is not the case. Then the total number of
$1$-moves in $W_{1},\ldots,W_{s}$ is at least

$\frac{1}{\log^{2}n}\cdot\sum_{i\in[s]}\textsf{len}(W_{i}^{\prime})\geq\Omega\left(\frac{(N^{\prime}-L+1)L}{\log^{3}n}\right)=\Omega\left(\frac{NL}{\log^{3}n}\right)$

using $L<N^{\prime}/2$. However, each $1$-move can only appear in no more than
$L$ many windows of length $L$. Given that there are only $N/\log^{5}n$ many
$1$-moves, the same number can be upper bounded by

$\frac{N}{\log^{5}n}\cdot L,$

a contradiction. This finishes the proof of the lemma. ∎

So we now have a valid move sequence $W$ of length $L$, as a window of the
original valid sequence $\mathcal{S}$, such that the number of $2$-moves in
$W$ that satisfy (23) is at least $\Omega(L/\log n)$. The rest of the proof
follows the same arguments used in Section 5. We give a sketch below.

First we define the same auxiliary graph $H=(V(W),E)$ such that there is a
one-to-one correspondence between $E$ and $2$-moves in $W$. Note that the
degree of a node $u$ in $H$ is the same as $\\#_{W}^{2}(u)$.

We then show that there are disjoint sets of nodes $V_{1},V_{2}\subset V(W)$
and a subset of edges $E^{\prime}\subseteq E$ that satisfy conditions similar
to those of Lemma 5.1:

######  Lemma 6.4.

There are two disjoint sets of nodes $V_{1},V_{2}\subset V(W)$ and a subset of
edges $E^{\prime}\subseteq E$ such that

  1. 1.

Every edge in $E^{\prime}$ has one node in $V_{1}$ and the other node in
$V_{2}$;

  2. 2.

$|V_{1}\cup V_{2}|=O(L/\log^{3}n)$ and $|E^{\prime}|=\Omega(L/\log n)$;

  3. 3.

$\\#_{W}(u)\leq 2\log^{7}n$ for every node $u\in V_{1}$.

The proof is exactly the same as that of Lemma 5.1, except that we define $V$
to be the set of nodex $v$ with $\\#_{W}^{2}(v)\geq\log^{3}n$ and $V_{h}$ to
be the set of nodes $v$ with $\\#_{W}(v)\geq 2\log^{7}n$.

Next we focus on $E^{\prime\prime}$, which contains all edges in $E^{\prime}$
of the same sign (or edges in $E^{\prime}$ of different signs, whichever
contains more edges). Similarly every cycle in $E^{\prime\prime}$ corresponds
to a dependent cycle of $W$. The case when $E^{\prime\prime}$ contains many
parallel edges can be handled exactly the same way as in Lemma 5.5. So we may
delete all parallel edges from $E^{\prime\prime}$, and finish the proof using
Lemma 5.6.

The proof of Lemma 5.6 for the general case is very similar, with the
following changes:

  1. 1.

In the definition of $k_{v}$ for each $v\in\mathsf{wit}_{2}(\mathcal{E}_{s})$,
we need it to be the number of moves (including both $1$-moves and $2$-moves)
in $W$ that involve at least one node in $\mathsf{wit}_{1}(v)$. This can still
be bounded from above by $|\mathsf{wit}_{1}(v)|\cdot 2\log^{7}n$ since we have
$\\#_{W}(u)\leq\log^{7}n$ for all $u\in V_{1}$ as promised in Lemma 6.4 above.

  2. 2.

As we commented earlier, Claim 5.10 works even when $W$ consists of both
$1$-moves and $2$-moves.

This finishes the proof of Lemma 3.3 for the general case.

##  7 Binary Max-CSP and Function Optimization Problems

We recall the definition of binary maximum constraint satisfaction problems,
and more generally function optimization problems.

######  Definition 7.1.

An instance of Binary Max-CSP (Constraint Satisfaction Problem), or MAX 2-CSP,
consists of a set $V=\\{x_{1},\ldots,x_{n}\\}$ of variables that can take
values over $\\{0,1\\}$ and a set $C=\\{c_{1},\ldots,c_{m}\\}$ of constraints
with given respective weights $w_{1},\ldots,w_{m}$, where each constraint is a
predicate on a pair of variables. The MAX 2-CSP problem is: given an instance,
find an assignment that maximizes the sum of the weights of the satisfied
constraints.

Several problems can be viewed as special cases of Binary Max-CSP where the
predicates of the constraints are restricted to belong to a fixed family
${\cal P}$ of predicates; this restricted version is denoted Max-CSP(${\cal
P}$). For example, the Max Cut problem in graphs is equivalent to Max-
CSP(${\cal P}$) where ${\cal P}$ contains only the “not-equal” predicate
($x\neq y$, where $x,y$ are the two variables). The Max Directed Cut problem,
where the input graph is directed and we seek a partition of the nodes into
two parts $N_{1},N_{2}$ that maximizes the total weight of the edges directed
from $N_{1}$ to $N_{2}$, corresponds to the case that ${\cal P}$ contains only
the $<$ predicate (i.e. $x<y$). MAX 2SAT corresponds to the case that ${\cal
P}$ consists of all 4 possible clauses on two variables.

A generalization of MAX 2-CSP is the class of Binary function optimization
problems (BFOP) where instead of constraints (predicates) we have functions on
two arguments that take values in $\\{0,1,\ldots,d\\}$ instead of $\\{0,1\\}$,
where $d$ is a fixed constant (or even is polynomially bounded). For
convenience and consistency with the notation of configurations in the Max Cut
problem, we will use in the following $\\{-1,1\\}$ as the domain of the
variables instead of $\\{0,1\\}$. That is, the problem is: Given a set
$V=\\{x_{1},\ldots,x_{n}\\}$ of variables with domain $D=\\{-1,1\\}$, a set
$F=\\{f_{1},\ldots,f_{m}\\}$ of functions, where each $f_{i}$ is a function of
a pair $(x_{i_{1}},x_{i_{2}})$ of variables, and given respective weights
$w_{1},\ldots,w_{m}$, find an assignment $\tau:V\rightarrow D$ to the
variables that maximizes $\sum_{i=1}^{m}w_{i}\cdot
f_{i}(\tau(x_{i_{1}}),\tau(x_{i_{2}}))$.

Even though a function in BFOP (or a constraint in Max-2CSP) has two
arguments, its value may depend on only one of them, i.e. it may be
essentially a unary function (or constraint). More generally, it may be that
the two arguments of the function can be decoupled and the function can be
separated into two unary functions. We say that a binary function $f(x,y)$ is
separable if there are unary functions $f_{1},f_{2}$ such that
$f(x,y)=f_{1}(x)+f_{2}(y)$ for all values of $x,y$; otherwise $f$ is
nonseparable. For binary domains there is a simple criterion for separability:
a function $f(x,y)$ is separable if and only if
$f(-1,-1)+f(1,1)=f(-1,1)+f(1,-1)$ [25]. If in a given BFOP instance some
binary functions are separable, then we can decompose them into the equivalent
unary functions. Thus, we may assume, without loss of generality, that a given
BFOP instance has unary and binary functions, where all the binary functions
are nonseparable. We say that an instance is complete, if every pair of
variables appear as the arguments of a (nonseparable) binary function in the
instance.

The 2-FLIP local search algorithm can be applied to a MAX 2-CSP or BFOP
problem to compute a locally optimal assignment that cannot be improved by
flipping the value of any one or two variables. We will show that the smoothed
complexity of 2-FLIP for any complete MAX 2-CSP or BFOP instance is (at most)
quasipolynomial.

See 1.3

###### Proof.

Consider a (complete) instance $I$ of a BFOP problem with $n$ variables and
$m$ functions, and a sequence $\mathcal{S}$ of moves of 2-FLIP starting from
an initial configuration. The proof follows the same structure as the proof
for Max Cut. The only thing that changes is the improvement vector in each
step, which depends on the specific functions of the instance: the vector has
one coordinate for each function $f_{i}$ in the instance and the entry is
equal to the change in the value of the function resulting from the move. Arcs
and cycles of $\mathcal{S}$ are defined in the same way as in Max Cut, and the
improvement vectors of arcs and cycles are defined in an analogous way from
the improvement vectors of the moves.

The heart of the proof for Max Cut is Lemma 3.3 which showed that there is a
window $\cal{W}$ and a set of arcs or a set of cycles of $\cal{W}$ whose
improvement vectors have rank
$\Omega(\frac{\textsf{len}(\cal{W})}{\log^{10}n})$. We will show that the
lemma holds for any BFOP problem.

We associate with the BFOP instance $I$ the graph $G$ where the nodes
correspond to the variables of $I$ and the edges correspond to the binary
functions of $I$; since $I$ is a complete instance, the graph $G$ is the
complete graph, possibly with multiple edges connecting the same pair of nodes
(if there are multiple functions with the same pair of arguments). We will
identify the variables of $I$ with the nodes of $G$ and the functions of $I$
with the edges of $G$.

In the general case of the Max Cut problem, in Case 1 where there is a large
number of 1-moves, we identified a window $\cal{W}$ and a large set
$A^{\prime}$ of arcs in the window whose set of improvement vectors are
linearly independent. The argument relied only on the zero-nonzero structure
of the improvement vectors: it showed that the matrix $M$ formed by these
vectors and a set of rows corresponding to a certain set $E^{\prime}$ of
witness edges is a lower triangular matrix with nonzero diagonal. Take a set
$F^{\prime}$ of functions of $I$ that contains for each edge $\\{u,v\\}\in
E^{\prime}$ a function $f_{k}(u,v)$ with this pair as arguments (it exists
because the instance $I$ is complete), and form the matrix $M^{\prime}$ with
the set $F^{\prime}$ as rows and the set $A^{\prime}$ of arcs as columns. We
will show that the matrix $M^{\prime}$ has the same zero-nonzero structure as
$M$, thus it also has full rank.

Consider an arc of the move sequence $\mathcal{S}$ corresponding to two moves
$\mathcal{S}_{i}=\\{u\\}$, $\mathcal{S}_{j}=\\{u\\}$, $i<j$, and a function
$f_{k}$ of $I$. If $u$ is not one of the arguments of the function, then the
corresponding entry of the improvement vector of the arc is obviously 0. If
$u$ is one of the argument, i.e. the $k$-th function is $f_{k}(u,v)$
(similarly if it is $f_{k}(v,u)$), then the corresponding entry of the
improvement vector of the arc is
$\gamma_{i}(u)[f_{k}(\gamma_{i}(u),\gamma_{i}(v))-f_{k}(-\gamma_{i}(u),\gamma_{i}(v))]-\gamma_{j}(u)[f_{k}(\gamma_{j}(u),\gamma_{j}(v))-f_{k}(-\gamma_{j}(u),\gamma_{j}(v))]$.
If $v$ moves an even number of times between $\mathcal{S}_{i}$ and
$\mathcal{S}_{j}$, then $\gamma_{i}(v)=\gamma_{j}(v)$ and it follows that the
entry is 0, both in the case that $\gamma_{i}(u)=\gamma_{j}(u)$ and in the
case that $\gamma_{i}(u)=-\gamma_{j}(u)$. On the other hand, if $v$ moves an
odd number of times between $\mathcal{S}_{i}$ and $\mathcal{S}_{j}$, then
$\gamma_{i}(v)=-\gamma_{j}(v)$ and it follows that the $k$-th entry of the
improvement vector is
$\gamma_{i}(u)[f_{k}(\gamma_{i}(u),\gamma_{i}(v))-f_{k}(-\gamma_{i}(u),\gamma_{i}(v))]-\gamma_{j}(u)[f_{k}(\gamma_{j}(u),-\gamma_{i}(v))-f_{k}(-\gamma_{j}(u),-\gamma_{i}(v))]$.
Letting $\gamma_{i}(u)=a,\gamma_{i}(v)=b$, the entry is
$a[f_{k}(a,b)+f_{k}(-a,-b)-f_{k}(-a,b)-f_{k}(a,-b)]$ (both when
$\gamma_{i}(u)=\gamma_{j}(u)$ and when $\gamma_{i}(u)=-\gamma_{j}(u)$); this
quantity is nonzero because $f_{k}$ is nonseparable. Thus, the entry for
$f_{k}(u,v)$ of the improvement vector of the arc is nonzero exactly when the
entry of the arc in the Max Cut problem for the edge $(u,v)$ is nonzero. It
follows that the matrix $M^{\prime}$ has the same zero-nonzero structure as
$M$, thus it also has full rank.

In Case 2 of the Max Cut problem, where the number of 2-moves is very large,
there were two subcases. In the first subcase, where there are many parallel
edges in the graph that we associated with the window of the move sequence, we
found a large set of 2-cycles whose improvement vectors were linearly
independent. In the other case, where there are "few" parallel edges, we
constructed a large set of cycles (of length $O(\log n))$, again with linearly
independent improvement vectors. In both cases, the proof of linear
independence relied again only on the zero-nonzero structure of the vectors,
and not on the precise value of the entries. We will argue that in both cases,
the corresponding vectors of these cycles in the BFOP instance $I$ have the
same zero-nonzero structure.

In the first subcase we found many 2-cycles
$(u_{1},v_{1}),\ldots,(u_{k},v_{k})$, and corresponding "witness" edges
$(u_{1},z_{1}),\ldots,(u_{k},z_{k})$ such that the matrix $M$ with rows
corresponding to the witness edges and columns corresponding to the 2-cycles
in the Max Cut problem is lower triangular with nonzero diagonal. The nodes
$u_{i}$ are distinct (the $v_{i}$ and the $z_{i}$ may not be distinct) and
$z_{i}\neq u_{i},v_{i}$ for all $i$. For each witness pair $(u_{i},z_{i})$
pick a function $f_{r_{i}}$ of instance $I$ with this pair of variables as
arguments, in either order, say wlog the function is $f_{r_{i}}(u_{i},z_{i})$.
Consider the matrix $M^{\prime}$ with rows corresponding to the functions
$f_{r_{i}}(u_{i},z_{i})$ and columns corresponding to the 2-cycles
$(u_{i},v_{i})$. Note that the entry $M(j,i)$ is nonzero if one of the nodes
$u_{j},z_{j}$ is in $\\{u_{i},v_{i}\\}$ and the other node appears an odd
number of times between the two moves $\\{u_{i},v_{i}\\}$, and it is 0
otherwise, i.e. if $\\{u_{j},z_{j}\\}\cap\\{u_{i},v_{i}\\}=\emptyset$, or if
one of $u_{j},z_{j}$ is in $\\{u_{i},v_{i}\\}$ and the other node appears an
even number of times between the two moves $\\{u_{i},v_{i}\\}$. Importantly it
cannot be that $\\{u_{j},z_{j}\\}=\\{u_{i},v_{i}\\}$ because $u_{j}\neq
u_{i},v_{i}$. Examining the value $M^{\prime}(j,i)$ in the same way as in the
case of arcs above, we observe that if $M(j,i)=0$ then also
$M^{\prime}(j,i)=0$, and if $M(j,i)\neq 0$ then also $M^{\prime}(j,i)\neq 0$.
Thus, $M^{\prime}$ has the same zero-nonzero structure as $M$ and hence it has
also full rank.

In the second subcase of Case 2, we found many cycles $C_{1},\ldots C_{k}$ and
corresponding witness edges $\\{u_{i},v_{i}\\}$ such that for every $i$, (1)
$C_{i}$ does not contain any $u_{j}$ for $j<i$, nor $v_{i}$, (2) $C_{i}$ has
exactly two edges incident to $u_{i}$ and node $v_{i}$ appears an odd number
of times between the two moves corresponding to these two edges, (3) if
$C_{i}$ contains $v_{j}$ for some $j<i$ (the cycle $C_{i}$ may go more than
once through $v_{j}$), then $u_{j}$ does not appear between any pair of moves
that correspond to consecutive edges of the cycle $C_{i}$ incident to $v_{i}$.
We used these properties in Max Cut to show that the matrix $M$ whose rows
correspond to the witness edges and the columns correspond to the cycles
$C_{i}$ is lower triangular with nonzero diagonal. As before, for each witness
pair $(u_{i},v_{i})$ pick a function $f_{r_{i}}$ of instance $I$ with this
pair of variables as arguments, and let $M^{\prime}$ be the matrix with these
functions as rows and the cycles $C_{i}$ as columns. We can use the above
properties to show that the matrix $M^{\prime}$ is also lower triangular with
nonzero diagonal. Property (2) and the fact that $v_{i}\notin C_{i}$ (from
property (1)) imply that $M^{\prime}(i,i)\neq 0$ for all $i$. Properties (1)
and (3) can be used to show that $M^{\prime}(j,i)=0$ for all $j<i$. Therefore,
$M^{\prime}$ has full rank.

Once we have Lemma 3.3 for the BFOP instance $I$, the rest of the proof is the
same as for Max Cut. The only difference is that, if the maximum value of a
function in $I$ is $d$ (a constant, or even polynomial in $n$), then the
maximum absolute value of the objective function is $md$ instead of $n^{2}$
that it was in Max Cut. ∎

##  8 Conclusions

We analyzed the smoothed complexity of the SWAP algorithm for Graph
Partitioning and the 2-FLIP algorithm for Max Cut and showed that with high
probability the algorithms terminate in quasi-polynomial time for any pivoting