Pragmatic Parameterized Algorithms

• Applicant: Professor Dr. Peter Rossmanith
• Subject Area: Theoretical Computer Science
• Term: from 2012 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 221760991

The paradigms of fixed-parameter and moderately exponential algorithmshave been spectacularly successful in obtaining efficient algorithms fora number of NP-complete problems. Many of these algorithms are, however,purely theoretical in the sense that they are not implementable in areal-world setting, i.e., under tight time and cost constraints. Forinstance, there are algorithms that rely on algorithmic meta-theorems - results that hold not just for a few isolated problemsbut for a whole class of problems. While meta-theorems are immensely useful inquickly establishing whether a problem at hand admits an algorithm of aparticular type, they are usually not very useful in designing algorithmsin practice. Then again there are algorithms that use deep structural theoremssuch as the Graph Minors Theorem. Such algorithms are not implementable either. Finally there are algorithms that use structural parameters that are themselves hardto compute. Efficient FPT-algorithms wrt these parameters might not be efficient in practice. The broad goal of this project is to bridge the gap between purely theoretical algorithmsand heuristics that are extensively used in practice but which produce solutions without any quality guarantee. In particular, we seek to develop efficient algorithms that are (1) easily translatable into programs and run successfully under real-worldconstraints; and, (2) competitive with or even faster than the currentbest algorithms in their asymptotic behavior. Our main aim is to improve and create new algorithmic techniques in order to take a stepforward towards implementability. These new algorithmic techniques themselves be complex or have the flavor of meta-theorems but we areinterested in those which are amenable to implementation.The real-world constraints we have in mind include implementation time,space requirements and running time guarantees. By providing transparenttime and space bounds, i.e., by keeping polynomial and constants factorswithin reasonable limits, we wish to push the envelope of algorithmsthat can eventually be engineered for use in industry andapplications.

• DFG Programme: Research Grants