Approximating Optimization Problems using EAs on
Scale-Free Networks
Ankit Chauhan∗

Tobias Friedrich∗

Francesco Quinzan∗

arXiv:1704.03664v2 [cs.DS] 14 Jun 2017

June 15, 2017

Abstract
It has been experimentally observed that real-world networks follow certain topological properties, such as small-world, power-law etc. To study these networks, many
random graph models, such as Preferential Attachment, have been proposed.
In this paper, we consider the deterministic properties which capture power-law
degree distribution and degeneracy. Networks with these properties are known as
scale-free networks in the literature. Many interesting problems remain NP-hard on
scale-free networks. We study the relationship between scale-free properties and the
approximation-ratio of some commonly used evolutionary algorithms.
For the Vertex Cover, we observe experimentally that the (1+1) EA always gives the
better result than a greedy local search, even when it runs for only O(n log(n)) steps.
We give the construction of a scale-free network in which the (1+1) EA takes Ω(n2 )
steps to obtain a solution as good as the greedy algorithm with constant probability.
We prove that for the Dominating Set, Vertex Cover, Connected Dominating Set
and Independent Set, the (1+1) EA obtains constant-factor approximation in expected
run time O(n log(n)) and O(n4 ) respectively. Whereas, GSEMO gives even better
approximation than (1+1) EA in expected run time O(n3 ) for Dominating Set, Vertex
Cover and Connected Dominating Set on such networks.

1

Introduction

Evolutionary Algorithms (EAs) are bio-inspired randomized optimization techniques and
have been shown to be very successful when applied to combinatorial optimization problems.
The success of EAs to solve such problems have attracted lots of attention and there has
been extensive research in recent years to understand the behavior of these algorithms. In
early research, the main concern was to analyze the run time of EAs like the (1+1) EA for
artificial pseudo-boolean functions [6, 12] as well as for some combinatorial optimization
problems [10, 18, 19]. Most of the results considered the exact optimization of the function,
however many combinatorial optimization problems are NP-hard. This means one cannot
hope for an exact solution in polynomial time unless P=NP. Thus, the goal of EAs are
to obtain a good approximation of an optimal solution within a certain amount of time
instead of finding a exact optimal solution. In previous years, some progress has been
made for worst-case approximation analysis of the EAs for the combinatorial problems
that can be achieved in a polynomial number of steps in expectation [9, 29, 15, 28].
However, for real-world instances, the solution quality heavily depends on the underlying
∗

Algorithm
Engineering
firstname.lastname@hpi.de

Group,

Hasso

1

Plattner

Institute

Potsdam,

Germany,

structural properties. Consider the example of the traveling salesman problem. If the
graph instance follows the triangle inequality than the TSP has 32 -approximate. On the
other hand, TSP for the general graphs cannot be approximate within constant factor
unless P=NP [27]. This means that on considering the topological properties of the
instances in the algorithms can obtain a good quality solution for those problems which
are even NP-hard to approximate. In practice, interesting optimization problems deal with
real-world network instances. Therefore, much effort has been made to identify properties
of real-world networks to bridge the gap between theory and practice. A wide range
of real-world networks, like Internet topologies, the web, power grids, protein-protein
interaction graphs, social networks and many other networks high clustering coefficient,
small diameter, almost power-law degree distribution and so on [7, 14, 16, 1, 24, 20, 26].
Thus, considering these properties in the analysis of algorithms gives a better understanding
about the behavior of the algorithm on real-world networks.
Recently, Cohen et al.[5] consider stability properties of real-world instances and show
that simple local search works well for clustering problems on such instances. In this
work, we follow the same line of research. Instead of considering stability properties, we
consider networks with power-law degree distribution - that is, scale-free networks. A
power-law degree distribution means that the number of vertices of degree k in the network
is proportional to k −β , where β > 1 is the power-law exponent, a constant inherent to
the network. Real-world networks, however, usually exhibit slight deviation from the
power-laws. To allow this deviation Brach et al.[3] identify the deterministic properties
for real-world networks that capture the degree distribution
of many real-world networks.


They define buckets containing vertices of degrees 2i , 2i+1 .If the number of vertices in
each bucket is at most as high as for a power-law degree sequence, a network is said to
be power-law bounded. We denote this property by PLB-U. Brach et al. also define PLB
neighborhoods. A network has PLB neighborhoods if the degree distribution of degrees of
neighbor of each vertices in the network also obey the power-law. In other words, for every
vertex of the degree k this property gives an upper-bound on the number of neighbors
of the degree atleast k. We denote this property by PLB-N. The PLB-N property is
closely related to the degeneracy of the graphs. We say a graph is d-degenerate if every
subgraph has vertex of degree at most d. Degeneracy of the network is d upper-bounded
by the maximum value of PLB-N among all buckets. Brach et al. exploit these properties
and prove that algorithms for page rank, maximum clique counting triangle etc. run
faster on power-law bounded networks than the known worst case lower bound for the
graph. Furthermore, Chauhan et al.[4] show that a simple greedy algorithm obtain a Θ(1)approximation for Minimum Dominating Set (MDS), Minimum Connected Dominating
Set (CDS), Minimum Vertex Cover (MVC), and Maximum independent Set (MIS). On
the contrary, a simple greedy algorithm achieves Ω(ln(∆))-approximation for the MDS,
CDS and ∆-approximation for MIS on general graphs where ∆ is the maximum degree
of the graph[27, 25]. The PLB-U property alone captures a much broader class of graph
hence Chauhan et al. define PLB-L, which gives lower-bound for the number of vertices in
each bucket to restrict networks to real-world networks. Chauhan et al. show that even if
the network have all three properties, PLB-(U,L,N) computing MDS, MVC and MIS is
APX-Hard. A formal definition of all three properties can be found in section 2.
We look at different instances of networks with PLB-(U,L,N) properties with power-law
exponent β > 2, and experimentally observed that the (1+1) EA always finds a better
solution for MVC than the degree-based greedy algorithm on the different instances with
these properties. This observation raises a serious question: does the (1+1) EA always give
2

problems

MVC
MDS
CDS
MIS

PLB-graphs

General graphs

run time

ratio

run time

ratio

O(n log n)
O(n log n)
O(n log n)
O(n4 )

Θ(1)
Θ(1)
Θ(1)
Θ(1)

O(n log n)
O(n log n)
O(n log n)
O(n4 )

O(n)
O(n)
O(n)
∆+1
2

Table 1: Comparison of the approximation ratios achieved by (1+1) EA on networks withPLB
properties and power-law exponent β > 2 and on general graphs. While on general graphs, (1+1) EA
takes polynomial many steps in expectation to achieve polynomial-approximation, (1+1) EA achieve
constant-approximation on networks with PLB properties and power-law exponent β > 2 within
expected polynomial many steps.

problems

MVC
MDS
CDS

PLB-graphs

General graphs

run time

ratio

run time

O(n3 )
O(n3 )
O(n3 )

Θ(1)
Θ(1)
Θ(1)

O(n3 )
O(n3 )
O(n3 )

ratio
O(log n)
O(log n)
O(log n)

Table 2: Comparison of the approximation ratios achieved by GSEMO on networks withPLB
properties and power-law exponent β > 2 and on general graphs. While on general graphs, GSEMO
takes polynomial many fitness evaluation in expectation to achieves logarithmic-approximation,
GSEMO achieve constant-approximation on networks with PLB properties and power-law exponent
β > 2 within polynomial many fitness evaluation in expectation.

a better solution than the greedy on the networks with PLB-(U,L,N) in asymptotically
lesser time?
We theoretically analyze EAs for well-known NP-hard problems: MDS, MVC, MIS
and CDS. The MVC has been studied extensively [22, 21], Friedrich et al. [9] presented a
instance of bipartite graph in which (1+1) EA can obtain arbitrary bad approximation in
expected polynomial time. To overcome this, Friedrich et al. provide a multi-objective
approach for MVC and prove that the GSEMO can obtain an optimal solution in the
expected polynomial time for that instance. Also, by using GSEMO they prove the
approximation of O(log n) for a more general problem, minimum set cover. Back et
al. in [2] give a single objective EA for MIS and claim its superiority by experimental
observations. Peng [23] analyzes the (1+1) EA for the maximum independent set, and
4
proves that the (1+1) EA obtains a ∆+1
2 -approximation within expected runtime of O(n ).
We analyze the (1+1) EA for all four above-mentioned problems. We prove that for MDS,
MVC and CDS the (1+1) EA gives O(1)-approximation within the expected runtime
O(n log n). Contrary to the experiments results, we give a worst case example of network
with PLB-(U,L,N) properties where (1+1) EA can obtain the worst possible solution
with O(1)-probability and the greedy algorithm obtains the optimal solution. Since the
(1+1) EA can obtain such a bad solution, we analyze the multi-objective EAs on networks
with PLB-(U,L,N). We study the GSEMO for the MDS, MVC and CDS on the networks
with PLB-(U,L,N). We prove that the GSEMO gives a better approximation than the
(1+1) EA in expected runtime of O(n3 ). Also, as a byproduct of the analysis of GSEMO,
we present an improvement over the result of Chauhan et al. [4] for the approximation on
3

