Computing the forcing spectrum of outerplanar graphs in polynomial time
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916111174336512 |
|---|---|
| author | Gorsky, Maximilian Kreßin, Fabian |
| author_facet | Gorsky, Maximilian Kreßin, Fabian |
| contents | The forcing number of a graph with a perfect matching $M$ is the minimum number of edges in $M$ whose endpoints need to be deleted, such that the remaining graph only has a single perfect matching. This number is of great interest in theoretical chemistry, since it conveys information about the structural properties of several interesting molecules. On the other hand, in bipartite graphs the forcing number corresponds to the famous feedback vertex set problem in digraphs.
Determining the complexity of finding the smallest forcing number of a given planar graph is still a widely open and important question in this area, originally proposed by Afshani, Hatami, and Mahmoodian in 2004. We take a first step towards the resolution of this question by providing an algorithm that determines the set of all possible forcing numbers of an outerplanar graph in polynomial time. This is the first polynomial-time algorithm concerning this problem for a class of graphs of comparable or greater generality. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_17704 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computing the forcing spectrum of outerplanar graphs in polynomial time Gorsky, Maximilian Kreßin, Fabian Discrete Mathematics Combinatorics 05C85, 05C70, 05C90, 05C92, 92E10, 68R10, 05C10, 05C45 G.2.2; F.2.2; J.2 The forcing number of a graph with a perfect matching $M$ is the minimum number of edges in $M$ whose endpoints need to be deleted, such that the remaining graph only has a single perfect matching. This number is of great interest in theoretical chemistry, since it conveys information about the structural properties of several interesting molecules. On the other hand, in bipartite graphs the forcing number corresponds to the famous feedback vertex set problem in digraphs. Determining the complexity of finding the smallest forcing number of a given planar graph is still a widely open and important question in this area, originally proposed by Afshani, Hatami, and Mahmoodian in 2004. We take a first step towards the resolution of this question by providing an algorithm that determines the set of all possible forcing numbers of an outerplanar graph in polynomial time. This is the first polynomial-time algorithm concerning this problem for a class of graphs of comparable or greater generality. |
| title | Computing the forcing spectrum of outerplanar graphs in polynomial time |
| topic | Discrete Mathematics Combinatorics 05C85, 05C70, 05C90, 05C92, 92E10, 68R10, 05C10, 05C45 G.2.2; F.2.2; J.2 |
| url | https://arxiv.org/abs/2401.17704 |