  Polaron formation plays a major role in determining the structural,
electrical and chemical properties of ionic crystals. Using a combination of
first principles calculations and scanning tunneling microscpoy/atomic force
microscopy (STM/AFM), we analyze the interaction of polarons with CO molecules
adsorbed on the rutile TiO$_2$(110) surface. Adsorbed CO shows attractive
coupling with polarons in the surface layer, and repulsive interaction with
polarons in the subsurface layer. As a result, CO adsorption depends on the
reduction state of the sample. For slightly reduced surfaces, many adsorption
configurations with comparable adsorption energies exist and polarons reside in
the subsurface layer. At strongly reduced surfaces, two adsorption
configurations dominante: either inside an oxygen vacancy, or at surface
Ti$_{5c}$ sites, coupled with a surface polaron.
