Title: Parameterized Complexity of Cardinality Constrained Optimization 
Speaker: Cai Leizhen

Department of Computer Science and Engineering
The Chinese University of Hong Kong

Date: Friday Nov 4, 2005
Time 11-12 Venue: Room 3464, HKUST   


Abstract 
A cardinality constrained optimization problem requires its solutions
to contain exactly a specified number k of elements to optimize
solution values, and most combinatorial optimization problems have
their natural cardinality constrained counterparts.
For instance, a natural such counterpart for the classical minimum
vertex cover problem is the problem of choosing k vertices in a graph to
cover as many edges as possible.

In this talk, I will discuss my current work on cardinality constrained
optimization problems from parameterized complexity point of view.
In short, we try to confine the combinatorial explosion of such problems to
the parameter k, the size of solutions, and thereby derive fast algorithms
for relatively small values of k. While exhaustive search algorithms may
take days for k = 5 and n = 1000, there are algorithms that can handle
k = 100 and n = 1,000,000 in a matter of minutes.

I will discuss the following aspects of cardinality constrained optimization
for many fundamental graph problems: approximability, fixed-parameter
tractability, fixed-parameter intractability and nontrivial exact algorithms