Vertex Cover in Graphs with Locally Few Colors

In [13], Erdős et al. defined the local chromatic number of a graph as the minimum number of colors that must appear within distance 1 of a vertex. For any Δ ≥ 2, there are graphs with arbitrarily large chromatic number that can be colored so that (i) no vertex neighborhood contains more than Δ different colors (

bounded local colorability

), and (ii) adjacent vertices from two color classes induce a complete bipartite graph (

biclique coloring

).

We investigate the weighted vertex cover problem in graphs when a locally bounded coloring is given. This generalizes the vertex cover problem in bounded degree graphs to a class of graphs with arbitrarily large chromatic number. Assuming the Unique Game Conjecture, we provide a tight characterization. We prove that it is UGC-hard to improve the approximation ratio of 2 − 2/(Δ + 1) if the given local coloring is not a biclique coloring. A matching upper bound is also provided. Vice versa, when properties (i) and (ii) hold, we present a randomized algorithm with approximation ratio of

$2- \Omega(1)\frac{\ln \ln \Delta}{\ln \Delta}$

. This matches known inapproximability results for the special case of bounded degree graphs.

Moreover, we show that the obtained result finds a natural application in a classical scheduling problem, namely the precedence constrained single machine scheduling problem to minimize the total weighted completion time. In a series of recent papers it was established that this scheduling problem is a special case of the minimum weighted vertex cover in graphs

G

P

of incomparable pairs defined in the dimension theory of partial orders. We show that

G

P

satisfies properties (i) and (ii) where Δ − 1 is the maximum number of predecessors (or successors) of each job.