Publications in Scientific Journals:

E. Eiben, R. Ganian, S. Szeider:
"Solving Problems on Graphs of High Rank-Width";
Algorithmica (online), 80 (2017), 80; 30 pages.

English abstract:
A modulator in a graph is a vertex set whose deletion places the
considered graph into some specified graph class. The cardinality of a
modulator to various graph classes has long been used as a structural
parameter which can be exploited to obtain fixed-parameter 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 more powerful for
fixed-parameter algorithms than the cardinality of modulators and
rank-width itself. Then, we develop a fixed-parameter algorithm for
finding such well-structured modulators to every 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 deciding
problems expressible in monadic second order logic, and prove that
this result is tight in the sense that it cannot be generalized to
LinEMSO problems.

"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)

Electronic version of the publication:

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