Future networks based on virtualization will enable on-the-fly instantiation of services in the form of "network slices". In this talk we will focus on a fundamental resource allocation problem in this context, that of finding a minimum cost embedding of a network slice onto a graph representing the available resources of our architecture.