  We describe a rational approach to reduce the computational and communication
complexities of lossless point-to-point compression for computation with side
information. The traditional method relies on building a characteristic graph
with vertices representing the source symbols and with edges that assign a
source symbol to a collection of independent sets to be distinguished for the
exact recovery of the function. Our approach uses fractional coloring for a
b-fold coloring of characteristic graphs to provide a linear programming
relaxation to the traditional coloring method and achieves coding at a
fine-grained granularity. We derive the fundamental lower bound for
compression, given by the fractional characteristic graph entropy, through
generalizing the notion of K\"orner's graph entropy. We demonstrate the coding
gains of fractional coloring over traditional coloring via a computation
example. We conjecture that the integrality gap between fractional coloring and
traditional coloring approaches the smallest b that attains the fractional
chromatic number to losslessly represent the independent sets for a given
characteristic graph, up to a linear scaling which is a function of the
fractional chromatic number.
