A brief glance at fixed-parameter algorithms and their applications
- Speaker: Dr Igor Razgon
- Date: Wednesday, 9 November 2011 from 16:45 to 17:45
- Location: Room 745, Malet Street
Fixed-parameter algorithms is a method of coping with NP-hardness. They use the fact that aprat from the input size $n$ computational problems are often accompanied with additional parameters (e.g. maximum allowed size of the output, a structural parameter of the underlying graph, etc.) The fixed parameter algorithms take time exponential in this parameter but polynomial in $n$. If the parameter is small compared to $n$ then the exponential part becomes a negligible multiplicative or even additive constant and we have an illusion of a polynomial time algorithm precisely solving an NP-hard optimization problem. Problems that can be solved this way are called fixed-parameter tractable (FPT) and the area studying fixed-parameter tractability of computational problems is called parameterized complexity.
This talk will consist of two parts. In the first part I will define the above notions in a little bit more formal fashion and present two simple yet quite elegant fixed-parameter algorithms with the purpose to convey the aesthetic beauty of the field. In the second part I will consider applications of the methodology of fixed-parameter computation to the following three fields: computational biology, efficient solving of large satisfiability instances, and knowledge compilation.
The main purpose of the talk is that after it the audience would feel that they have learned something new and interesting. Therefore the talk will be self-contained and (I hope) entertaining.