### Page Content

## ALEPH: Algorithm Engineering for NP-hard Problems: Parameterized Algorithms versus Established Techniques

Funded by Deutsche Forschungsgemeinschaft (Project ALEPH, HU 2139/1)

project term: March 2013 - February 2016

Synopsis:

Many combinatorial problems from diverse application areas such as biology, operations research, or data mining, are NP-hard. In practice, mainly heuristics or mathematical programming (ILPs) are employed for such problems; however, these typically lack guarantees on solution quality or guarantees on running time. Parameterized algorithms are a recent approach that tries to solve problems from practice optimally in provably bounded time. Although there is much progress in the theory and the field has the explicit claim of applicability, there are few works on implementation and experiments with real-world data that lead to practically deployable software. In this project, first based on parameterized algorithmics new methods for solving NP-hard problems will be developed; these will then be implemented and compared to conventional technique approaches, in order to reach general recommendations. Further, parameterized techniques will be used to improve heuristics and ILP approaches. In this way, it will be examined how far parameterized algorithmics can hold up to the claim of delivering practically relevant solution methods. For this, also general principles and instructions will be developed that show how to attack a hard problem with the methods of parameterized algorithmics.

Head: Falk Hüffner

## DARE: Data Reduction and Problem Kernels

Funded by Deutsche Forschungsgemeinschaft (Project DARE, NI 369/11)

project term: March 2010 - January 2014

Synopsis:

Preprocessing by means of data reduction rules is a common approach for the algorithmic treatment of combinatorially difficult and compute-intensive problems. Typically, the data reduction approaches used so far have an ad hoc character and are not systematically developed. Theory construction has not taken place for this universally applicable method so far. With the concept of the problem kernels originating from parameterized complexity, it is now for the first time possible to undertake a systematic, theoretically supported investigation on the effectiveness of data reduction techniques. In addition, these theoretical investigations can—as shown in first case studies—very effectively guide the search for new, better data reductions. With algorithm engineering, practical tools can be developed, and the actual capability of data reduction rules in most diverse applications can be examined. Eventually, this opens up new application potential for this basic algorithmic technology.

People: Mathias Weller, Vincent Froese

Head: Rolf Niedermeier

## PAWS: Parameterized Algorithmics for Voting Systems

Funded by Deutsche Forschungsgemeinschaft (Project PAWS, NI 369/10)

project term: May 2009 - February 2017

Synopsis:

Voting systems play a central role in modern society. Voting scenarios arise whenever the preferences of different parties have to be aggregated to form a joint decision. This is what happens in political elections, group decisions, web site rankings, or multiagent systems. There is a great variety of voting protocols that lead to a rich area of research questions. Questions arising in this area concern the efficient determination of a winner as well as manipulation, control, and lobbying. Many of these problems turn out to be NP-hard. The main goal of this project is the design of parameterized algorithms to efficiently analyze and handle voting systems.

People: Robert Bredereck

Head: Rolf Niedermeier

## AREG: Algorithms for Generating Quasi-Regular Structures in Graphs

Funded by Deutsche Forschungsgemeinschaft (Project AREG, NI 369/9)

project term: February 2008 - December 2013

Synopsis:

Algorithms to find quasi-regular structures in graphs make up a broad field in graph algorithmics. A simple special case is the well-known Vertex Cover problem. Recently, new problems in this context with interesting applications were introduced, and new techniques were developed. Examples of such techniques are, e.g, the interative compression technique or the characterization via forbidden subgraphs. However, the studies of the problems and the techniques were quite specific and isolated from each other up to now. In this project, these problems and techniques are studied in a more general context, using all relevant algorithmic methods for NP-hard problems (including experiments).

People: René van Bevern and Ondřej Suchý

Head: Rolf Niedermeier

## PABI: Parameterized Algorithmics for Bioinformatics

Funded by Deutsche Forschungsgemeinschaft (Project PABI, NI 369/7)

project term: October 2007 - February 2014

Synopsis:

The project "Parameterized algorithmics for bioinformatics (PABI)" heads at exploring and understanding the reasons for computational intractability (NP-hardness) of a large number of problems in algorithmic bioinformatics. As it turned out in recent years, the hardness of these problems can often be attributed to problem-specific parameters. In particular, if these problem parameters are small - and if the seemingly unavoidable combinatorial explosion inherent to the NP-hard problems can be confined to these parameters - then the concept of fixed-parameter tractability may offer an opportunity for efficient (and exact) algorithms despite NP-hardness.

People: Falk Hüffner and Manuel Sorge

Head: Rolf Niedermeier