The project mainly focuses on experimental evaluation of the recent theoretical developments in kernelization – a rigorous framework to analyse preprocessing routines. The experiments will be conducted in three main directions:
- LP-guided branching, see e.g. this recent result.
- Preprocessing in sparse graph classes, such as planar graphs and graphs of bounded expansion.
- Preprocessing using matroid tools, such as representative sets (see, e.g., this work).
Furthermore, the project includes theoretical research of selected aspects of Turing kernelization.
It is likely that a nonempty subset of the researchers involved in the project will participate in one of the next editions of Parameterized Algorithms and Computational Experiments Challenge.
The project is conducted with three international partners:
- Bart M.P. Jansen, Eindhoven University of Technology.
- Stefan Kratsch, University of Bonn.
- Magnus Wahlstrom, Royal Holloway University of London.
The project is funded in 100% from the European Union through the European Regional Development Fund, up to the amount of 597 866 PLN.