R. Ganian:

"Algorithmic Applications of Large Well-Structured Modulators";

Talk: Algorithmic Model Theory Meeting 2015 - ALMOTH 2015, Bayreuth, Deutschland (invited); 2015-02-26 - 2015-02-27.

A modulator of a graph G to a specified base class C is a set of vertices whose deletion puts G in C. The cardinality of a modulator to various tractable graph classes has long been used as a form of structure which can be exploited to obtain efficient algorithms for a range of important problems, and various popular notions such as vertex cover and feedback vertex set form special cases of modulators (see for instance the work of Fellows et al. or Fomin et al.). Here we investigate what happens when a graph contains a modulator to some tractable class 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 show that the parameters derived from such well-structured modulators are not only more general than the cardinality of modulators, but are in fact more general than rank-width itself. We provide an FPT algorithm for finding such well-structured modulators to any graph class which can be characterized by a finite set of obstructions. Aside from developing algorithms utilizing well-structured modulators for individual problems, we also show that well-structured modulators can be used for the efficient model checking of any Monadic Second Order sentence, as long as certain necessary conditions are met.

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