Evolving Solutions to Graph Theory Problems
A THESIS
SUBMITTED TO THE FACULTY OF THE GRADUATE SCHOOL
OF THE UNIVERSITY OF MINNESOTA
BY
Luke Branson
IN PARTIAL FULFILLMENT OF THE REQUIREMENTS
FOR THE DEGREE OF
MASTER OF SCIENCE
Dr. Andrew Sutton
May 2023
© Luke Branson 2023
Acknowledgements
First I would like to acknowledge my advisor Dr. Andrew Sutton for his support and
advice during my time as a Master’s student at the University of Minnesota-Duluth.
Working with him has helped me discover a passion for research that I didn’t know I
would have, it has also provided me with the opportunity to travel to Boston where
I was able to meet other researchers and present our work at GECCO 2022.
I would also like to thank everyone in both the department of Computer Science
and the department of Mathematics and Statistics at the University of Minnesota-
Duluth. The staff, faculty, and student body has given me support and provided me
with a great learning environment.
i
Abstract
Randomized search heuristics such as evolutionary algorithms are general-purpose
techniques that have been shown to be effective at solving combinatorial optimiza-
tion problems. In this thesis, we use both empirical and theoretical techniques to
examine the use of a simple evolutionary algorithm, the (1+1) EA, applied to com-
binatorial optimization problems from graph theory. First, we investigate the evo-
lutionary algorithm on problems k-VertexCover, k-FeedbackVertexSet, and
k-OddCycleTransversal, and present Fixed-Parameter Tractable performance
guarantees for the (1+1) EA equipped with a tailored jump-and-repair operator. We
then follow up with empirical results of the (1+1) EA applied to the k-VertexCover
problem. Next we move on to investigate the (1+1) EA applied to graceful labeling.
We present the first rigorous runtime analysis of an evolutionary algorithm finding
graceful labelings of graphs, and prove polynomial time upper bounds for paths, stars,
and complete bipartite graphs with a constant sized partition. To supplement the
theoretical results, we also empirically compare the performance of the (1+1) EA to
that of a complete constraint solver.
ii
Contents
Contents iii
List of Tables v
List of Figures vi
1 Introduction 1
2 Background 3
2.1 Combinatorial Optimization . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Evolutionary Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2.1 Evolutionary Algorithms . . . . . . . . . . . . . . . . . . . . . 4
2.2.2 Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Runtime Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.1 Fixed-parameter tractable EAs . . . . . . . . . . . . . . . . . 11
2.3.2 Iterative compression . . . . . . . . . . . . . . . . . . . . . . . 12
2.4 Problems From Graph Theory . . . . . . . . . . . . . . . . . . . . . 13
2.4.1 Vertex Cover . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4.2 Odd Cycle Transversal . . . . . . . . . . . . . . . . . . . . . . 14
2.4.3 Feedback Vertex Set . . . . . . . . . . . . . . . . . . . . . . . 15
iii
2.4.4 Graph Labeling . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3 Results 20
3.1 Jump and Repair Operators . . . . . . . . . . . . . . . . . . . . . . . 21
3.1.1 k-Vertex Cover . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.2 Feedback Vertex Sets in Tournaments . . . . . . . . . . . . . . 31
3.1.3 Odd Cycle Transversals . . . . . . . . . . . . . . . . . . . . . 37
3.1.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2 Evolving Graph Labelings . . . . . . . . . . . . . . . . . . . . . . . . 51
3.2.1 Star Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.2.2 Bicliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.2.3 Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.2.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4 Conclusions 73
iv
List of Tables
v
List of Figures
2.1 Examples of graceful graphs with their graceful labelings. . . . . . . . 17
3.5 Mean running time of (1+1) EAk on random planted vertex cover
instances. Shaded bands represent standard deviation. . . . . . . . . 45
3.6 Mean running time of (1+1) EAk on vertex cover instances. Shaded
bands represent standard deviation. . . . . . . . . . . . . . . . . . . . 46
3.7 Mean running time of (1+1) EAk divided by n2 lnn on random planted
vertex cover instances. . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.11 Star graph K1,7 with a graceful labeling. . . . . . . . . . . . . . . . . 55
3.12 Path graph P10 with two graceful labelings (top and middle) and a
non-graceful labeling (bottom) that contains local symmetries from
each. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.13 Genotype-phenotype mapping from permutations of vertex labels into
selection of unique edges. This is composed with a linear function on
phenotype space. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.14 The top path is a baseline, the second path shows the operation R(x, i+
1, j), the third path shows the operation R(x, i, j − 1), paths four
through six demonstrate Case 3 subcase 1. . . . . . . . . . . . . . . 68
vi
3.15 Timing data for constraint solver, (1+1) EA and (1+1) EAℓ′ on path
graphs Pn. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.16 Timing data for constraint solver, (1+1) EA and (1+1) EAℓ′ on bi-
cliques K2,n−2. For (1+1) EAℓ′ we also compare size 1 and size 2
partial labelings. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.17 Timing data for EAs and constraint solver on cycle graphs Cn (left)
and wheel graphs Wn (right). . . . . . . . . . . . . . . . . . . . . . . 72
3.18 Timing data for (1+1) EAℓ′ and constraint solver on bicliques with
partition size 3 and 4. . . . . . . . . . . . . . . . . . . . . . . . . . . 72
vii
1 Introduction
Evolutionary Algorithms (EAs) also referred to as Genetic Algorithms (GAs) are
algorithms inspired by biological evolution, and use things like reproduction, muta-
tion, recombination, and selection to search for solutions to optimization problems.
They have been used as optimization tools in an industrial setting and studied aca-
demically for decades. EAs are a popular method for solving optimization problems
since they can optimize a function with little information about it. Many EAs are
considered to be black-box models where they only have access to the problem through
the use of their fitness functions. In this thesis we will examine the use of EAs for
solving combinatorial optimization problems, specifically graph theory problems.
First we present parameterized results, defined in 2.3.1, using repair operators,
defined in 2.2.2, for finding a k-VertexCover and k-OddCycleTransversal
in undirected graphs and finding a k-FeedbackVertexSet in tournaments in 3.1.
All of these are all considered NP-Hard graph problems closed under induced sub-
graphs. We prove that a simple EA, the (1+1) EA, can find a k-VertexCover
in O(2kn2 log n) time, if one exists. This is an exponential (in k) improvement over
the best-known parameterized bound for evolutionary algorithms on VertexCover
given by Kratsch and Neumann [31]. For the k-FeedbackVertexSet problem in
tournaments, we prove that the EA finds a feasible feedback set in O(2kk!n2 log n)
iterations in expectation, and for k-OddCycleTransversal, we prove the EA re-
quires at most O(3kkmn2 log n) time. To our knowledge, this is the first run time
analysis of an evolutionary algorithm on both FeedbackVertexSet and OddCy-
1
cleTransversal. In 3.1.4 we present empirical results on the k-VertexCover
problem.
If we let G = (V,E) be a graph where V is the set of vertices and E is the set of
edges, we call G a graceful graph if there exists a graceful labeling. A graceful labeling
is a vertex labeling of G with an injective mapping ℓ : V → X where X is a finite
set of labels. This vertex labeling induces a natural edge labeling where an edge
e = uv is assigned the label |ℓ(u) − ℓ(v)|. Suppose G has n vertices and m edges.
A vertex labeling is called a graceful labeling if X = {0, 1, . . . ,m} and ℓ induces an
edge labeling bijective to the set {1, 2, . . . ,m} := [m]. This implies the induced edge
labels under graceful labelings are unique.
Graceful labeling was first introduced by A. Rosa in 1967 [49] under the name of
β−valuation. Since then graceful labeling has become an important problem in pure
mathematics [22, 8], and has several real-world applications such as in coding theory,
determining ambiguities in X-ray crystallography, design of communication networks,
optimizing circuit layout [7], the configuration of antennas in radio astronomy [6] and
link-labeling algorithms in multi-protocol label switching (MPLS) networks [3].
The performance of the (1+1) EA when searching for a graceful labeling of a
graph can change depending on the structure of the graph, the fitness function, and
the mutation operator. We provide the first runtime analysis results of evolutionary
algorithms on the graceful labeling problem, providing bounds for the (1+1) EA
equipped with different mutation operators and fitness functions, on different classes
of graphs in 3.2. We present the empirical results and discussion in 3.2.4.
2
2 Background
2.1 Combinatorial Optimization
We call the area of mathematics that is primarily concerned with counting Com-
binatorics. This is both used for obtaining results and defining properties of finite
structures, being closely related to other branches of mathematics and applied in
many other fields.
In this paper when we talk about optimization, or optimization problems, what
we mean is that we are looking for the best possible solution in the set of all feasible
solutions. A feasible solution is a point in the set of solutions that satisfies all the
constraints to the problem. When solving these types of problems there is usually
some value that we are trying to minimize or maximize.
Many of the problems of this type suffer from a combinatorial explosion: when
a problem exhibits a rapid grown of complexity based on the problems inputs, con-
straints, and bounds. This is relevant because as the problem grows in size, the
solution space grows rapidly, and with it the difficulty of solving the problem.
A combinatorial optimiztion problem is an optimization problem in which it is
necessary to search a discrete but large solution space to try to find an optimal solu-
tion. Usually these problems are inside a space so large that an exhaustive search is
not possible. More formally, given a finite but intractably large set X and a function
f , we want to find an element x ∈ X that maximizes (or minimizes) f(x). The Travel-
ing Salesman Problem, Integer Linear Programming, and Minimum Vertex Cover are
3
some examples of well-studied combinatorial optimization problems. Many of these
problems are important due to their real world applications, and are considered to be
NP-Hard. Some traditional methods of solving combinatorial optimization problems
are local search, constraint optimization, branch and bound.
We call a problem a constraint satisfaction problem (CSP) when there exists a set
of restrictions on what a solution can have, or a set of constraints or limitations that
must be satisfied for the problem to be considered solved. There has been extensive
research into different types of CSPs. These problems can modeled as optimization
problems.
GECODE is a complete constraint solver written in C++. It is open source and
provides a state-of-the-art performance while being modular and extensible [23]. It
can be used to find solutions for combinatorial optimization problems. In 3.2.4 we
compare the perfomance GECODE to the performance of a evolutionary algorithms,
defined in 2.2, for finding graph labelings 2.4.4.
2.2 Evolutionary Algorithms
2.2.1 Evolutionary Algorithms
As the name suggests, Evolutionary Algorithms (EAs), sometimes called Genetic
Algorithms (GAs), are randomized algorithms that use mechanisms inspired by bio-
logical evolution. In biological evolution, results become noticeable after many small
mutations occur over a long period of time, where only the fittest offspring are able to
survive and reproduce. Evolutionary algorithms take advantage of mechanisms like
reproduction, mutation, recombination, and selection.
We call a possible solution to a problem a candidate solution. We use a fitness
4
function to measure how well the candidate solution performs. Similar to biologi-
cal evolution, only the fittest are selected to reproduce. Each generation, candidate
solutions go through a process that changes the offspring, this process is called re-
combination or crossover if there are multiple candidate solutions being put together
to create more, or called mutation if only one parent is required. The hope is that
after generations of mutations we will find an optimal solution.
For many problems it is not feasible to check all possible solutions to find the best
solutions, and an approximate solution would be sufficient. In these types of problems,
EAs usually perform well. Due to how they are designed, evolutionary algorithms can
find many solutions to problems with multiple solutions or find approximate solutions
to problems that cannot be easily solved using other techniques.
When working with EAs and GAs, there are single objective optimization algo-
rithms and multi-objective optimization algorithms. As the name suggests, single
objective optimization algorithms have a fitness function defined to optimize a sin-
gle objective. Multi-objective optimization problems are generally seen to be more
difficult to solve than single objective optimization problems [42]. The (1+1) EA
Algorithm 1 and (µ + λ)−EA Algorithm 2 are both examples of single objective
algorithms, while Global SEMO Algorithm 3 [31] is an example of multi-objective
EA.
Algorithm 1: (1+1) EA-Generic
1 x← randomly generated Candidate Solution;
2 while stopping condition not met do
3 y ← x;
4 mutate(y);
5 if f(y) ≥ f(x) then x← y;
The (1+1) EA is a very simple single-objective optimization algorithm that has
5
been applied to many problems. It has a population of size one, and in each generation
there is only one offspring, with the better of the parent and the offspring moving
on to reproduce in the following generation. It has also been the target of runtime
analysis research [43], [20].
Algorithm 2: (µ+ λ)EA
1 Create P from µ uniformly at random generated candidate solutions;
2 while stopping condition not met do
3 P ′ ← P ; for i in range(λ) do
4 Choose x ∈ P uniformly at random;
5 y ← mutate(x) ;
6 P ′ ← P ′ ∪ {y} ;
7 Remove the λ candidate solutions with the lowest fitness from P ′;
P ← P ′;
The (µ+λ)−EA has a population of size µ and an offspring population size λ. This
algorithm is simple and similar to the (1+1) EA, but allows for a larger population
size, which can help with diversity. The (1+1) EA is a specific case of the (µ+λ)−EA
where µ = 1 and λ = 1.
Algorithm 3: Global SEMO
1 x← randomly generated Candidate Solution;
2 Find f(x);
3 P ← {x};
4 while stopping condition not met do
5 Choose x ∈ P uniformly at random y ← x;
6 mutate(y);
7 if If y is not dominated by x, for all x ∈ P then P ← {y} and P\{Z},
where Z is the set of all points weakly dominated by y;
Some problems benefit from trying to optimize not just one function, but multiple.
In multiobjective optimization problems the objectives can conflict, where one cannot
improve without the other getting worse.
6
In single objective optimization it is straightforward to compare the fitness of
two points, just choose the point that has a greater or a lesser fitness depending on
if we are trying to minimize or maximize. However, when trying to solve a multi-
objective optimization problems, we have k fitness functions f1, . . . , fk. These k
fitness function form a vector. So a candidate solution x has f : x → Rk. We also
could have conflicting fitness functions, where fi can only improve if fj gets worse.
To get around this it helps to define dominance as [16]:
A ⪰ B ⇐⇒ ∀i ∈ {1, . . . , n}ai ≥ bi, and∃i ∈ {1, . . . , n}, ai > bi
Where A,B are candidate solutions and A dominates B, and fi(A) = ai.
When the objectives are conflicting, there is no single solution that will dominate
all of the others, we call A nondominated if it is not dominated by any other. We
hold onto all of these nondominated solutions which we call Pareto Optimal in a set
F that we call the Pareto Front.
2.2.2 Operators
The seminal paper by Scharnow, Tinnefeld, and Wegener [51] introduced a version
of the (1+1) EA adapted to permutations using different mutation operators for
reordering the permutation. The simplest mutation operator is swap(i), in which
positions i and i+1 of the permutation are swapped. They also introduced three other
more general operations: exchange(i, j) which exchanges the elements at positions i
and j, jump(i, j) which makes the element at position i jump to position j shifting
all the elements between in the appropriate direction, and finally reverse(i, j), where
i < j, reverses the ordering of the elements in positions i, i+ 1, . . . , j.
More recently Doerr, Ghannane, and Ibn Brahim introduced the scramble muta-
7
tion operation [12]. This operation selects a random subset of the permutation and
shuffles, or scrambles, these positions by reordering with a random permutation.
In many problems, mutating the candidate solution will result in a new candidate
solution that is infeasible, or doesn’t satisfy basic constraints that any solution must
satisfy. When this happens many times the infeasible solution can be corrected using a
problem specific repair operator [10]. Using a repair operator allows the EA to freely
generate infeasible offspring that can be then made feasible at a low computational
cost.
Techniques for constraint-handling in evolutionary algorithms include penalty
functions, multi-objective optimization in both fitness and constraint space, special
operators (such as random keys) and repair mechanisms. When mutation or crossover
produce a solution that is infeasible, a repair operator will apply a transformation to
the infeasible solution to make if feasible again.
Early work on repair mechanisms in the context of evolutionary computation at-
tempted to reconcile the use of standard bit string representations for more restrictive
combinatorial structures. For example, Hamiltonian cycles in a graph can be easily
encoded as bit strings, but classical mutation and crossover operators are very un-
likely to result in offspring that are legal Hamiltonian cycles. This was an obstacle
for traditional genetic algorithms tasked to solve problems over permutations such as
the Traveling Salesperson Problem (TSP), and one proposed expedient was to repair
infeasible offspring by applying a greedy algorithm [34]. Repair-based crossover oper-
ators that work directly on permutation encodings have also been investigated [24, 40,
39]. For cardinality constraints on bit strings, the genetic fix and restricted search ap-
proaches ensure that offspring always have fixed Hamming weight after crossover [50].
Repair techniques for minimum vertex cover were examined empirically for hier-
archical Bayesian optimization (hBOA) and the simple genetic algorithm (SGA) [44].
8
The repair mechanism employed was a local search algorithm that transformed in-
feasible offspring into valid vertex covers. The authors found that these approaches
(along with simulated annealing) discovered optimal vertex covers on Erdo˝s-Re´nyi
random graphs significantly faster than complete branch-and-bound search.
One drawback to repair mechanisms (including the one we present in this thesis)
is that they are often problem-dependent, and require domain-specific knowledge [10].
Of course, it should be no surprise that extra domain knowledge can positively in-
fluence the efficiency of an evolutionary algorithm. For example, in the context of
VertexCover, He, Yao and Li [27] empirically demonstrated that allowing the mu-
tation probability for each bit to depend on the corresponding vertex degree resulted
in a significant performance gain over a pure black-box EA (i.e., access to the instance
only via the fitness function).
In the 2012 paper by Kratsch and Neumann [31] they find that Global SEMO
(Algorithm 3) equipped with the Alternative Mutation Operator in Algorithm 4 can
find a minimum vertex cover of size k in O(n2 + log n + k · n2 + n · 4k) time, giving
us a parameterized result, defined in Section 2.3.1.
Algorithm 4: Global SEMO Alternative Mutation Operator
1 Choose b ∈ {0, 1} uniformly at random;
2 if b=1 then
3 for i ∈ {1, . . . , n} do
4 If there exists an edge {vi, vj} ∈ E E(x), flip xi with probability 12 .
Otherwise flip xi with probability
1
n
5 else
6 for i ∈ {1, . . . , n} do
7 Flip xi with probability
1
2
.
9
2.3 Runtime Analysis
The amount of time needed to execute an algorithm, or how the size of an algo-
rithm’s input related to the number of steps needed to complete the algorithm is the
time complexity of an algorithm. The process of finding the time complexity of an
algorithm is called runtime analysis. Best, worst, and average case runtime are all
studied, since problems of the same size input may differ in performance.
Randomized search heuristics are computational procedured that generate stochas-
tic sequences of elements x(1), x(2), x(3), . . . ∈ X where the only access to f is through
evaluating these points. We define runtime of a randomized search heuristic as
T = inf{t : f(x(t)) is optimal} where T is a random variable, and runtime analy-
sis seeks to understand its expectation (and concentration).
To analyze the runtime of algorithms in this thesis we define runtime as the
number of calls to the fitness function. We let x(t) be the best candidate solution seen
by generation t. This allows the runtime T to be the first generation where f(x(T ))
is optimal.
The following theorems are commonly used for analyzing the runtime of evolu-
tionary algorithms. Specifically they are used to relate the expected change in one
step of the process to the time that it will take for the process to find a solution.
Theorem 1 (Additive Drift Theorem [26]). Let (Xt)t∈N be a sequence of nonnegative
random variables with finite support S ⊆ R≥0 such that 0 ∈ S. Let T := inf{t ≥ 0 :
Xt = 0}. Then, if there exists δ > 0 such that for all s ∈ S \ {0}, E[Xt−Xt+1 | Xt =
s] ≥ δ, then E[T ] ≤ E[X0]/δ.
Theorem 2 (Multiplicative Drift Theorem [13]). Let (Xt)t∈N be a sequence of non-
negative random variables with finite support S ⊆ R≥0 such that 0 ∈ S. Let smin =
min(S \ {0}) and let T := inf{t ≥ 0 : Xt = 0}. Then, if there exists δ > 0 such that
10
for all s ∈ S \ {0}, E[Xt −Xt+1 | Xt = s] ≥ δs, then E[T ] ≤ 1+E[ln(X0/smin)]δ .
2.3.1 Fixed-parameter tractable EAs
The theory of parameterized complexity [15, 19] allows the analysis of the run-
ning time of an algorithm to be decomposed into multiple parameters of the input.
The motivation is that many large intractable problems can be solved in practice
because real-world problem instances usually exhibit some kind of restriction over
their structure. Parameterized complexity aims to distill the source of hardness in a
problem class by isolating the superpolynomial contribution to the running time to a
parameter independent of the problem size.
Formally, a parameterized problem is a language L ⊆ Σ∗×N for a finite alphabet
Σ. A problem L is fixed-parameter tractable if (x, k) ∈ L can be decided in time
g(k)|x|O(1) for some function g that depends only on k. The complexity class of
fixed-parameter tractable problems is FPT. A problem L is slice-wise polynomial if
(x, k) ∈ L can be decided in time |x|g(k). The complexity class of slice-wise polynomial
problems is denoted XP. Note that for a problem in FPT, each fixed parameter value
determines (via g) the size of a leading constant of a polynomial running time, whereas
a slice-wise polynomial problem also has polynomial running time for each fixed-
parameter value, but each fixed parameter value governs the degree of the polynomial.
Applying parameterized complexity analysis to the run time analysis of evolution-
ary algorithms is useful when one would like to gain direct insight into how problem
instance structure influences run time on NP-hard problems [41, 54]. For a random-
ized search heuristic, the optimization time is characterized as a random variable T
that measures the number of fitness function evaluations until an optimal solution
is first visited. With a suitable fitness function, it is possible to apply randomized
11
search heuristics for optimization problems to decision problems as follows. An algo-
rithm is a Monte Carlo FPT algorithm for a parameterized problem L if it accepts
(x, k) ∈ L with probability at least 1/2 in time g(k)|x|O(1) and accepts x ̸∈ L with
probability zero. Any randomized search heuristic with a bound E[T ] ≤ g(k)|x|O(1)
on L can be trivially transformed into a Monte Carlo FPT algorithm by stopping its
execution after 2g(k)|x|O(1) iterations. It is therefore convenient to say a randomized
search heuristic runs in randomized FPT time on a parameterized problem of size n
when E[T ] ≤ g(k)nO(1) (similarly for randomized XP time).
2.3.2 Iterative compression
The technique of iterative compression was first presented by Reed, Smith and
Vetta for finding odd cycle transversals in a graph [48]. The main idea is to employ a
compression routine that takes as input a problem instance together with a solution
S and calculates a smaller solution or proves S is already of minimum size.
The running time of the compression routine depends exponentially on the size
|S| of the solution to compress, so a good way to utilize it is to build a graph up one
vertex at a time while always keeping the minimum possible solution. In other words,
starting with an empty graph V ′ = ∅ and S = ∅, since the problems we consider are
closed under induced subgraphs, S would be a valid solution of G[V ′]. We then iterate
over the vertex set V adding each vertex v to both V ′ and S (see Algorithm 5). In
each step, since S would again be a solution for G[V ′], we call the compression routine
on G[V ′] and S to compute a smaller solution for G[V ′], or certify none exists. Thus
if the compression routine runs in O(g(k) · nc) time for a constant c > 0, iterative
compression correctly solves the parameterized problem in O(g(k) · nc+1) time.
The iterative compression technique motivates the (1+1) EAk framework pre-
12
Algorithm 5: IterativeCompression
input: A graph G = (V,E)
1 V ′ ← ∅;
2 S ← ∅;
3 for v ∈ V do
4 V ′ ← V ′ ∪ {v};
5 S ← S ∪ {v};
6 S ← Compress(G[V ′], S);
7 return S;
sented in this paper. In the remainder of the paper, we will prove that the jump-and-
repair approach enables the (1+1) EA to simulate iterative compression, resulting in
the solution of certain NP-hard graph problems in randomized FPT time.
2.4 Problems From Graph Theory
2.4.1 Vertex Cover
Let G = (V,E) be a graph with V as the set of vertices and E as the set of edges,
where an edge connects two vertices. A graph can either be directed or undirected.
In an undirected graph, the edges go both ways, while in a directed graph, edges have
a specific direction, in this case the edges are often referred to as Arcs.
A Vertex Cover is a set of vertices of a graph such that an endpoint of every
edge is adjacent to a vertex of this set. The vertex cover problem is an optimization
problem in which we want to find the minimum number of vertices that form a vertex
cover. Given an undirected graph G = (V,E) where |V | = n and |E| = m we want
a subset V ′ ⊆ V of minimum cardinality such that for each e ∈ E, e ∩ V ′ ̸= ∅ holds.
This problem is both NP-Complete and fixed-parameter tractable. Due to this, it has
been the target for research [31, 43, 44, 30] .
13
A Matching is a set of edges of a graph that have no vertices in common. A
maximal matching is any matching of G that is not a proper subset of any other
matching. A maximum matching is a matching containing the largest possible number
of edges. There could be multiple maximum matchings. Each maximum matching
is also a maximal matching, however a maximal matching might not be a maximum
matching. The endpoints of a maximal matching form a vertex cover.
2.4.2 Odd Cycle Transversal
In an undirected graph G = (V,E) an odd cycle transversal is a set S ⊆ V such
that G[V \S] is bipartite. So S, a set of vertices, is an odd cycle transversal if the
graph G′ = ([V \S], E) is bipartite. Finding an odd cycle transversal is called a node-
deletion problem for a nontrivial hereditary property, and is NP-complete [33]. The
parameterized version for finding an odd cycle transversal of at most k, a k−odd
cycle transversal, is fixed-parameter tractable. The k−odd cycle transversal was
also the first problem to have an iterative compression technique developed, this was
done in the seminal paper of Reed, Smith, and Vetta [48]. In the paper the authors
presented an iterative compression algorithm for solving k-odd cycle transversal that
was O(4kkmn). Since then [29] improved the analysis further to O(3kkmn) and [35]
further simplified it. Currently the fastest parameterized algorithm for the problem
is O(2.3146k·poly(n)) and is due to Lokshtanov et al. [36].
A tournament is an orientation of a complete graph, that is, a directed graph
G = (V,E) such that for every distinct u, v ∈ V , either (u, v) ∈ E or (v, u) ∈ E. A
tournament G is transitive when
(u, v), (v, w) ∈ E =⇒ (u,w) ∈ E.
14
We call a tournament transitive if and only if it contains no directed cycles. More-
over, all cycles contain a directed triangle, yielding the following basic proposition.
Proposition 3. A tournament G is transitive if and only if it contains no directed
triangles.
Proof. If G contains a directed triangle, then it is not transitive. If G is not transitive,
it must contain some u, v, w ∈ V such that (u, v), (v, w) ∈ E but (u,w) ̸∈ E (otherwise
it is transitive). Since G is a tournament, it follows that (w, u) ∈ E so it contains the
directed triangle u→ v → w → u.
2.4.3 Feedback Vertex Set
In a directed graph G = (V,E) a feedback vertex set S ⊆ V is a set that intersects
every directed cycle in G. So an induced subgraph G′ = ([V \S], E) is transitive.
Finding a feedback vertex set of minimum size corresponds to the problem of making
an antisymmetric relation transitive by eliminating the smallest possible number of
elements. The problem is NP-hard [53, 9], however the parameterized version is in
FPT [14]. The parameterized version of the problem, k-FVST, has us start with a
tournament G and we search for a feedback vertex set of size at most k.
Since every transitive tournament has a unique topological sort by starting from
the vertex with zero in-degree, removing that vertex and recursively sorting the re-
mainder of the graph we have the following proposition.
15
Proposition 4. If G = (V,E) is a tournament and S ⊆ V is a feedback vertex set of
G, then there is a unique sequence on V \ S
Sort(G,S) := (v1, v2, . . . , v|V \S|),
where (vi, vj) ∈ E ⇐⇒ i < j.
2.4.4 Graph Labeling
Graph labeling is an assignment of labels to the vertices, edges, or faces of the
graph. The labels are generally represented by integers, but the problem of graph
coloring can be thought of as a graph labeling problem.
A labeling can be considered a function of the parts of the graph to a set of labels
L. For example a function from V onto L would be called a vertex-labeling, similarly
an edge-labeling would be a function from E onto L and a face-labeling would be a
function from F onto L, where F is the set of faces in the graph.
In 1967 Rosa introduced the β-valuation, a function f on a graph G = (V,E)
with m edges, where f maps V → {0, 1, . . . ,m} where each edge xy is given the label
|f(x) − f(y)|, and each of the edge labels is unique. The since the vertex labels are
unique, function |f(x) − f(y)| forces the edge labels to be in the set {1, 2, . . . ,m}.
The graceful labeling was introduced as a tool to be used to decompose graphs into
isomorphic subgraphs. [22]
Later on Golomb referred to the β-valuation as a graceful labeling, which is now
the popular term and will be referred to as such for the rest of this paper [22].
Several classes of graphs have been proved to be graceful (or not). For exam-
ple, the complete graph Kn is graceful if and only if n ≤ 4 [25, 7]. The cycle Cn
is graceful if and only if n ≡ 0 or 3 (mod 4) [49]. All paths, wheels [21], double
16
07
3
1
6
3
2
8
0
7
42
5
3
1 6
(a) Cycle graph C8
2
14
13
3
11
5
9
0 2
2
14 12
13
1
3
10
118
5
6
9
4
(b) Wheel graph W8
211
0
3
9 1
8
12
2
9
11
3
6
8
7
412
12
5
(c) Crown graph S04
0
3
1
6
2
9
3
6
9 2
5
8 1
4
7
(d) Bipartite graph
K3,3
Figure 2.1: Examples of graceful graphs with their graceful labelings.
wheels [32], helms [4], crowns and complete bipartite graphs [25] are graceful. We
refer to Figure 2.1 for an example of graceful labelings of some of these graphs.
There are many classes of trees known to be graceful including symmetrical trees,
trees with diameter at most 5, and trees with at most 4 end vertices. More generally
there exists the Kotzig-Ringel conjecture [22], also known as the Graceful Tree Con-
jecture, claims that all trees are graceful, for each tree there exists a graceful labeling.
Since this conjecture came into existence, many papers have been focused on trying
to prove partial results related to the Graceful Tree Conjecture.
Many direct labeling algorithms developed so far are computational approaches
for verifying the graceful tree conjecture on finite classes of trees. This conjecture,
sometimes called the Ringel-Kotzig conjecture, is that every tree admits a graceful
labeling.
The typical approach to this verification is to systematically generate each tree
with n vertices using the algorithm of Wright et al. [57] for small n, and then applying
some kind of search for a graceful labeling of each tree.
An early example of this was due to Aldred and McKay [2] who used this approach
to verify that every tree with at most 27 vertices is graceful. To find a graceful labeling
for a given tree, they employed an algorithm that searches the space of vertex label
17
permutations with a random vertex label swap operator and tabu list to hill climb on
the number of distinct edge labels induced by the vertex labeling.
Another approach by Horton [28] parallelized the search over trees and used greedy
backtracking search on each tree to show that trees with at most 29 vertices are
graceful. Fang [18] used a similar deterministic backtracking search together with
a stochastic local search heuristic with a tabu list and Metropolis-like acceptance
condition to verify all trees of to size 35 are graceful. This backtracking approach
labels a tree by first picking a “root” to label with 0, and then systematically assigning
legal labels until backtracking is necessary. If no labeling is found, a new vertex is
selected as root.
Eshghi and Azimi [17] posed the graceful labeling problem as an instance of integer
programming, and developed a branch-and-bound search algorithm. They experimen-
tally investigated the running time of this approach, and compared the performance
of different branching rules. Similarly, Redl [47] described an integer programming
approach, as well as a constraint programming approach to generating graceful label-
ings.
Mahmoudzadeh and Eshghi [37] developed an ant colony optimization (ACO)
metaheuristic for finding graceful labelings. In their approach, a vertex labeling is
characterized as a matching on the complete bipartite graph Kn,m+1 between the n
vertices and the m + 1 possible vertex labels. The cost of a vertex labeling is the
count of repeated induced edge labels. The ants are tasked at finding matchings that
minimize this cost, since a zero cost matching corresponds to a graceful labeling.
They empirically tested the running time on small graphs (up to 25 vertices) and
performed an experimental comparison between the ACO approach and the integer
programming approach of Eshghi and Azimi [17].
Graceful Labelings are important in pure mathematics, being the focus of many
18
mathematicians since first being introduced [22, 8]. Graceful Labelings have several
real-world applications such as in coding theory, determining ambiguities in X-ray
crystallography, design of communication networks, optimizing circuit layout [7], the
configuration of antennas in radio astronomy [6] and link-labeling algorithms in multi-
protocol label switching (MPLS) networks [3].
19
3 Results
In this chapter we will be discussing results related to different combinatorial opti-
mization problems. First we will consider parameterized graphs problems finding run-
time results for k-VertexCover, k-FeedbackVertexSet, and k−OddCycleTransversal
using the (1+1) EA and a tailored jump and repair operator. Then we will go on
to analyze the performance of the (1+1) EA when applied to the graceful labeling
problem, finding runtime results for different classes of graphs.
To collect our experimental results we used GNU parallel [56], a free software
package that allows users to execute multiple jobs in parallel using one or more
computers. We ran these experiments on a heterogeneous HPE cluster with AMD
ROME compute nodes provided by the Minnesota Supercomuting Institute (MSI) at
the University of Minnesota [38].
20
3.1 Jump and Repair Operators
In this section we will be considering multiple parameterized graph problems in
which we are given a graph G = (V,E), either directed or undirected, and a nat-
ural number k with the goal to find a set S ⊆ V with |S| ≤ k such that S is
in some sense feasible with respect to G. The problems we will consider are k-
VertexCover, where we we insist each edge of E is incident to at least one vertex
in S, k-FeedbackVertexSet, where deleting S from the graph leaves us with
a cycle-free graph, and k-OddCycleTransversal, where the graph obtained by
deleting S is bipartite.
Given a subset V ′ ⊆ V , the induced subgraph of G with respect to G, denoted
G[V ′], is the graph obtained from G by including only vertices from V ′ and edges from
E with both endpoints in V ′. Note that feasible solutions of the above listed problems
are closed under induced subgraphs, i.e., if S is feasible with respect to G, then for
any V ′ ⊆ V , S ∩ V ′ is feasible with respect to G[V ′]. The (open) neighborhood of a
vertex v ∈ V in G is defined as the set N(v) = {u : (v, u) ∈ E}. The neighborhood
of a set S ⊆ V is denoted by N(S) = ⋃v∈S N(v).
Evolutionary algorithms tasked with solving problems like VertexCover typi-
cally operate by representing a solution as a bitstring in {0, 1}n where |V | = n, which
selects elements from V to include in S. The task is then to minimize the Hamming
weight of the bitstring (and hence the cardinality of the chosen set) subject to the
constraint that it must be a feasible solution, e.g., a valid vertex cover. The hope is
that the algorithm would eventually find a feasible solution of Hamming weight k.
We will take a different perspective to parameterized graph problems by two new
insights
21
1. We expand the search space to both candidate solutions S and induced sub-
graphs of G.
2. We employ a focused jump-and-repair step that has the potential to efficiently
repair an offspring made infeasible by mutation.
Thus, instead of searching for S-sets in G where |S| ≤ k, we design the EA to
search for induced subgraphs of G such that |S| ≤ k and S is already a feasible solution
for the subgraph. The fitness of a solution is the size of the induced subgraph. In this
way, we systematically build up induced subgraphs together with already-feasible
sets until the entire graph is recovered. We argue that this approach is useful on
parameterized graph problems that are closed under induced subgraphs, such as the
ones we investigate in this paper.
To characterize both a set S and an induced subgraph of G, we define the search
space over {0, 1}2n so that a candidate length-2n bit string x has a length-n prefix
corresponding to vertices selected for the solution set and a length-n suffix corre-
sponding to vertices selected for the subgraph. It is convenient from an analytical
perspective to factor such a string into an ordered pair x := (xS, xV ) where xS corre-
sponds to a candidate solution set in the induced subgraph G[xV ]
1. Ignoring vertices
outside the induced subgraph, given a parameterized graph problem, a candidate
string x = (xS, xV ) has two feasibility constraints:
Solution constraint: xS must be a valid solution for G[xV ].
Cardinality constraint: |xS| ≤ k.
It is therefore convenient to use the following definitions.
1Here, and throughout the paper, we will often abuse notation by directly interpreting length-n
bitstrings as sets on n elements and vice-versa.
22
Definition 5. We say a string x = (xS, xV ) is solution feasible for G when xS is a
a valid solution for the induced subgraph G[xV ], that is, the vertex set S = xS ∩ xV is
feasible in the induced subgraph. We say x is cardinality feasible when |xS| ≤ k. We
say a x is infeasible if at least one of these properties is violated.
We define a general fitness function for a parameterized graph problems as follows.
fk(x) =

