R. Ganian:

"Well-Structured Modulators: FPT Algorithms and Kernels";

Talk: Workshop on Graph Classes, Optimization, and Width Parameters (GROW), Aussois, France (invited); 2015-10-11 - 2015-10-15.

A modulator of a graph G to a specified graph class H is a set of vertices whose deletion puts G into H. The cardinality of a modulator to various tractable graph classes has long been used as a structural parameter which can be exploited to obtain both FPT algorithms and polynomial kernels for a range of hard problems. Here we investigate what happens when a graph contains a modulator which is large but "well-structured" (in the sense of having bounded rank-width). Can such modulators still be exploited to obtain efficient algorithms? And is it even possible to find such modulators efficiently? We first show that the parameters derived from such well-structured modulators are more general (and hence applicable on broader graph classes) than modulators as well as other established parameters used for kernelization and fixed parameter tractability. Then, we develop algorithms for finding such well-structured modulators to a range of graph classes. Finally, we use the concept of well-structured modulators to develop algorithmic meta-theorems for deciding problems expressible in Monadic Second Order (MSO) logic, and prove that this result is tight in the sense that it cannot be generalized to LinEMSO problems.

Created from the Publication Database of the Vienna University of Technology.