CATS-Sep-27-2013
Title[edit]
List H-Coloring a Graph by Removing Few Vertices
Speaker[edit]
Rajesh Chitnis, University of Maryland
Abstract[edit]
Traditionally fixed-parameter algorithms (FPT) and approximation algorithms have been considered as different approaches for dealing with NP-hard problem. The area of fixed-parameter approximation algorithms tries to tackle problems which are intractable to both these techniques. In this talk we will start with the formal definitions of fixed-parameter approximation algorithms and give a brief survey of known positive and negative results. Then (under standard conjectures in computational complexity) we show the first fixed-parameter inapproximability results for Clique and Set Cover, which are two of the most famous fixed-parameter intractable problems. On the positive side we obtain polynomial time f(OPT)-approximation algorithms for a number of W[1]-hard problems such as Minimum Edge Cover, Directed Steiner Forest, Directed Steiner Network, etc. Finally we give a natural problem which is W[1]-hard, does not have a constant factor approximation in polynomial time but admits a constant factor FPT-approximation.
This is joint work with MohammadTaghi Hajiaghayi and Guy Kortsarz.
