  We study the zero-error source coding problem in which an encoder with Side
Information (SI) $g(Y)$ transmits source symbols $X$ to a decoder. The decoder
has SI $Y$ and wants to recover $f(X,Y)$ where $f,g$ are deterministic. We
exhibit a condition on the source distribution and $g$ that we call "pairwise
shared side information", such that the optimal rate has a single-letter
expression. This condition is satisfied if every pair of source symbols "share"
at least one SI symbol for all output of $g$. It has a practical
interpretation, as $Y$ models a request made by the encoder on an image $X$,
and $g(Y)$ corresponds to the type of request. It also has a graph-theoretical
interpretation: under "pairwise shared side information" the characteristic
graph can be written as a disjoint union of OR products. In the case where the
source distribution is full-support, we provide an analytic expression for the
optimal rate. We develop an example under "pairwise shared side information",
and we show that the optimal coding scheme outperforms several strategies from
the literature.
