2026-07-23T20:08:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23176 2025-10-02T12:42:00Z ddc:004 open_access

An 11/6-Approximation Algorithm for Vertex Cover on String Graphs Bonnet, Édouard Rzążewski, Paweł Approximation algorithms string graphs Vertex Cover Coloring odd girth 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, Panolan, Saurabh, Xue, and Zehavi [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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Édouard Bonnet and Paweł Rzążewski 2025 Is Part Of LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2025.24 urn:nbn:de:0030-drops-231764 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.24 eng https://creativecommons.org/licenses/by/4.0/legalcode