−(|xS|+ |xV |) if x is infeasible,
|xV | otherwise.
(3.1)
The function fk is designed to penalize infeasible solutions by attaining a negative
value that pressures solutions toward smaller sets and graphs, while feasible solutions
are rewarded for their size.
In Algorithm 6 we define the (1+1) EA equipped with an additional JumpAn-
dRepair operation as (1+1) EAj+rk . This is a rather general framework that can be
used to apply an evolutionary algorithm to parameterized graph problems, and we
will use for all of the problems that we consider.
Algorithm 6: (1+1) EAj+rk
input: A graph G on n vertices
1 choose x from {0, 1}2n uniformly at random;
2 while fk(x) < n do
3 Obtain y from x by flipping each bit with probability 1
2n
;
4 if y is solution feasible but not cardinality feasible then
5 y′ ← JumpAndRepair(y,G);
6 y ←{y,y′} fk;
7 if fk(y) ≥ fk(x) then x← y;
This outlines a rather general framework for applying an evolutionary algorithm
to a parameterized graph problem. Apart from the fitness function, there is only
23
one additional module that requires problem-specific knowledge to attempt to repair
solutions. Moreover, there is also a just-in-time appeal to this approach, as at any
point during the execution of the (1+1) EAj+rk , a feasible solution is a valid k-solution
to some induced subgraph.
In Algorithm 7 we give a general framework for the focused jump-and-repair op-
eration. It starts with taking a solution-feasible offspring, not necessarily cardinality
feasible, and executes a focused jump by selecting a random subset of the elements
of xS (in line 3) and then calling a problem-specific repair procedure if the set of se-
lected elements is not solution feasible (in line 5). This operation is successful when it
kicks out enough elements for the repaired string to be both cardinality and solution
feasible (see Figure 3.1).
Algorithm 7: JumpAndRepair
input: A pair of strings x = (xS, xV ) and a graph G
/* Jump */
1 S ′ ← ∅;
2 for i ∈ {1, . . . , n : xS[i] = 1} do
3 with probability 1/2 do S ′ ← S ′ ∪ {i};
4 if S ′ is solution feasible for G[xV ] then return (xS′ , xV );
/* Repair */
5 Find a minimal set T ⊆ xV \ xS s.t. S ′ ∪ T is solution feasible for G[xV ];
6 return (xS′∪T , xV );
Like the alternative mutation operator (Algorithm 4) for Global SEMO (Algo-
rithm 3) discussed earlier on page 9, the goal of the jump operation is to focus the
search on components of the solution that need attention. Unlike the alternative
mutation operator, which focuses on elements yet to be included in the solution,
the jump operation tries to find a promising subset of the solution that can then be
repaired.
The repair part of the operation is problem specific and later we will define different
24
offspring
focused jump
repair
solution-feasible
region
cardinality-feasible
region
feasible
region
Figure 3.1: A successful jump-and-repair operation transforms a cardinality-
infeasible offspring by focusing on a random subset of xS and applying a repair oper-
ation on the result to make it solution feasible again.
repair operators for each of the parameterized graph problems that we consider. It is
important that the repair operation runs in polynomial time for n for any meaningful
FPT results, however it could more generally run in FPT time.
According to Equation (3.1), any infeasible solution has a negative fitness, whereas
every feasible solution has nonnegative fitness. This immediately yields the following
lemma.
Lemma 6. If the underlying parameterized graph problem is closed under induced
subgraphs, then the (1+1) EAj+rk produces a feasible solution after O(n log n) steps in
expectation. After this point, it does not accept infeasible solutions.
Proof. We consider the potential function
ϕ(x) := max{−fk(x), 0}
and let (Xt)t≥0 be the stochastic process corresponding to the potential of the solution
25
generated by (1+1) EAk in the t-th iteration. The elitist nature of the (1+1) EAk
ensures that this potential is nonincreasing, and since feasible points always attain
nonnegative fk-values, ϕ(x) = 0 ⇐⇒ x is feasible. Thus it suffices to bound the
drift E[Xt −Xt+1 | Xt = s] and apply Theorem 2.
Assume that the point x in the t-th iteration is infeasible. It follows that Xt > 0,
and in fact, Xt = |x| by Equation (3.1). We argue that there is a reasonably good
chance that the (1+1) EAk can reduce the potential by at least one. For any index
i such that x[i] = 1, the probability of producing an offspring y by flipping only the
i-th bit of x to zero in the mutation step, leaving the remaining bits unchanged, is at
least
1
2n
(
1− 1
2n
)2n−1
≥ 1
2en
.
After this, if the offspring y happens to be solution feasible but not cardinality feasible,
then JumpAndRepair is called (line 5 of Algorithm 6) to produce an intermediate
point y′.
We now argue that y′ is copied back to y only if the potential of y′ is no larger
than the potential of y. Note that y′ is guaranteed to be solution feasible, since the
repair procedure always returns a cover. In the case that y′ is still not cardinality
feasible, then in line 6, y′ is copied back to y only if fk(y′) ≥ fk(y) (and hence
ϕ(y′) ≤ ϕ(y) = Xt − 1).
Otherwise, if y′ is also cardinality feasible, then it must be a feasible point. Since
all feasible points attain nonnegative fk-values, we have fk(y
′) > fk(x) and y′ becomes
the new offspring in line 6. We would then have Xt+1 = 0 < Xt. In any case, under
this mutation event, we have Xt+1 ≤ Xt − 1, and the mutation event occurs with
probability at least 1/(2en).
Summing over all one-bits in x, we have E[Xt−Xt+1 | Xt = s] ≥ s2en , and applying
26
Theorem 2, the expected time until a feasible solution z is first generated is O(n log n).
At this point, since fk(z) ≥ 0 and every infeasible solution has a negative fitness, no
infeasible solution is subsequently accepted.
3.1.1 k-Vertex Cover
The first FPT problem that we consider is the k-Vertex Cover Problem. In this
problem we are given an undirected graph G = (V,E) with |V | = n vertices and
|E| = m edges, a positive integer k, with the goal of finding a set S ⊆ V such that
|S| ≤ k and, for each {u, v} ∈ E, {u, v} ∩ S ̸= ∅, i.e., at least one endpoint of
every edge in E is in S. Since vertex covers are closed under induced subgraphs, our
framework introduced in Algorithm 7 is applicable.
In the following lemma we introduce a compression routine for k-Vertex Cover.
Lemma 7 (Compression for k-VertexCover). Suppose that S is a vertex cover of
a graph G = (V,E) with |S| > k, and that G has a vertex k-cover. Then a cover
of size at most k can be found by removing some subset R ⊆ S and repairing each
uncovered edge by adding N(u) for each u ∈ R.
Proof. Assume there is a vertex k-cover S∗ in G and let R := (S \ S∗) ⊆ S. Suppose
removing the vertices of R leaves a set F ⊆ E edges uncovered. Let {u, v} ∈ F be
an arbitrary uncovered edge, and w.l.o.g., assume u ∈ R. It follows that v ∈ S∗ since
S∗ is a cover for G. Thus, N(R) ∪ (S \ R) = S∗, and thus adding the vertices N(u)
for each u ∈ R obtains a k-cover for G.
In Algorithm 8 we present a jump-and-repair operator for vertex covers that we
were able to design using the result of Lemma 7. This operator takes a set selected
by xS and executes a focused jump by flipping each element in {i : xS[i] = 1} with
27
probability 1/2, hence choosing a random subset S ′ of the set selected by xS. If S ′
is already a vertex cover, this is returned. Otherwise, the solution S ′ is repaired to
be solution feasible by covering all of the uncovered edges with the neighbors of the
“removed” elements from xS \S ′. The resulting set is guaranteed to be a vertex cover,
which is then returned by the operator.
Algorithm 8: JumpAndRepairVC
input: A pair of strings x = (xS, xV ) and a graph G
/* Jump */
1 S ′ ← ∅;
2 for i ∈ {1, . . . , n : xS[i] = 1} do
3 with probability 1/2 do S ′ ← S ′ ∪ {i};
4 if S ′ is a vertex cover for G[xV ] then return (xS′ , xV );
/* Repair */
5 T ← ∅;
6 for v ∈ xS \ S ′ do
7 T ← T ∪N(v)
8 return (xS′∪T , xV );
Now in the next theorem we are able to show what the expected optimization
time is of the (1+1) EAj+rk .
Theorem 8. Let G = (V,E) be a graph with a k-vertex cover. Then the expected
optimization time of the (1+1) EAj+rk applied to G is bounded by O(2
kn2 log n).
Proof. By Lemma 6, a feasible solution is generated after O(n log n) iterations in
expectation and infeasible solutions are not accepted thereafter. It remains to bound
the time spent on feasible solutions. We consider the potential function ϕ(x) =
n− fk(x) and consider the stochastic process (Xt)t≥0 on {0, . . . , n} corresponding to
the potential ϕ of the solution generated by the execution of the (1+1) EAj+rk after
the first feasible solution is found.
28
Let x = (xS, xV ) be the solution in the t-th feasible iteration of (1+1) EA
j+r
k .
Since we assume x is feasible, |xS| ≤ k and corresponds to a cover on G[xV ]. Denote
by Ei the event that mutation changes xV [i] from 0 to 1 and that, after mutation,
xS[i] = 1. We argue that Pr(Ei) ≥ (2en)−2. It is sufficient that mutation flips bit i of
xV , which happens with probability
(
1− 1
2n
)2n−1 ≥ 1
2en
. To derive a lower bound on
the probability of Ei, we pessimistically assume that xS[i] = 0 which also flips with
probability at least 1
2en
.
After event Ei has occurred, the intermediate offspring corresponds to a new graph
G[xV ∪ {i}] and xS ∪ {i} must be a cover, since only vertex i was introduced, and all
edges in G[xV ∪{i}] incident to i are covered as i is in the set corresponding to xS∪{i}.
Therefore, this string is solution feasible (but not necessarily cardinality feasible). Let
J denote the event that the subsequent call to JumpAndRepairVC produces an
offspring y that is a valid k-cover of G[yV ]. Since x is feasible, then |xS| ≤ k, and it
holds that |xS ∪ {i}| ≤ k + 1. By Lemma 7, there is a k-cover that can be obtained
by removing a subset of elements in xS and ensuring that any uncovered edges are
covered by neighbors of xS. JumpAndRepairVC selects exactly this subset with
probability 2−|S| and so we have Pr(J | Ei) ≥ 2−|S| ≥ 2−(k+1).
We now argue that the joint occurrence of events Ei and J results in a feasible
offspring y with a strictly larger fitness value. In particular, |xV ∪{i}| = |xV |+1 and
so f(y) = f(x)+1 since J ensures that y is feasible. Therefore, the drift conditioned
on J ∩ Ei is 1. We can bound the total drift as follows.
E[Xt −Xt+1 | Xt = s] ≥
∑
i:xV [i]=0
Pr(J ∩ Ei) =
∑
i:xV [i]=0
Pr(J | Ei) Pr(Ei)
≥ |{i : xV [i] = 0}|
4e22k+1n2
= Ω
( s
2kn2
)
.
29
Applying Theorem 2 completes the proof.
It follows that the (1+1) EAk can be characterized as a Monte Carlo FPT al-
gorithm for the k-VertexCover problem on graphs. This also allows for one to
develop a strategy to finding the minimum vertex cover of a graph in FPT time. In
particular, consider the restart strategy for the (1+1) EAk listed in Algorithm 9.
Algorithm 9: Restart framework
input: A graph G = (V,E)
1 k ← 1;
2 while a vertex cover for G has not been found do
3 Run the (1+1) EAj+rk on G for 6e
22kn2 lnn steps;
4 k ← k + 1;
Theorem 9. Let G = (V,E) be a graph with an optimal vertex cover of size OPT .
Then with probability 1 − o(1), the restart framework of the (1+1) EAj+rk in Algo-
rithm 9 finds an optimal vertex cover for G within O(2OPTn2 log n) function calls.
Proof. Since there are no vertex covers for G of size k < OPT , Algorithm 9 is
successful when the run in which k = OPT finds a vertex cover for G. Thus, it suffices
to bound the probability of success in this run. Observe that this is equivalent to the
probability that an unbounded run would be successful before the cutoff time. Let T
denote the random variable that measures the optimization time on an unbounded
run of (1+1) EAj+rk with k = OPT , and let T = T1+T2 where T1 measures the steps
spent on infeasible solutions and T2 the steps spent on feasible solutions. We thus
seek to bound Pr(T1 + T2 < 6e
22OPTn2 lnn).
In the proof of Theorem 8, we have bounded the drift in the feasible phase from
below as δ ≥ 1/(e22k+1n2). Thus, setting r = 1
2
lnn in the tail bound of Theorem 2,
30
we get
Pr(T2 > 6e
22OPT−1n2 lnn) < e−r =
1√
n
.
Similarly, the drift in the infeasible phase, obtained in the proof of Lemma 6, is
δ = Ω(n), and so
Pr(T1 > 6e
22OPT−1n2 lnn) < e−Ω(n),
and it follows that
Pr(T1 + T2 < 6e
22OPTn2 lnn) = 1− o(1).
If Algorithm 9 is successful in its k-th run where k = OPT , it spends only a
constant fraction of time on too-small vertex covers, and the total optimization time
is
OPT∑
k=1
6e22kn2 lnn = O(2OPTn2 log n),
which completes the proof.
Ignoring polynomial factors, this constitutes an upper bound that is smaller by
an exponential factor (in OPT ) than the bound presented for global SEMO solving
minimum VertexCover, which requires O(n2 log n + OPT · n2 + 4OPTn) fitness
evaluations in expectation [31].
3.1.2 Feedback Vertex Sets in Tournaments
A feedback vertex set is a set S ⊆ V that intersects every directed cycle of G (and
thus G \ S is transitive). Finding a feedback vertex set of minimum size corresponds
to the problem of making an antisymmetric relation transitive by eliminating the
smallest possible number of elements. The problem is NP-hard [53, 9], however the
31
parameterized version is in FPT [14]. In the parameterized version of the problem,
k-FVST, we are given a tournament G, and the task is to find a feedback vertex set
of size at most k.
Figure 3.2: A transitive tournament on 8 vertices.
Every transitive tournament has a unique topological sort by starting from the
vertex with zero in-degree, removing that vertex and recursively sorting the remainder
of the graph. Thus we have the following proposition.
Proposition 10. If G = (V,E) is a tournament and S ⊆ V is a feedback vertex set
of G, then there is a unique sequence on V \ S
Sort(G,S) := (v1, v2, . . . , v|V \S|),
where (vi, vj) ∈ E ⇐⇒ i < j.
Similar to k-VertexCover, we can construct the following compression result
for k-FVST.
Lemma 11 (Compression for k-FVST). Let G = (V,E) be a tournament. Suppose
that S ⊆ V is a feedback vertex set of G (that is, G − S is transitive), and |S| > k.
Suppose there exists a feedback vertex set S∗ of G with |S∗| ≤ k. Then a feedback
vertex set of size at most k can be found by
32
1. removing a set R of vertices from S, and
2. guessing the correct relative ordering on R in Sort(G,S∗).
Proof. Set S ′ = S ∩ S∗ and R = S \ S ′. Let T denote the set of vertices v ̸∈ S that
appear in a directed triangle u, v, w where u,w ∈ R. It follows that T ⊆ S∗ because
otherwise G− S∗ would not be cycle-free.
We seek to find the smallest set that extends S ′ ∪ T but does not overlap with R
(note that S∗ is one such extension).
Pick an arbitrary W where W ⊇ (S ∪ T ). Note that W is a feedback vertex set
since G− S is transitive and W ⊇ S. We construct a sequence σW on V \W . Define
a labeling p : V \W → |π| as follows. For each v ∈ V \W ,
p(v) = min
(
{i : (v, πi) ∈ E} ∪ {|π|+ 1}
)
.
Then for all v, w ∈ V \W we set
v ≺σW w ⇐⇒

