Structural Parameterizations of Vertex Integrity
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916462574174208 |
|---|---|
| author | Gima, Tatsuya Hanaka, Tesshu Kobayashi, Yasuaki Murai, Ryota Ono, Hirotaka Otachi, Yota |
| author_facet | Gima, Tatsuya Hanaka, Tesshu Kobayashi, Yasuaki Murai, Ryota Ono, Hirotaka Otachi, Yota |
| contents | The graph parameter vertex integrity measures how vulnerable a graph is to a removal of a small number of vertices. More precisely, a graph with small vertex integrity admits a small number of vertex removals to make the remaining connected components small. In this paper, we initiate a systematic study of structural parameterizations of the problem of computing the unweighted/weighted vertex integrity. As structural graph parameters, we consider well-known parameters such as clique-width, treewidth, pathwidth, treedepth, modular-width, neighborhood diversity, twin cover number, and cluster vertex deletion number. We show several positive and negative results and present sharp complexity contrasts. We also show that the vertex integrity can be approximated within an $\mathcal{O}(\log \mathsf{opt})$ factor. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_05892 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Structural Parameterizations of Vertex Integrity Gima, Tatsuya Hanaka, Tesshu Kobayashi, Yasuaki Murai, Ryota Ono, Hirotaka Otachi, Yota Data Structures and Algorithms The graph parameter vertex integrity measures how vulnerable a graph is to a removal of a small number of vertices. More precisely, a graph with small vertex integrity admits a small number of vertex removals to make the remaining connected components small. In this paper, we initiate a systematic study of structural parameterizations of the problem of computing the unweighted/weighted vertex integrity. As structural graph parameters, we consider well-known parameters such as clique-width, treewidth, pathwidth, treedepth, modular-width, neighborhood diversity, twin cover number, and cluster vertex deletion number. We show several positive and negative results and present sharp complexity contrasts. We also show that the vertex integrity can be approximated within an $\mathcal{O}(\log \mathsf{opt})$ factor. |
| title | Structural Parameterizations of Vertex Integrity |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2311.05892 |