Approximation Algorithms for Partially Colorable Graphs
share
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 α≤ 1 and k ∈Z^+, we say that a graph G=(V,E) is α-partially k-colorable, if there exists a subset S⊂ V of cardinality |S | ≥α | 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 - ϵ)-partially 3-colorable graph G and a constant γ∈ [ϵ, 1/10], and colors a (1 - ϵ/γ) fraction of the vertices using Õ(n^0.25 + O(γ^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.
READ FULL TEXT