Technical Reports
HPL-2010-177
Click here for full text:
Flexible Coloring
Xiaozhou (Steve) Li, Atri Rudra, Ram Swaminathan
HP Laboratories
HPL-2010-177
Keyword(s): graph coloring; hardness of approximation
Abstract: Motivated by reliability considerations in data deduplication for storage systems, we introduce the problem of flexible coloring. Given a hypergraph H and the number of allowable colors k, a flexible coloring of H is an assignment of one or more colors to each vertex such that, for each hyperedge, it is possible to choose a color from each vertex's color list so that this hyperedge is strongly colored (i.e., each vertex has a different color). Different colors for the same vertex can be chosen for different incident hyperedges (hence the term flexible). The goal is to minimize color consumption, namely, the total number of colors assigned, counting multiplicities. Flexible coloring is NP-hard and trivially 
approximable, where s is the size of the largest hyperedge, and n is the number of vertices. Using a recent result by Bansal and Khot, we show that if k is constant, then it is UGC-hard to approximate to within a factor of s - ε, for arbitrarily small constant ε > 0. Lastly, we present an algorithm with an 
appr oximation ratio, where k' is number of colors used by a strong coloring a lgorithm for H.
5 Pages
Additional Publication Information: to be published in Information ProcessLetters.
External Posting Date: March 11, 2011 [Fulltext]. Approved for External Publication
Internal Posting Date: March 11, 2011 [Fulltext]