Algorithm 1 (µ + 1) EA

5:

choose population Pµ ⊆ {0, 1} u.a.r. of size µ
while convergence criterion not met do
choose parent x ⊆ Pµ u.a.r.
create offspring y by flipping bits of x w.p.
discard weakest element in Pµ ∪ {y}

6:

return fittest element in Pµ

1:
2:
3:
4:

1
n

Algorithm 2 GSEMO
1:
2:
3:
4:
5:
6:
7:
8:
9:

choose x ∈ {0, 1}n uniformly at random
add x to Pareto front P
while convergence criterion not met do
Choose x ∈ P uniformly at random
create y by flipping bits of x with probability n1
if y is not dominated by any point in P then
add y to P
delete all solutions in P dominated by y.
return P

MDS and CDS. A summary of these results is given in Table 1 and Table 2.

2

Preliminaries

In this section, we introduce the algorithms considered in this paper, and define the basic
definitions that are used later in the proofs. We consider undirected graphs G = (V, E)
without loops, where V is the set of vertices and E is the set of edges in the graph with
n := |V |. Throughout the paper we use deg(v) to denote the degree of the vertex v ∈ V ,
∆ for maximum degree of the graph and OPT for the optimal solution set. For a S ⊆ V
P
we then define vol(S) = i∈S deg(i).

2.1

Algorithms

The (µ + 1) EA is a randomized algorithm inspired by the process of natural selection (cf.
Algorithm 1). After an initial population of size µ is chosen uniformly at random (u.a.r),
the (µ + 1) EA chooses a parent x from Pµ u.a.r. An offspring y is then generated, by
flipping all bits of x independently with probability 1/n. The fitness is then computed
for all elements of Pµ ∪ {x}, and the weakest one is discarded. The (1+1) EA is an
instance of the (µ + 1) EA, with µ = 1. The (1+1) EA is one of the simplest instances of
a single-objective evolutionary algorithm.
The GSEMO algorithm is a multi-objective evolutionary strategy (cf. Algorithm 2). As
in the case of the (1+1) EA, this heuristic chooses an initial solution u.a.r. from the
objective space, and stores it in the Pareto front. An element x is then chosen u.a.r. from
the Pareto front P , and a new solution y is then computed from x by flipping each bit
independently with probability (w.p.) 1/n. If y is not strongly dominated by any other
solution in the Pareto front, the y is saved as a new solution, and all elements which are
strongly dominated by y are discarded.
4

Algorithm 3 Local Search Algorithm
1:
2:
3:
4:
5:
6:

choose x ∈ {0, 1}n u.a.r.
while (termination condition not satisfied) do
choose y in a neighborhood of x u.a.r.
if f (y) > f (x) then
x←y
return x

Algorithm 4 Greedy Algorithm for vertex cover on G = (V, E)
S←∅
while not all edges are covered do
3:
add vertex s ∈ V \ S with highest degree to S
4: return S
1:
2:

Local search algorithms are iterative improvement algorithms (cf. Algorithm 3). Again,
the first step is to choose a solution u.a.r. Then, a second solution is chosen u.a.r. in a
neighborhood of x. Again, the two solutions are compared and the best one is stored in
memory. The last algorithm we take into account for the analysis is a deterministic one
(cf. Algorithm 4). This algorithm is specifically designed to find a minimum vertex cover
of an input graph. It iteratively adds nodes, which have highest degree to the cover, until
all edges are covered. For the randomized algorithms the run time is always counted in
terms of the number of fitness evaluations, and for the deterministic processes the run
time is given in the number of steps.

2.2

Technical definitions

Particularly important for the analysis is the power-law distribution hypothesis. We
formally frame this concept, by giving some related definitions (cf. Brach et. al. [3]
and Chauhan et. al. [4]). Many of these concepts have been informally introduced in the
introduction.
Definition 1. A graph G is power law upper-bounded (PLB-U) for some parameters
1 < β = O(1) and t ≥ 0, and universal hconstantc1 > 0 if for every integer d ≥ 0, the
number of vertices v, such that deg(v) ∈ 2d , 2d+1 is at most

c1 n(t + 1)

β−1

2d+1
X−1

(i + t)−β .

i=2d

Definition 2. A graph G is power law lower-bounded (PLB-L) for some parameters
1 < β = O(1) , t ≥ 0 and universal constant c2 > 0 ifh for every
 integer blog dmin c ≤ d ≤
d
d+1
blog ∆c, the number of vertices v, such that deg(v) ∈ 2 , 2
is at least

c2 n(t + 1)

β−1

2d+1
X−1

(i + t)−β .

i=2d

We also consider the definition of PLB neighbourhood, given below. Again, we follow
the work of Brach et. al. [3].
5

Definition 3. A graph G has PLB neighborhoods (PLB-N) if for every vertex
v of degree
k, the number of neighbors
of v of degree at least k is at most


Pn−1
β−2
−β
c3 max log n, (t + 1)
k i=k i(i + t)
where c3 > 0 is constant and 1 < β = O(1) ,
t ≥ 0 are parameters.
We conclude with a definition that describes how the solution of an optimization
problem is approximated.
Definition 4. An algorithm is an α-approximation for problem P if it produces a solution
|
set S with α ≥ |S| if P is a minimization problem and with α ≥ |OPT
if P is a
|S|
|OPT|
maximization problem.
Useful for the analysis is the following lemma. The lemma gives the upper-bound on
P
the i∈S h(deg(S))|S| by using the highest possible volume in the PLB-U graph. The
reader may find a proof in Chauhan et. al. [4].
Lemma 1 (Potential Volume Lemma). Let G be a graph without loops and with the
PLB-U property for some β > 2, some constant c1 > 0 and some constant t ≥ 0. Let S be
a solution set for which we can define a function g: R+ → R as continuously differentiable
and h(x) := g(x) + C for some constant C such that
1. g non-decreasing,
2. g(2x) ≤ c · g(x) for all x ≥ 2 and some constant c > 0,
3. g 0 (x) ≤

g(x)
x ,

P

then it holds that

x∈S

h(deg(x))
|S|



is at most


β−1

c 1 +

β−21−

1


t+2
t+1


1−β  g

where M (n) ≥ 1 is chosen such that

3



P

β−1 n
c1 β−2
M

x∈S

β−1

·2

β−1

· (t + 1)



1
β−2



+ C,

deg(x) ≥ M .

The Minimum Dominating Set

In this section we consider two problems commonly found in combinatorial optimization.
Given a graph G = (V, E), we consider a minimum dominating set (MDS) problem, this
consists of finding a subset S ⊆ V of minimum size such that for each v ∈ V either v or a
node adjacent to v is in S. Similarly, the minimum vertex cover (MVC) problem consists
of finding a subset S ⊆ V of minimum size such that each edge e ∈ E is incident to at
least one node from S.

3.1

Single-objective optimization

In order to implement the (1+1) EA to obtain a solution for the MDS and MVC, we first
need to give the encoding of the solution and the definition of fitness functions. For each
S ⊆ V , we can use (x1 , x2 , · · · , xn ) ∈ {0, 1}n to represent it, where n is the number of
6

vertices in the graph G(V, E). We set bit xi = 1 iff. the vertex vi is in S, otherwise xi = 0.
The fitness function is defined as
F (x) = n2 u(x) + |x|1
where u(x) is the number of uncovered nodes, and |x|1 gives the number of 1s in the
current solution. The solution space can be partitioned into two sets according to the
value of fitness function, as shown below.
S1 = {x ∈ {0, 1}n : x is infeasible and F (x) ≥ n}
S2 = {x ∈ {0, 1}n : x is feasible and F (x) < n}
Because of the weight on u(x), the (1+1) EA first tries to find a feasible solution than
it will minimize accordingly. We can use the same fitness function for the vertex cover,
with the difference that u(x) returns the number of uncovered edges, instead of uncovered
vertices. The following theorem holds.
Theorem 1. For the PLB graphs with parameters β > 2, t ≥ 0 consider the quantities
aβ,t := 1 +

β−1
1


