E. Eiben, R. Ganian, S. Szeider:

"Solving Problems on Graphs of High Rank-Width";

Talk: Algorithms and Data Structures Symposium, Victoria, Canada; 2015-08-05 - 2015-08-07; in: "Proceedings of the 14th International Symposium on Algorithms and Data Structures", LNCS, 9214 (2015), ISBN: 978-3-319-21839-7; 314 - 326.

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 graph classes has long been used as a structural parameter

which can be exploited to obtain FPT algorithms 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 strictly more general than the cardinality of modulators

and rank-width itself. Then, we develop an FPT algorithm for finding

such well-structured modulators to any graph class which can be characterized

by a finite set of forbidden induced subgraphs. We proceed by

showing how well-structured modulators can be used to obtain efficient

parameterized algorithms for Minimum Vertex Cover and Maximum

Clique. Finally, we use the concept of well-structured modulators to

develop an algorithmic meta-theorem for efficiently 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.

http://publik.tuwien.ac.at/files/PubDat_247934.pdf

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