Algorithms and Complexity of Sandwich Problems in Graphs (extended abstract) Martin Charles Golumbic, Haim Kaplan and Ron Shamir Abstract: Given two graphs $G^1=(V,E^1)$ and $G=(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 belongs to a specified graph family? Such problems generalize recognition problems and arise in various applications. Concentrating mainly on subfamilies of perfect graphs, we give polynomial algorithms for several families and prove the NP-completeness of others.