β − 2 1 − t+2 1−β
t+1



β
β−1
bc1 ,β,t := c1 β−1
β−2 · 2 · (t + 1)



1
β−2

+1

Then the (1+1) EA find a (2 · aβ,t · bc1 ,β,t )-approx dominating set in expected O(n log n).
Proof. The run-time of O(n log n) follows from the Theorem 1 of [8] and from the fact that
a vertex cover is also a dominating set. Let A be the solution produced by the (1+1) EA.
This solution is an α−approximation of OPT. To give the bound on the approximation
ratio α we use Lemma 1. Consider a worst case instance where (1+1) EA obtains exactly
α-approximation solution. This means,
|A|
=α
|OPT|
Since the solutions produced after (Phase 2) of the (1+1) EA have no redundant nodes,
this means that |A| ≤ n − |OPT|.
n − |OPT|
≥α
|OPT|
This is the case when every neighbor of the node in the optimal solution is taken as the
solution by the (1+1) EA
n − |OPT|
α≤
≤
|OPT|

P

i∈OPT deg(i)

|OPT|

(1)

As x∈OPT deg(x) ≥ n2 than by taking S = OPT we have that h(deg(x)) = deg(x),
g(x) = h(x), and that M = n2 . Since g(x) follows the all three properties of Lemma 1 we
get, α ≤ 2 · aβ,t · bc1 ,β,t
P

7

|V1 | = constant
1

|V2 | = O(n c )

···
···

···

···

···

|V3 | = O(n)

|V4 | = O(n)

1

Figure 1: Worst Case graph Gvc for the (1+1) EA with ∆ = dn β−1 e, δ = 22 and |V | = N = Θ(n).
|A1 | is the set of red vertices and A2 is the set of blue vertices. On this graph a greedy search
beats the (1+1) EA.

We now discuss two worst-case graphs with PLB-(U,L,N) properties. The first example
relates to the MVC problem, and it shows that on an instance with PLB-(U,L,N) properties
the (1+1) EA outputs the worst possible solution in Θ(n log n) many fitness evaluations.
In the second example, we show that on a PLB-(U,L,N), graph greedy outperforms the
(1+1) EA.
Example 1: We give a construction of the graph Gvc = (V, E)(cf. Figure 1), and
show that it has PLB-(U,L,N) properties. Consider δ = 2p , where δ is the smallest degree
1
and is a constant. Also, ∆ = dn β−1 e is a maximum degree of the graph Gvc . Let bi be the
PLB buckets where blog ∆ is the bucket which contains the vertices with degree ∆. The
procedure of constructing the Gvc is given as follows:
1. This steps consists of filling constant
l P j+1many high
m degree vertices. For all j ∈ {log2 (∆)−
2
−1 −β
p, · · · , log2 (∆)} fill bj with n i=2j i
many vertices, with p a constant such
that the number of vertices in these buckets is at least δ − 1. This gives the first
layer V1 of the vertices. Let {v1 , · · · , vk } be the vertices created during this step, and
degc (v) the current degree of the vertex v. Also, let deg(v) be the resultant degree
needed for the vertex v.
2. Arrange the vertices according to their resultant degree in decreasing order. Add
new vertices {u1 , · · · udeg(v1 ) } say second layer of vertices V2 and then add an edge
between each ui and v1 . Now for each ui add an edge to the next vj such that
degree of each ui is exactly δ − 1. If there is an vertex vi whose degree does not
satisfy the degree to be in bucket for which it was created then create another
{udeg(v1 )+1 · · · udeg(vi )−degc (vi ) }. For each iteration j repeat the above step for each
vi until all vertices v1 , · · · vk have there resultant degree needed. If there is some
vertex ub whose degree is not δ − 1 and adding an edge to some vj is not possible
ub
than create δ − degc (ub ) many new vertices v ub = {v1ub , · · · , vδ−deg
} and add an
c (ub )
edge to ub .
3. Now for each vertex ui of degree δ − 1, add a vertex vk+i and add an edge (ui , vk+i ).
Let this is the third vertex layer V3 which currently contain the vertices vk+i for
each ui and the set v ub for each ub in the second layer.
Now for meach bucket bj
l P j+1
2
where j ∈ {2, · · · , log2 (∆) − p}. Fill the buckets with n i=2j −1 i−β many vertices
by using currently present vertices and by adding more vertices. Add the edge as
described in the first step creating fourth layer of vertices V4 . Now for each vi4 in
V4 add an edge to the next vj such that degree of each vi4 is exactly δ. If there is
a some vertex with degree less than δ in V4 than choose an vertex vi in bucket j
8

such that j ∈ {4, · · · , log2 (∆) − p} and add an edge to v. It is to be noted that there
can be at most constant many vertices in V4 whose degree is not δ after sequential
addition. Thus addition some more edges to the vertices in above bucket will not
change the number of vertices in each bucket as the degree blow up is less than half
for any of the above vertices.
We use the lemma below to prove that the graph G has PLB-(U,L,N) properties (cf.
Chauhan et. al. [4]). This lemma helps us to give the bound for the number of vertices in
each bucket of PLB graph G.
Lemma 2. Let 1 ≤ a ≤ b/2, for a, b natural numbers, and let c > 0 be a constant. Then
−c

a

≤

c
1−2−c

b−1
X

i−c−1 .

i=a

Theorem 2. Gvc is a N vertices graph have PLB-(U,L,N) properties with parameter β,
t = 0, c1 = (2δ)3β−1 , c2 = pδ and c3 = 1 where N = Θ(n) and 0 < p < 1.
Proof. First we give the bound in the number of vertices N in graph G. From the graph
construction algorithm we know that
N = |V1 |+|V2 |+|V3 |+|V4 |
We give the upper bound on the number of vertices in each set by using the simple
integration method,
|V1 | =



log
X∆



2j+1
X−1

n
i−β 




j=log(∆)−p
i=2j
log
X∆

≤

(n

2j+1
X−1

i−β + 1)

i=2j

j=log(∆)−p

∈ O(1)

|V2 | ≤



log
X∆



2j+1
X−1

n
i ∗ i−β 




j=log(∆)−p
i=2j
log
X∆

≤

(n

i1−β + 1)

i=2j

j=log(∆)−p

2j+1 −1

log
X∆

≤n

2j+1
X−1

X

2

i1−β + n β−1

j=log(∆)−p i=2j

≤n

Z ∆

1

1
n p(β−1)

x1−β dx + n β−1

1

∈ Θ(n β−1 )
log(∆)−p

|V3 | ≤

X
j=2



2j+1
X−1


1

