Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2409.18820 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917788739698688 |
|---|---|
| author | Bonnet, Édouard Rzążewski, Paweł |
| author_facet | Bonnet, Édouard Rzążewski, Paweł |
| contents | We present a 1.8334-approximation algorithm for Vertex Cover on string graphs given with a representation, which takes polynomial time in the size of the representation; the exact approximation factor is $11/6$. Recently, the barrier of 2 was broken by Lokshtanov et al. [SoGC '24] with a 1.9999-approximation algorithm. Thus we increase by three orders of magnitude the distance of the approximation ratio to the trivial bound of 2. Our algorithm is very simple. The intricacies reside in its analysis, where we mainly establish that string graphs without odd cycles of length at most 11 are 8-colorable. Previously, Chudnovsky, Scott, and Seymour [JCTB '21] showed that string graphs without odd cycles of length at most 7 are 80-colorable, and string graphs without odd cycles of length at most 5 have bounded chromatic number. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_18820 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An $11/6$-Approximation Algorithm for Vertex Cover on String Graphs Bonnet, Édouard Rzążewski, Paweł Data Structures and Algorithms Computational Geometry Discrete Mathematics Combinatorics 68W25, 05C15, 05C62 F.2.2 We present a 1.8334-approximation algorithm for Vertex Cover on string graphs given with a representation, which takes polynomial time in the size of the representation; the exact approximation factor is $11/6$. Recently, the barrier of 2 was broken by Lokshtanov et al. [SoGC '24] with a 1.9999-approximation algorithm. Thus we increase by three orders of magnitude the distance of the approximation ratio to the trivial bound of 2. Our algorithm is very simple. The intricacies reside in its analysis, where we mainly establish that string graphs without odd cycles of length at most 11 are 8-colorable. Previously, Chudnovsky, Scott, and Seymour [JCTB '21] showed that string graphs without odd cycles of length at most 7 are 80-colorable, and string graphs without odd cycles of length at most 5 have bounded chromatic number. |
| title | An $11/6$-Approximation Algorithm for Vertex Cover on String Graphs |
| topic | Data Structures and Algorithms Computational Geometry Discrete Mathematics Combinatorics 68W25, 05C15, 05C62 F.2.2 |
| url | https://arxiv.org/abs/2409.18820 |