### Inhalt des Dokuments

## MaMu: Matching under Preferences: Multimodal Views and Domain Restrictions

Funded by Deutsche Forschungsgemeinschaft (Project MaMu, NI 369/19) and the National Natural Science Foundation of China, starting April 2018.

Synopsis:

Given the great relevance of matching under preferences, the goals
of this joint research project are basically two-fold. First, we want
to investigate how restrictions on the allowed preferences can improve
the efficiency for several solving algorithms. Doing so, we want to
extend and improve results from the literature. Second, we plan to
study stable matching for multi-layer preferences, a new direction we
introduce here. Indeed, it is very well-motivated by the fact of
having multi-modal data available (from different sources). To this
end, after carefully introducing the relevant notions it is of central
interest to investigate how classical concepts and algorithms can be
transferred to this more general scenario. Finally, in a third part we
plan to study further models, going beyond the two mentioned main
parts. In particular, here we aim at touching on issues such as
“incremental scenarios” or game-theoretic aspects.

The
projects brings together the expertise of the Chinese and the German
research groups. Both sides have actively contributed to several
topics related to Computational Social Choice and, in particular, to
restricted preferences and issues of preference aggregation. Moreover,
both groups are heavily involved into parameterized complexity
analysis and algorithms for hard combinatorial problems in general.
Based on this common ground, the proposed project builds on (partially
joint) previous experiences and joins forces in attacking a
fundamental issue of Computational Social Choice and closely related
areas; matching under preferences, as we will demonstrate, both being
fundamental and being unexplored in several directions, allows for
numerous future innovations (conceptually and methodologically) we
want to provide.

People at TU Berlin: N.N.; Head: Rolf Niedermeier

People at Shandong University: Jiong Guo [1] and Hong Liu [2]; Head: Daming Zhu [3]

## TORE: Trade-offs in Parameterized Data Reduction

Funded by Deutsche Forschungsgemeinschaft (Project TORE, NI 369/18) and Russian Foundation for Basic Research, starting in March 2018.

Synopsis:

Kernelization is arguably one of the major contributions of parameterized complexity analysis to algorithm design. In this project, based on many years of experience with various facets of kernelization, we plan to further push the development of new aspects of kernelization, particularly focussing on various trade-off effects. In particular, we are interested in trade-offs of efficient kernelization time and effective kernel size with a number of quality measures for kernels. So we are interested in Pareto-optimal kernels, then making use of “chaining effects” by executing one kernelization after another. Further, we plan to systematically explore concepts such as partial kernelization, approximative kernelization, randomized kernelization, Turing kernelization etc., all with the ultimate goal to trade better running time and/or kernel size against some relaxation of the kernel concept. Doing so, we plan to contribute both theoretically (including new frameworks and lower bounds) and practically (up to algorithm engineering). Although our focus is on NP-hard problems, we also include polynomial-time solvable problems in our considerations.

People at TU Berlin: Till Fluschnik; Head: Rolf Niedermeier

People at Novosibirsk State University: Oxana Tsidulko; Head: René van Bevern [4]

## MATE: Multivariate Algorithmics for Temporal Graph Problems

Funded by Deutsche Forschungsgemeinschaft (Project MATE, NI 369/17) started in February 2018.

Synopsis:

The focus of this project shall lie on temporal graphs: We are
given a fixed vertex set and discrete time steps such that at each
time step we may have another edge set. We aim to develop efficient
(parameterized) algorithms for some of the most central problems
related to temporal graphs. The topics we study herein are

•
community detection and clustering, in particular with respect to
their evolution over time,• routing problems on temporal graphs or
with temporal aspects,

• multi-layer graphs and preservation
problems.

We aim to fill a gap in the current literature by
concentrating mostly on exact combinatorial algorithms in the context
of parameterized complexity. That is, we study the influence of small
parameters on the complexity of our problems. To this end, we need to
extend the toolbox of parameterized algorithmics with new approaches
that deal with the temporal aspects of the given problems.

Using
problems from the above contexts in case studies, we aim to identify
key properties of temporal graphs that enable or hinder the
development of efficient algorithms. That is, we aim to identify
important parameters that exhibit the structure of temporal graphs and
we want to study the ways in which this structure can be exploited to
find efficient algorithms. In this way, we aim to contribute in equal
parts to the theory of temporal graphs as well as to practical
solutions for temporal graph problems.

