  Many resource allocation problems in the cloud can be described as a basic
Virtual Network Embedding Problem (VNEP): finding mappings of request graphs
(describing the workloads) onto a substrate graph (describing the physical
infrastructure). In the offline setting, the two natural objectives are profit
maximization, i.e., embedding a maximal number of request graphs subject to the
resource constraints, and cost minimization, i.e., embedding all requests at
minimal overall cost. The VNEP can be seen as a generalization of classic
routing and call admission problems, in which requests are arbitrary graphs
whose communication endpoints are not fixed. Due to its applications, the
problem has been studied intensively in the networking community. However, the
underlying algorithmic problem is hardly understood.
  This paper presents the first fixed-parameter tractable approximation
algorithms for the VNEP. Our algorithms are based on randomized rounding. Due
to the flexible mapping options and the arbitrary request graph topologies, we
show that a novel linear program formulation is required. Only using this novel
formulation the computation of convex combinations of valid mappings is
enabled, as the formulation needs to account for the structure of the request
graphs. Accordingly, to capture the structure of request graphs, we introduce
the graph-theoretic notion of extraction orders and extraction width and show
that our algorithms have exponential runtime in the request graphs' maximal
width. Hence, for request graphs of fixed extraction width, we obtain the first
polynomial-time approximations.
  Studying the new notion of extraction orders we show that (i) computing
extraction orders of minimal width is NP-hard and (ii) that computing
decomposable LP solutions is in general NP-hard, even when restricting request
graphs to planar ones.
