2026-07-25T05:17:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11243 2024-03-06T10:47:47Z ddc:004 open_access

Approximation Algorithms for Partially Colorable Graphs Ghoshal, Suprovat Louis, Anand Raychaudhury, Rahul Approximation Algorithms Vertex Coloring Semi-random Models Graph coloring problems are a central topic of study in the theory of algorithms. We study the problem of partially coloring partially colorable graphs. For alpha <= 1 and k in Z^+, we say that a graph G=(V,E) is alpha-partially k-colorable, if there exists a subset S subset V of cardinality |S| >= alpha |V| such that the graph induced on S is k-colorable. Partial k-colorability is a more robust structural property of a graph than k-colorability. For graphs that arise in practice, partial k-colorability might be a better notion to use than k-colorability, since data arising in practice often contains various forms of noise. We give a polynomial time algorithm that takes as input a (1 - epsilon)-partially 3-colorable graph G and a constant gamma in [epsilon, 1/10], and colors a (1 - epsilon/gamma) fraction of the vertices using O~(n^{0.25 + O(gamma^{1/2})}) colors. We also study natural semi-random families of instances of partially 3-colorable graphs and partially 2-colorable graphs, and give stronger bi-criteria approximation guarantees for these family of instances. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Suprovat Ghoshal and Anand Louis and Rahul Raychaudhury 2019 Is Part Of LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2019.28 urn:nbn:de:0030-drops-112438 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.28 eng https://creativecommons.org/licenses/by/3.0/legalcode