Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

Fixed Parameter Tractability

DST-DAAD Joint Project

Project approved under the Personnel Exchange Programme 1999 of the Department of Science and Technology, Government of India, and the Deutscher Akademischer Austauschdienst (German Academic Exchange Service), Germany.


Duration: April 1999 to March 2002.


Project Members

Institution Project Member
Humboldt University, Berlin, Germany. Johannes Köbler (Principal Investigator from Germany)
Wolfgang Lindner
Johannes Mayer
Olaf Beyersdorff
Ulm University, Ulm, Germany. Rainer Schuler
The Institute of Mathematical Sciences, Chennai, India. V. Arvind (Principal Investigator from India)
Meena Mahajan
Venkatesh Raman
S. Srinivasa Rao
Chennai Mathematical Institute, Chennai, India. K. V. Subrahmanyam
University of Aarhus, Aarhus, Denmark. N V Vinodchandran

Research background

The decision versions of many NP-complete problems have some associated parameters. If k is the parameter and n is the input size of the problem, then typically several problems have an O(nck) algorithm for some constant c. Since the problems are NP-hard, the exponential dependence on k seems unavoidable.

The recent theory of Parameterized Complexity, proposed by Rod Downey and Mike Fellows, tries to identify which of these problems are fixed-parameter tractable FPT, i.e. have algorithms running in O(f(k) nd) time, where f is some arbitrary (exponential or worse) function of k alone, and d is a constant independent of k. Such an algorithm (for reasonable values of f) is of practical importance for small values of the parameter k. Often the design of such algorithms throws up new approaches to solving special cases of the general problem.

Furthermore, for problems not known to be in FPT, the new theory allows a stratification based on the notion of W-hardness. This provides a finer classification of NP-complete problems.

The Parameterized Complexity framework thus provides new strategies for coping with classical intractibility, and new tools for understanding and quantifying hardness.

Some related links