The {\em graph sandwich problem for property} $\Phi$ is defined as follows: Given two graphs $G_1 = (V,E_1)$ and $G_2 = (V,E_2)$ such that $E_1 \subseteq E_2$, is there a graph $G = (V,E)$ such that $E_1 \subseteq E \subseteq E_2$ which satisfies property $\Phi$? These problems generalize recognition problems and arise in various applications such as computational biology. Golumbic, Kaplan and Shamir studied several classes of graphs with respect to sandwich problems. A {\em homogeneous set} in a graph $G = (V,E)$, is a proper subset $H$ of vertices of $G$, with $|H| \geq 2$, such that each vertex of $V \setminus H$ is either adjacent to all vertices of $H$ or to none of the vertices of $H$. Homogeneous sets are used as a tool for decomposition in perfect graph theory. In this talk I will present a polynomial-time algorithm for solving the graph sandwich problem, when property $\Phi$ is to contain a homogeneous set. This is joint work with M\'arcia R. Cerioli, Celina M. H. de Figueiredo, and Sulamita Klein.