Approximation Algorithms for Partially Colorable Graphs

Abstract

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 \le 1$ and $k\in {\mathbb{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|\ge \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 $\tilde{O}\left(n^{0.25+O({\gamma }^{1/2})}\right)$ 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.

25 Pages