Parameterized Algorithmics for Finding Exact Solutions of NP-Hard Biological Problems

Abstract

Fixed-parameter algorithms are designed to efficiently find optimal solutions to some computationally hard (NP-hard) problems by identifying and exploiting "small" problem-specific parameters. We survey practical techniques to develop such algorithms. Each technique is introduced and supported by case studies of applications to biological problems, with additional pointers to experimental results.

Keywords: Algorithm design; Computational intractability; Discrete problems; Exponential running times; Fixed-parameter tractability; NP-hard problems; Optimal solutions.