
arXiv: 2409.18820
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.
16 pages, 4 figures
Computational Geometry (cs.CG), FOS: Computer and information sciences, Discrete Mathematics (cs.DM), string graphs, 68W25, 05C15, 05C62, [MATH] Mathematics [math], [INFO] Computer Science [cs], Approximation algorithms, odd girth, Computer Science - Data Structures and Algorithms, Vertex Cover, FOS: Mathematics, Coloring, Computer Science - Computational Geometry, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), Combinatorics (math.CO), F.2.2, Computer Science - Discrete Mathematics, ddc: ddc:004
Computational Geometry (cs.CG), FOS: Computer and information sciences, Discrete Mathematics (cs.DM), string graphs, 68W25, 05C15, 05C62, [MATH] Mathematics [math], [INFO] Computer Science [cs], Approximation algorithms, odd girth, Computer Science - Data Structures and Algorithms, Vertex Cover, FOS: Mathematics, Coloring, Computer Science - Computational Geometry, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), Combinatorics (math.CO), F.2.2, Computer Science - Discrete Mathematics, ddc: ddc:004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
