Aspects of Preprocessing

This work considers multiple aspects of efficient (that is, polynomial-time executable) preprocessing for NP-hard problems in the context of parameterized complexity theory. Special emphasis is put on the following topics: Non-standard parameterization, linear-time kernelization, preprocessing beyond kernelization, and parallelizable Turing kernelization. All these topics are practically relevant and, pioneering work on parallelizable Turing kernelizations, the final topic is of special theoretical interest.