
It has been observed that many complex realworld networks have certain
properties, such as a high clustering coefficient, a low diameter, and a
powerlaw degree distribution. A network with a powerlaw degree distribution
is known as scalefree network. In order to study these networks, various
random graph models have been proposed, e.g. Preferential Attachment, ChungLu,
or Hyperbolic.
We look at the interplay between the powerlaw degree distribution and the
run time of optimization techniques for well known combinatorial problems. We
observe that on scalefree networks, simple evolutionary algorithms (EAs)
quickly reach a constantfactor approximation ratio on common covering problems
We prove that the singleobjective (1+1)EA reaches a constantfactor
approximation ratio on the Minimum Dominating Set problem, the Minimum Vertex
Cover problem, the Minimum Connected Dominating Set problem, and the Maximum
Independent Set problem in expected polynomial number of calls to the fitness
function.
Furthermore, we prove that the multiobjective GSEMO algorithm reaches a
better approximation ratio than the (1+1)EA on those problems, within
polynomial fitness evaluations.

Network creation games investigate complex networks from a gametheoretic
point of view. Based on the original model by Fabrikant et al. [PODC'03] many
variants have been introduced. However, almost all versions have the drawback
that edges are treated uniformly, i.e. every edge has the same cost and that
this common parameter heavily influences the outcomes and the analysis of these
games.
We propose and analyze simple and natural parameterfree network creation
games with nonuniform edge cost. Our models are inspired by social networks
where the cost of forming a link is proportional to the popularity of the
targeted node. Besides results on the complexity of computing a best response
and on various properties of the sequential versions, we show that the most
general version of our model has constant Price of Anarchy. To the best of our
knowledge, this is the first proof of a constant Price of Anarchy for any
network creation game.

Large realworld networks typically follow a powerlaw degree distribution.
To study such networks, numerous random graph models have been proposed.
However, realworld networks are not drawn at random. Therefore, Brach, Cygan,
{\L}acki, and Sankowski [SODA 2016] introduced two natural deterministic
conditions: (1) a powerlaw upper bound on the degree distribution (PLBU) and
(2) powerlaw neighborhoods, that is, the degree distribution of neighbors of
each vertex is also upper bounded by a power law (PLBN). They showed that many
realworld networks satisfy both deterministic properties and exploit them to
design faster algorithms for a number of classical graph problems.
We complement the work of Brach et al. by showing that some wellstudied
random graph models exhibit both the mentioned PLB properties and additionally
also a powerlaw lower bound on the degree distribution (PLBL). All three
properties hold with high probability for ChungLu Random Graphs and Geometric
Inhomogeneous Random Graphs and almost surely for Hyperbolic Random Graphs. As
a consequence, all results of Brach et al. also hold with high probability or
almost surely for those random graph classes.
In the second part of this work we study three classical NPhard
combinatorial optimization problems on PLB networks. It is known that on
general graphs with maximum degree {\Delta}, a greedy algorithm, which chooses
nodes in the order of their degree, only achieves an {\Omega}(ln
{\Delta})approximation for Minimum Vertex Cover and Minimum Dominating Set,
and an {\Omega}({\Delta})approximation for Maximum Independent Set. We prove
that the PLBU property suffices for the greedy approach to achieve a
constantfactor approximation for all three problems. We also show that all
three combinatorial optimization problems are APXcomplete, even if all
PLBproperties hold.

Robustness is one of the key properties of nowadays networks. However,
robustness cannot be simply enforced by design or regulation since many
important networks, most prominently the Internet, are not created and
controlled by a central authority. Instead, Internetlike networks emerge from
strategic decisions of many selfish agents. Interestingly, although lacking a
coordinating authority, such naturally grown networks are surprisingly robust
while at the same time having desirable properties like a small diameter.
To investigate this phenomenon we present the first simple model for selfish
network creation which explicitly incorporates agents striving for a central
position in the network while at the same time protecting themselves against
random edgefailure. We show that networks in our model are diverse and we
prove the versatility of our model by adapting various properties and
techniques from the nonrobust versions which we then use for establishing
bounds on the Price of Anarchy. Moreover, we analyze the computational hardness
of finding best possible strategies and investigate the game dynamics of our
model.

We study structural aspects of randomized parameterized computation. We
introduce a new class ${\sf W[P]}$${\sf PFPT}$ as a natural parameterized
analogue of ${\sf PP}$. Our definition uses the machine based characterization
of the parameterized complexity class ${\sf W[P]}$ obtained by Chen et.al [TCS
2005]. We translate most of the structural properties and characterizations of
the class ${\sf PP}$ to the new class ${W[P]}$${\sf PFPT}$.
We study a parameterization of the polynomial identity testing problem based
on the degree of the polynomial computed by the arithmetic circuit. We obtain a
parameterized analogue of the well known SchwartzZippel lemma [Schwartz, JACM
80 and Zippel, EUROSAM 79].
Additionally, we introduce a parameterized variant of permanent, and prove
its $\#W[1]$ completeness.