Switching Classes: Characterization and Computation
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_ | 1866909286857179136 |
|---|---|
| author | Antony, Dhanyamol Cao, Yixin Pal, Sagartanu Sandeep, R. B. |
| author_facet | Antony, Dhanyamol Cao, Yixin Pal, Sagartanu Sandeep, R. B. |
| contents | In a graph, the switching operation reverses adjacencies between a subset of vertices and the others. For a hereditary graph class $\mathcal{G}$, we are concerned with the maximum subclass and the minimum superclass of $\mathcal{G}$ that are closed under switching. We characterize the maximum subclass for many important classes $\mathcal{G}$, and prove that it is finite when $\mathcal{G}$ is minor-closed and omits at least one graph. For several graph classes, we develop polynomial-time algorithms to recognize the minimum superclass. We also show that the recognition of the superclass is NP-complete for $H$-free graphs when $H$ is a sufficiently long path or cycle, and it cannot be solved in subexponential time assuming the Exponential Time Hypothesis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_04263 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Switching Classes: Characterization and Computation Antony, Dhanyamol Cao, Yixin Pal, Sagartanu Sandeep, R. B. Data Structures and Algorithms Combinatorics In a graph, the switching operation reverses adjacencies between a subset of vertices and the others. For a hereditary graph class $\mathcal{G}$, we are concerned with the maximum subclass and the minimum superclass of $\mathcal{G}$ that are closed under switching. We characterize the maximum subclass for many important classes $\mathcal{G}$, and prove that it is finite when $\mathcal{G}$ is minor-closed and omits at least one graph. For several graph classes, we develop polynomial-time algorithms to recognize the minimum superclass. We also show that the recognition of the superclass is NP-complete for $H$-free graphs when $H$ is a sufficiently long path or cycle, and it cannot be solved in subexponential time assuming the Exponential Time Hypothesis. |
| title | Switching Classes: Characterization and Computation |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2403.04263 |