Exponential Time Approximation for Coloring 3-Colorable Graphs
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_ | 1866911929580126208 |
|---|---|
| author | Guruswami, Venkatesan Jain, Rhea |
| author_facet | Guruswami, Venkatesan Jain, Rhea |
| contents | The problem of efficiently coloring $3$-colorable graphs with few colors has received much attention on both the algorithmic and inapproximability fronts. We consider exponential time approximations, in which given a parameter $r$, we aim to develop an $r$-approximation algorithm with the best possible runtime, providing a tradeoff between runtime and approximation ratio. In this vein, an algorithm to $O(n^\varepsilon)$-color a 3-colorable graphs in time $2^{Θ(n^{1-2\varepsilon}\log(n))}$ is given in (Atserias and Dalmau, SODA 2022.)
We build on tools developed in (Bansal et al., Algorithmic, 2019) to obtain an algorithm to color $3$-colorable graphs with $O(r)$ colors in $\exp\left(\tilde{O}\left(\frac {n\log^{11/2}r} {r^3}\right)\right)$ time, asymptotically improving upon the bound given by Atserias and Dalmau. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_15563 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Exponential Time Approximation for Coloring 3-Colorable Graphs Guruswami, Venkatesan Jain, Rhea Data Structures and Algorithms Discrete Mathematics The problem of efficiently coloring $3$-colorable graphs with few colors has received much attention on both the algorithmic and inapproximability fronts. We consider exponential time approximations, in which given a parameter $r$, we aim to develop an $r$-approximation algorithm with the best possible runtime, providing a tradeoff between runtime and approximation ratio. In this vein, an algorithm to $O(n^\varepsilon)$-color a 3-colorable graphs in time $2^{Θ(n^{1-2\varepsilon}\log(n))}$ is given in (Atserias and Dalmau, SODA 2022.) We build on tools developed in (Bansal et al., Algorithmic, 2019) to obtain an algorithm to color $3$-colorable graphs with $O(r)$ colors in $\exp\left(\tilde{O}\left(\frac {n\log^{11/2}r} {r^3}\right)\right)$ time, asymptotically improving upon the bound given by Atserias and Dalmau. |
| title | Exponential Time Approximation for Coloring 3-Colorable Graphs |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2406.15563 |