p(v) < p(w) or,
p(v) = p(w),Sort(G,W )[v] < Sort(G,W )[w].
We claim that σW = Sort(G,W ) if and only if W \R is a feedback vertex set for G.
First, assume σW = Sort(G,W ). Suppose for contradiction that there is a cycle
in G− (W \ R). Then by Proposition 3, there must be a directed triangle u, v, w in
G− (W \R). Note that G−W is triangle-free (since W is a feedback vertex set), so
there must be at least one vertex of this triangle in R. Furthermore, there can be at
most one vertex of this triangle in R since if there were two vertices appearing in R,
then the third would be in S ′∪T which do not appear in G− (W \R). Obviously, all
three triangle endpoints cannot be in R since S∗ is a feedback vertex set. Without
33
loss of generality, suppose u ∈ R and v, w ̸∈ R with (v, w) ∈ E. Note that u = πi
for some i and the triangle is completed by edges (w, πi) ∈ E and (πi, v) ∈ E.
Since (w, πi) ∈ E, it follows that i ≥ p(w), and since (πi, v) ∈ E, it follows that
i < p(v) and we have p(w) < p(v) and so w appears before v in σW . However,
(v, w) ∈ E so v appears before w in Sort(G,W ), which contradicts the assumption
the σW = Sort(G,W ).
Now suppose σW ̸= Sort(G,W ). Then there must be a pair v, w ∈ V \W with
(v, w) ∈ E but p(v) > p(w). This means for i = p(w), we have (w, πi) ∈ E and
(v, πi) ̸∈ E. But since G is a tournament, (v, πi) ̸∈ E =⇒ (πi, v) ∈ E. Since πi ∈ R,
there is a triangle v, w, πi in G− (W \R).
Thus, given S ′ and π, it suffices to find the minimal suchW so that σW is equal to
Sort(G,W ). This can be done by computing the sequences for σS∪T and Sort(G,S∪
T ) and adding to S ∪ T the vertices not in a longest common subsequence. Since we
know that there exists at least one feedback vertex set S∗ disjoint from R with size
at most k, it follows that this method computes a feedback vertex cover with size at
most k.
T
S ′
R
S S∗
u
vw
Figure 3.3: Illustration of possible directed triangles in the proof of the compression
lemma for k-FVST (Lemma 11).
Using Lemma 11, we are able to design a focused jump-and-repair operation for
34
Algorithm 10: JumpAndRepairFVST
input: A pair of strings x = (xS, xV ) and a tournament G
/* Jump */
1 S ′ ← ∅;
2 for i ∈ {1, . . . , n : xS[i] = 1} do
3 with probability 1/2 do S ′ ← S ′ ∪ {i};
4 R← xS \ S ′;
5 π ← a random permutation of R;
6 if G[xV \ S ′] is transitive then return (xS′ , xV );
/* Repair */
7 T ← ∅;
8 while ∃ a directed triangle u, v, w s.t. u,w ∈ R and v ̸∈ T do
9 T ← T ∪ {v}
10 for v ∈ xV \ (xS ∪ T ) do
11 p[v] = min({i : (v, πi]) ∈ E} ∪ {|π|+ 1})
12 σ ← Sort(G, xS ∪ T );
13 σ′ ← the sequence obtained by sorting xV \ (xS ∪ T ) by p and breaking ties
by σ;
14 Z ← vertices in longest common subsequence of σ and σ′;
15 return (xS′∪T∪(xV \Z), xV );
the k-FVST problem (Presented in Algorithm 10). This operation is slightly more
complicated than that of the k-VertexCover, since we also guess the correct or-
dering on the vertices removed from the current feedback set, and it is necessary to
find the longest subsequence common the two arrangements of the remaining ver-
tices. The former slows the optimization time by a factor of k!. The latter is not
directly reflected in the optimization time, but would incur an extra factor of O(n2)
in each repair operation for solving the LongestCommonSubsequence problem
using, e.g., dynamic programming [11]. Using this we are able to prove the following
Theorem.
Theorem 12. Let G = (V,E) be a tournament with a feedback vertex set of size
at most k. Then the expected optimization time of the (1+1) EAj+rk applied to G is
35
bounded by O(2kk!n2 log n).
Proof. We focus only on the phase of execution that consists of feasible solutions,
which occurs after O(n log n) iterations in expectation by Lemma 6.
As with the proof of Theorem 8, we bound the drift of the potential function
ϕ(x) = n − fk(x) modeled by the stochastic process (Xt)t≥0 which starts after the
first feasible iterations, and hits the absorbing state when a feedback vertex set of
size at most k on the entire graph G is discovered.
Again, assume that x = (xS, xV ) is the candidate solution in the t-th feasible
iteration of the (1+1) EAj+rk , and denote Ei as the event that changes xV [i] from
0 to 1 and xS[i] = 1 after mutation. The resulting string is solution feasible, but
not necessarily cardinality feasible. Let J be the event conditioned on Ei that the
subsequent call to JumpAndRepairVC results in a solution y that is a feedback
vertex set of size at most k for the induced subgraph G[yV ].
Since G has a k feedback vertex set, the induced subgraph G[xV ∪ {i}] must also
have a k feedback vertex set S∗ ⊆ xV ∪ {i}. With probability 2−(|xS |+1) the jump
phase of Algorithm 10 selects S ′ = (xS ∪ {i}) ∩ S∗, and with probability 1(|xS |+1−|S′|)! ,
it selects the permutation π that corresponds to the order of the vertices in xS \ S ′
in Sort(G[xV ∪ {i}, S∗].
By Lemma 11, if this jump operation was successful, the subsequent repair step
produces a feedback vertex set for G[xv ∪ {i}] with size at most k. Since |xS| ≤ k,
and |S ′| > 0, we have
Pr(J ) ≥ 2
−|xS |
(|xS|+ 1− |S ′|)! ≥
1
2k+1k!
.
As the resulting offspring y is feasible and |yV | = |xV |+1, it follows that f(y) > f(x).
By the same argumentation as in the proof of Theorem 8, Pr(Ei) ≥ (2en)−2, and
36
we bound the total drift as
E[Xt −Xt+1 | Xt = s] ≥
∑
i:xV [i]=0
Pr(J ∩ Ei)
=
∑
i:xV [i]=0
Pr(J | Ei) Pr(Ei)
≥ |{i : xV [i] = 0}|
4e22k+1k!n2
= Ω
( s
2kk!n2
)
,
and the claim is proved by applying Theorem 2.
3.1.3 Odd Cycle Transversals
The final FPT graph problem that we will consider is the k-OddCycleTransversal.
This problem has us search an undirected graph G = (V,E) for a set S ⊆ V such
that G[V \ S] is bipartite.
We layout a jump-and-repair operation in Algorithm 11. Given a solution feasible
odd cycle transversal that is not cardinality feasible, the jump procedure randomly
removes some vertices from the transversal, and then guesses a bipartition of these
removed vertices. The repair procedure, outlined in Algorithm 12, takes advantage of
a result presented by Lokshtanov et al. in [35] that relates two odd cycle transversals
in a graph to a vertex cut separating certain sets. After the jump, the repair attempts
to judiciously remove any odd cycles exposed by calculating a vertex cut in the
remainder of the graph.
The following lemma demonstrates the repair performed by Algorithm 12 is suc-
cessful if the jump is successful. The proof is similar to the proofs of Lemmas 3.2 and
3.3 of Lokshtanov et al. [35].
Lemma 13 (Compression for k-OddCycleTransversal). Let S be an odd cycle
37
Algorithm 11: JumpAndRepairOCT
input: A pair of strings x = (xS, xV ) and a graph G
/* Jump */
1 S ′ ← ∅;
2 for i ∈ {1, . . . , n : xS[i] = 1} do
3 with probability 1/3 do S ′ ← S ′ ∪ {i};
4 if S ′ is an odd cycle transversal for G[xV ] then return (xS′ , xV );
/* Repair */
5 R← xS \ S ′;
6 Select a bipartition A,B of R uniformly at random;
7 Calculate T using repair Algorithm 12 called with inputs G[xV ], S,R, A, B;
8 return (xS′∪T , xV );
Algorithm 12: Repair odd cycles that are exposed by removing R from S
input: A graph G = (V,E)
input: An odd cycle transversal S of G
input: A set R ⊆ S vertices to remove from S
input: A partition A,B of R
1 Let C and D be the bipartition of G[V \ S];
2 Find a minimal vertex cut T in G[V \ S] separating
(C ∩N(A)) ∪ (D ∩N(B)) and (C ∩N(B)) ∪ (D ∩N(A));
3 return T ;
A
B
S ′
C ∩N(A)
C ∩N(B)
D ∩N(A)
D ∩N(B)
S S∗
T
C
D
Figure 3.4: Illustration of partitions of G = (V,E) in the proof of the compression
lemma for k-OddCycleTransversal (Lemma 13).
38
transversal of a graph G = (V,E) with |S| > k, and suppose there exists an odd cycle
transversal S∗ of G with |S∗| < k. Then an odd cycle transversal of size at most k
can be found by
1. removing a set R of vertices from S,
2. guessing the correct partition A ⊎ B = R that splits R correctly into the bipar-
tition of G induced by S∗, and
3. running Algorithm 12 on these sets to repair any odd cycles exposed by removing
R.
Proof. Let S∗ be an odd cycle transversal of size at most k in G. Then G[V \ S∗]
is bipartite with bipartition VA, VB. We prove that if we remove the vertex set R :=
S \ S∗, then calling Algorithm 12 with sets R, A := R ∩ VA and B := R ∩ VB results
in an odd cycle transversal of size at most k. Let S ′ = S ∩ S∗ and C,D ⊆ V \ S be
the bipartition formed by S (see Figure 3.4 for an illustration).
We first argue that T := S∗ \ S is a vertex cut that separates (C ∩N(A)) ∪ (D ∩
N(B)) and (C ∩N(B)) ∪ (D ∩N(A)) in the graph G[V \ S].
Let P be a path in G[V \ (S ∪T )]. We show that P cannot connect (C ∩N(A))∪
(D ∩ N(B)) and (C ∩ N(B)) ∪ (D ∩ N(A)) in G[V \ S] by ruling out the possible
endpoints of P . Let (u, . . . , v) be the sequence of vertices associated with P .
Case 1: Suppose u ∈ C ∩ N(A) and v ∈ C ∩ N(B). Since u, v ∈ C and C is an
independent set in G[V \ (S ∪ T )], P must contain an odd number of vertices.
Furthermore, u has a neighbor a ∈ A and v has a neighbor b ∈ B. Thus
replacing the vertices in S \ S∗ would allow us to construct the path P ′ =
(a, u, . . . , v, b) in G[V \ S∗], also with an odd number of vertices. Since P ′ also
has an odd vertex count, there is no proper 2-coloring of P ′ that places its
39
endpoints in opposite color classes. But a ∈ A ⊆ VA and b ∈ B ⊆ VB, so this
contradicts the fact that G[V \ S∗] is bipartite with bipartition VA and VB.
Case 2: Suppose u ∈ C ∩ N(A), v ∈ D ∩ N(A). Since u ∈ C and v ∈ D, then P
has an even count of vertices. Note that both u and v have neighbors a, a′ ∈ A
(respectively), so replacing the vertices in S \S∗ would allow us to construct an
even-length path P ′ = (a, u, . . . , v, a′) in G[V \S∗]. Since P ′ has an even vertex
count, there is no proper 2-coloring of P ′ that places its endpoints in the same
color class. Again, this contradicts the fact that S∗ is an odd-cycle transversal
as described above.
Case 3: If u ∈ D ∩ N(B), v ∈ C ∩ N(B), then P cannot exist by a symmetric
argument to Case 2, swapping C with D and A with B.
Case 4: If u ∈ D ∩ N(B), v ∈ D ∩ N(A), then P cannot exist by a symmetric
argument to Case 1, swapping C with D and A with B.
Thus, no path exists in G[V \ (S ∪ T )] between the sets (C ∩ N(A)) ∪ (D ∩ N(B))
and (C ∩ N(B)) ∪ (D ∩ N(A)) and therefore T is a vertex cut separating these two
sets in G[V \ S].
Finally, we argue that if T ′ is any vertex cut separating (C ∩N(A))∪ (D∩N(B))
and (C ∩N(B)) ∪ (D ∩N(A)) in G[V \ S], then T ′ ∪ S ′ is an odd cycle transversal
in G.
Let Q be an arbitrary cycle in G[V \ (T ′ ∪ S ′)] and denote as (e1, e2, . . . , eq) the
sequence of edges in the order they appear in Q. It suffices to show that q must be
even. If Q has no vertices in A ∪B, then q must be even since S = A ∪B ∪ S ′ is an
odd cycle transversal. On the other hand, suppose Q has at least one point in A∪B.
We call an edge ei internal if ei ∩ (A ∪B) = ei, and external if ei ∩ (A ∪B) = ∅.
40
Similarly, we call a path an internal path when it is comprised only of internal edges.
An external path is an edge sequence (ei, . . . , ej) where |ei∩(A∪B)| = |ej∩(A∪B)| =
1, and the remaining edges are external. Note that Q can always be decomposed into
a sequence of internal and external paths where |e1 ∩ eq| = 1.
SinceG[A] andG[B] are independent sets, every internal path with both endpoints
in A or both endpoints in B has an even number of edges, and every internal path
with one endpoint in A and one endpoint in B has an odd number of edges.
Now consider an external path P in G[V \ (S ∪ T ′)] with endpoints u and v. If
u, v ∈ A then the vertex sequence for P is (u,w, . . . , y, v) for some w, y ∈ N(A). But
T ′ is a vertex cut separating C ∩N(A) and D∩N(A), so there are no paths between
these sets, so either w, y ∈ C or w, y ∈ D. In either case, the subpath from w to y
has an even count of edges in G[V \ (S ∪ T ′)] since C and D is a bipartition induced
by the odd cycle transversal S. A similar argument shows that external paths with
both endpoints in B must have even length, and one endpoint in A and one in B
must have odd length.
Now let Q = (P1, P2, . . . , Pℓ) be a decomposition of Q into internal and external
paths. Each path Pi with endpoints in A and B must have a return path Pi with
endpoints in B and A. Therefore, there must be an even number of paths Pi with an
odd count of edges, and so Q must contain an even count of edges.
To complete the proof, we see that Algorithm 12 finds a minimal vertex cut T ′
that separates (C∩N(A))∪(D∩N(B)) and (C∩N(B))∪(D∩N(A)), and |T ′| ≤ |T |
since T must also be such a vertex cut. As |S ′ ∪ T | ≤ k, it follows that S ′ ∪ T ′ is an
odd cycle transversal of G with size at most k.
The repair procedure of Algorithm 12 finds a minimum vertex separator between
two vertex sets, which can be done in O(nm) time by computing the maximum flow
41
in the appropriate network, e.g., by the Ford-Fulkerson method [11]. If we insist on
a vertex separator on size at most k, the running time bound can be improved to
O(km), as the existence of a separator of this size can be decided, and subsequently
constructed, within this bound. In the case that a vertex separator of size at most
k cannot be found, the repair procedure can return an arbitrary set (e.g., R), as the
repair would have failed.
We also point out a small deviation from the general JumpAndRepair procedure
listed in Algorithm 7. In line 3 of Algorithm 11, we only select a vertex for S ′ with
probability 1/3 rather than 1/2, which ultimately improves the bound by a (1.33)k
factor.
Theorem 14. Let G = (V,E) be a graph where |V | = n, |E| = m and G con-
tains an odd cycle transversal of size k. Then the expected optimization time of the
(1+1) EAj+rk applied to G is bounded by O(3
kkmn2 log n).
Proof. Again by Lemma 6, after O(n log n) iterations in expectation, all subsequent
solutions are feasible. Let x = (xS, xV ) be a feasible solution, that is, |xS| ≤ k and
corresponds to an odd cycle transversal of G[xV ]. Let i ∈ {j : xV [j] = 0} and let
Ei denote the event that after mutation xS[i] = xV [i] = 1 and no other bits have
changed.
Clearly, xS ∪ {i} is also an odd cycle transversal of G[xV ∪ {i}] so the resulting
offspring conditioned on Ei must be solution feasible, but not necessarily cardinality
feasible. In the latter case, note that we have assumed that G admits an odd cycle
transversal S∗ ⊆ V where |S∗| ≤ k. Since odd cycle transversals are closed under
induced subgraphs, (xV ∪ {i}) ∩ S∗ is an odd cycle transversal of G[xV ∪ {i}].
Let J1 be the event that in the jump phase of Algorithm 11, the process chooses
to flip to zero the set of bits R = (xS ∪ {i}) \ S∗, hence keeping the set S ′ =
42
((xV ∪ {i}) ∩ S∗) ∩ (xS ∪ {i}) set to 1. Let J2 be the event that R is partitioned
exactly into the sets A,B which are each respectively a subset of a bipartition induced
by (xV ∪ {i}) ∩ S∗. Then Pr(J1) = (2/3)|R|(1/3)|S′| and Pr(J2 | J1) = (1/2)|R|, so
we have Pr(J1 ∩ J2) = (1/3)|R|+|S′| ≥ 3−(k+1). Under this joint event, by Lemma 13,
Algorithm 12 must return an odd cycle transversal for xV ∪ {i} of size at most k.
Arguing in the same way as with the proofs of Theorems 8 and 12, we may set up
a potential function with multiplicative drift
E[Xt −Xt+1 | Xt = s] ≥
∑
i:xV [i]=0
Pr(J1 ∩ J2 ∩ Ei) ≥ |{i : xV [i] = 0}|
4e23k+1n2
= Ω
( s
3kn2
)
.
Applying Theorem 2, the expected number of iterations of the (1+1) EAj+rk until an
odd cycle transversal is generated for the entire graph G is O(3kn2 log n). Since the
repair procedure of Algorithm 12 costs O(km), we obtain the claimed result.
3.1.4 Experiments
To interpret the concrete running time of (1+1) EAj+rk on k-VertexCover
instances as a function of both n and k and to estimate the magnitude of hid-
den constants, we performed a number of experiments on different instances of k-
VertexCover. In order to maintain experimental control over both n and k, we
created three graph classes: random planted, clique/anticlique and biclique. In the
random planted class, instances are randomly generated by drawing each graph from
a planted version of the standard Erdo˝s-Re´nyi random graph model in which a k-cover
is “planted” into the graph and edges are selected for inclusion with fixed probability
p subject to having an end point in the planted cover. In particular, each random
graph on n vertices with a planted k-cover was generated by first randomly choosing
k vertices for the vertex cover and then iterating over each vertex pair vi, vj, such that
43
i ∈ {1, . . . , k} and j ∈ {k+1, . . . , n}, and adding the edge (vi, vj) with probability p.
In the limiting case of p = 1 we obtain a (nonrandom) clique/anticlique instance
comprised of a k-clique fully connected to an n − k anticlique, that is, every vertex
in the k-clique is connected to every other vertex in the graph, and the remaining
vertices are connected to every vertex in the k-clique (but not each other). Finally,
we also investigate bicliques Kk,n−k, that is, complete bipartite graphs with k vertices
in one of the partitions.
We generated graph instances using values of n ∈ {20, 30, . . . , 100} and k ∈
{3, 4, . . . , 8}. For the nonrandom graphs (clique/anticlique and biclique) we generated
an instance for each n and k, resulting in 54 instances each of the two classes. For
the random graphs, we also controlled for edge density using p ∈ {0.1, 0.25, 0.5, 0.75},
and for each value of n, k and p, we generated 10 separate random graph instances,
resulting in 2160 total random graph instances.
On each instance, we measured the mean (and standard deviation) of the iterations
required for the (1+1) EAk to find a k-cover for the entire graph over 100 runs per
instance. In Figure 3.5, we plot the mean running time as a function of n for the
random planted instances grouped by edge density p. The shaded bands represent
the standard deviation from the mean.
To compare the empirical running time to the bound proved in Theorem 8 and
assess the magnitude of hidden constants, we plot the mean running time normalized
by n2 lnn in Figures 3.7 and 3.8. The results here suggest that not only is the
normalized running time is bounded above by a fixed value that depends only on k,
as predicted, but also that the bound in Theorem 8 may be too large, at least for
these instances.
In order to observe the dependence of the running time on k for fixed n, we plot
the mean running time (again normalized by n2 lnn) as a function of k in Figures 3.9
44
20 40 60 80 100
0
2
4
6
8
·104
n
m
ea
n
ru
n
ti
m
e
k = 8
k = 6
k = 4
(a) p = 0.1
20 40 60 80 100
0
2
4
6
8
·104
n
m
ea
n
ru
n
ti
m
e
k = 8
k = 6
k = 4
(b) p = 0.25
20 40 60 80 100
0
2
4
6
8
·104
n
m
ea
n
ru
n
ti
m
e
k = 8
k = 6
k = 4
(c) p = 0.5
20 40 60 80 100
0
2
4
6
8
·104
n
m
ea
n
ru
n
ti
m
e
k = 8
k = 6
k = 4
(d) p = 0.75
Figure 3.5: Mean running time of (1+1) EAk on random planted vertex cover in-
stances. Shaded bands represent standard deviation.
and 3.10. We compare these results with a plot of 2k/100 and observe that the growth
with k appears to be even subexponential. The constant 1/100 is used as a scaling
factor for the comparison. We conjecture that these graph instances are relatively
easy to solve once a k-cover in an induced subgraph has been identified.
45
20 40 60 80 100
0
2
4
6
8
·104
n
m
ea
n
ru
n
ti
m
e
k = 8
k = 6
k = 4
(a) clique/anticlique
20 40 60 80 100
0
2
4
6
8
·104
n
m
ea
n
ru
n
ti
m
e
k = 8
k = 6
k = 4
(b) biclique
Figure 3.6: Mean running time of (1+1) EAk on vertex cover instances. Shaded
bands represent standard deviation.
46
20 40 60 80 100
0
1
2
3
n
m
ea
n
ru
n
ti
m
e/
(n
2
ln
n
) k = 8 k = 7
k = 6 k = 5
k = 4 k = 3
(a) p = 0.1
20 40 60 80 100
0
1
2
3
n
k = 8 k = 7
k = 6 k = 5
k = 4 k = 3
(b) p = 0.25
20 40 60 80 100
0
1
2
3
n
m
ea
n
ru
n
ti
m
e/
(n
2
ln
n
) k = 8 k = 7
k = 6 k = 5
k = 4 k = 3
(c) p = 0.5
20 40 60 80 100
0
1
2
3
n
k = 8 k = 7
k = 6 k = 5
k = 4 k = 3
(d) p = 0.75
Figure 3.7: Mean running time of (1+1) EAk divided by n2 lnn on random planted
vertex cover instances.
47
20 40 60 80 100
0
1
2
3
n
m
ea
n
ru
n
ti
m
e/
(n
2
ln
n
) k = 8 k = 7
k = 6 k = 5
k = 4 k = 3
(a) clique/anticlique
20 40 60 80 100
0
1
2
3
n
k = 8 k = 7
k = 6 k = 5
k = 4 k = 3
(b) biclique
Figure 3.8: Mean run time divided by n lnn of (1+1) EAk on vertex cover instances.
48
3 4 5 6 7 8
0
0.5
1
1.5
2
2.5
k
m
ea
n
ru
n
ti
m
e/
(n
2
ln
n
) n = 100
n = 90
n = 80
n = 70
n = 60
n = 50
2k/100
(a) p = 0.1
3 4 5 6 7 8
0
0.5
1
1.5
2
2.5
k
n = 100
n = 90
n = 80
n = 70
n = 60
n = 50
2k/100
(b) p = 0.25
3 4 5 6 7 8
0
0.5
1
1.5
2
2.5
k
m
ea
n
ru
n
ti
m
e/
(n
ln
n
) n = 100
n = 90
n = 80
n = 70
n = 60
n = 50
2k/100
(c) p = 0.5
3 4 5 6 7 8
0
0.5
1
1.5
2
2.5
k
n = 100
n = 90
n = 80
n = 70
n = 60
n = 50
2k/100
(d) p = 0.75
Figure 3.9: Mean run time of (1+1) EAk divided by n2 lnn on random planted vertex
cover instances as a function of k.
49
3 4 5 6 7 8
0
0.5
1
1.5
2
2.5
k
m
ea
n
ru
n
ti
m
e/
(n
ln
n
) n = 100
n = 90
n = 80
n = 70
n = 60
n = 50
2k/100
(a) clique/anticlique
3 4 5 6 7 8
0
0.5
1
1.5
2
2.5
k
n = 100
n = 90
n = 80
n = 70
n = 60
n = 50
2k/100
(b) biclique
Figure 3.10: Mean run time of (1+1) EAk divided by n2 lnn on vertex cover instances
as a function of k.
50
3.2 Evolving Graph Labelings
Similar to the work on local search for graceful tree labelings [2], we pose the
problem of finding graceful labelings as an instance of combinatorial optimization in
which the permutations of vertex labelings are searched to maximize the number of
unique induced edge labels. Let G = (V,E) be a graph on n vertices and m edges.
We represent a candidate labeling for V as a linear ordering on [m] ∪ {0}, i.e., an
ordered sequence x = (x1x2 . . . xm+1) of distinct integers. A linear ordering x induces
a labeling on V by assigning the label xi to vertex vi ∈ V . When m > n − 1, the
labels in xk for k > n are unused, and do not contribute to the labeling.
For a given candidate solution x we define the sequence of label counts Li(x), i =
1, 2 . . . ,m as
Li(x) = |{uv ∈ E : |xu − xv| = i}|.
We define the following sequence of indicator functions
χi(x) =

1 if Li(x) = 1,
0 otherwise.
By the definition of a graceful labeling we know that the candidate solution x corre-
sponds to a graceful labeling if and only if for all i ∈ [m], Li(x) = χi(x) = 1.
We define a weighted fitness function
f(x) =
m∑
i=1
wiχi(x). (3.2)
We will consider the following three weight variants, funit, in which wi = 1 for all
i ∈ [m], flin, in which wi = i for all i ∈ [m] and fexp, in which wi = 2i−1 for all
51
i ∈ [m]. We point out that flin is similar to the evaluation used in the local search
algorithm of Fang [18], but our version further penalizes non-unique induced edge
labelings.
Algorithm 13: (1+1) EA
input: A graph G = (V,E) on n vertices and m edges;
A fitness function f ∈ {funit, flin, fexp};
1 x← (0, 1, . . . ,m)
2 randomly shuffle x
3 while stopping condition not met do
4 y ← x
5 Draw r from a Poisson distribution with λ = 1
6 for i← 1 to r do
7 randomly exchange two elements of y
8 if f(y) ≥ f(x) then x← y
Due to local graph symmetries, the fitness landscape of the graceful labeling prob-
lem can contain local optima that are difficult to escape. One possible way of over-
coming these local symmetries is by fixing a small partial labeling and searching over
labelings of the remaining graph. In fact, this procedure can be used as a subroutine
for systematic search by exhaustively iterating over small partial labelings. For ex-
ample, this is exactly the approach taken for graceful labeling of trees by Fang [18]
in the context of backtracking search. For backtracking methods, this is a method
of symmetry breaking in which one would like to constrain the search to a subset of
the search space by adding a symmetry-breaking constraint that forces a vertex to
a certain label. This and other symmetry-breaking techniques have been shown to
be effective for constraint programming search with graceful labeling by Petrie and
Smith [45].
This kind of constraint symmetry breaking can also be useful for hill climbing
algorithms because it can result in a more favorably structured fitness landscape [46].
52
We implement such a framework in Algorithm 14, which takes a small constant set of
labels, and systematically iterates over all partial labelings and calls as a subroutine
a slightly modified EA (the (1+1) EAℓ′ , listed in Algorithm 15) with a predefined
budget to search over the remaining labels. In line 8 of Algorithm 15, we denote
ℓ′⊙ x as the vertex labeling of V obtained by joining the partial labeling ℓ′ of V ′ and
the partial labeling x of V \ V ′.
Algorithm 14: Symmetry-breaking restart framework for the (1+1) EA
input: A graph G = (V,E);
A fitness function f ∈ {funit, flin, fexp};
A set L of c = O(1) labels;
A runtime budget b;
1 for each subset S ⊂ V of size c do
2 for each partial labeling ℓ′ : S → L do
3 Run the (1+1) EAℓ′ on G for b steps with partial labeling ℓ
′
Algorithm 15: (1+1) EAℓ′
input: A graph G = (V,E) on n vertices and m edges;
A fitness function f ∈ {funit, flin, fexp};
A partial labeling ℓ′ assigning labels to V ′ ⊂ V ;
// x is a partial labeling of the induced subgraph G[V \ V ′]
1 x← a sequence on {0, 1, . . . ,m} \ ℓ′[V ′];
2 randomly shuffle x;
3 while stopping condition not met do
4 y ← x;
5 Draw r from a Poisson distribution with λ = 1;
6 for i← 1 to r do
7 randomly exchange two elements of y;
8 if f(ℓ′ ⊙ y) ≥ f(ℓ′ ⊙ x) then x← y;
For the following classes of graphs that we consider, there is a known partial
labeling that will result in a graceful labeling, so it is enough to prove runtime re-
sults for Algorithm 15. In the general case of the problem, a partial labeling may
53
not be known. We use the following proposition to connect the runtime results on
Algorithm 15 to the general framework of Algorithm 14.
Proposition 15. Let g(n) be an asymptotically positive function of n, c > 0 be a
constant, and G = (V,E) be a graceful graph with |V | = n vertices. Let L be a list of
at most c labels from {0, . . . ,m}.
Suppose that the (1+1) EAℓ′ has an expected runtime of at most T on G using
some partial labeling ℓ′ : V ′ → L. Then Algorithm 14 with a budget of b = g(n) · T
finds a graceful labeling for G with probability 1 − 1/g(n) using at most nc · g(n) · T
fitness evaluations.
Proof. By Markov’s inequality, the (1+1) EAℓ′ with partial labeling ℓ
′ is successful
within g(n)·T iterations with probability at least 1−1/g(n). Pessimistically assuming
that Algorithm 14 fails when checking every other n!/(n−c)!−1 ≤ nc partial labeling
from L. The total number of fitness evaluations is thus at most b · nc.
When proved rigorous runtime results on the running time of the (1+1) EA when
ran on various classes of graceful graphs. We find polynomial time upper bounds for
the (1+1) EA (or Algorithm 15) for all the classes of graphs that we consider.
3.2.1 Star Graphs
The first graph that we consider is the star graph (see Figure 3.11), or the complete
bipartite graph K1,m, a tree on n nodes and m edges with a single internal node of
degree m and m leaves. Graceful Labelings of stars are simple to find since any time
the graph has the internal node labeled with 0 orm, it is graceful. Because of this fact
every non-graceful vertex labeling neighbors a global optimum, making it particularly
easy for the (1+1) EA to find a solution.
54
12
3
4
5
6
7
0 1
2
3
4
5
6 7
Figure 3.11: Star graph K1,7 with a graceful labeling.
Theorem 16. Using any of the fitness functions funit, flin or fexp, the expected number
of fitness evaluations until the (1+1) EA finds a graceful labeling for K1,n−1 is at most
e(n2 − n)/4.
Proof. Given an arbitrary permutation x of vertex labels from [n − 1] ∪ {0}, we
assume without loss of generality, that x1 corresponds to the label of the vertex of
degree n− 1 (the center vertex). The induced label on each of the n− 1 edges of the
graph is |xi − x1| for i ∈ [n] \ {1}.
If 0 < x1 < n − 1, then there will be at least two edges with the induced label
z = |(x1 + 1) − x1| = |(x1 − 1) − x1|, and hence χz(x) = 0. Otherwise, each edge
label will be unique. Hence, the labeling corresponding to x is graceful if and only if
x1 = 0 or x1 = n− 1.
For any f ∈ {funit, flin, fexp}, f(x) =
∑m
i=1wi if and only if x corresponds to a
graceful labeling, otherwise, f(x) <
∑m
i=1wi. Thus, if mutation produces a graceful
labeling y in line 7 of Algorithm 13, it will always be accepted.
We bound the probability that mutation produces a graceful labeling. If x is not
graceful, there is a pair of indices k, ℓ ∈ [n] \ {1} where xk = 0 and xℓ = n− 1. Let E
denote the event that r = 1 in line 5 of Algorithm 13 and the single swap exchanges
1 with k or ℓ. Then,
Pr(E) = 4Pr (Pois(λ = 1) = 1)
n(n− 1) =
4
en(n− 1) .
55
Event E is sufficient to produce a graceful labeling from an arbitrary labeling x, so
the probability that a graceful labeling is produced in any iteration from a non- is
at least Pr(E). The waiting time until a graceful labeling is found is geometrically
distributed with expectation at most Pr(E)−1, completing the proof.
3.2.2 Bicliques
A biclique is a bipartite graph G = (V,E) where A,B is a partition of V such
that A and B are independent sets, and ab ∈ E for every a ∈ A and b ∈ B.
We consider highly unbalanced bicliques that have one partition with a small
constant size. It is likely that there are many different graceful labelings for bicliques,
but in the following lemma we prove that a partial labeling of the small partition
gives us a fitness landscape with a unique local optimum. We start by considering
the biclique K2,n−2 where |A| = 2 and |B| = n− 2.
Lemma 17. Consider the biclique K2,n−2 with independent sets A,B. Let ℓ be any
labeling such that a1, a2 ∈ A are ℓ(a1) = 0, ℓ(a2) = n−2. Then ℓ is a graceful labeling
if and only if
ℓ[B] =
{m
2
+ 1,
m
2
+ 2, . . . ,m
}
.
Proof. Let ℓ be such a labeling. Denote bi ∈ B such that ℓ(bi) = m/2 + i. An edge
incident on a1 has induced label |0−ℓ(bi)| = ℓ(bi) = m/2+i, whereas an edge incident
on a2 has induced label |(n − 2) − ℓ(bi)| = m/2 − (m/2 + i) = i since m/2 = n − 1.
Thus each of the m edges has a unique induced label from {1, 2, . . . ,m}.
On the other hand, let ℓ be a graceful labeling with ℓ(a1) = 0 and ℓ(a2) = n− 2.
Suppose for contradiction that there exists a j ∈ ℓ[B] where j ≤ m/2. Let b ∈ B
be the vertex such that ℓ(b) = j. Note that under these conditions 0 < j < m/2,
otherwise the uniqueness of vertex labels is violated. Since the induced label on edge
56
a1b is j, there cannot exist a b
′ ∈ B with ℓ(b′) = m/2+ j, otherwise the induced edge
label on a2b
′ would be |n − 2 − (m/2 + j)| = j, and therefore not unique. But this
implies no edge has induced label m/2 + j, contradicting the assumption that ℓ is a
graceful labeling.
Using this lemma we prove the following bound on the runtime of the (1+1) EAℓ′
on K2,n−2 when we give the smaller partition a partial labeling.
Theorem 18. Consider K2,n−2 with independent sets A and B such that |A| = 2. Let
ℓ′(a1) = 0, ℓ′(a2) = n− 2 be a partial labeling of the vertices in A. Then the expected
time of the (1+1) EAℓ′ to find a graceful labeling of K2,n−2 using any of the fitness
functions {funit, flin, fexp} is O(n2 log n).
Proof. We define a potential function on sequences (x1, x2, . . . , xm−1) of the label set
{0, 1, . . . ,m} \ ℓ′[A] = {1, 2, . . . , n− 3, n− 1, . . . ,m} as follows. For a given sequence
x, define
ϕ(x) = m−
m∑
i=1
χi(x) = m− flin(x).
Clearly ϕ(x) = 0 if and only if x corresponds to a graceful labeling.
Note that ϕ counts the number of edges where the induced label either (1) does
not appear in the labeling corresponding to x, or (2) appears more than once in the
labeling corresponding to x. We call an edge with a nonunique label bad.
Let ϕ(x) > 0. Since every edge has an induced label, there must exist bad edges
in the labeling corresponding to x. We argue that every bad edge either
1. Is incident to a vertex b ∈ B with ℓ(b) < m/2, or
2. Implies the existence of another bad edge incident to a vertex b ∈ B with
ℓ(b) < m/2.
57
To see this, consider the latter case in which a bad edge e is incident to a vertex
b′ ∈ B such that ℓ(b′) > m/2. Let k := m/2− ℓ(b′). It follows that e must be incident
to a2 since the induced label on the edge a1b is m/2 + k, which cannot be doubled
(and so χm/2+k(x) = 1). Therefore, since e is bad and incident to a2, the induced
edge label on e is |(n− 2)− (m/2 + k)| = k and it must be the case that χk(x) = 0.
But if e is bad, there must be another edge e′ = a′b′ with induced label k, and this
would imply ℓ(b′) = k < m/2.
We now show that for each bad edge, we can either repair it or its pair. Let
e be a bad edge incident to a vertex b ∈ B, and by the above argument, suppose
that ℓ(b) < m/2. Let e1 = a1b and e2 = a2b (hence e ∈ {e1, e2}). Furthermore, let
xi = ℓ(b) be the component of x corresponding to b’s label.
We make the following case distinction.
Case 1. Only one of the induced labels on e1 and e2 is unique. Let the unique
induced label be k, i.e., χk(x) = 1. This implies that there is no vertex b
′ such
that ℓ(b′) = m/2 + k, otherwise a2b′ would also have induced label k. So the
label xj = m/2 + k lies at index j > n − 2. Swapping xi and xj would thus
increase χm/2+k(x) from zero to one, whereas χk(x) would remain at one. Since
only the edge labeled k was unique, it follows that this swap gains a unique
edge, and thus decreases the potential ϕ by one.
Case 2. Neither of the induced labels on e1 and e2 are unique. This implies the
existence of an xj with j > n− 2 and xj > m/2. Since no edge can have label
xj, swapping xi and xj would gain at least one unique induced label, hence
decreasing the potential by at least one.
Consider the stochastic process (Xt)t∈N where Xt corresponds to the value of the
potential function ϕ applied to the candidate solution in the t-th step of the algorithm.
58
As argued above, if a candidate solution x produces ϕ(x) bad edges, at least ϕ(x)/2
are incident to vertex b ∈ B such that ℓ(b) < m/2, and this vertex corresponds to a
unique element xi = ℓ(b) where i ≤ n− 2. In either case above, there exists at least
one element xj with j > n− 2 such that swapping xi and xj reduces the potential ϕ
by at least one. Furthermore, since each fitness function {funit, flin, fexp} is inverseely
proportional to ϕ, a strict reduction in ϕ corresponds to a strict increase in the fitness,
and the resulting point is accepted. We therefore have E[Xt−Xt+1 | Xt] ≥ 2n(n−1) · Xt2 ,
and the claimed runtime bound follows by Theorem 2.
Now that we have seen a runtime bound when we the partial labeling completely
labels the smaller partiton, it is natural to ask if it is possible to find a similar bound
when we run the (1+1) EAℓ′ with only a single labeled vertex. The following theorem
shows that the O(n2 log n) bound of Theorem 18 is still possible, but now only as a
constant-probability tail bound. We may still bound the expectation by a cubic term.
Theorem 19. Consider the biclique K2,n−2 with independent sets A and B such
that |A| = 2. Let ℓ′(a1) = n − 2 be a partial labeling of the vertices in A. Then
the (1+1) EAℓ′ using partial labeling ℓ
′ has a runtime of O(n2 log n) with constant
probability, and O(n3) in expectation.
Proof. Let X be the set of all sequences on {0, 1, . . . ,m} \ {n− 2} and let X ′ ⊂ X
be the set of sequences {x ∈ X : χm(x) = 1}. Clearly, for all x, y ∈ X, if x ∈ X ′
and y ∈ X \X ′, then fexp(x) ≥ 2m > 2m − 1 ≥ fexp(y). Thus, once a sequence from
X ′ is generated by the (1+1) EAℓ′ , no sequence from X \ X ′ will be subsequently
selected. After this, we may apply the same drift arguments from Theorem 18 (using
bad edges adjacent to labels larger than m/2 if ℓ(a2) = m instead of zero).
A sequence x ∈ X ′ if and only if the indexes containing 0 and m are both at
most n − 1. Since in this case, |x| = m = 2(n − 2), with probability at least 1/4
59
the initial solution is already in x′, and applying Markov’s inequality to the result of
Theorem 18 yields the claimed tail bound.
Otherwise, we bound the time until a sequence from X ′ is first generated. Let x ∈
X \X ′ be an arbitrary point, and let xi = 0 and xj = m. Without loss of generality,
assume that x1 corresponds to the label on vertex a1. We also pessimistically assume
that both i, j > n− 1. To produce an offspring y ∈ X ′, it suffices to swap xi with x1
and xj with xj′ for any j
′ ≤ n− 1. The probability of such a mutation is at least
Pr (Pois(λ = 1) = 2)(
n−1
2
) · n− 1(n−1
2
) = 4
e2n2(n− 1) = Ω
(
1
n3
)
.
The waiting time until such a mutation occurs is distributed geometrically with ex-
pectation O(n3), after which the proof of Theorem 18 can be applied. The cubic term
dominates the expectation.
Theorem 18 can be generalized to all bicliques given a fixed partial labeling of one
of the partitions.
Theorem 20. Let Kc,n−c be a biclique with partitions A,B such that a1, a2, . . . , ac ∈ A
and ℓ′(ai) = (i− 1)(n− c) for all i ∈ {1, . . . , c} be the partial labeling of the partition
A. Then using any of the fitness functions funit, flin, or fexp, the expected runtime of
the (1+1) EAℓ′ is bounded above by O(n
2 log n).
3.2.3 Paths
A path Pn is a graph on V = v1, v2, . . . , vn where vi and vi+1 are adjacent for all
i ∈ {1, 2, . . . , n − 1}. Unlike star graphs, the structure of paths causes local sym-
metries that do not translate to global symmetries. This leads to synchronization
problems where all the local symmetries need to agree on an optimal solution. Syn-
60
0 9 1 8 2 7 3 6 4 5
9 8 7 6 5 4 3 2 1
8 1 9 0 6 3 7 2 4 5
7 8 9 6 3 4 5 2 1
0 9 1 8 6 3 7 2 4 5
9 8 7 2 3 4 5 2 1
Figure 3.12: Path graph P10 with two graceful labelings (top and middle) and a
non-graceful labeling (bottom) that contains local symmetries from each.
chronization problems are well-studied for pseudo-Boolean problems, particularly in
the case of so-called spin-flip symmetry DBLP:journals/ec/HoyweghenNG02. Fig-
ure 3.12 demonstrates these local symmetries.
To counter this, we fix a single end vertex with the label zero in a partial labeling
and run the (1+1) EAℓ′ . This breaks the symmetry and guarantees that there is only
a single global optimum, proven in Lemma 21. Note that in general, the number
of optimal solutions for Pn is Ω(2.37
n) [1]. It simplifies the proofs greatly to fix a
degree-one vertex, but we point out that Proposition 15 ensures that Algorithm 14
adds at most a linear factor overhead to systematically search each vertex to fix to
zero.
Lemma 21. Let Pn be the path on n vertices v1, v2, . . . , vn where vi is adjacent to vi+1
for all i ∈ [n − 1]. Then there is exactly one unique graceful labeling with ℓ(v1) = 0.
Moreover, this labeling corresponds to the vertex label sequence
x∗ = (0,m, 1,m− 1, 2,m− 2, . . . , ⌈m/2⌉),
where m = n− 1 is the number of edges in Pn.
Proof. Let e1, e2, . . . , em be the sequence of edges in Pn such that ei = vivi+1. The
induced edge label of ei under x
∗ is m+1− i, so each edge label in 1, 2, . . . ,m appears
exactly once. Thus, x∗ corresponds to a graceful labeling. Uniqueness is proved by
61
the following inductive argument. If ℓ(v1) = 0 is fixed, then there is only one valid
position for m, and that is adjacent to the zero in the first position (otherwise, the
induced edge label m would not appear). Therefore, m must appear in this position
in every graceful labeling. Consider now the subsequence x∗[1 . . k] where k ≥ 1.
Suppose for induction that every global optimum is identical to x∗ in the first k
elements. By construction, the element in the k-th position of x∗ is either ⌊k−1
2
⌋ or
m− ⌊k−1
2
⌋. Again, the only way for the induced edge label m− 2⌊(k − 1)/2⌋ − 1 to
appear is for the vertex label m− (⌊k−1
2
⌋+ 1), or respectively, (⌊k−1
2
⌋+ 1) to appear
in the next position of the sequence. But this is equal to x∗k+1. Thus x
∗ is unique.
Unfortunately, partial labeling is not enough to overcome problems that arise from
symmetry. We now prove the existence of local optima under the funit function that
are difficult to escape.
Proposition 22. Let Pn be the path on n vertices with m = n−1 edges. The sequence
xloc := (0,m− 1, 1,m− 2, 2, . . . , ⌊m/2⌋,m)
is a (nonstrict) local optimum in the for the (1+1) EAℓ′ using the fitness function
funit. Furthermore, x
loc is at distance Ω(n) from the global optimum.
Proof. Let e1, e2, . . . , em denote the sequence of adjacent edges of Pn. The sequence
of induced edge labels produced by xloc is
m− 1,m− 2,m− 3, . . . , 3, 2, 1, ⌈m/2⌉.
Therefore, all the induced edge labels are unique except for ⌈m/2⌉, which appears
exactly twice. Thus funit(x
loc) = m− 2. Note that funit(x) ≤ funit(xloc) for all x ̸= x∗
where x∗ is the unique global optimum for Pn described in Lemma 21.
62
Note that |{i : xloci ̸= x∗i } ≥ ⌊m/2⌋ since the labels do not match in every other
position. Since x∗ is the unique global optimum of Pn, it is necessary to move at least
⌊m/2⌋ elements. Since each swap can move at most two elements into the correct
position, we conclude that at least ⌊m/2⌋/2 ≥ (m− 2)/4 = Ω(n) swaps are necessary
to transform xloc into x∗.
In order to overcome local optima of the type presented in Proposition 22, we de-
compose Equation (3.2) into two components. Similar to the genotype-phenotype
maps from early work in genetic programming [5], we consider permutations of
{0, 1, . . . ,m} isomorphic to the symmetric group Sm+1, as the genotype space, and
the sets of unique edges in the corresponding labeling, isomorphic to (a subset) of
{0, 1}m as the phenotype space. Equation (3.1) can be written as the composition of
a linear function pseudo-Boolean function f : {0, 1}m → N and a genotype-phenotype
mapping g : Sm+1 → {0, 1}m. See Figure 3.13 for an illustration.
genotype space phenotype space
Sm+1 {0, 1}m
fi
tn
es
s
unique edges linear function
Figure 3.13: Genotype-phenotype mapping from permutations of vertex labels into
selection of unique edges. This is composed with a linear function on phenotype
space.
We use Domino Convergence to our advantage. Employing the exponentially
weighted fitness function fexp forces the phenotype function into domino convergence.
fexp causes unique edges to become fixed one-by-one, preventing the (1+1) EAℓ′ from
becoming stuck in a local optimum. Doing this we guarantee a polynomial time
expected performance of the (1+1) EAℓ′ on paths, proven in the next theorem.
63
Theorem 23. Let Pn be a path on n vertices and ℓ
′(v) = 0 be the partial labeling of
a single degree-one vertex of Pn. Then using the fitness function fexp, the expected
runtime of the (1+1) EAℓ′ is bounded above by
en3
4
.
Proof. Denote the vertices of Pn as v0, v1, . . . , vm, and the edges as e1, e2, . . . , em such
that ei = vi−1vi. Obviously, m = n− 1, and without loss of generality, let ℓ′(v0) = 0
in the (1+1) EAℓ′ . Let x
∗ = (m, 1,m − 1, 2, . . .) be the unique optimum described
in Lemma 21 with the zero element removed, and let x = (x1, x2, . . . , xn−1) be an
arbitrary permutation of (1, . . . , n − 1). We define the potential function over such
permutations as follows
ϕ(x) := n−min{{i ∈ [n− 1] : xi ̸= x∗i } ∪ n}.
Thus x is a graceful labeling (and fexp is maximized) if and only if ϕ(x) = 0.
We first argue that the potential cannot increase during a run of the (1+1) EAℓ′ .
For any sequence x,
fexp(x) ≥
m−ϕ(x)∑
k=0
2m−k = 2m+1 − 2ϕ(x),
since at least the induced edge labels e1, e2, . . . , em−ϕ(x) are unique. Moreover, we
have
fexp(x) ≤
(
m∑
k=0
2k
)
− 2m−(m−ϕ(x)+1) = 2m+1 − 2ϕ(x)−1 − 1,
because we know at least the induced edge label for em−ϕ(x)+1 is incorrect.
64
Thus, if y is produced from x during the mutation step of the (1+1) EAℓ′ and
ϕ(y) > ϕ(x),
fexp(x)− fexp(y) ≥ 2ϕ(y)−1 − 2ϕ(x) + 1 > 0,
and thus y would not be accepted.
Now let (Xt)t≥0 be the sequence of random variables corresponding to the values of
the potential function ϕ during a run of the (1+1) EAℓ′ . Let x be the current labeling
at time t (so Xt = ϕ(x)). Then the induced edge labels on edges e1, e2, . . . , em−ϕ(x)
are unique, since xn−ϕ(x) = xm−ϕ(x)+1 ̸= x∗m−ϕ(x)+1, there must be an element xj of
the sequence where j > n− ϕ(x) and xj = x∗m−ϕ(x)+1. A strictly improving move can
be produced by exchanging xj and xn−ϕ(x). This occurs with probability at least
2 Pr (Pois(λ = 1) = 1)(
n−1
2
) = 4
e(n− 1)(n− 2) .
Since such a move decreases the potential by at least one, the drift of the potential is
E[Xt−Xt+1 | Xt] ≥ 4e(n−1)(n−2) , and the claim follows by application of Theorem 1.
Naturally we wonder how the (1+1) EAℓ′ would perform when equipped with the
Jump or Reverse operations introduced in [51]. Using the same ideas as Theorem 23
we can prove the following Theorem.
Theorem 24. Let Pn be a path on n vertices and ℓ
′(v) = 0 be the partial labeling of
a single degree-one vertex of Pn. Then using the fitness function fexp, the expected
runtime of the (1+1) EAℓ′ equipped with the Jump or Reverse mutation operator is
bounded above by en
3
4
.
When we equip the (1+1) EAℓ′ with the fexp fitness function and the Reverse
mutation operator we are able to find a graceful labeling without fixing any of the
65
vertices and we do not need to rely on Domino Convergence. But first we need to
note the following.
Proposition 25. There are k+ 1 vertex pairs that can be selected for Reverse to get
the edge weight w(uv) = |xu−xv| = m−k such that xu > xv. These pairs are exactly:
(xu, xv) ∈ {(m, k), (m− 1, k − 1), . . . , (m− k, 0)} = Ck.
Let Lk(α) be a labeling of Pn where the k largest edge weights are unique and
part of α subpaths. We call a vertex label locked if it is an internal vertex on one of
the α subpaths.
Proposition 26. There are k − α locked vertices vertex labels in Lk(α).
Proof. Call the i-th subpath pi, and say |pi| is the number of vertices in the subpath.
There are then |pi| − 1 edges in the i-th subpath and |pi| − 2 interior locked vertices.
That means
∑α
i=1(|pi| − 1) = k so the total number of vertices in the subpaths is∑k
i=1 |pi| = k+ α and
∑α
i=1(|pi| − 2) =
∑α
i=1 |pi| − 2α = (k+ α)− 2α = k− α locked
vertices.
For a weight m− k, we call a vertex combination (xu, xv) infeasible if xu or xv is
locked in Lk(α). If we have the candidate solution x let R(x, i, j) be the Reverse oper-
ator that omits the candidate solution x′ = (x1x2 . . . , xj, xj−1, . . . , xi, xj+1, . . . , xm+1),
reversing xi, xi+1, . . . , xj. We can now prove the following lemma.
Lemma 27. Given Lk(α) we can use at most two Reverse operations to get Lk+1(α
′)
until k ≥ m
2
Proof. The largest weight not in Lk(α) is m − k, so to get Lk+1(α′) we need to add
this weight. Since there are k−α locked vertices 26 and there are k+1 combinations
66
to get edge weight m− k we get that there are (k+1)− (k−α) = α+1 vertex pairs
(xu, xv) ∈ {(m, k), (m− 1, k− 1), . . . , (m− k, 0)} such that neither xu or xv is locked.
This is because {m, k} ∪ {m − 1, k − 1} ∪ . . . ∪ {m − k, 0} = ∅, if k ≥ m
2
this is not
true. Now we know that there are α subpaths, so if each vertex is an end vertex in
one of the subpaths, there are at least two vertex labels not in these α subpaths. Let
(xi, xj) be vertex labels not in the same subpath giving edge weight m− k.
Case 1: Neither xi or xj are labels of end vertices of a subpath. The reverse operations
R(x, i+ 1, j) and R(x, i, j − 1) emit Lk+1(α + 1).
Case 2: Exactly one of xi or xj is the labeling of an end vertex of some subpath.
Without loss of generality, suppose this vertex is xi.
Subcase 2.1: Pi = vi, vi+1, . . . , vh is the subpath. We can use R(x, i, j − 1) to get
Lk+1(α).
Subcase 2.2: Pi = vh, vh+1, . . . , vi is the subpath. We can use R(x, i+ 1, j) to get
Lk+1(α).
Case 3: Both xi and xj are labelings of subpaths Pi and Pj respectively.
Subcase 3.1: xi and xj labelings of the left (or right) end vertices of their sub-
paths. Without loss of generality let them the the right end vertices. Then Pi =
vi, vi+1, . . . , vh and Pj = vj, vj+1, . . . , vh′ . We can use the operation R(x, i, j − 1) to
get Lk+1(α− 1).
Subcase 3.2.1: Pi = vi, vi+1, . . . , vh and Pj = vh′ , vh′+1, . . . , vj. We can use the two
operations R(x, h′, j) = x′ to reverse Pj and R(x′, i, j − 1) to get Lk+1(α− 1).
Subcase 3.2.2: Pi = vh, vh+1, . . . , vi and Pj = vj, vj+1, . . . , vh′ . We can use the two
operations R(x, j, h′) = x to reverse Pj and R(x′, i+ 1, j) to get Lk+1(α− 1).
Now that we know that there is always at least a pair of operations that will give
us a candidate solution with the next largest weight, we prove the following Theorem.
67
· · · xi−2 xi−1 xi xi+1 xi+2 · · · xj−2 xj−1 xj xj+1 xj+2 · · ·
· · · xi−2 xi−1 xi xj xj−1 xj−2 · · · xi+2 xi+1 xj+1 xj+2 · · ·m−
k
· · · xi−2 xi−1 xj−1 xj−2 · · · xi+2 xi+1 xi xj xj+1 xj+2 · · ·m−
k
· · · xi−1 xi xi+1 · · · xh · · · xh′−1 xh′ · · · xj−1 xj · · ·
· · · xi−1 xi xi+1 · · · xh · · · xh′−1 xj xj−1 · · · xh′ · · ·
· · · xi−1 xh′−1 · · · xh · · · xi+1 xi xj xj−1 · · · xh′ · · ·m−
k
Figure 3.14: The top path is a baseline, the second path shows the operation
R(x, i + 1, j), the third path shows the operation R(x, i, j − 1), paths four through
six demonstrate Case 3 subcase 1.
Theorem 28. Let Pn be a path on n vertices, using the fitness function fexp, the
expected runtime of the (1+1) EAℓ′ equipped with the Reverse mutation operator to
find a labeling with the largest m
2
edges unique is bounded by O(n5).
Proof. Let x = (x1, x2, . . . , xn−1) be an arbitrary permuation of (1, 2, . . . , n − 1).
Define the potential function over these permutations as
ϕ(x) = max{{i ∈ [n− 1] : χi(x) = 0} ∪ {0}}
ϕ(x) = 0 if an only if fexp(x) is maximized and x is a graceful labeling.
If we have a candidate solution x with the k largest induced edge weights being
unique, and a candidate solution x′ with the k+1 largest induced edge weights being
unique, we know that fexp(x
′) ≥ ∑ki=0 2m−i > ∑k−1i=0 2m−i ≥ fexp(x). Because of this
once a solution with the k largest induced edge weights being unique, all following
candidate solutions will have at least the k largest induced edge weights unique. Also
because of this ϕ will nver increase during a run of the (1+1) EAℓ′ .
68
Let (Xt)t≥0 be the sequence of random variables corresponding to ϕ during a run
of the (1+1) EAℓ′ . Also let x be the current labeling at time t (so Xt = ϕ(x)). We
know from 27 that we can find a strictly improving move using at most two Reverse
operations. This occurs with probability at least
Pr (Pois(λ = 1) = 2)(
n−1
2
)(
n−1
2
) = 1
e2(n− 1)2(n− 2)2 = Ω
(
1
n4
)
.
Since the potential is decreased by at least one when this move occurs, the drift
of the potential is E[Xt−Xt+1 | Xt] = O(n5), and the claim follows by application of
Theorem 1.
3.2.4 Experiments
To empirically investigate the runtime of the (1+1) EA and (1+1) EAℓ′ and com-
pare their performance against a complete constraint solver, we ran experiments on a
heterogeneous HPE cluster with AMD ROME compute nodes, distributing runs using
GNU Parallel [55]. We collected data on paths Pn, wheel graphs, cycles of length 0, 3
(mod 4) and various bicliques.
The problem of finding a graceful labeling can be characterized as a constraint
satisfaction problem [52] in which both the vertex and edge labels are variables and
there is a ternary constraint on each edge that enforces the edge variable is the
absolute difference of the variables corresponding to its incident vertices. Moreover,
the global AllDiff constraint is enforced over the set of vertex label variables and
edge label variables. To compare the evolutionary algorithms to a complete constraint
solver for this setting, we contrasted the (1+1) EA and the (1+1) EAℓ′ using the
different fitness functions to the GECODE constraint solver [23]. For each of the
different graphs classes and solving methods, we collected data for graph sizes between
69
5 10 15 20 25 30 35 40 45 50
0.0001
0.001
0.01
0.1
1
10
100
funit
flin
fexp
(1+1) EA
funit
flin
fexp
(1+1) EAℓ′
CSP solver
n
ti
m
e
[s
ec
]
Figure 3.15: Timing data for constraint solver, (1+1) EA and (1+1) EAℓ′ on path
graphs Pn.
n = 5 and n = 50. For each n, we collected 50 trials of each search algorithm, with a
two hour cutoff.
In Figure 3.15, we plot for each approach the wall clock time vs. n on path graphs
Pn. We see that the EAs outperform the CSP solver for finding graceful labelings,
and the advantage increases with n. Nevertheless, even for n > 26, the traditional
(1+1) EA is not able to find a graceful labeling within the cutoff. When we fix a
degree-one vertex to label zero and use the exponentially weighted function fexp, we
see extremely efficient behavior. In fact, this technique was the only one that could
solve up to P50, and could do so in a fraction of a second. This supports our theoretical
70
5 10 15 20 25 30 35 40 45 50
0.00001
0.0001
0.001
0.01
0.1
1
10
100
funit
flin
|ℓ′| = 2
funit
flin
|ℓ′| = 1
(1+1) EAℓ′
funit
flin
(1+1) EA
CSP solver
n
ti
m
e
[s
ec
]
Figure 3.16: Timing data for constraint solver, (1+1) EA and (1+1) EAℓ′ on bicliques
K2,n−2. For (1+1) EAℓ′ we also compare size 1 and size 2 partial labelings.
analysis that symmetry breaking with partial label-fixing and enforcing phenotypic
domino convergence is useful for this problem.
Figure 3.17 plots the running time of the algorithms in dependence of n on cycle
graphs Cn and wheel graphs Wn. The (1+1) EA outperforms the constraint solver on
cycles (the latter does not complete all trials within the cutoff already for n > 16),
and the (1+1) EA with the unit fitness function funit outperforms both the constraint
solver and the other fitness functions on wheels.
For bicliques K2,n−2, we measured the running time of the (1+1) EA and the
(1+1) EAℓ′ with a partial labeling assigning a1, a2 ∈ A the labels 0 and n − 2, as in
71
8 10 12 14 16 18 20 22 24
0.00001
0.1
1,000
funit
flin
fexp
(1+1) EA
CSP solver
n
ti
m
e
[s
ec
]
6 8 10 12 14
0.0001
0.1
100
funit
flin
fexp
(1+1) EA
CSP solver
n
ti
m
e
[s
ec
]
Figure 3.17: Timing data for EAs and constraint solver on cycle graphs Cn (left) and
wheel graphs Wn (right).
10 20 30 40 50
0.00001
0.01
10
funit
flin
(1+1) EAℓ′
CSP solver
n
ti
m
e
[s
ec
]
(a) K3,n−2.
10 20 30 40 50
0.00001
0.01
10
funit
flin
(1+1) EAℓ′
CSP solver
n
ti
m
e
[s
ec
]
(b) K4,n−4.
Figure 3.18: Timing data for (1+1) EAℓ′ and constraint solver on bicliques with
partition size 3 and 4.
the claim of Theorem 18. We also ran the (1+1) EAℓ′ with a size-one partial labeling
by assignment a1 the label n− 2 as in the claim of Theorem 19. Figure 3.16 reports
these results. The plot supplies empirical evidence that the expectation bound in
Theorem 19 is not tight, and that O(n2 log n), as in Theorem 18 is closer to the
truth. However, we note some strange oscillations in the timing of funit when |ℓ′| = 1.
This suggests the existence of local optima trapping the process on the funit fitness
landscape in this setting. We also plot the running time of the (1+1) EAℓ′ and
constraint solver in Figure 3.18 for larger partition sizes. Note that we omit fexp
for bicliques due to the fact that m = 2(n − c), and so as n approaches 32 + c, the
experiments begin to suffer from integer overflow on 64-bit architecture.
72
4 Conclusions
In this thesis we analyzed the performance of variations of the simple evolutionary
algorithm, the (1+1) EA, when applied to various combinatorial optimization graph
problems. In Section 3.1 we presented (1+1) EAj+rk , a variant of the (1+1) EA, that
uses a focused jump-and-repair operation to find feasible vertex sets of size k to solve
parameterized variants of graph problems closed under induced subgraphs. Instead of
searching for a vertex set that is feasible on the entire graph we search in parallel for an
induced subgraph and a vertex set that is feasible on this induced subgraph. When an
offspring is found that has a cardinality infeasible vertex set we give it the opportunity
to be probabilistically repaired by the focused jump-and-repair operation. Using this
approach we proved that the (1+1) EAj+rk is an FPT Monte-Carlo algorithm for the
k-VertexCover, the k-FVST, and the k-OddCycleTranversal problems. We
then proved that using a simple restarting framework allows the (1+1) EAj+rk can
solve the minimum VertexCover problem in O(2OPTn2 log n) where OPT is the
size of the optimal vertex cover. This upper bound outperforms the best known
upper bound for FPT evolutionary algorithms on the minimum VertexCover by
an exponential factor in OPT . We investigate leading constants and small-n behavior
empirically in Section 3.1.4.
A downside to our approach is the jump-and-repair operation is problem spe-
cific and needs to be designed with each problem in mind. In some problems, like
the k-VertexCover problem, the repair operation is natural, but in others, like
k-FVST and k-OddCycleTransversal, the repair operation is more involved.
73
The problem-tailored jump-and-repair operation and the fitness function are the only
problem-specific components required by the (1+1) EAj+rk to solve parameterized
problems. Using the general framework presented will make it easier to design repair
operators for other parameterized problems.
Similarly, in Section 3.2 we present results for the (1+1) EA when finding graceful
labelings of certain classes of graphs that have clean structure. We present rigor-
ous runtime bounds for stars, paths, and bicliques. We also demonstrate a way to
overcome synchronization problems that arise from local symmetries by using partial
labelings to force domino convergence to find graceful labelings. The results prove
that evolutionary algorithms using these techniques can label some types of graphs in
expected polynomial time. These results are the first runtime bounds for evolutionary
algorithms on graph labeling problems.
In Section 3.2.4 we present empirical results that demonstrate the (1+1) EA typ-
ically outperforms a complete constraint solver, even without the use of partial la-
belings to break symmetry. This includes results on classes of graphs not covered by
our theoretical results.
This work leaves us with many directions for future work. First the upper bounds
for the (1+1) EA applied to the graceful labeling problem can be tightened. Then
there are missing lower bounds on the FPT evolutionary algorithms for Vertex-
Cover and the (1+1) EA on the graceful labelings. These missing bounds make it
difficult to directly compare algorithms, and without lower bounds it is hard to fully
understand the performance of these algorithms. Also experiments comparing the em-
pirical runtimes for both the traditional EAs and Global SEMO on VertexCover
would be important. It would also be valuable to generalize the performance of the
(1+1) EA on the graceful labeling problem to that of a more sophisticated search
heuristic and larger graph classes. This could be carried out experimentally. It could
74
also prove interesting to investigate the performance of evolutionary algorithms on
other types of graph labelings.
75
Bibliography
[1] M. Adamaszek. “Efficient enumeration of graceful permutations”. In: CoRR
math/0608513 (2006). url: http://arxiv.org/abs/math/0608513.
[2] R. E. L. Aldred and B. D. McKay. “Graceful and harmonious labellings of
trees”. In: Bulletin of the Institute of Combinatorics and its Applications 23
(1998), pp. 69–72.
[3] I. C. Arkut, R. C. Arkut, and N. Ghani. “Graceful label numbering in op-
tical MPLS networks”. In: OptiComm 2000: Optical Networking and Com-
munications. Ed. by I. Chlamtac. Vol. 4233. International Society for Optics
and Photonics. SPIE, 2000, pp. 1–8. doi: 10.1117/12.401809. url: https:
//doi.org/10.1117/12.401809.
[4] J. Ayel and O. Favaron. The helms are graceful. Universite´ Paris-Sud, Centre
d’Orsay, Laboratoire de recherche en Informatique, 1981.
[5] W. Banzhaf. “Genotype-Phenotype-Mapping and Neutral Variation - A Case
Study in Genetic Programming”. In: Parallel Problem Solving from Nature -
PPSN III, International Conference on Evolutionary Computation. The Third
Conference on Parallel Problem Solving from Nature, Jerusalem, Israel, Octo-
ber 9-14, 1994, Proceedings. Ed. by Y. Davidor, H. Schwefel, and R. Ma¨nner.
Vol. 866. Lecture Notes in Computer Science. Springer, 1994, pp. 322–332. doi:
76
10.1007/3-540-58484-6\_276. url: https://doi.org/10.1007/3-540-
58484-6%5C_276.
[6] J.-C. Bermond. “Graceful graphs, radio antennae and French windmills”. In:
Proceedings of the One Day Combinatorics Conference. Vol. 34. Research Notes
in Mathematics. Pitman, 1979, pp. 18–37.
[7] G. S. Bloom and S. W. Golomb. “Applications of Numbered Undirected Graphs”.
In: Proceedings of the IEEE 65.4 (Apr. 1977), pp. 562–570.
[8] L. Brankovic and I. M. Wanless. “Graceful Labelling: State of the Art, Appli-
cations and Future Directions”. In: Math. Comput. Sci. 5.1 (2011), pp. 11–20.
doi: 10.1007/s11786-011-0073-6.
[9] M. Cai, X. Deng, and W. Zang. “An Approximation Algorithm for Feedback
Vertex Sets in Tournaments”. In: SIAM Journal on Computing 30.6 (2001),
pp. 1993–2007. doi: 10.1137/s0097539798338163. url: http://dx.doi.org/
10.1137/S0097539798338163.
[10] C. A. Coello Coello. “Theoretical and numerical constraint-handling techniques
used with evolutionary algorithms: a survey of the state of the art”. In: Com-
puter Methods in Applied Mechanics and Engineering 191.11-12 (Jan. 2002),
pp. 1245–1287. issn: 0045-7825. doi: 10.1016/s0045-7825(01)00323-1. url:
http://dx.doi.org/10.1016/S0045-7825(01)00323-1.
[11] T. H. Cormen et al. Introduction to Algorithms. Third. The MIT Press, 2009.
[12] B. Doerr, Y. Ghannane, and M. I. Brahim. “Towards a Stronger Theory for
Permutation-Based Evolutionary Algorithms”. In: Proceedings of the Genetic
and Evolutionary Computation Conference. GECCO ’22. Boston, Massachusetts:
Association for Computing Machinery, 2022, pp. 1390–1398. isbn: 9781450392372.
77
doi: 10.1145/3512290.3528720. url: https://doi.org/10.1145/3512290.
3528720.
[13] B. Doerr, D. Johannsen, and C. Winzen. “Multiplicative Drift Analysis”. In:
Algorithmica 64 (2012), pp. 673–697.
[14] M. Dom et al. “Fixed-parameter tractability results for feedback set problems
in tournaments”. In: Journal of Discrete Algorithms 8.1 (2010), pp. 76–86. doi:
10.1016/j.jda.2009.08.001. url: http://dx.doi.org/10.1016/j.jda.
2009.08.001.
[15] R. G. Downey and M. R. Fellows. Parameterized Complexiy. Springer, 1999.
[16] A. E. Eiben and J. E. Smith. Introduction to Evolutionary Computing. 2nd.
Springer Publishing Company, Incorporated, 2015. isbn: 3662448734.
[17] K. Eshghi and P. Azimi. “Applications of mathematical programming in grace-
ful labeling of graphs”. In: Journal of Applied Mathematics (2004), pp. 1–8.
doi: 10.1155/S1110757X04310065.
[18] W. Fang. “A Computational Approach to the Graceful Tree Conjecture”. In:
CoRR abs/1003.3045 (2010). arXiv: 1003.3045. url: http://arxiv.org/
abs/1003.3045.
[19] J. Flum and M. Grohe. Parameterized complexity theory. Springer-Verlag, 2006.
[20] T. Friedrich et al. “Approximating covering problems by randomized search
heuristics using multi-objective models”. In: Proceedings of the Conference on
Genetic and Evolutionary Computation (GECCO). 2007, pp. 797–804. doi: 10.
1145/1276958.1277118. url: http://dx.doi.org/10.1145/1276958.
1277118.
78
[21] R. Frucht. “Graceful Numbering of Wheels and Related Graphs”. In: Annals
of the New York Academy of Sciences 319.1 (1979), pp. 219–229. doi: https:
//doi.org/10.1111/j.1749-6632.1979.tb32792.x.
[22] J. A. Gallian. “A dynamic survey of graph labeling”. In: Electronic Journal of
Combinatorics (2021). Dynamic Surveys #DS6.
[23] Gecode Team. Gecode: Generic Constraint Development Environment. Avail-
able from http://www.gecode.org. 2019.
[24] D. E. Goldberg, R. Lingle, et al. “Alleles, loci, and the traveling salesman
problem”. In: Proceedings of the First International Conference on Genetic Al-
gorithms and their Applications (ICGA). Ed. by J. J. Grefenstette. Vol. 154.
Hillsdale, NJ: Lawrence Erlbaum, 1985, pp. 154–159.
[25] S. W. Golomb. “How To Number A Graph”. In: Graph Theory and Com-
puting. Ed. by R. C. Read. Academic Press, 1972, pp. 23–37. isbn: 978-1-
4832-3187-7. doi: https://doi.org/10.1016/B978- 1- 4832- 3187- 7.
50008-8. url: https://www.sciencedirect.com/science/article/pii/
B9781483231877500088.
[26] J. He and X. Yao. “A study of drift analysis for estimating computation time
of evolutionary algorithms”. In: Natural Computing 3 (2004), pp. 21–35.
[27] J. He, X. Yao, and J. Li. “A comparative study of three evolutionary algo-
rithms incorporating different amounts of domain knowledge for node covering
problem”. In: IEEE Transactions on Systems, Man, and Cybernetics, Part C
(Applications and Reviews) 35.2 (2005), pp. 266–271. doi: 10.1109/TSMCC.
2004.841903.
79
[28] M. Horton. “Graceful Trees: Statistics and Algorithms”. Bachelor’s Thesis. Uni-
versity of Tasmania, 2003.
[29] F. Hu¨ffner. “Algorithm Engineering for Optimal Graph Bipartization”. In: J
Graph Algorithms Appl 13.2 (2009), pp. 77–98. doi: 10.7155/jgaa.00177.
[30] S. Khuri and T. Ba¨ck. “An Evolutionary Heuristic for the Minimum Vertex
Cover Problem”. In: Proceedings of the Eighteenth Annual German Conference
on Artificial Intelligence (KI-94). Ed. by J. Kunze and H. Stoyan. 1994, pp. 86–
90.
[31] S. Kratsch and F. Neumann. “Fixed-Parameter Evolutionary Algorithms and
the Vertex Cover Problem”. In: Algorithmica 65.4 (2012), pp. 754–771. doi:
10.1007/s00453-012-9660-4. url: http://dx.doi.org/10.1007/s00453-
012-9660-4.
[32] R. Le Bras, C. P. Gomes, and B. Selman. “Double-wheel graphs are grace-
ful”. In: Twenty-Third International Joint Conference on Artificial Intelligence.
2013.
[33] J. M. Lewis and M. Yannakakis. “The Node-Deletion Problem for Hereditary
Properties is NP-Complete”. In: J. Comput. Syst. Sci. 20.2 (1980), pp. 219–230.
doi: 10.1016/0022-0000(80)90060-4.
[34] M. L. Lidd. Traveling salesman problem domain: Application of a fundamentally
new approach to utilizing genetic algorithms. Tech. rep. Air Force Contract
F4920-90-G-003. MITRE Coroporation, 1991.
[35] D. Lokshtanov, S. Saurabh, and S. Sikdar. “Simpler Parameterized Algorithm
for OCT”. In: Combinatorial Algorithms, 20th International Workshop, IWOCA
2009, Hradec nad Moravicı, Czech Republic, June 28-July 2, 2009, Revised Se-
80
lected Papers. Ed. by J. Fiala, J. Kratochvıl, and M. Miller. Vol. 5874. Lecture
Notes in Computer Science. Springer, 2009, pp. 380–384. doi: 10.1007/978-3-
642-10217-2\_37. url: https://doi.org/10.1007/978-3-642-10217-2_37.
[36] D. Lokshtanov et al. “Faster Parameterized Algorithms Using Linear Program-
ming”. In: ACM Trans. Algorithms 11.2 (2014), 15:1–15:31. doi: 10.1145/
2566616.
[37] H. Mahmoudzadeh and K. Eshghi. “A Metaheuristic Approach to the Graceful
Labeling Problem of Graphs”. In: 2007 IEEE Swarm Intelligence Symposium.
2007, pp. 84–91. doi: 10.1109/SIS.2007.368030.
[38] Minnesota Super COmputing Institute. url: http://www.msi.umn.edu.
[39] G. G. Mitchell et al. “GeneRepair - A Repair Operator for Genetic Algorithms”.
In: Proceedings of the Genetic and Evolutionary Computation (GECCO). 2003.
url: http://mural.maynoothuniversity.ie/10351/.
[40] H. Mu¨hlenbein. “Parallel Genetic Algorithms in Combinatorial Optimization”.
In: Computer Science and Operations Research: New Developments in their
Interfaces. Elsevier, 1992, pp. 441–453. doi: 10.1016/b978-0-08-040806-
4.50034- 4. url: http://dx.doi.org/10.1016/B978- 0- 08- 040806-
4.50034-4.
[41] F. Neumann and A. M. Sutton. “Parameterized Complexity Analysis of Ran-
domized Search Heuristics”. In: Theory of Evolutionary Computation: Recent
Developments in Discrete Optimization. Ed. by B. Doerr and F. Neumann.
Natural Computing Series. Springer International Publishing, 2020, pp. 213–
248. isbn: 978-3-030-29414-4. doi: 10.1007/978-3-030-29414-4_4. url:
https://doi.org/10.1007/978-3-030-29414-4_4.
81
[42] F. Neumann and C. Witt. “Bioinspired Computation in Combinatorial Opti-
mization: Algorithms and Their Computational Complexity”. In: Proceedings
of the 14th Annual Conference Companion on Genetic and Evolutionary Com-
putation. GECCO ’12. Philadelphia, Pennsylvania, USA: Association for Com-
puting Machinery, 2012, pp. 1035–1058. isbn: 9781450311786. doi: 10.1145/
2330784.2330928. url: https://doi.org/10.1145/2330784.2330928.
[43] P. S. Oliveto, J. He, and X. Yao. “Analysis of the (1 + 1)-EA for Finding
Approximate Solutions to Vertex Cover Problems”. In: IEEE Transactions on
Evolutionary Computation 13.5 (2009), pp. 1006–1029. doi: 10.1109/tevc.
2009.2014362. url: http://dx.doi.org/10.1109/TEVC.2009.2014362.
[44] M. Pelikan, R. Kalapala, and A. K. Hartmann. “Hybrid evolutionary algorithms
on minimum vertex cover for random graphs”. In: Proceedings of the Genetic
and Evolutionary Computation Conference (GECCO). ACM, 2007, pp. 547–
554. doi: 10.1145/1276958.1277073. url: https://doi.org/10.1145/
1276958.1277073.
[45] K. E. Petrie and B. M. Smith. “Symmetry Breaking in Graceful Graphs”. In:
Principles and Practice of Constraint Programming - CP 2003, 9th Interna-
tional Conference, CP 2003, Kinsale, Ireland, September 29 - October 3, 2003,
Proceedings. Ed. by F. Rossi. Vol. 2833. Lecture Notes in Computer Science.
Springer, 2003, pp. 930–934. doi: 10.1007/978-3-540-45193-8\_81. url:
https://doi.org/10.1007/978-3-540-45193-8%5C_81.
[46] S. D. Prestwich and A. Roli. “Symmetry Breaking and Local Search Spaces”.
In: Integration of AI and OR Techniques in Constraint Programming for Com-
binatorial Optimization Problems, Second International Conference, CPAIOR
2005, Prague, Czech Republic, May 30 - June 1, 2005, Proceedings. Ed. by R.
82
Barta´k and M. Milano. Vol. 3524. Lecture Notes in Computer Science. Springer,
2005, pp. 273–287. doi: 10.1007/11493853\_21. url: https://doi.org/10.
1007/11493853_21.
[47] T. A. Redl. “Graceful Graphs and Graceful Labelings: Two Mathematical Pro-
gramming Formulations and Some Other New Results”. In: Congressus Numer-
antium 164 (2003), pp. 17–31.
[48] B. Reed, K. Smith, and A. Vetta. “Finding odd cycle transversals”. In: Opera-
tions Research Letters 32.4 (2004), pp. 299–301. issn: 0167-6377. doi: https://
doi.org/10.1016/j.orl.2003.10.009. url: https://www.sciencedirect.
com/science/article/pii/S0167637703001482.
[49] A. Rosa. “On certain valuations of the vertices of a graph”. In: Theory of
Graphs, International Symposium. Gordon and Breach; Dunod, 1967, pp. 349–
355.
[50] S. Salcedo-Sanz. “A survey of repair methods used as constraint handling tech-
niques in evolutionary algorithms”. In: Computer Science Review 3.3 (Aug.
2009), pp. 175–192. issn: 1574-0137. doi: 10.1016/j.cosrev.2009.07.001.
url: http://dx.doi.org/10.1016/j.cosrev.2009.07.001.
[51] J. Scharnow, K. Tinnefeld, and I. Wegener. “The analysis of evolutionary al-
gorithms on sorting and shortest paths problems”. In: J. Math. Model. Algo-
rithms 3.4 (2004), pp. 349–366. doi: 10.1007/s10852- 005- 2584- 0. url:
https://doi.org/10.1007/s10852-005-2584-0.
[52] B. M. Smith and J. Puget. “Constraint models for graceful graphs”. In: Con-
straints 15.1 (2010), pp. 64–92. doi: 10.1007/s10601- 009- 9071- 6. url:
https://doi.org/10.1007/s10601-009-9071-6.
83
[53] E. Speckenmeyer. “On feedback problems in digraphs”. In: Graph-Theoretic
Concepts in Computer Science. Ed. by M. Nagl. Berlin, Heidelberg: Springer
Berlin Heidelberg, 1990, pp. 218–231. isbn: 978-3-540-46950-6.
[54] A. M. Sutton. “Fixed-Parameter Tractability of Crossover: Steady-State GAs on
the Closest String Problem”. In: Algorithmica 83.4 (2021), pp. 1138–1163. doi:
10.1007/s00453-021-00809-8. url: https://doi.org/10.1007/s00453-
021-00809-8.
[55] O. Tange. “GNU Parallel - The Command-Line Power Tool”. In: ;login: The
USENIX Magazine 36.1 (Feb. 2011), pp. 42–47. doi: http://dx.doi.org/10.
5281/zenodo.16303. url: http://www.gnu.org/s/parallel.
[56] O. Tange. GNU Parallel 20210822 (’Kabul’). GNU Parallel is a general paral-
lelizer to run multiple serial command line programs in parallel without chang-
ing them. Aug. 2021. doi: 10.5281/zenodo.5233953. url: https://doi.org/
10.5281/zenodo.5233953.
[57] R. A. Wright et al. “Constant Time Generation of Free Trees”. In: SIAM Journal
on Computing 15.2 (1986), pp. 540–548. doi: 10.1137/0215039.
84