n
β−1 )
i−β 

 + Θ(n
 i=2j

1

∈ O(n + n β−1 )
∈ Θ(n)
9

log(∆)−p

|V4 | ≤





2j+1
X−1

1

n
β−1 )
i ∗ i−β 
 + δ ∗ O(n


 i=2j

X
j=2

∈ Θ(n)
Thus, N ∈ Θ(n). Now we prove that the graph Gvc have PLB-(U,L,N) properties.
PLB-(U,L): From the step 1,2 and 3 it can be observed that the number of vertices bj
with degree in [2j , 2j+1 ) where j ∈ {2, · · · , log2 (∆ − 1)} is
n

2j+1
X−1

−β

i

≤ bj ≤ n

2j+1
X−1

i=2j

i=2j

2j+1 −1

X

n

i−β + 1

−β

i

≤ bj ≤ 2n

i=2j

2j+1
X−1

i−β

i=2j

(2)
Since |V3 |= C ∗ n, where C is some constant hence n ≥ pN where p ≤ 1
pN

2j+1
X−1

i

−β

≤ bj ≤ 2N

2j+1
X−1

i=2j

i−β

i=2j

Now for j=1
log2 (∆)

|V4 |< b1 ≤



2j+1
X−1


1

n
β−1 )
i−β 

 + O(n


j
j=2
i=2
X

|V3 |
< b1 ≤ 3N
δ

∆
X

i−β

i=2log(δ)+1

X
pN 2δ−1
3N
i−β ≤ b1 ≤
·
(2δ)1−β
δ
β
−
1
i=δ
2δ−1
X
X
pN 2δ−1
1
i−β ≤ b1 ≤ 3N ·
i−β
β−1
δ i=δ
(2δ)
i=δ

(3)

Inequality 3 follows from lemma 2 G also have PLB-N property as the vertices of degree
more than δ are adjacent to the degree δ vertices. Thus graph is a PLB-(U,L,N) with
c1 = (2δ)3β−1 , c2 = pδ and c3 = 1.
Theorem 3. For the PLB-(U,L,N) graph Gvc , the (1+1) EA with probability O(1) output
worst possible vertex cover in expected Θ(N log N ) time whereas takes Ω(N δ ) to converge.
Proof. We can divide the vertices of Gvc in two sets, A1 = {V1 ∪V3 }, A2 = {V2 ∪V4 }. It can
be easily observable that the OPT = A1 as |A1 |< |A2 |. Let |A1 |= N and |A2 |= (1 − )N
In the first phase we investigate the probability that the (1+1) EA takes A2 as vertex
cover with at least one vertex of |A1 | missing in the solution. In the second phase we give
the lower bound on the probability that all the vertices of the |A1 | will be removed to
obtain a local optimum. We conclude that the (1+1) EA reaches a configuration with
constant probability, from which it escapes in expected Ω(nδ ) many steps.
10

4e
First phase: This phase runs for (1−)
N ln N steps. We prove that the (1+1) EA
outputs a vertex cover within this phase which contains A2 with constant probability. We
consider a simple event, by which only single bit flips of A2 occur. The probability of the
e
simple event is at least 1−
e , meaning that its expected waiting time is 1− . Now if the
(1+1) EA runs for k steps, than by the Chernoff bound the probability that there are

at least

k(1−)
2e

A2 bit flips is greater than 1 − e−

k(1−)
8e

. Since k =

4e
(1−) N

ln N , then the




probability that in this phase 2N ln N many simple A2 events occur is at least 1 − N1 .
Let N 0 be the current number of uncovered edges in the graph. All simple A2 -steps that add
a vertex of A2 are accepted and the total distance decrease of these step is N 0 , since choosing
all vertices from A2 is clearly a valid vertex cover. Thus the number of uncovered edges
1
after a simple event adds the vertex to the solution is at most N 0 (1− (1−)N
). Since N 0 ≤ N ,
1
then the number of uncovered edges after 2N ln N steps is N (1 − (1−)N
)2N ln N ≤ N1 ,
which is strictly less than 12 . Combining this observation
with Markov’s
inequality, a vertex



cover with A2 is produced with probability at least 21 1 − N1 .
We now analyze the probability that the (1+1) EA does not include at least one vertex of
4e
A1 with constant degree in the solution, after (1−)
N ln N steps. Consider the case when

A2 is in the solution before A1 . By Chernoff bound at least |A31 | = N
3 many vertices of
A1 are not in the initial solution with probability 1 − eΩ(N ) . Thus the probability that
4e
the vertices from |A1 | which are not in the initial solution is not chosen after (1−)
N ln N
steps is at least
4e


(1−)
N ln N  N
1  (1−)
3
1− 1− 1−
> 1 − e− 12e
N
Combining this inequality with the probability that the (1+1) EA choose A2 in the solution
we get the total probability that the (1+1) EA chooses A2 without at least one node from
A1 is lower bounded by

(1−)
12e

1−e−
2



1−

1
N



.

Second phase: We give that with constant probability all the accepted vertices of A1 will
be removed in expected O(N log N ) steps. We consider the case when all nodes of A2 and
all nodes of A1 but one is in the solution. We consider two possibilities. Either the number
of vertices of A1 in solution increases and as many vertices of A2 decreases we call bad
event. This is the case when all the missing node in the neighbor of v ∈ A2 are included
in the solution and at least as many vertices of A2 are removed from the solutionj. The
other possibility we consider is when the number of vertices of A1 decrease or stay same
after an mutation step, which we call good event. Following our terminology, if a bad event
occurs, then the solution drifts away from the local optimum. On the other side, as more
and more good events occur the covering approaches the solution A2 . The probability of a
1
1 |−k
good event is at least |Aen
≥ eN
where k is the missing vertices of A1 from the current
−2+

1

β−1 + N −1 . We
solution. The probability of the bad event is upper bounded from N
calculate the probability of a good event before a bad event, which is lower bounded by

1/eN
−2+ 1
β−1
2/eN +N

=

1
β−1
1
−2+
β−1 +2e
N

N

−2+

. Thus the probability that all the nodes of V1 is remove

from the solution is,
n 
Y
k=1

N
N

1
−2+ β−1

1
−2+ β−1

11

+e



∈ Ω(1)

···
S1

···

···

S2

S3

···

S`

1

Figure 2: Worst Case graph GW for the (1+1) EA with ∆ = dn β−1 e + 1 and |V | = N = Θ(n).
V1 is the set of red vertices and V2 is the set of blue vertices. On this graph a greedy search beats
the (1+1) EA.

Now to converge the solution towards global optima, at least δ many vertices of A1 are
needed to be added to remove at least one more than that many vertices of A2 from the
1
−δ−1+ β−1
common neighborhood of added vertices, the probability of this event is at most n
.
1
−δ−1+ β−1
δ
Thus the expected waiting time to converge the solution is Ω(n
) ∈ Ω(n ), from
which the thesis follows.
Example 2 We give a graph GW as described below (cf. Figure 2).
l P j+1
m
2
−1 −β
i
many star graphs where
j
i=2

1. for all j ∈ {2, · · · , log2 (∆ − 1)} construct n
degree of the center vertex is 2j .

2. Let ` be the total no. of star graphs, then pick an arbitrary vertex vi from the star
i and add an edge between vi and center vertex of star (i + 1) (mod `). This step
ensures that the graph is connected.
Theorem 4. GW is a N vertices graph have PLB-(U,L,N) properties with parameter
2
β, t = 0, c1 = 1−2−β+1
, c2 = (41−β − 51−β )p and c3 = 1 where N = Θ(n) and p =


2 · 41−β



4
β−2

+

1
β−1

−1

.

Proof. First we give the bound in the number of vertices N in graph G, From the step 1
of graph construction algorithm,


log2 (∆−1)

X

N=

(2j + 1) 
n

j=2



log2 (∆−1)

2j+1 −1

X

X

j=2

i=2j

≤n
≤ 2n

Z ∆

2j+1
X−1
i=2j



i−β 


log2 (∆−1)

i−β (i + 1) +

X

(2j + 1)

j=2

x−β (x + 1)dx

4

≤2·4

1−β



1
4
+
n
β−2 β−1


(4)

From inequality 4, N = Θ(n)
Now we prove that the graph GW have PLB-(U,L,N) properties.
PLB-(U,L): From the step 1 and 2, it can be observed that the number of vertices bj

12

with degree in [2j , 2j+1 ) where j ∈ {2, · · · , log2 (∆ − 1)} is
n

2j+1
X−1

−β

≤ bj ≤ n

i

2j+1
X−1

i=2j

i=2j

2j+1 −1

X

n

i−β + 1

−β

≤ bj ≤ 2n

i

2j+1
X−1

i=2j

i−β

i=2j

(5)
From inequality 4, n ≥ pN
pN

2j+1
X−1

i

−β

≤ bj ≤ 2N

2j+1
X−1

i=2j

i−β

i=2j

Now for j=1
log2 (∆−1)

X

n

2j+1
X−1

j=2

log2 (∆−1)

i−β ≤ b1 =

j=2

i=2j

pN

∆
X

−β

≤ b1 ≤ 2N

i

pN

j −β ·

j=4

(41−β

51−β )

−
β−1

3
X

i−β ≤ b1 ≤

i=2

pN

3
X

2j+1
X−1



i−β

i=4

i=4
∆
X

∆
X



n
i−β 


 i=2j


X

2N 1−β
2
β−1

i−β ≤ b1 ≤ 2N ·

i=2

3
X
1
i−β
1 − 2−β+1 i=2

(6)

Inequality 6 follows from lemma 2 and since 3i=2 i−β < 1. Now it remain to prove for
the number of vertices of degree 1 for vertices of degree 1 we just need to prove PLB-L as
N = Θ(n) hence they already follow P LB − U .
P

log2 (∆−1)

b0 ≥

X

(2j − 1)n

j=2

≥ 3n

2j+1
X−1

i−β

i=2j

(41−β

51−β )

−
β−1

G also have PLB-N property as the vertices of degree more than 2 are adjacent to the
2
, c2 =
degree 1 and degree 2 vertices. Thus graph is a PLB-(U,L,N) with c1 = 1−2−β+1
(41−β −51−β )
p
β−1

and c3 = 1.

Theorem 5. 1 For the PLB-(U,L,N) graph GW with β > 2.5, the (1+1) EA with probability
O(1) produces worst possible dominating set in Θ(N log N ) time whereas takes Ω(N 2 ) time
to produce a dominating set better than that.
1

Corrected version the theorem 3.4 from paper appeared in GECCO’17

13

Proof. We can divide the vertices of GW in two sets, V1 = {v ∈ V |deg(v) > 3}, V2 = {v ∈
V | deg(v) ≤ 2}. It can be easily observable that the OPT = V1 . In the first phase we
investigate the probability that (1+1) EA takes V2 as dominating set with at least one
vertex of |V1 | missing in the solution. In the second phase we give the lower bound on the
probability that all the vertices of the |V1 | will be removed to obtain a local optimum. We
conclude that the (1+1) EA reaches a configuration with constant probability, from which
it escapes in expected Ω(n2 ) many steps.
4e
First phase: This phase runs for (1−)
N ln N steps. We prove that the (1+1) EA outputs
a dominating set with in this phase which contains V2 with constant probability. We
consider a simple event, by which only single bit flips of V2 occur. Probability of the simple
e
event is at least 1−
e , meaning that its expected waiting time is 1− . Now if the (1+1) EA

runs for k steps, than by the Chernoff bound the probability that there are at least
V2 bit flips is greater than 1 − e

k(1−)
− 8e

. Since k =

4e
(1−) N

k(1−)
2e

ln N , then the probability that




in this phase 2N ln N many simple events occur is at least 1 − N1 .
Let N 0 be the current number of non-dominated vertices in the graph. All simple V2 -steps
that add a vertex of V2 are accepted and the total distance decrease of these step is N 0 ,
since choosing all vertices from V2 is clearly a valid dominating set. Thus the number of
non dominated vertices after a simple event adds the vertex to the solution is at most
1
N 0 (1 − (1−)N
). Since N 0 ≤ N , then the number of non dominated vertices after 2N ln N
1
)2N ln N ≤ N1 , which is strictly less than 12 . Combining this observation
steps is N (1 − (1−)N
with
inequality, a dominating set with V2 is produced with probability at least
 Markov’s

1
1
2 1− N .
We now analyze the probability that the (1+1) EA does not include constant many nodes
4e
of V1 with constant degree in the solution, after (1−)
N ln N steps. Consider the case when

V2 is in the solution before V1 . By Chernoff bound at least |V31 | = N
3 many vertices of V1
are not in the initial solution with probability 1 − eΩ(N ) . Thus the probability that the
4e
vertices from |V1 | which are not in the initial solution is not chosen after (1−)
N ln N steps
is at least
4e


(1−)
N ln N  N
1  (1−)
3
> 1 − e− 12e
1− 1− 1−
N
Combining this inequality with the probability that (1+1) EA choose V2 in the solution
we get the total probability that the (1+1) EA chooses V2 without at least one node from
V1 is lower bounded by

(1−)
12e

1−e−
2



1−

1
N



· Θ(1).

Second phase: We give that with constant probability all the accepted vertices of V1 will
be removed in expected O(N log N ) steps. We consider the case when all nodes of V2 and
all nodes of V1 but one is in the solution. We consider two possibilities. A missing nodes
of V1 is chosen and added to the solution removing at least one more V2 vertices, which
we call bad event. The other possibility we consider is when the number of vertices of V1
decrease or stay same after an mutation step, which we call good event. Following our
terminology, if a bad event occurs, then the solution drifts away from the local optimum.
On the other side, as more and more good events occur the covering approaches the
|−k
1
solution V2 . The probability of a good event is at least |V1en
≥ eN
where k is the missing
vertices of V1 from the current solution. We claim that probability of the bad event is
upper bounded from N −2 + N −1 . We calculate the probability of a good event before a
14

1/eN
bad event, which is lower bounded by 2/eN
=
+N −2
the nodes of V1 is remove from the solution is,
N 
Y
k=1

N
2N +e .

Thus the probability that all

N 
≥ e−2e ∈ Ω(1)
N + 2e

Thus the expected waiting time for removing V1 vertices is O(N log N ). We give an upper
bound on the probability of a bad event as follows.
Claim 6. The probability of the bad event when at least one more vertex of the A2 are
removed from the solution then the number of vertices of A1 are included in the solution is
at most


3
1
O(1)
−1
−1
2(β−1)
N
Θ(N −2 ) 1 + Θ(N (β−1) +
≤ Θ(N −2 ).
( ln N )2
Proof of claim 6. For the bad event to be happening, the accepted moves are when at least
one bit corresponding to the vertex v in V1 is set to 1 and at least two bit corresponding
to the neighbor vertices of v is set to 0. Thus if k vertices of V1 are accepted in solution
than at least k + 1 vertices of V2 are needed to be removed from the solution. First we
consider the case with 3 and 4 accepted bit flips in the solution. Since there are
N many

P
V1 vertices, then the total number of accepted three bits flips are v∈V1 deg(v)
.
It follows
2
P
P∆ 2−β
deg(v)
that v∈V1
≤ N i=4 i
∈ Θ(N ). This gives an upper bound of Θ(N −2 ) on
2
1

−3

the favorable 3-bit flips. Similarly, we can give the upper bound of Θ(N β−1 ) for the
favorable 4-bits flips. We now analyze the case of at least 5 favorable bit-flips occur. This
is the case when more than one vertices of V1 are accepted in the solution. Let S be the
set of accepted steps in the (1+1) EA, where at least i ≥ 2 vertices of V1 is accepted in
the solution. We denote with E(i, j, `) the event s.t. one vertex v ∈ V1 is accepted in the
solution and j many adjacent vertices are removed from the solution. The corresponding
probability is
deg(v)
N 1 X deg(v)
i N i j=2
j

!

P r[E(i, j, l)] =



!
Y

deg(u)

X


u∈S\v

`u =1

!

deg(u) 
`u

where lu is the number of vertices of V2 is removed from the solution which are adjacent

15

to the vertex u ∈ V2 \ v. Using the integral approximation of the sum there holds




deg(v)
deg(u)
N 1 X deg(v) 1 Y  X deg(u) 1 
i N i j=2
j
N j u∈S\v ` =1
`u
N `u

!

P r[E(i, j, l)] =

!

!

u

deg(v)

≤ i

X
j=2

≤ i

Z cN



1 Y  X
1
deg(v)j j
deg(u)`u `u 
N u∈S\v ` =1
N
u

1
β−1



x

cN β−1

−x



Y Z deg(u)  deg(u) y

dx

2

u∈S\v
2
−2
β−1

− 1) N
≤
(β − 2) ln (N )
i (β



deg(u)

dy

1

Y (b − 1) N 2b−2 −1
u∈S\v

2
−2
β−1

N

1

(7)

(b − 2) ln (N )

`
−` 
 (b − 1) N 2b−2

(β − 1) N
(β − 2) ln N
(b − 2) ln N
`+2
O(1)
−(`+2)
2(β−1)
≤
2N
( ln N )
3
O(1)
−3
2(β−1)
≤
.
2N
( ln N )
≤ i

