Parameterized complexity and graph algorithms

Algorithms and their design and analysis are the hart of information technology and play a crucial role in the data processing underlying such technological developments as internet search engines, graphics applications and bioinformatics. Both in these a nd other application fields real-world problems are often abstracted by means of a binary relation and modelled as a graph. Unfortunately, many graph problems thus defined cannot be solved efficiently, in polynomial-time, by traditional algorithm techniqu es. The recently introduced theory of parameterized complexity concerns the efficiency of solution algorithms as related to a specific parameter of the input instance, as well as the instance size. Limiting that parameter value may result in existence of efficient algorithms. This project will explore the use of parameterized complexity techniques for developing practical algorithms for graph problems.