Solving Problems on Graphs of High Rank-Width

J 2018

Solving Problems on Graphs of High Rank-Width

EIBEN, Eduard, Robert GANIAN a Stefan SZEIDER

Základní údaje

Originální název

Solving Problems on Graphs of High Rank-Width

Autoři

EIBEN, Eduard (703 Slovensko), Robert GANIAN (203 Česká republika, garant, domácí) a Stefan SZEIDER (40 Rakousko)

Vydání

Algorithmica, Springer, 2018, 0178-4617

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.882

Kód RIV

RIV/00216224:14330/18:00106821

Organizační jednotka

Fakulta informatiky

DOI

http://dx.doi.org/10.1007/s00453-017-0290-8

UT WoS

000424203700014

Klíčová slova anglicky

parameterized complexity; rank-width; modulators

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 3. 5. 2019 15:00, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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.

Návaznosti

MSM0021622419, záměr

Název: Vysoce paralelní a distribuované výpočetní systémy

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy

Citovat

EIBEN, Eduard, Robert GANIAN a Stefan SZEIDER. Solving Problems on Graphs of High Rank-Width. Algorithmica. Springer, 2018, roč. 80, č. 2, s. 742-771. ISSN 0178-4617. Dostupné z: https://dx.doi.org/10.1007/s00453-017-0290-8.

@article{1523844,
   author = {Eiben, Eduard and Ganian, Robert and Szeider, Stefan},
   article_number = {2},
   doi = {http://dx.doi.org/10.1007/s00453-017-0290-8},
   keywords = {parameterized complexity; rank-width; modulators},
   language = {eng},
   issn = {0178-4617},
   journal = {Algorithmica},
   title = {Solving Problems on Graphs of High Rank-Width},
   volume = {80},
   year = {2018}
}

TY  - JOUR
ID  - 1523844
AU  - Eiben, Eduard - Ganian, Robert - Szeider, Stefan
PY  - 2018
TI  - Solving Problems on Graphs of High Rank-Width
JF  - Algorithmica
VL  - 80
IS  - 2
SP  - 742-771
EP  - 742-771
PB  - Springer
SN  - 01784617
KW  - parameterized complexity
KW  - rank-width
KW  - modulators
N2  - 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.
ER  -

EIBEN, Eduard, Robert GANIAN a Stefan SZEIDER. Solving Problems on Graphs of High Rank-Width. \textit{Algorithmica}. Springer, 2018, roč.~80, č.~2, s.~742-771. ISSN~0178-4617. Dostupné z: https://dx.doi.org/10.1007/s00453-017-0290-8.

Podrobný výpis o publikaci