Some Prospects forEfficient Fixed Parameter Algorithms
Rolf Niedermeier5 
| (5) |
Wilhelm-Schickard-Institut für Informatik, UniversitÄt Tübingen, Sand 13, D-72076 Tübingen, Fed. Rep. of Germany |
Abstract
Recent time has seen quite some progress in the development of exponential time algorithms for NP-hard problems, where the
base of the exponential term is fairly small. These developments are also tightly related to the theory of fixed parameter
tractability. In this incomplete survey, we explain some basic techniques in the design of efficient fixed parameter algorithms, discuss deficiencies of parameterized complexity theory, and try to point out some future research
challenges. The focus of this paper is on the design of efficient algorithms and not on a structural theory of parameterized
complexity. Moreover, our emphasis will be laid on two exemplifying issues: Vertex Cover and MaxSat problems.
Supported by a Feodor Lynen fellowship of the Alexander von Humboldt-Stiftung, Bonn, and the Center for Discrete Mathematics,
Theoretical Computer Science and Applications (DIMATIA), Prague. Author’s address in 1998: DIMATIA MFF UK, Charles University,
Malostranské námĚstí 25, 118 00 Praha 1, Czech Republic.
References secured to subscribers.