Cargando…
Solving Problems on Graphs of High Rank-Width
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 prob...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Springer US
2017
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6957011/ https://www.ncbi.nlm.nih.gov/pubmed/31997848 http://dx.doi.org/10.1007/s00453-017-0290-8 |
_version_ | 1783487246205190144 |
---|---|
author | Eiben, Eduard Ganian, Robert Szeider, Stefan |
author_facet | Eiben, Eduard Ganian, Robert Szeider, Stefan |
author_sort | Eiben, Eduard |
collection | PubMed |
description | 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. |
format | Online Article Text |
id | pubmed-6957011 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2017 |
publisher | Springer US |
record_format | MEDLINE/PubMed |
spelling | pubmed-69570112020-01-27 Solving Problems on Graphs of High Rank-Width Eiben, Eduard Ganian, Robert Szeider, Stefan Algorithmica Article 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. Springer US 2017-02-13 2018 /pmc/articles/PMC6957011/ /pubmed/31997848 http://dx.doi.org/10.1007/s00453-017-0290-8 Text en © The Author(s) 2017 Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. |
spellingShingle | Article Eiben, Eduard Ganian, Robert Szeider, Stefan Solving Problems on Graphs of High Rank-Width |
title | Solving Problems on Graphs of High
Rank-Width |
title_full | Solving Problems on Graphs of High
Rank-Width |
title_fullStr | Solving Problems on Graphs of High
Rank-Width |
title_full_unstemmed | Solving Problems on Graphs of High
Rank-Width |
title_short | Solving Problems on Graphs of High
Rank-Width |
title_sort | solving problems on graphs of high
rank-width |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6957011/ https://www.ncbi.nlm.nih.gov/pubmed/31997848 http://dx.doi.org/10.1007/s00453-017-0290-8 |
work_keys_str_mv | AT eibeneduard solvingproblemsongraphsofhighrankwidth AT ganianrobert solvingproblemsongraphsofhighrankwidth AT szeiderstefan solvingproblemsongraphsofhighrankwidth |