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

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(n^ck) 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) n^d) 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

• Parameterized Complexity
  Book by Rodney G. Downey and Michael R. Fellows, in the Series: Monographs in Computer Science of Springer-Verlag . 1999.
• Computational Tractability: The View From Mars
  A survey article by Rodney G. Downey, Michael R. Fellows, and Ulrike Stege, that appeared in the EATCS Bulletin Number 69 (October 1999) in the Computational Complexity Column edited by Eric Allender.
• Compendium of Parameterized Results
  Compiled by Michale T. Hallett and H. Todd Wareham .
• Todd Wareham's Parameterized Complexity Home Page