Parameterized Complexity of Cardinality Constrained Optimization
(L. Cai)

Cardinality constrained optimization problems require their solutions to contain exactly a given number of elements to optimize solution values, and most combinatorial optimization problems have their natural cardinality constrained counterparts. For example, the classical minimum vertex cover problem asks for the minimum number of vertices in a graph to cover all edges, and a cardinality constrained counterpart of it is the maximum k-vertex cover problem that requires us to find k vertices to cover the maximum number of edges. In this project, we are mainly interested in parameterized complexity of cardinality constrained optimization problems, i.e., we study how the solution size k affects the running time of algorithms. In particular, we are developing a powerful randomized method, random separation, for solving these problems.