Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2020
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912730026344448 |
|---|---|
| author | Bonamy, Marthe Defrain, Oscar Micek, Piotr Nourine, Lhouari |
| author_facet | Bonamy, Marthe Defrain, Oscar Micek, Piotr Nourine, Lhouari |
| contents | Enumerating minimal transversals in a hypergraph is a notoriously hard problem. It can be reduced to enumerating minimal dominating sets in a graph, in fact even to enumerating minimal dominating sets in an incomparability graph. We provide an output-polynomial time algorithm for incomparability graphs whose underlying posets have bounded dimension. Through a different proof technique, we also provide an output-polynomial algorithm for their complements, i.e., for comparability graphs of bounded dimension posets.
Our algorithm for incomparability graphs is based on flashlight search and relies on the geometrical representation of incomparability graphs with bounded dimension, as given by Golumbic et al. in 1983. It runs with polynomial delay and only needs polynomial space. Our algorithm for comparability graphs is based on the flipping method introduced by Golovach et al. in 2015. It performs in incremental-polynomial time and requires exponential space.
In addition, we show how to improve the flipping method so that it requires only polynomial space. Since the flipping method is a key tool for the best known algorithms enumerating minimal dominating sets in a number of graph classes, this yields direct improvements on the state of the art. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2004_07214 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets Bonamy, Marthe Defrain, Oscar Micek, Piotr Nourine, Lhouari Discrete Mathematics Data Structures and Algorithms Combinatorics Enumerating minimal transversals in a hypergraph is a notoriously hard problem. It can be reduced to enumerating minimal dominating sets in a graph, in fact even to enumerating minimal dominating sets in an incomparability graph. We provide an output-polynomial time algorithm for incomparability graphs whose underlying posets have bounded dimension. Through a different proof technique, we also provide an output-polynomial algorithm for their complements, i.e., for comparability graphs of bounded dimension posets. Our algorithm for incomparability graphs is based on flashlight search and relies on the geometrical representation of incomparability graphs with bounded dimension, as given by Golumbic et al. in 1983. It runs with polynomial delay and only needs polynomial space. Our algorithm for comparability graphs is based on the flipping method introduced by Golovach et al. in 2015. It performs in incremental-polynomial time and requires exponential space. In addition, we show how to improve the flipping method so that it requires only polynomial space. Since the flipping method is a key tool for the best known algorithms enumerating minimal dominating sets in a number of graph classes, this yields direct improvements on the state of the art. |
| title | Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets |
| topic | Discrete Mathematics Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2004.07214 |