Designing
Faster Algorithms by Random Separation
By

Professor
CAI Leizhen

Department
of Computer Science & Engineering

The
Chinese University of Hong Kong

Date:
Feb 4, 2008 (Monday) 
Time:
4:00pm  5:00 pm 
Venue:
Rm. 1009 William M.W. Mong Engineering Building,
CUHK 
Abstract
:
Parameterized
complexity is a useful framework for dealing with
NPhard problems. In this framework, we choose some
part of the input instance of an NPhard problem as
a parameter k and try to design an FPT algorithm,
i.e., an algorithm that runs in time f(k)poly(n) for
some function f independent of the input size n.For
instance, the classical Vertex Cover problem can be
solved in O(kn + 1.274^k)time when we choose the size
of a vertex cover as the parameter k.This FPT algorithm
can easily solve Vertex Cover instances for k = 100
and n in millions, while the straightforward O(n^k)time
exhaustive search algorithm can hardly solve an instance
with k = 10 and n = 100. In this talk, I will discuss
a novel method, called random separation, for designing
FPT algorithms. This method was recently developed
by Cai, Chan and Chan for solving fixedcardinality
optimization problems on graphs, i.e.,problems concerning
solutions with exactly k elements(e.g., k vertices
V') that optimize solution values (e.g., the number
of edges covered by V').The key idea of the method
is to randomly partition the vertex set of a graph
into two disjoint sets to separate a solution from
the rest of the graph into connected components, and
then select appropriate components to form a solution.
We can use universal sets to derandomize algorithms
obtained from this method. The random separation method
is versatile and powerful as we can use it to obtain
FPT algorithms for classes of fixedcardinality optimization
problems on degreebounded graphs, graphs of bounded
degeneracy (a large family of graphs that contains
degreebounded graphs, planar graphs, graphs of bounded
treewidth,and nontrivial minorclosed families of
graphs), and even general graphs.
Biography
:
Cai
Leizhen received his PhD from the Department of Computer
Science at University of Toronto in 1992. His main
research interests are graph algorithms, graph theory,
and parameterized complexity. His major contributions
include the work on graph spanners, parameterized
graph families and fixedcardinality optimization
problems.