People: Hendrik Molter, Malte Renken

Head: Rolf Niedermeier

## FPTinP: More Efficient Algorithms for Polynomial-Time Solvable Graph Problems

Funded by Deutsche Forschungsgemeinschaft (Project FPTinP, NI 369/16) started in December 2017.

Synopsis:

The central goal of this project is to extend the focus of
parametrized algorithmics from NP-hard problems to polynomial-time
solvable problems. This is motivated by the observation that
polynomial-time algorithms with cubic running times are for many
applications questionable at least; this is a fact that is
particularly obvious in the context of Big Data.

In contrast, an
algorithm with running in O(k^4 · n) time for some problem specific
parameter can be much more desirable provided that k is much smaller
than n in the application. Like in classical parameterized
algorithmics, we want to focus on graph problems with polynomial-time
algorithms using the rich arsenal of parameterized methods and
techniques developed so far.

People: Anne-Sophie Himmel

Head: Rolf Niedermeier

## AFFA: Algorithms for Fair Allocations

Funded by Deutsche Forschungsgemeinschaft (Project AFFA, NI 369/15 and BR5207/1) started in October 2016.

Synopsis:

The main focus of AFFA is the investigation of important computational problems in context of fair allocations with respect to their algorithmic tractability. The goals include basic problems such as the verification of the existence of fair allocations, finding the corresponding allocations, and the computational complexity of specific fixed protocols that find the allocations. Moreover, we want to analyze problems in context of manipulation, bribery, and external control. The underlying problems very often are NP-hard, which also motivates the application of parameterized, approximation, and heuristic approaches. In particular, we want to identify the limits of approximability in polynomial and FPT time. In addition, efficient reductions to established standard solving methods (like highly optimized SAT or ILP solvers) seem promising to find exact solutions for at least for some inputs. Finally, we also plan to test the developed algorithms with respect to their practical usefulness by implementations and experimental investigations and also want to make our software publicly available.

People: Andrzej Kaczmarczyk

Head: Rolf Niedermeier, Robert Bredereck

## DAMM: Data Reduction in Parameterized Algorithmics - New Models and Methods

Funded by Deutsche Forschungsgemeinschaft (Project DAMM, NI 369/13) started in December 2012.

Synopsis:

Preprocessing by means of data reduction rules is a common approach for the algorithmic treatment of combinatorially difficult and compute-intensive problems. Parameterized Algorithmics formalizes the concept of preprocessing in terms of problem kernels. So far, research mainly focussed on the size of the problem kernel and lacked a broader analysis of preprocessing. Thus, the goal of DAMM is to investigate different aspects of preprocessing taking into consideration other interesting properties of problem kernels, such as the running time for example. We also aim at developing kernelizations with respect to "non-standard" and "multivariate" parameterizations which could be of practical interest. Finally, we will consider different kernelization models that generalize the concept of problem kernels, such as Turing kernels, analyzing their relations and possible applications.

Head: Rolf Niedermeier

## DAPA: Data Driven Parameterized Algorithmics for Graph Modification Problems

Funded by Deutsche Forschungsgemeinschaft (Project DAPA, NI 369/12) started in January 2012.

Synopsis:

Problems from many different fields like biology, operations research and image processing can be modeled as graph modification problems in a simple and elegant fashion. The task is then to modify the structure of a given graph according to particular conditions. Allowed modifications are often as simple as adding edges or deleting vertices or edges. Unfortunately, most graph modification problems are NP-hard, that is, they presumably admit no efficient algorithms for finding the minimum number of modifications needed. However, there is hope for relevant and efficiently solvable special cases because of the following. First, there is often only a small number of modifications needed in practice. Second, the input graphs often obey structures that are specific to the application. Both these observations can be used to create "problem parameterizations" which can be exploited in the development of efficient parameterized algorithms. In this project, finding such parameterizations will be data driven, that is, promising parameterizations will be extracted from "real world" data. We focus on applications in the context of "data clustering" and "planning". Aside from theoretical analyses we will also provide implementations and empirical evaluation.

Head: Rolf Niedermeier

493