Abstract :

Parameterized complexity is a useful framework for dealing with NP-hard problems. In this framework, we choose some part of the input instance of an NP-hard 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 fixed-cardinality 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 fixed-cardinality optimization problems on degree-bounded graphs, graphs of bounded degeneracy (a large family of graphs that contains degree-bounded graphs, planar graphs, graphs of bounded tree-width,and nontrivial minor-closed 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 fixed-cardinality optimization problems.