Parameterized Complexity Analysis of Evolutionary Algorithms

We consider the Steiner Multicut problem, which asks, given an undirected graph G, a collection T = { T 1 , ź , T t } , T i ź V ( G ) , of terminal sets of size at most p, and an integer k, whether there is a set S of at most k edges or nodes such that ...

The Paired Domination problem is one of the well-studied variants of the classical Dominating Set problem. In a graph G on n vertices, a dominating set D (set of vertices such that $N[D]=V(G)$) is called a paired dominating set of G, if G[D] has ...

In this paper we study the notion of parameterized exponential time complexity. We show that a parameterized problem can be solved in parameterized 2^o^(^f^(^k^)^)p(n) time if and only if it is solvable in time O(2^@d^f^(^k^)q(n)) for any constant @d>0, ...