> Friedrich-Schiller-Universität Jena
Fakultät für Mathematik und Informatik
Theoretische Informatik I
> Research: Completed projects

DAAD-Project D/05/57666 (India–Germany Joint Research Collaboration): “Provably Efficient Exact Algorithms for Computationally Hard Problems”

This is a joint project with the group of Venkatesh Raman, Theoretical Computer Science at the Institute of Mathematical Sciences, Chennai, India.

Visits funded by the project:

DFG-Project PIAF (NI 369/4): “Fixed-Parameter Algorithms”

In the last few years fixed-parameter algorithms developed into an important alternative to heuristic and approximation algorithms for solving combinatorially hard problems. The main idea of fixed-parameter algorithms is to restrict the seemingly inherent combinatorial explosion of solving algorithms for these problems to problem-specific parameters. The project PIAF aims at an investigation of the research field of fixed-parameter algorithms also taking into regard practical aspects: Implementation and experiments with real-world data shall be an equally important component of the project. With respect to practical applications, we concentrate on central techniques such as data reduction by efficient preprocessing. We investigate fundamental problems as Vertex Cover and Dominating Set (in particular, variants of these problems arising in practice). The relationships of fields such as heuristic or approximation algorithms to fixed-parameter algorithms will also be part of our project.

DFG-Project ITKO (NI 369/5): “Iterative Compression for Solving Hard Network Problems”

The technique of “iterative compression” recently suggested by Reed, Smith, and Vetta provides a new tool for the design of exact algorithms for combinatorial complex network problems. The project ITKO aims to investigate the theoretical foundations of iterative compression and to explore and extend its range of application. In particular the (improved) method is to be applied to a list of concretely suggested network problems to obtain new efficient algorithms. Last but not least an objective is to implement and and test the thus gained algorithms in a practical environment. First experiences of the working group in handling iterative compression are very promising.

See the ITKO project homepage for more details.

DFG Project OPAL (NI 369/2): “Optimal Solutions for Hard Problems in Computational Biology”

Computational biology has become an independent, interdisciplinary area of research that emerged from biology, chemistry, computer science, and mathematics. Many problems from this field are of combinatoric nature and turn out to be hard in the computational sense. The molecular biologist Joseph Felsenstein is cited in 1998 as follows: “About ten years ago, some computer scientists came by and said they heard we have some really cool problems. They showed that the problems are NP-complete and went away!”

To investigate the tractability of hard combinatorial problems in molecular biology is the main concern of this project. Its focus is on exact algorithms with optimal solutions and guaranteed bounds on the running time. In particular, we intend to reveal the parameterized complexity of biological problems. The concept of parameterized complexity is to try to restrict the “combinatorial explosion”, e.g., for NP-hard problems, to a parameter and, thereby, to obtain fast algorithms with optimal and not only approximated results. Implementing our algorithms, we complement them with heuristic strategies to further improve their performance in practice. Thus, the OPAL project is the problem-oriented, practically aimed sister to the more theoretically focused PEAL project (Parameterized Complexity and Exact Algorithms).

We cooperate with partners from biology and biochemistry on hard combinatorial problems in the analysis of DNA sequences, e.g., phylogenetics, primer design, motif search, and genome comparison.

DFG Project PEAL (NI 369/1): “Parameterized Complexity and Exact Algorithms”

The analysis of the parameterized complexity of NP-hard problems can well be considered as one of the latest proposals to deal with combinatorially hard problems. The main idea of this approach consists in isolating one (or several) parameter(s) as part of the input instance onto which the seemingly inherent "combinatorial explosion" can be restricted. In this way, assuming that the value of the parameter is small, one obtains efficient exact algorithms for the underlying problem.

Formally, the class of parameterized problems which allow for efficient parameterized algorithms is called FPT (short for “fixed parameter tractable”). But already Downey and Fellows, the fathers of the theory of parameterized complexity, write at the end of the introduction of their monograph Parameterized Complexity (R. G. Downey and M. R. Fellows, Springer-Verlag, 1999): “The positive toolkit for designing FPT algorithms contains several key methods that are very deep and general—but for which practicality is still not yet clearly established. Much remains to be explored.”

This project aims to investigate the strength and the weak parts of the concept of parameterized complexity and to clarify its practical usefulness. Beyond this, we plan to implement efficient parameterized algorithms for several problems motivated from practice and investigate the performance of such algorithms.

Valid HTML 4.01! Last modified: Tue Oct 20 18:27:36 CEST 2009