(8)
1

Inequality 7 is valid because there is only one vertex with maximum degree n β−1 +
1
1
1
1 ≤ cN β−1 , and because the second highest degree of graph GW is n 2(β−1) ≤ cN 2(β−1) .
`+2

−(`+2)

Inequality 8 is valid because there holds ` ≥ 1, and because the function N 2(β−1)
is
a decreasing function with the increasing value of `. We can estimate the probability of a
bad event occurring as
P r[3 − accepted bits] + P r[4 − accepted bits] + P r[E(i, j, l)]
3
1
O(1)
−3
−3
2(β−1)
≤ Θ(N −2 ) + Θ(N β−1 ) +
2N
( ln N )
≤ Θ(N −2 ) 1 + Θ(N

1
−1
(β−1)

!

3
O(1)
−1
2(β−1)
+
N
.
2
( ln N )

From the claim above, ti follows that the probability of the (1+1) EA hitting the
−

(1−)





locally optimal solution V2 is at least 1−e 2ee12e 1 − N1 · Θ(1) ∈ Ω(1) . Now if the current
solution has to be updated in a way s.t. the (1+1) EA adds all the nodes of V1 removing
at least one more than as many
V2 from the solution, than
the probability of

 as nodes of
1
3
−1
−1
O(1)
−2
2(β−1)
this event is at most Θ(N ) 1 + Θ(N (β−1) +
. Thus the expected
2N
( ln N )
waiting time such that the (1+1) EA gives produces solution S where |S| < N − |OPT|)
produced is
Ω(1)N 2 = N Ω(2) ,
.
The corollary below follows from the theorem 1.
16

Corollary 1. For the PLB graphs with parameters β > 2, t ≥ 0 1+1-EA produces
(2 · aβ,t · bc1 ,β,t )-approx vertex cover in expected O(n log n) time.
Since a dominating set in the graph G is also a vertex cover, all hereby presented result
generalize to the MVC.

3.2

Multi-objective optimization

We consider GSEMO, which is the multi-objective counterpart of the (1+1) EA. The
fitness function is defined as
F (x) = (u(x), |x|1 )
where u(x) is the number of uncovered vertices, and |x|1 the number of 1s in input string.
The following lemma holds.
Lemma 3. Given a graph G having a minimum dominating set of size OPT and with
nk as the number of non dominated vertices after taking k nodes in the solution, then
at each step there exists a node v such that after taking node v in solution there holds


nk ≤ n 1 −

1
|OPT|

k

.

Proof. We prove this by induction for base case take, i = 1 and since the number of non
ni
dominated is n than there exist a v ∈ V such that it dominates atleast
many
|OPT|
vertices in the graph otherwise OPT is not the optimal solution. Then the number of non
dominated vertices are,
1
n
≤n· 1−
n1 ≤ n −
|OPT|
|OPT|




Let for ni the statement is true i.e, ni ≤ n 1 −

1



i

|OPT|
Now again there will be at least one vertex vi+1 ∈ V such that it dominate atleast
ni
otherwise optimum have more than |OPT| vertices. Therefore the number of
|OPT|
vertices to be dominated after vi+1 in solution is

ni
|OPT|


1
≤ ni 1 −
|OPT|
i+1

1
≤n 1−
|OPT|

ni+1 ≤ ni −

Theorem 7. The expected time until GSEMO has obtained ln 2+ ln (aβ,t · bc1 ,β,t ) + 1approximation for dominating set on PLB-U graphs with β > 2, t ≥ 0 is O(n3 ).
Proof. We first analyze the expected time until GSEMO has produced the solution 0n for
the first time. This solution is a Pareto optimal and therefore will stay in the solution
once added to the population. Also, the population size can be at most n + 1 as it
will contain at most one solution with exactly i 1-bits. The solution 0n is the feasible
solution hence no infeasible will be added after that. To analyze this, we consider in each
17

iteration the individual P with the minimum number of 1-bits, let b = |P |1 be the number
1
of 1−bits. Probability to choose P is atleast n+1
Since the b can not increase during
the run hence the probability of producing a solution P 0 where |P 0 |1 = b − 1 is atleast
1 b
n
n+1 en . Therefore the expected waiting time to include the solution 0 is upper bounded
Pn



b
en2

−1

= O(n2 log n).
Now that 0n bit string with fitness vector included in the population. By Lemma 3
there exist a vertex such that adding
that vertex
to the 0n will reduce number of non


by

b=1

dominated vertices to at most n · 1 −

1
|OPT|

. Since the probability of this vertex is at

1
1
least n1 = en
and probability of choosing the individual 0n is at least (n+1)
. Hence, in
2
expected O(n ) time a individual with fitness value (n1 , 1) can be added to the solution.



If n1 ≥ 1, then there still exist a vertex which will make u(x) ≤ n 1 −

2

1
|OPT|

.

Thus an individual (n2 , 2) can be added to the solution in expected O(n2 ) after adding
(n1 , 1). Similarly individual (nk , k) can be added to the population after (nk−1 , k − 1) is
included in population in expected O(n2 ).


Since we know that ni ≤ n · 1 −

i

1
|OPT|

Now we give bound on the value of k, Since

to be dominating set ni ≤ ni−1 and nk = 0, we have nk−|OPT|≥|OPT| . Set i = k−|OPT|
P
and n ≤ x∈OPT deg(x) + 1
1
(deg(x) + 1) · 1 −
|OPT|
x∈OPT


X

P

x∈OPT (deg(x)

+ 1)

|OPT|

·

i

≥|OPT|

1
≥1
ei/|OPT|

(9)
(10)

Now again by taking S = OPT, h(deg(x)) = deg(x) + 1, g(x) = h(x) − 1 and M =
in theorem 1. we can rewrite equation 9,

2 · (aβ,t · bc1 ,β,t ) ·

1
ei/|OPT|

n
2

as

≥1

since k = i+|OPT|
(ln 2 + ln (aβ,t · bc1 ,β,t ) + 1)|OPT| ≥ k
So, a dominating set with k many vertices will be included in population in O(n2 k) = O(n3 )
after (n, 0) included in the population.
Corollary 2. The expected time of until GSEMO has obtained the optimal solution on
the graph G is O(n3 ).
Proof. The corollary is a consequence of theorem 7 and the fact that the greedy output V1
as solution of the graph G which is also a optimal solution.
We can restate the result for the general graphs also which is the consequence of
Lemma 3 and can be proven by same argument,
18

Corollary 3. The expected time until GSEMO has obtained ln n + 1-approximation
OPT
for minimum dominating set on PLB-U graphs with β > 2, t ≥ 0 is O(n3 ).
Corollary 4. The expected time until GSEMO has obtained ln 2 + ln (aβ,t · bc1 ,β,t ) + 1approximation for minimum vertex cover on PLB-U graphs with β > 2, t ≥ 0 is O(n3 ).
Again, the hereby presented results can be easily generalized to the MVC.

4

The Connected Dominating Set

We consider the following problem. Given a Graph G = (V, E), a connected dominating
set is a minimum connected subset S ⊆ V , such that for each v ∈ V either v or a neighbor
of v is in S. The connected dominating set problem (CDS) consists of finding a minimal
connected dominating set.

4.1

Single-objective optimization

We study the optimization process for the CDS with the (1+1) EA. The fitness function
is defined as
F (x) = n2 (u(x) + (p(x) − 1))+|x|1 ,
where u(x) is the number of uncovered vertices, and p(x) is the number of connected
components in the complete sub-graph induced by the chosen solution. Again, the goal is
to minimize F (x). It can be observed that the x is a connected dominating set if and only
if u(x) = 0 and p(x) = 1. The algorithm tends to reach a state s.t. p(x) − 1 + u(x) = 0,
and then it removes unnecessary nodes. Again, the objective space can be divided into
two sets.
S1 = {x ∈ {0, 1}n : x is infeasible and F (x) ≥ n − 2}
S2 = {x ∈ {0, 1}n : x is feasible and F (x) < n − 2}

Theorem 8. (1+1) EA obtains (2 · aβ,t · bc1 ,β,t )-approximation connected dominating set
in expected O(n log n) run time.
The argument behind this theorem is identical to the one given for Theorem 1.

4.2

Multi-objective optimization

To implement the GSEMO we view the fitness F (x) described above as two objective
functions F (x) = (F1 (x), F2 (x)), with F1 (x) = |x|1 and F2 = u(x) + p(x). Note that there
holds minx {F2 (x)} = 1. From this point of view, once a covering has been found, the
algorithm tries to join the dominating set found at each iteration. In fact, GSEMO tries
to add a vertex which will either dominate the maximum number of vertices or connect
the maximum number of vertices already in solution. The following Lemma 4 holds.
Lemma 4. Let G be a connected graph, OPT be the optimal connected dominating set
of the solution and fi the value of u(x) + p(x) after taking i-many vertices as a solution.

19

Then there exist a vertex such that
fi ≤ fi−1 −


≤ f0

fi−1
+1
|OPT|

1
1−
|OPT|

i−1 
X

i

+

j=1

1
1−
|OPT|

j

A proof of this lemma is given by Guha et. al. [11]. The following theorem holds.
Theorem 9. The expected time until GSEMO has obtained ln 2 + ln (aβ,t · bc1 ,β,t ) + 1approximation for minimum connected dominating set on PLB-U graphs with β > 2, t ≥ 0
is O(n3 ).
Proof. This theorem can be proved by using the same argument of the theorem 7. Since
there are also at most n + 1 individuals in the population hence the expected time to
include the (n, 0) is O(n2 log n). Now if there are k many vertices are sufficient for the
connected dominating set then the expected time for GSEMO is O(kn2 ). We just need to
give bound on k, From Lemma 4 we know that for every i there exist a vertex such that,


fi ≤ f0


≤ f0

1
1−
|OPT|

i

1
1−
|OPT|

i

+

i−1 
X
j=1

1
1−
|OPT|

j

1
+ |OPT| · 1 − 1 −
|OPT|




≤ (f0 − |OPT|) 1 −

1
|OPT|

i !

i

+ |OPT|

Since fi = fi−1 − 1 and fk = 1 hence fk−2|OPT| ≥ 2|OPT| + 1, set i = k − |OPT|


(n − |OPT|) 1 −

1
|OPT|

i

+ |OPT| ≥ 2OPT

1
≥ OPT
i/|OPT|
e


n − |OPT|
|OPT| ln
≥i
|OPT|
P

x∈OPT (deg(x) + 1)
−1 ≥i
|OPT| ln
|OPT|
|OPT| ln(aβ,t · bc1 ,β,t − 1) + ln 2 ≥ i
(n − |OPT|) ·

As k = i + 2|OPT|,
k ≤ |OPT|(ln(aβ,t · bc1 ,β,t − 1) + ln 2 + 2)
Thus GSEMO will produce |OPT|(ln(aβ,t · bc1 ,β,t − 1) + ln 2 + 2)-approximation connected
dominating set in expected O(n3 ) time.
We can restate the result for the general graphs also which is the consequence of
Lemma 4 and can be proven by same argument,
Corollary 5. The expected time until GSEMO has obtained ln

n
|OPT|

+ 3-approximation

for minimum connected dominating set on PLB-U graphs with β > 2, t ≥ 0 is O(n3 ln n).
20

5

Maximum Independent Set

For a graph G = (V, E), the maximum independent set (MIS) is a subset S ⊆ V of
maximum size, such that no two different vertices u, v ∈ S are adjacent.

5.1

Single-objective optimization

To implement the (1+1) EA we use the fitness function used by Back et al. [2], which is
defined as
n
n
F (x) = |x|1 − n2

X
i=1

xi

X

xj eij

j=1

where eij is 1 if there is an edge (vi , vj ). In this case, the objective of the (1+1) EA is to
maximize the F (x). The first part of the fitness function gives the number of vertices in
P
P
the solution. It can be observe that the second part n ni=1 xi nj=1 xj eij = 0 if and only if
the vertices from the first part give an independent set. First the (1+1) EA adds vertices
in the solution, in order to obtain a consistent solution. Then, it will try to remove points
to maximize the fitness. To perform the analysis, we show that (1+1) EA can simulate the
3-flip neighborhood algorithm for maximum independent set. Khanna et al. [13] proved
that 3-flip neighborhood produces ∆+1
2 -approx solution for the independent set. We first
prove that the 3-flip neighborhood is a constant-approx for the P LBU -Graphs.
Lemma 5. For the PLB-U graphs with parameters β > 2, t ≥ 0 a 3-flip neighborhood
local search produces a (aβ,t · bc1 ,β,t )-approx independent set, where (aβ,t · bc1 ,β,t ) ≥ 1.
Proof. We prove this lemma by using the same argument used by Khanna et al. [13]. Let
S is the solution produced by 3-flip neighborhood. Let OPT be the optimal solution and
I = S ∩ OPT. Since we can not add a vertex outside S to get the bigger independent set
it means that every vertex in S have atleast one incoming edge from V \S. Also, since
we can not two vertices outside S to get bigger independent set it means that at most
|S\I| vertices in |OPT\I| can have exactly one vertices coming into S. Thus, |OPT| − |I|
vertices in OPT\I must have at least two edges incoming to S.
This implies that the minimum number of edges between between S and OPT\I is
|S| − |I| + 2(|OPT| − |S|). Also the maximum number edges between S and OPT\X is
bounded by the vol(S\I). Hence,
|S| − |I| + 2(|OPT| − |S|) ≤ vol(S\I) ≤ vol(S)

(11)

Now the equation 11 can be rewritten as,
|S| − |I| + 2(|| − |S|)
vol(S)
≤
|S|
|S|

(12)

Now again using Lemma 1 h(deg(x)) = deg(x) + 1, M = n2 , g(x) = deg(x) we can rewrite
the equation 12 as,
|S| − |I| + 2(|OPT| − |S|)
vol(S)
≤
|S|
|S|
|I|
|OPT|
+2
− 1 ≤ (2 · aβ,t · bc1 ,β,t )
1−
|S|
|S|
|OPT|
(aβ,t · bc1 ,β,t ) + 1 ≥
|S|
21

Hence the 3-flip neighborhood algorithm gives (aβ,t · bc1 ,β,t ) + 1-approximation solution.
By using the Lemma 5, we partition the objective space in three parts.
S1 = {x ∈ {0, 1}n : x is infeasible and F (x) < 0}
S2 = {x ∈ {0, 1}n : x is feasible and
0 ≥ F (x) < (aβ,t · bc1 ,β,t ) + 1}
S3 = {x ∈ {0, 1}n : x is feasible solution and
F (x) ≥ (aβ,t · bc1 ,β,t ) + 1}
The following theorem holds.
Theorem 10. For the PLB-U graphs with parameters β > 2, t ≥ 0 (1+1) EA produces
(aβ,t · bc1 ,β,t ) + 1-approx independent set in expected O(n4 ) time.
Proof. Let there be ` many nodes in the solutions, whose deletion will make the solution
from S1 to S2 . By the same argument as in theorem 1, a solution x can be changed into a
feasible one in O(n log n) fitness evaluations.
If we assume that the current solution is in S2 , then there exists a 3-bit flip operation. The probability that the (1+1) EA performs a 3-bit flip operation is bounded


n−3

by n13 1 − n1 )
≥ en1 3 . It can be observe that when the solution x ∈ S2 then
1 ≤ F (x) ≤ n − 1. Thus, there are at most n 3 − bit flips. It takes at most O(n4 )
on expectation to perform all valid 3-bit flips. Hence it takes O(n4 ) to bring the solution
from S2 to S3 .

6

Experiments

We experimentally compare the performance of the (1+1) EA and greedy algorithm on
scale-free networks. We consider both artificially generated graphs and real-world instances
from the Stanford Network Analysis Project (SNAP). We consider the Minimum Vertex
Cover problem. As previously described, for a given graph G = (V, E), with n nodes, a
solution is stored in memory as a pseudo-boolean array, its length is the number of vertices
of the graph. In all cases, the quality of the solution is evaluated against the following
function
f (x) = n2 u(x) + |xi |1
(13)
with u(x) returning the number of uncovered edges. In all cases we perform non-linear
regression to infer asymptotic trend. The fitting is performed using the nonlinear leastsquares Marquardt-Levenberg algorithm implemented by the ”lm” command of R 3.2.2
GUI 1.66 Mavericks build (6996). We perform a t-Student Test on the each model, to
determine whether it outperforms ”random noise” as a predictor. All tests are preformed
on Ubuntu 14.04.4 LTS, and implemented as Unix command line executable. In the first
set of experiments we compare the (1+1) EA with the greedy algorithm on artificially
generated scale-free graphs. We consider both the Chung-Lu and the Hyperbolic model.
For a given number of nodes n, we generate a random graph with power-law distribution
exponent β = 2.5. We then let the (1+1)-EA run for Θ(n log(n)) steps. In all cases, the
(1+1) EA is able to find a covering. We consider 102 runs and we look at the sample
mean of the solution size. We then compare it with the fitness of the solution found
22

covering size [sample mean]

800

Algorithm
EA [Chung−Lu]
EA [Hyperbolic]
Greedy [Chung−Lu]
Greedy [Hyperbolic]

600

400

200

250

500

750

number of nodes

Figure 3: Run time for the (1+1) EA and greedy algorithm on artificially generated scale-free
graphs with power law exponent β = 2.5, to find an approximation of the minimum vertex cover.
We let the (1+1) EA run for Θ(n log(n)) steps, and take the sample mean of 102 runs. The
greedy algorithm stops as soon as covering is generated. The fitting curves are obtained via
non-linear regression, and the shading is proportional to the sample standard deviation. We see
that the (1+1) EA beats the greedy algorithm on all graphs, both for the Hyperbolic model and
the Chung˙Lu model.

deterministically with the greedy algorithm. The results are displayed in Figure 3. We
clearly see that, for increasing number of nodes, the (1+1) EA outperforms the greedy
√
search. In fact, in the case of the (1+1) EA the fitting curve is O( n), while in the case
of greedy the best solution has linear size Θ(n) in the number of nodes. Given the positive
results for the (1+1) EA, we consider the more generic (µ + 1) EA and test it with a real
social network. We consider the General Relativity and Quantum Cosmology collaboration
network, from the e-print arXiv (cf. Leskovec et. al. [17]). It covers scientific collaborations
between authors submitted to General Relativity and Quantum Cosmology category. If an
author i co-authored a paper with author j, the graph contains a undirected edge from i
to j. It consists of 5 × 103 nodes and 14 × 105 edges. For a given population size µ, we let
the (µ + 1) EA run for Θ(n log(n)) fitness evaluations. Since a large population requires
more fitness evaluations at each step, then there is a trade-off between population size and
number of steps. In Figure 5 we display the fitness of the best solution found, for a given
population size. We display both the size of the covering and the number of uncovered
edges. We see that for increasing µ, more and more edges are left uncovered, and the
covering size decreases. Thus, with fitness defined as in Equation 13 the (µ + 1) EA does
not yields a significant advantage in comparison with the (1+1) EA. However, a lighter
weight on the u(x) may give a different optimal µ. We conclude by experimentally showing
that on the worst-case graph outlined in Section 3, the (1+1) EA gives worst performance
23

Figure 4: Run time for the (µ + 1) EA on a real-world network. We consider a scale-free network
from the Stanford Network Analysis Project (SNAP), which has 5 × 103 nodes and 14 × 105 edges.
We let (µ + 1) EA run for Θ(n log(n)) fitness evaluations. The dashed curves are obtained via
non-linear regression, and the shading is proportional to the sample standard deviation. We see
that the covering size decreases, and that the number of uncovered edges increases.

than Greedy. Note that on any such worst-case graph the minimum vertex cover problem
as outlined above is equivalent th the minimum dominating set problem. As in the case of
the first experiment, for a given number of nodes n, we generate a graph with power-law
distribution exponent β = 2.5. We then let the (1+1) EA run until the optimal solution is
generated. We consider 102 runs and we look at the sample mean of the solution size. In
Figure ?? we display the fitness of the best solution found, for a given number of nodes.
The curve outlined for greedy follows the bound given in Theorem 5. We see that the
experimental results follows the theoretical predictions: For increasing problem size greedy
outperforms the (1+1) EA in terms of number of steps needed to obtain the optimal
solution.

7

Conclusion

In this paper, we looked at the approximation ratio and run time analysis of both single- and
multi-objective EAs, for well known NPon the graphs with deterministic PLB properties,
and the power-law exponent β > 2. In sections 3 and 4 we analyze the (1+1) EA
and GSEMO for the maximum dominating set, maximum vertex cover and connected
dominating set problems. We show that the (1+1) EA and GSEMO obtain constantapproximation within polynomial run time. In section 5 we analyze the (1+1) EA for the
maximum independent set problem and show that it obtains constant approximation ratio
within expected polynomial steps.
24

Algorithm
EA [worst−case]
Greedy [worst−case]

run time [sample mean]

1 × 10+6

5 × 10+5

0 × 10+0
0

200

400

600

800

number of nodes

Figure 5: Run time for the (1+1) EA and on the worst-case example with power law exponent
β = 2.5, to find an approximation of the minimum vertex cover (cf. Section 3). We let the
(1+1) EA run until the global optimum is found, and take the sample mean of 102 runs. The run
time of greedy is given by the upper bound predicted theoretically (cf. Theorem 5). The fitting
curve is obtained via non-linear regression, and the shading is proportional to the sample standard
deviation. We see that greedy beats the (1+1) EAon these graphs.

In section 6 we observe experimentally that the (1+1) EA always produces better
results than the greedy algorithm for the minimum vertex cover problem. We show
that the (1+1) EA gives better approximation ratio than greedy on the Chung-Lu and
Hyperbolic model. We observe that on the Hyperbolic model the (1+1) EA reaches better
approximation ratio than in the Chung-Lu case. We give a worst case instance with the
PLB properties, where greedy algorithm obtain an optimal solution, but the (1+1) EA
gives worst possible solution with constant probability. We conclude that the EAs for the
above-mentioned problems on the graphs with PLB properties and β > 2, obtain better
approximation than the known worst-case approximation. This implies that topological
properties of real-world instances play an important role in the performance of EAs. On
the other hand, the worst-case example indicates that just PLB properties are not enough
to always obtain a better results than the greedy algorithm. Therefore, other properties of
real-world networks may affect the EAs run time.
We plan to further explore the interplay between topological properties and the run
time analysis of single- and multi-objective algorithms in the future.

References
[1] L. Adamic, O. Buyukkokten, and E. Adar. A social network caught in the web. First
Monday, 8, 2003.
25

[2] T. Bäck and S. Khuri. An evolutionary heuristic for the maximum independent set
problem. In Proc. of 1st WCCI, pages 531–535, 1994.
[3] P. Brach, M. Cygan, J. Lacki, and P. Sankowski. Algorithmic complexity of power
law networks. In Proc. of 27th SODA, pages 1306–1325, 2016.
[4] A. Chauhan, T. Friedrich, and R. Rothenberger. Greed is good for deterministic
scale-free networks. In Proc. of 36th FSTTCS, pages 33:1–33:15, 2016.
[5] V. Cohen-Addad and C. Schwiegelshohn. One Size Fits All : Effectiveness of Local
Search on Structured Data. ArXiv e-prints, 1701.08423, 2017.
[6] S. Droste, T. Jansen, and I. Wegener. On the analysis of the (1+1) evolutionary
algorithm. Theoretical Computer Science, 276:51 – 81, 2002.
[7] M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law relationships of the
internet topology. In Proc. of SIGCOMM, pages 251–262, 1999.
[8] N. Fountoulakis and A. Huber. Quasirandom rumour spreading on the complete
graph is as fast as randomized rumour spreading. SIAM J. Disc. Math., 23:1964–1991,
2009.
[9] T. Friedrich, N. Hebbinghaus, F. Neumann, J. He, and C. Witt. Approximating
covering problems by randomized search heuristics using multi-objective models. In
Proc. of GECCO, pages 797–804, 2007.
[10] O. Giel and I. Wegener. Evolutionary algorithms and the maximum matching problem.
In Proc. of 20th STACS, 2003.
[11] S. Guha and S. Khuller. Approximation algorithms for connected dominating sets.
Algorithmica, 20:374–387, 1998.
[12] T. Jansen and I. Wegener. Evolutionary algorithms - how to cope with plateaus of
constant fitness and when to reject strings of the same fitness. IEEE Transactions on
Evolutionary Computation, 5:589–599, 2001.
[13] S. Khanna, R. Motwani, M. Sudan, and U. Vazirani. On syntactic versus computational
views of approximability. SIAM Journal on Computing, 28:164–191, 1998.
[14] R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. Trawling the web for
emerging cyber-communities. Computer Networks, 31:1481–1493, 1999.
[15] X. Lai, Y. Zhou, J. He, and J. Zhang. Performance analysis of evolutionary algorithms
for the minimum label spanning tree problem. IEEE Transactions on Evolutionary
Computation, 18:860–872, 2014.
[16] J. Leskovec, J. Kleinberg, and C. Faloutsos. Graphs over time: Densification laws,
shrinking diameters and possible explanations. In Proc. of 11th KDD, pages 177–187,
2005.
[17] J. Leskovec, J. Kleinberg, and C. Faloutsos. Graph evolution: Densification and
shrinking diameters. ACM Transactions on Knowledge Discovery from Data, 1, 2007.
26

[18] F. Neumann. Expected runtimes of a simple evolutionary algorithm for the multiobjective minimum spanning tree problem. European Journal of Operational Research,
181:1620 – 1629, 2007.
[19] F. Neumann and I. Wegener. Randomized local search, evolutionary algorithms, and
the minimum spanning tree problem. Theoretical Computer Science, 378:32–40, 2007.
[20] M. E. J. Newman. The structure and function of complex networks. SIAM Review,
45:167–256, 2003.
[21] P. S. Oliveto, J. He, and X. Yao. Evolutionary algorithms and the vertex cover
problem. In Proc. of CEC, pages 1870–1877, 2007.
[22] P. S. Oliveto, J. He, and X. Yao. Analysis of population-based evolutionary algorithms
for the vertex cover problem. In Proc. of CEC, pages 1563–1570, 2008.
[23] X. Peng. Performance analysis of (1+1) EA on the maximum independent set problem.
In Proc. of 1st ICCCS, pages 448–456, 2015.
[24] A. G. Phadke and J. S. Thorp. Computer Relaying for Power Systems. John Wiley
& Sons, Ltd, 2009.
[25] L. Ruan, H. Du, X. Jia, W. Wu, Y. Li, and K. Ko. A greedy approximation for
minimum connected dominating sets. Theoretical Computer Science, 329:325–330,
2004.
[26] D. J. Watts and S. H. Strogatz. Collective dynamics of ’small-world’ networks. Nature,
393:440–442, 1998.
[27] D. P. Williamson and D. B. Shmoys. The Design of Approximation Algorithms.
Cambridge University Press, New York, NY, USA, 1st edition, 2011.
[28] C. Witt. Worst-Case and Average-Case Approximations by Simple Randomized Search
Heuristics, pages 44–56. 2005.
[29] Y. Yu, X. Yao, and Z.-H. Zhou. On the approximation ability of evolutionary
optimization with application to minimum set cover. Artificial Intelligence, 180:20 –
33, 2012.

27

