Parameterized Algorithms for Graph Problems

Abstract

The fixed parameter approach to a problem is a technique of designing an algorithm to solve combinatorially hard problems. A parameterized problem has an input instance x as well as a parameter k which is sufficiently small compared to the input size of the instance. A parameterized problem is FPT (fixed parameter tractable) if there exists an algorithm which correctly decides whether the input instance of the given problem is a yes or no instance in f(k).|x|^O(1) time where f is some computable function. Similarly, if the algorithm requires f(k).|x|^g(k) time then it is called XP (here f and g are computable functions). In this project, we study paramaterized complexity, kernelization techniques, branching algorithms and treewidth.