{'fraction_non_alphanumeric': 0.0476608278757873, 'fraction_numerical': 0.008209820449346662, 'mean_word_length': 3.8255084297270736, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 22, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 25, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
(FPT-)Approximation Algorithms for the Virtual Network Embedding Problem

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.


Introduction
At the heart of the cloud computing paradigm lies the idea of efficient resource sharing: due to virtualization, multiple workloads can co-habit and use a given resource infrastructure simultaneously. Indeed, cloud computing introduces great flexibilities in terms of where workloads can be mapped and accordingly where resources are allocated. At the same time, exploiting this mapping flexibility poses a fundamental algorithmic challenge. The underlying algorithmic problem is essentially a graph theoretical one: both the workload as well as the infrastructure can be modeled as graphs. The former, the so-called request graph, describes the resource requirements both on the nodes (e.g., the virtual machines) as well as on the interconnecting network. The latter, the so-called substrate graph, describes the physical infrastructure and its resources (servers and links).
The problem is known in the networking community under the name Virtual Network Embedding Problem (VNEP) and has been studied intensively in recent years [8,13]. The  Figure 1 Examples for virtual networks (i.e., request graphs). Left: A service chain envisioned in 5G networks [19]. Right: a virtual cluster abstraction envisioned in batch processing applications [3].
problem arises in many settings, and is also studied in the realm of embedding service chains [16,22] and virtual clusters [25].
The online variant in which a minimal cost embedding for a single request is sought after is most prominently studied in the literature. In this work, we study the offline generalization in which multiple requests are given and the objective is to either maximize the profit by selecting a maximal subset of requests to embed or to minimize the cumulative embedding costs. Thus, the offline cost minimization variant reduces to the online problem when considering only a single request.
The design of approximation algorithms for the Virtual Network Embedding Problem has been an open problem for over a decade [8].

Incarnations of the VNEP in Practice
To highlight the practical relevance of the VNEP, we present two examples in Figure 1. On the left, a service chain is depicted, which composes existing network functions (such as a cache, a proxy, or a firewall) into a more advanced network service. The virtualization of network functions enables the faster and more flexible allocation in provider networks [30]. Concretely, the depicted example is envisioned in the context of mobile operators [19]: loadbalancers (LB 1 ,LB 2 ) are used to route (parts) of the traffic through a cache to optimize the user experience, the firewall (FW) is used to provide security and the network-address translation (NAT) function is used to provide private IP addresses to the customers.
Depicted on the right of Figure 1 is a virtual cluster, which was proposed as an abstraction for batch processing applications in the cloud [3]. Concretely, a virtual cluster consists of a set of virtual machines (VMs) and a single logical switch which connects all virtual machines. As originally proposed, all virtual machines and all links have the same computational and bandwidth demands, respectively. The abstraction is attractive due to its simplicity: users only need to specify three numbers, namely the number of VMs together with their uniform demands and the bandwidth to the logical switch.

Problem Statement
Given is a physical network G S = (V S , E S ) offering a set T of computational types. We refer to the physical network as the substrate network. For a type τ ∈ T , the set V τ S ⊆ V S denotes the substrate nodes that can host functionality of the type τ . Denoting the node resources by R V S = {(τ, u) |τ ∈ T , u ∈ V τ S } and all substrate resources by R S = R V S ∪ E S , the capacity of nodes and edges is denoted by d S (x, y) > 0 for (x, y) ∈ R S .
The set of request is denoted by R. For each request r ∈ R, a directed graph G r = (V r , E r ) is given. We refer to the nodes of these graphs as virtual or request nodes and to the edges as virtual or request edges. The type of a virtual node is given via the function τ r : V r → T . We allow for node and edge mapping restrictions. Concretely, we assume that the mapping of a virtual node i ∈ V r is restricted to a set V r,i S ⊆ V τr(i) S , while the mapping of a virtual edge (i, j) is restricted to a set E r,i,j S ⊆ E S . Each virtual node i ∈ V r and each edge (i, j) ∈ E r is attributed with a resource demand d r (i) ≥ 0 and d r (i, j) ≥ 0, respectively. Virtual nodes and edges can only be mapped on substrate nodes and edges of sufficient capacity and we have V r,i S ⊆ {u ∈ V τr(i) S |d S (u) ≥ d r (i)} and E r,i,j S ⊆ {(u, v) ∈ E S |d S (u, v) ≥ d r (i, j)}. We denote by d max (r, x, y) the maximal demand that a request r may impose on a resource (x, y) ∈ R S , i.e. d max (r, τ, u) = max i∈Vr:u∈V r,i S d r (i) for (τ, u) ∈ R V S and d max (r, u, v) = max (i,j)∈Er:(u,v)∈E r,i,j S d r (i, j) for (u, v) ∈ E S . The mapping of a request onto the substrate graph is captured by the following definition.

Definition 1 (Valid Mapping).
A valid mapping m r of request r ∈ R is a tuple (m V r , m E r ) of functions m V r : V r → V S and m E r : E r → P(E S ), such that the following conditions hold: Virtual nodes are mapped to allowed substrate nodes: m V r (i) ∈ V r,i S holds for all i ∈ V r . The mapping m E r (i, j) of virtual edge (i, j) ∈ E r is a path connecting m V r (i) to m V r (j), which only uses allowed edges, i.e., m E r (i, j) ⊆ P(E r,i,j S ) holds.
We denote by M r the set of all valid mappings of request r ∈ R.
Note that the edge mapping m E r (i, j) may be empty, iff. m V r (i) = m V r (j) holds for edges (i, j) ∈ E r . Next, we introduce the notion of allocations induced by a valid mapping.
Definition 2 (Allocations of a Valid Mapping). The allocation A(m r , x, y) induced by mapping m r on resource (x, y) ∈ R S is defined as follows: A(m r , τ, u) = i∈Vr,τ (i)=τ,m V r (i)=u d r (i) holds for (τ, u) ∈ R V S and A(m r , u, v) = (i,j)∈Er,(u,v)∈m E r (i,j) d r (i, j) holds for (u, v) ∈ E S , respectively. The maximal allocation that a valid mapping of request r may impose on a substrate resource (x, y) ∈ R S is denoted by A max (r, x, y) = max m k r ∈Mr A(m r , x, y). Given a collection of valid mappings {m r } r∈R for a subset of requests R ⊆ R, we refer to this collection as feasible if the cumulative allocations obey substrate capacities, i.e., r∈R A(m r , x, y) ≤ d S (x, y) holds for all resources (x, y) ∈ R S . Definition 3 (Virtual Network Embedding Problem). The profit variant of the Virtual Network Embedding Problem (VNEP) asks for finding a feasible collection {m r } r∈R of mappings while maximizing the overall profit r∈R b r , where b r > 0 denotes the benefit obtained for embedding request r. For the cost variant all of the given requests R must be feasibly embedded while minimizing the resource costs (x,y)∈R S c S (x, y) · r∈R A(m r , x, y), where c S (x, y) ≥ 0 denotes the resource cost of (x, y) ∈ R S .
The VNEP can be expressed as the non-polynomial sized Formulation 1, which explicitly enumerates all valid mappings: for each request r ∈ R and each mapping m k r ∈ M r a variable f k r is introduced. Setting f k r ∈ {0, 1} yields integer programs and setting f k r ∈ [0, 1] yields the respective linear programs. We refer to the problem over the linear variables, in which convex combinations of valid mappings are allowed, as the fractional VNEP. The Virtual Network Embedding Problem is known to be strongly N P-hard [27].

Putting the VNEP Into Perspective
The VNEP can be seen as a generalization of many well-studied problems. The profit variant is e.g. related to routing requests [2,6] and virtual circuits [1,20], and the unsplittable flow problem [4], while the cost variant is related to the shortest k-disjoint paths problem [7,24], and the subgraph isomorphism problem [10]. The most notable differences to the aforementioned problems are (i) that request node locations are not fixed a priori and that (ii) a single request represents a graph instead of e.g. a single link as in the unsplittable flow problem. Accordingly, the key challenge we face when designing approximation algorithms, is that virtual nodes can in principle be mapped on any substrate node and each virtual edge may traverse any substrate edge.

Our Results and Techniques
In this paper we set out to initiate the study of approximation algorithms for the VNEP for arbitrary request graphs. Leverging the VNEP's connection to multi-commodity flow problems, we employ randomized rounding to obtain our results. This technique has proven both simple and effective: given an Integer Program (IP) for a problem, solutions of its Linear Program (LP) are decomposed into convex combinations (cf. Formulation 1) and then rounded according to their weight.
While in many contexts the natural LP, obtained by relaxing the corresponding integer program, is sufficiently strong to extract convex combinations of solutions, this is not the case for the VNEP. As the mapping of flow endpoints is flexible in the VNEP, we prove that the natural Multi-Commodity Flow (MCF) formulation for the VNEP fails to ensure the decomposability into convex combinations. In fact, it fails to capture the structure of valid mappings and we prove that the MCF formulation's integrality gap is unbounded.
Analyzing the shortcomings of the MCF formulation, we obtain sufficient conditions to ensure decomposability. Accordingly, we develop a novel LP formulation for the VNEP which incorporates the requests' individual structure. The dependency of our formulation on the underlying request graphs comes at the price that the size of the formulation grows exponentially in the 'complexity' of the request graphs. Our formulation relies on acyclic (re-)orientations of request graphs called extraction orders to guide the process of extracting valid mappings. Based on confluences in these extraction orders, i.e. disjoint paths, we introduce the notion of extraction width. In turn, we show that the size of our LP formulation, and hence also the runtime of our approximations, are fixed-parameter tractable (FPT) in the extraction width of the given extraction orders.
Hence, finding efficient approximations boils down to finding extraction orders of small width. Our initial results are quite intriguing: we show that depending on the chosen extraction order the width can differ by a factor of Ω(|G r |) (which is maximal) and that finding the minimal extraction width is itself N P-hard. While this may raise questions about the sensibility of our graph-theoretic notions, we also show that there cannot exist any polynomial-time algorithm (neither linear nor combinatorial) that can solve the fractional VNEP (even when restricting the requests to planar graphs).
Having set out to obtain approximations for the VNEP, we eventually derive the first (FPT-)approximations for the profit and cost variants of the VNEP for arbitrary request graphs by using our novel LP formulation. The presented approximations provide constant approximation guarantees for the cost and the profit while exceeding resource capacities by a factor of O(1 + ε · 2 · ∆(R S ) · log |V S |), where ε ≤ 1 is the ratio of maximal demand to minimal capacity and ∆(R S ) = max (x,y)∈R S r∈R Amax(r,x,y) dmax(r,x,y) 2 captures the (sum of squared) ratios of the maximal cumulative allocation divided by the maximal allocation.

Related Work
In the last decade, the VNEP has attracted much attention due to its numerous applications. A survey from 2013 lists more than 80 different algorithms for its many variations [13]. A large fraction of the existing literature considers heuristics without giving approximation guarantees [8,31]. Other works proposed exact methods as integer or constraint programming, coming at the cost of an exponential runtime [21,29].
In contrast, we initiate the study of (FPT-)approximation algorithms for the VNEP with provable approximation guarantees for arbitrary substrate and request graphs. The works closest to ours are by Even et al. [11,12] and Bansal et al. [5]. Even et al. studied approximation algorithms and competitive online algorithms for the embedding of request chains. Bansal et al. consider the setting of embedding tree request graphs under the objective to minimize the maximum load and also provide approximations and competitive online algorithms. Their main result is a n O(d) time O(d 2 log (nd))-approximation algorithm for the embedding of a single tree of depth d on a substrate with n nodes, which is based on a strong LP relaxation inspired by the Sherali-Adams hierarchy. By considering only tree requests, Bansal et al. do not address the problem of computing valid mappings for request graphs containing cycles. However, and importantly, the approach of Bansal et al. is complementary to ours and may hence potentially be combined with our results in the future to obtain stronger approximations and also derive competitive online algorithms. Bibliographic Note. This work significantly extends the authors' previous technical report [26] as well as the publication [28], which only consider approximation algorithms for cactus request graphs and are hence not applicable for arbitrary request graphs.

Organization
The remainder of this paper is organized as follows. Section 2 studies the classic multicommodity flow formulation and shows its limitations. In Section 3 we present our decomposable LP formulation and introduce graph-theoretic notions as extraction confluences and extraction width. In Section 4 we present our FPT-approximations for the VNEP. In Section 5 we shortly study properties of the novel extraction width concept and show that cactus request graphs have a constant extraction width. We conclude our paper in Section 6.

Limitations of Classic Multi-Commodity Formulations for VNEP
In this section, we study the Multi-Commodity Flow (MCF) formulation for solving the VNEP (see Formulation 2), which is widely used [8,17,27,29]. We first show the positive result that the formulation is sufficiently strong to compute solutions to the fractional VNEP when requests are trees. Subsequently, we show that the formulation fails to allow for the decomposition of cyclic request graphs into convex combinations of valid mappings.

The Multi-Commodity Formulation
We explain the formulation by considering its integer variant. The variable x r ∈ {0, 1} indicates whether request r ∈ R is embedded or not. The variable y u r,i ∈ {0, 1} indicates whether virtual node i ∈ V r is mapped on substrate node u. Similarly, the flow variable z u,v r,i,j ∈ {0, 1} indicates whether the substrate edge (u, v) ∈ E S is part of the path of the virtual edge (i, j) ∈ E r . The variable a x,y r ≥ 0 denotes the cumulative allocations that the embedding of request r induces on resource (x, y) ∈ R S . By Constraints 6 and Constraint 7, virtual nodes are only mapped on suitable substrate nodes when x r = 1 holds. Constraint 8 induces an unsplittable unit flow for each virtual edge (i, j) ∈ E r from the substrate location onto which i was mapped to the substrate location onto which j was mapped. By Constraint 9 the mapping of virtual edges may only consist of allowed substrate edges. Constraints 10 and 11 compute the cumulative allocations while Constraint 12 enforces that resource capacities are respected. Applying the objective max r∈R b r · x r the profit variant is obtained. Setting min (x,y)∈R S ,r∈R c S (x, y) · a x,y r and enforcing x r = 1 for all requests r ∈ R the cost variant is obtained.
The LP formulation is obtained by relaxing the domain of the above introduced binary variables to [0, 1]. The following lemma states that whenever a virtual node i ∈ V r is (fractionally) mapped on a certain substrate node, suitable mappings for all incident edges and their endpoints can be found.

Lemma 4 (Local Connectivity Property of the MCF Formulation).
Consider a fractional solution (x r , y r , z r , a r ) to the LP Formulation 2 for request r ∈ R. If y u r,i > 0 holds for i ∈ V r and u ∈ V r,i S , then for incoming edges (k, i) ∈ E r and outgoing edges (i, j) ∈ E r there exist substrate paths P v,u r,k,i and P u,w r,i,j , such that: 1. P v,u r,k,i is a path from v to u, such that y v r,k > 0 and z e r,k,i > 0 holds for e ∈ P v,u r,k,i . 2. P u,w r,i,j is a path from u to w, such that y w r,j > 0 and z e r,i,j > 0 holds for e ∈ P u,w r,i,j .
The respective paths P v,u r,k,i and P u,w r,i,j can be found in time O(|E S |) by a simple graph search.
Proof. Fix any substrate node u ∈ V S for which y u r,i > 0 holds. We first consider the outgoing edges (i, j) ∈ E r . By Constraint 6, u∈V r,i S y u r,i = v∈V r,j S y v r,j holds. Hence, the virtual node j ∈ V r must be mapped also at least with value y u r,i . If j is also partially mapped on u, i.e., if y u r,j > 0 holds, then the result follows directly, as u connects to u using (and allowing) the empty path P u,u r,i,j = . If, on the other hand, y u r,j = 0 holds, then Constraint 8 induces an flow of value y u r,i at substrate node u with respect to the commodity z r,i,j . As the right hand side of Constraint 8 may only attain negative values at nodes w ∈ V r,j S for which y w r,j > 0 holds, the flow (of commodity z r,i,j ) emitted at node u must eventually reach a node w ∈ V r,j S with y w r,j > 0 and hence the result follows for any outgoing edge (i, j) ∈ E r . Note that the corresponding path P u,w r,i,j can be constructed in time O(|E S |) by a simple breadth-first search, which only considers edges (u , v ) ∈ E S for which z u ,v r,i,j > 0 holds. The argument for incoming edges (k, i) ∈ E r is the same and the respective paths P v,u r,k,i can be recovered by breadth-first searches traversing substrate edges (u, v) ∈ E S in their opposite direction when z u,v r,k,i > 0 holds.

Decomposing Solutions to the MCF Formulation
Given the connectivity property of Lemma 4, we argue how solutions to the LP relaxation of the MCF formulation can be decomposed into convex combinations D r = {(f k r , m k r )} k (cf. LP Formulation 1) as long as the request graphs are trees. The ideas presented henceforth will also apply for the decomposition of our novel formulation presented in Section 3.
We naturally apply the idea of Ford and Fulkerson [14] for decomposing s − t flows into paths to our setting. Given a LP solution (x r , y r , z r , a r ) for request r ∈ R, we need to find a valid mapping m r = (m V r , m E r ) ∈ M r which is covered by the embedding variables.
} denote all the LP variables involved under mapping m r , we say that the mapping m r is covered by the LP solution iff. f r = min V => 0 holds. Accordingly, the mapping m r of weight f r can be extracted by reducing the variables in V by f r while adding (f r , m r ) to the set of convex combinations D r . Importantly, after the extraction, the now adapted LP solution is still feasible and hence the extraction process can be repeated. To find a mapping in the first place, the mapping of nodes and edges has to be done in some order. We refer to this order as the extraction order: . Given a virtual network G r = (V r , E r ), we refer to any rooted graph G X r = (V r , E X r , s r ) as an extraction order, if the following holds: 1. G X r is a directed acyclic graph, s.t. each node is reachable from the root s r ∈ V r , and 2. E X r is obtained from E r by (potentially) reversing the orientation of some edges.
We denote by − → E r : E X r → E r the function yielding the edge's original orientation and by to denote the outgoing and incoming edges with respect to the edge set E X r .
Given the extraction order G X r , the extraction process works by first choosing a suitable mapping location for the root s r . Given this location, Lemma 4 is applied to obtain mappings for all outgoing edges of s r (according to E X r ) together with their heads. Continuing to apply Lemma 4 for each of the newly mapped nodes, a complete mapping in which all virtual nodes and edges are mapped on suitable substrate nodes and edges is constructed.
Algorithm 1 formalizes the decomposition scheme to extract convex combinations of valid mappings from solutions to Formulation 2. The algorithm extracts mappings m k r of value f k r iteratively, as long as x r > 0 holds. Initially, in the k-th iteration, none of the virtual nodes and edges are mapped. As x r > 0 holds, the root node s r must be mapped accordingly by Constraint 6, i.e. there must exist a node u ∈ V r,sr S with y u r,sr > 0 and the algorithm sets m V r (s r ) = u. Given this initial fixing, the algorithm iteratively extracts nodes from the queue Algorithm 1: Decomposition algorithm of MCF solutions for Tree Requests Input : Tree request r ∈ R together with a solution (x r , y r , z r , a r ) for Formulation 2 to D r and set k ← k + 1 20 return D r Q which have already been mapped and considers all outgoing virtual edges (i, j) ∈ E X r . If the orientation of edge (i, j) was not changed, i.e., if (i, j) = − → E r (i, j) holds, then Lemma 4 is applied to obtain a mapping of the edge (i, j) together with its head j. If the edge's orientation was reversed, i.e. iff. (i, j) = − → E r (i, j) holds, Lemma 4 can be applied again, only now a path from the mapping of the head i (according to the edge's original orientation) to some mapping of the tail j is obtained. Lastly, the minimum mapping value f k r is computed and the variables of the LP (including the allocation variables) are decreased accordingly. The formal correctness of the algorithm is proven in Lemma 6. Lemma 6. Given a virtual network request r ∈ R, whose underlying undirected graph is a tree, and a solution (x r , y r , z r , a r ) to the LP Formulation 2, the solution can be decomposed into convex combinations of valid mappings

such that the following holds:
The decomposition is complete, i.e., x r = k f k r holds. The decomposition's resource allocations are bounded by a r , i.e., a x,y Proof. Note that the mapping of each virtual node and each virtual edge is valid by construction: Constraints (7) and (9) enforce that a node and an edge can only be mapped in a valid fashion. Furthermore, as G X r is an arborescence, node mappings are never revoked and each node of G r will eventually be mapped. The mapping value f k r is computed as the minimum of the mapping variables V k used for constructing m k r . Reducing the values of the mapping variables together with the load variables a r , the Constraints 6-10 continue to hold.
As the decomposition process continues as long as x r > 0 holds and in the k-th step at least one variable's value is set to 0, it is easy to check that (i) the algorithm terminates with a complete decomposition for which k f k r = x r holds and (ii) the algorithm has polynomial runtime, as the number of variables for request r is bounded by O(|G r | · |E S |).

Limitations of the MCF Formulation
Having shown the decomposability of LP solutions for tree requests, we now show that this does not hold, if the request graphs contain cycles. Figure 2 gives an example for an LP solution of Formulation 2 from which no valid mapping (that is covered) can be extracted. Concretely, considering the mapping of i on u 1 and following the depicted extraction order, k and j must be mapped on u 6 and u 2 , respectively. However, the mapping of j on u 2 only allows for the mapping of k on u 3 and no valid mapping can be extracted and we obtain:

Theorem 7. Solutions to the LP Formulation 2 can (in general) not be decomposed into convex combinations of valid mappings, if request graphs contain cycles. Accordingly, the integrality gap of the LP Formulation 2 is unbounded for cyclic request graphs.
Proof. Figure 2 depicts an example solution to the LP Formulation 2 from which not a single valid mapping can be extracted. The validity of the depicted solution is easy to check. As virtual node i ∈ V r is mapped onto substrate node u 1 ∈ V S , and u 2 ∈ V S is the only neighboring node with respect to the commodity z r,i,j that hosts j ∈ V r , a mapping Hence the virtual node i ∈ V r must be mapped both on u 1 and u 4 . As the same argument applies when considering the mapping of i onto u 4 , no valid mapping can be extracted.
We now show that the formulation exhibits an unbounded integrality gap. Consider the following restrictions for mapping the virtual links: Note that the solution depicted in Figure 2 is still feasible for the MCF LP. Considering the profit variant of the MCF formulation, the LP will attain an objective of b r . As on the other hand, there does not exist a valid mapping of request r on G S , the optimal solution achieves a profit of 0. Hence, the integrality gap of the profit formulation is unbounded.
For the cost variant, we add an edge (u 3 , u 1 ) of arbitrarily high cost to the substrate and include this edge in the set of allowed edges for the virtual edge (k, i) ∈ E r . Hence, there exists only a single valid mapping, which uses this edge (u 3 , u 1 ) while the MCF formulation Example showing that solutions to the LP Formulation 2 cannot be decomposed into convex combinations of valid mappings. The LP solution with xr = 1 is depicted as follows. Substrate nodes are annotated with virtual node mappings: 0.5i at node u1 indicates y u 1 r,i = 1/2. Substrate edge colors match the color of the virtual edges mapped to it. All virtual edges are also mapped using flow values 1/2. The color of substrate edge (u1, u2) therefore implies that z u 1 ,u 2 r,i,j = 1/2 holds. might still use the LP solution depicted in Figure 2. Hence, as the cost of the edge (u 3 , u 1 ) can be arbitrarily high, the integrality gap is unbounded.

Novel Decomposable LP Formulation
In this section we present our novel LP formulation to solve the fractional VNEP and is the basis for our randomized rounding approximation algorithms for the VNEP. We first present the high-level idea of our formulation and introduce crucial concepts as extraction confluences and the extraction width. After introducing further notation, we formally present the LP formulation and show the decomposability of its solutions.

Idea and Definitions
We shortly outline the key idea of our formulation by analyzing the shortcomings of the MCF formulation. Considering the example of Figure 2, we observe that there exist two virtual paths towards k in G X r , namely (i, k) and (i, j), (j, k) . We refer to the combination of two such paths in G X r leading from a common virtual node to another common node as an extraction confluence: We refer to i as the source and to j as the target of the confluence C X i,j .
According to the connectivity property of the MCF formulation (cf. Lemma 4), (partial) mappings can always be extended, but the disjoint paths of a confluence might lead to different mappings of the confluence's target as depicted in Figure 2. However, this divergence is only possible when the confluence's target can be mapped on multiple locations and is not fixed.  We use this as follows. Considering a confluence C X i,j , our LP formulation considers multiple copies of the MCF formulation for each potential mapping location of the confluence's target. In each of these copies, the mapping of the confluence's target is fixed to a specific substrate node. To generalize this idea to multiple confluences, we label edges with confluence targets as follows.
Definition 9 (Extraction Edge Labels). We introduce edge labels L X r,e ⊆ V r for e ∈ E X r as follows. The extraction order edge e is labeled with node j, i.e., j ∈ L X r,e holds, iff. a confluence C X i,j with target j exists that contains e. We also label the edges in their original orientation accordingly: for edge e ∈ E r we set L r,e L X r,e with e = The edge labels will be used in our novel LP formulation to instantiate copies of the MCF formulation. Additionally, we introduce confluence edge bags which partition outgoing edges.
Definition 10 (Confluence Edge Bags). Given an extraction order G X r , the outgoing edges δ + X (i) of each node i ∈ V r are partitioned into a set of edge bags B X r,i = {B X ,b r,i } b , such that two edges e 1 , e n ∈ δ + X (i) are placed in the same bag B X ,b r,i , iff. there exists a series of edges e 2 , e 3 . . . , e n−1 ∈ δ + X (i) such that L X r,e l ∩ L X r,e l+1 = ∅ holds for l ∈ {1, . . . , n − 1}. We denote by L X ,b r,i = e∈B X ,b r,i L X r,e the union of labels contained in a bag B X ,b r,i ∈ B X r,i and by L X b∩e = L X r,e ∩ L X ,b r,i the intersection of labels of the bag B X ,b r,i and the edge e ∈ E X r .
The size of our formulation will be proven to be exponential in the maximal number of labels contained in any edge bag, and we define the notion of extraction width accordingly: Definition 11 (Extraction Width). The width ew X (G X r ) of a given extraction order G X r is the maximal number of labels contained in an edge bag plus one: ew X (G X r ) = 1 + max i∈Vr,B X ,b Denoting by X (G r ) the set of all extraction orders of a graph G r , the extraction width of an arbitrary graph G r is the minimum width of any extraction order: ew(G r ) = min G X r ∈X (Gr) ew X (G X r ). Figure 3 depicts an example extraction order containing 5 confluences, which can be uniquely identified by their sources and targets:

Structure of Edge Labels
In the following, we study the structure of extraction confluences and of the edge labels. We employ the following notation for indicating edges being reachable from and/or by nodes in the extraction order.

Definition 12 (Reachable Edge Sets).
Given an extraction order G X r , we denote by E X ,suc r the set of edges which can be reached from i ∈ V r and which may lead to j ∈ V r . We denote by E X r,i j = E X ,suc the edges lying on a path from i to j.
The following lemma forms the basis for efficiently computing edge labels.

Lemma 13.
Edge e ∈ E X r is labeled with j ∈ V r iff. there exists a node i ∈ V r , such that (i) e lies on a path from i to j, i.e. e ∈ E X r,i j , and (ii) a confluence C X i,j from i to j exists.
Proof. It is easy to see that the above two conditions are necessary. Clearly, if the first condition does not hold for some node i ∈ V r , then there cannot exist a confluence from i to j covering the edge e. Secondly, if there does not exist any confluence between i and j, then there cannot exist a confluence from i to j covering e. We now show that these conditions are also sufficient. First, note that any path from i to j must be contained in E X r,i j . Let e ∈ E X r,i j denote any edge for which the above conditions hold. We show that edge e lies on a confluence with target j. By the second condition, there exist two node-disjoint paths P 1 i,j , P 2 i,j ⊆ E X r,i j from i to j. Now, if e lies on either of these paths, then P 1 i,j P 2 i,j already constitutes a confluence. Hence, assume that e does not lie on either of these paths. Let e = (k, l), i.e. k is the tail and l the head. Furthermore, let P i,k ⊆ E X r,i j denote any path from i to k and denote by P l,j ⊆ E X r,i j any path from l to j. Let P i,e,j denote the path obtained from joining P i,k , e = (k, l), and P l,j .
If P i,e,j only intersects with P 1 i,j (or P 2 i,j ), then P i,e,j together with P 2 i,j (or P 1 i,j ) constitutes a confluence towards j which covers e, proving our claim. Hence, assume that P i,e,j intersects with both paths. Let k be the last node on path P i,k which also lies on P 1 i,j or P 2 i,j and let l denote the first node on P l,j which also lies on P 1 i,j or P 2 i,j . Assume now w.l.o.g. that both k and l lie on path P 1 i,j , then the subpath of P 1 i,j from k to l can be substituted with the subpath from k to l of P i,e,j , yielding the confluence depicted on the left of the subpath of P i,e,k from k to l together with the suffix of P 2 i,j starting at l , a confluence is found that covers e. By construction, as the nodes of path P i,e,j between k and l do neither lie on P 1 i,j nor P 2 i,j , the paths of the constructed confluence are disjoint (see Figure 4 (center) for a visualization). Hence, the two conditions stated in the lemma are also sufficient to decide whether an edge e ∈ E X r is covered by a confluence towards j ∈ V r holds.
Based on Lemma 13, the edge labels can be computed in polynomial-time. Concretely we apply Menger's theorem [18] to decide for any combination of virtual nodes i, j ∈ V r , whether two disjoint paths exist from i to j. If this is the case, then all edges lying in E X r,i j must be labeled with j and we obtain: Proof. We argue that the conditions of Lemma 13 can be checked in polynomial time. For each potential target node j ∈ V r and each source node i ∈ V r , we check whether two node-disjoint paths exist from i to j by applying Menger's theorem [18]: for each node k lying on a path from i to j, we decide whether j is still reachable from i when k is removed. If this is true for each intermediate node, then by Menger's theorem, there exist at least two node-disjoint paths from i to j and hence there must exist a confluence C X i,j . Hence, given the existence of a confluence, all edges in E X r,i j are labeled by j. At most O(|V r | 2 ) many node pairs need to be considered and the check whether two node-disjoint paths exist can be implemented in time O(|V r | · |E r |). Hence, the overall runtime to compute all labels is bounded by O(|V r | 3 · |E r |).
The two following lemmas state important structural properties for edge labels, namely that incoming edges are always labeled the same and that each label has a unique source.

Lemma 15. L X
r,e = L X r,e holds for any pair of incoming edges e, e ∈ δ − X (l) of node l ∈ V r .
Proof. Assume for the sake of contradiction that an edge e = (m, l) is labeled with j, i.e. j ∈ L X r,e , and that some other incoming edge e = (k, l) is not labeled with j, i.e. j / ∈ L X r,e . As the edge e is labeled with j, there must exist some confluence C X i,j covering e. As the edge e = (k, l) is not labeled with j, we obtain from Lemma 13 that the edge e is not reachable from i, i.e., e / ∈ E X r,i j holds. As both i and k are reachable from the root s r of G X r , there must exist paths P sr,i and P sr,k leading from the root s r to i and k, respectively. Let s denote the last node that lies on both of these paths. The subpaths P s ,i and P s ,k of P sr,i and P sr,k starting at s do not use any of the edges in E X r,i j . Hence, joining P s ,i with P 1 i,j and joining P s ,k with e = (k, l) and the subpath of P 2 i,j beginning at node l, a confluence is constructed that covers edge e (see Figure 4 (right) for an visualization of the construction). Therefore, also e must be labeled with j, yielding a contradiction to our assumption that e was not labeled by j and all incoming edges must be labeled the same.
Lastly, the following lemma shows that any label is introduced only once.

Lemma 16.
For each label j ∈ V r there exists a unique root node s j ∈ V r , such that:

1.
Any edge e ∈ E X r being labeled with j ∈ L X r,e is contained in E X r,sj j . 2. Any path from s r (the root of the extraction order) to j passes through s j .
Proof. Consider two nodes i, i ∈ V r being the sources of confluences C X i,j and C X i ,j towards j. Assume that neither i occurs in E X r,i j nor that i occurs in E X r,i j . As the graph G X r is rooted, there must exist a node s reaching both i and i and spawning a confluence towards r,s j holds in this case. Hence, for any pair of nodes i, i being sources of confluences towards j, either one of the nodes is reachable from the other, or there exists another node s ∈ V r such that E X r,i j and E X r,i j are contained in E X r,s j . Clearly, as either i dominates i or i dominates i, or there exists some other node s dominating both, there must exist a single unique root node s j ∈ V r such that all edges labeled with j lie in E X r,sj j . The second claim is immediate: if there was to exist some path from the root s r to an edge being labeled with j without passing through the unique root s j ∈ V r , then there must exist a confluence C X s ,j starting at some other node s ∈ V r , such that s reaches s j but s j does not reach s . Hence, by our above observation s dominates s j and s j cannot be the unique root. Thus, all paths from the root must pass through s j on their way to j.

Novel Decomposable LP Formulation
Our novel Linear Programming Formulation 3 is based on the idea to decide the mapping locations of confluence targets a priori. We do so by considering copies or sub LPs of the MCF formulation (see Constraint 13) and we employ the following notation. For an edge e = (i, j) ∈ E r , we denote by G r,e = (V r,e , E r,e ) with V r,e = {i, j} and E r,e = {e} the subgraph of G r containing only edge e. Variables of sub LPs are named as before, but are now additionally indexed: α β denotes the variable α in the copy identified by β. To denote the combinations of mapping possibilities of labels, we employ M(X) to denote the function space from the set X to V S , i.e., M(X) = [X → V S ]. Accordingly, considering an edge e ∈ E r of request r ∈ R being labeled by L r,e , we instantiate one copy of the MCF formulation per edge label mapping m L e ∈ M(L r,e ) (cf. Constraint 13). For better readability, we write ⦉f |Z⦊ : Z → Y to denote f |Z , i.e., the (standard) restriction of the function f : X → Y on the subset Z ⊆ X. Hence, ⦉f |Z⦊(z) = f (z) holds for z ∈ Z.
To link the LP copies, we employ two types of global node mapping variables. We use the (global) y u r,i variables already presented in Formulation 2 as well as node mapping variables γ u r,i,b,a ∈ [0, 1] for edge bags B X ,b r,i ∈ B X r,i , each mapping m L a ∈ M(L X ,b r,i ) of the labels contained in the respective edge bag, and the mapping locations u ∈ V r,i S . The classic variables y u r,i are used for coupling the embedding variable x r and the sub-LP node mapping variables (see Constraints 14 and 15) as well as for computing the node load (see Constraint 19). The node mapping variables for edge bags γ u r,i,b,a are defined for all mappings of their label set m L a ∈ M(L X ,b r,i ). As L X r,e ⊆ L X ,b r,i holds for all edges e ∈ B X ,b r,i , the node mapping variables of an edge bag directly induce node mappings for all edges contained in the respective bag (see Constraint 16).
In the following, we argue how 'flows' are induced and accordingly how solutions to the formulation can be decomposed. Figure 5 visualizes the workings of Constraints 16 to 18.
Assuming that x r > 0 holds, then by Constraint 14 there will exist a substrate node u ∈ V r,sr S onto which the root s r is placed, i.e. y u r,sr > 0 holds. Constraint 15 distributes the quantity y u r,sr over the sub LP node mapping variables while Constraint 16 ensures that these node mapping variables agree with each other. Due to the validity of the MCF Formulation 2, by setting the node mapping variable for one of the endpoints of the edge graph G r,e , the node mapping variables of the other endpoint of G r,e must be set accordingly. On the other hand, Constraint 17 ensures that any incoming edge (according to the extraction order) agrees with the respective node bag variables and hence force the further distribution of 'flows'. The correctness of the formulation then mostly follows from the following observations: (i) Based on the acylicity of the extraction order and the fact that all nodes can be reached from the root s r , 'flow' is distributed throughout the whole request graph. (ii) A novel edge label j is introduced only exactly once according to Lemma 16, namely at the root s j ∈ V r and hence only at node s j the a priori mapping of j is fixed. (iii) For any confluence C X k,i with target i all incoming edges of i are itself labeled by i (cf. Lemma 15). Accordingly, considering a mapping m L e ∈ M(L r,e ) of an incoming edge e ∈ δ − X (i), Constraint 18 explicitly forbids node placements of i to nodes V r,i S \ {m L e (i)} in the respective sub LPs. Hence, incoming edges of node i labeled by m L e can only map i to m L e (i) ∈ V r,i S .

Figure 5
Visualization of the relation of the different node mapping variables for the example of Figure 3 under the assumption that the virtual nodes i, j, k ∈ Vr can be mapped only on i k , j k , l k ∈ VS for k ∈ {1, 2}, respectively. Depicted are only the variables relating to the mapping of i to i1. To highlight that the LP copies are created upon the original orientation of edges, we assume that (i, a), (f, i) ∈ Er holds and that these were reversed for G X r depicted in Figure 3 on Page 10. The edges and nodes are to be read as 'flows' for which flow preservation holds. The directions of the edges shall help the reader to follow how the node mapping variables of 'incoming' edges trigger the node mapping variables of 'outgoing' edges. The connections on the left are due to Constraint 17 and the connections on the right are due to Constraint 16. Note that the dashed edges on the left will be 0 due to Constraint 18: in the index of the respective sub LP, the virtual node i is mapped onto i2 and hence the respective dashed variables are set to 0.

Theorem 17. Considering specific extraction orders G X r for each request r ∈ R, the size of the novel decomposable Formulation 3 is bounded by
Proof. Consider a single request r ∈ R and a fixed extraction order G X r . There are at most ew X (G X r ) − 1 many sub LPs for each edge e ∈ E X r , as |L X r,e | ≤ ew X (G X r ) − 1 holds by definition. Otherwise, the formulation's size is dominated by the node bag mapping variables γ u r,i,b,a and the respective Constraints 16 -18. Since the bags partition the outgoing edges and encode all potential mappings of the respective label set L X ,b r,i while including the mapping location of the respective virtual node i ∈ V r , the size of the respective formulation parts is bounded by O(|V r | · |V S | ew X (G X r ) ). The result is obtained by summing over the requests.

Decomposition Algorithm for the Novel LP Formulation
We now formally present the decomposition algorithm (see Algorithm 2) and prove its correctness. The algorithm builds on the ideas of the decomposition algorithm for the MCF Formulation 2 presented in Section 2.2. Fixing the mapping of the root initially, mappings for the outgoing edges (with respect to the extraction order) are extracted again together with the mappings of the heads of these edges using Lemma 4. However, as the edge embeddings are computed using a copy of the MCF formulation for each node mapping function of the edge's labels, the mapping of the edge's labels to substrate nodes must be fixed first. To this end, we employ the node mapping variables γ u r,i,b,a of the edge bags. Concretely, whenever the outgoing edges of i ∈ V r are mapped, we show that given the mapping of the virtual node i onto some substrate node m V r (i) = u, we can always find a variable γ u r,i,b,a for edge bag B X ,b r,i ∈ B X r,i and m L a ∈ M(L X ,b r,i ), such that (i) the mapping of the bag m L a agrees with the previous node mappings, i.e., m L a (i ) = m V r (i ) holds for all previously mapped virtual nodes i , and that (ii) the variable γ u r,i,b,a is strictly greater 0. Given such a variable γ u r,i,b,a and fixing the Algorithm 2: Decomposition algorithm for solutions to the novel LP formulation 3 Input : Request r ∈ R, extraction order G X r , solution to Formulation 3 Output : add D k r = (f k r , m k r ) to D r and set k ← k + 1 28 return D r with an edge being labeled by l must be reachable from s l . However, as all incoming labels agree on their labels (see Lemma 15) and no incoming edge of the node i hence lies on a confluence with target l, we must have i = s l . In this case however, the node mapping of l cannot have been decided before as the algorithm only fixes these node mappings once the choose operation was executed at the respective node s l . Hence, L X ,b r,i ∩ M V ⊆ L X r,(k,i) holds. As all previous mapping steps have been valid and the mappings were obtained by the application of Lemma 4, we know that y u . Consider now the particular mapping m L (k,i) = ⦉m V r |L X b∩(k,i) ⦊ which is well-defined, as all labels of the incoming edge (k, i) must have been fixed before extracting the mapping of this edge. From the validity of Constraint 17 we obtain that m L ,a > 0 holds, since the restriction in the sum's index has been loosened. Hence, the choose operation in Line 10 can always be successfully executed and the mapping constructed in the k-th iteration will always be valid.
It is easy to check that the claims with respect to the completeness and the bounds by the load variables also hold: the mapping is always covered by respective mapping variables in V k and as the load is computed as a function of these mapping variables, the extracted fractional resource allocations are also bounded by a r .
Lastly, every time a valid mapping is extracted, a mapping variable's value is set to 0. As the formulation has size O(|G S | ew X (G X r ) · |G r |) (cf. Theorem 17) for request r, and this also bounds the number of variables, at most O(|G S | ew X (G X r ) · |G r |) many valid mappings may be recovered. For recovering a single valid mapping, the runtime can be bounded by O(|G S | ew X (G X r )+1 · |G r |), as the choose operation in Line 10 is executed at most |V r | times and the path computations in Lines 14 and 17 can be implemented in time O(|E S |) (cf. Lemma 4). Hence, the overall runtime of the decomposition algorithm is bounded by O(|G S | 2·ew X (G X r )+1 · |G r | 2 ).

FPT-Approximations for the Virtual Network Embedding Problem
As shown above, our novel LP Formulation 3 is sufficiently strong, such that its solutions can be decomposed into convex combinations D r = {(f k r , m r )} k for each request r ∈ R. In this section we now apply randomized rounding [23] on the decomposed solution to obtain fixed-parameter tractable tri-criteria approximations for the profit and the cost variant of the VNEP.
In the following, we cast the quality of the found solutions in terms of random variables to bound the respective probabilities of not finding a suitable solution. To this end, we employ the following well-known tail bounds.
Proof. We apply Hoeffding (cf. Theorem 20) with t = ε · 2 · ∆ · log(|V S | · |T |) · d S (τ, u): We then plugged in the definition of ∆ and reduced the fraction. Lastly, to obtain the lemma's statement, we utilize that the expected allocations E(A τ,u ) are upper bounded by the capacity d S (τ, u): The probability to violate edge resources can be bounded analogously (see Appendix A for the proof): Main Result. Given the above, we can now prove that Algorithm 3 indeed is a FPT approximation for the profit variant of the VNEP with high probability. Theorem 24. Assume |V S | ≥ 3. Let 0 < ε ≤ 1 be chosen minimally, such that d max (r, x, y)/d S (x, y) ≤ ε holds for (x, y) ∈ R S and r ∈ R. Randomized rounding yields a (α, β, γ) tri-criteria FPT approximation for the profit variant of the VNEP, such that it finds a solution with high probabiliy of at least an α = 1/3 fraction of the optimal profit, and cumulative allocations within factors of β (nodes) and γ (edges) of the original capacities, for β = 1 + ε · 2 · ∆(R V S ) · log(|V S | · |T |) and γ = 1 + ε · 2 · ∆(E S ) · log |V S | with ∆ : P(R S ) → R ≥0 being defined as ∆(X) = max (x,y)∈X r∈R Amax(r,x,y) dmax(r,x,y) Proof. We consider the probability of the rounding step failing to produce a (α, β, γ)approximate solution. By applying a union bound for any node and edge resource exceeding β or γ times the capacity (cf. Lemma 22 and Lemma 23) together with the probability of not achieving 1/3 of the LP's objective (cf. Lemma 21), the probability to not find a solution is upper bounded by 19/20. Hence, the probability of finding an approximate solution within N iterations is at least 1 − (19/20) N , i.e., Algorithm 3 will produce such a solution with high probability. With respect to the runtime of Algorithm 3 we note that the LP Formulation 3 can be solved in O poly( r∈R |G r | · |G S | ew X (G X r ) ) by e.g. using the Ellipsoid algorithm [15] (cf. 17) and the decomposition algorithm's runtime has the same runtime. Hence, the runtime of Algorithm 3 is bounded by O N · poly( r∈R |G r | · |G S | ew X (G X r ) ) , when performing at most N rounding tries. Hence Algorithm 3 is fixed-parameter tractable with respect to the maximal width of any of the extraction orders.
Main Result. Given the Lemmas 27, 29, and 30, a result analogous to Theorem 24 can be obtained for the cost variant of the VNEP.
Theorem 31. Assume that |V S | ≥ 3. Let 0 < ε ≤ 1 be chosen minimally, such that d max (r, x, y)/d S (x, y) ≤ ε holds for (x, y) ∈ R S and r ∈ R. Randomized rounding yields a (α, β, γ) tri-criteria FPT approximation for the cost variant of the VNEP, such that it finds a solution with high probabiliy of cost at most α = 2 times the optimal cost, and cumulative allocations within factors of β (nodes) and γ (edges) of the original capacities, for β = being defined as ∆(X) = max (x,y)∈X r∈R Amax(r,x,y) dmax(r,x,y) 2 .

Extraction Width: Graph Classes and Complexity
The runtime of our approximation algorithms grows exponentially in the maximal width of any extraction order. Hence, three questions arise: (i) are there any polynomial-time (unparameterized) approximations for the VNEP, (ii) which graph classes have a bounded extraction width, and (iii) how can extraction orders of minimal width be computed?
The first question can be answered quite easily: there cannot exist polynomial-time approximations (unless P = N P), as the following theorem shows.
Theorem 32. The fractional VNEP is N P-hard and inapproximable (unless P = N P). This even holds when request graphs are planar.
Proof. The authors of this paper have recently shown in [27] that finding valid mappings for planar requests is N P-complete when allowing for node and edge placement restrictions. Hence, optimizing over a convex combination of valid mappings is N P-hard and the fractional VNEP is (polynomial-time) inapproximable (unless P = N P). This even holds when not considering substrate graph capacities.
The above theorem validates our FPT approach to computing solutions to the fractional VNEP, as there cannot exist polynomial-time algorithms for general request graphs and unless P = N P holds. It furthermore underlines that the complexity of the request graphs must be reflected when computing solutions to the fractional VNEP.

Graph Classes of Bounded Extraction Width
Given the impossibility of polynomial-time approximations for arbitrary request graphs, we now study graph classes that have bounded extraction width. In particular, we show that 'cactus graph requests' and generalizations thereof have bounded extraction width.
Theorem 33. Consider a cactus request graph G r , i.e., one for which cycles in its unidrected interpretation intersect in at most a single node. Then ew X (G X r ) ≤ 2 holds for any extraction order G X r . Hence, our approximations run in polynomial-time for cactus graph requests.
Proof. Consider any extraction order G X r . |L X r,e | ≤ 1 must hold for all edges e ∈ E X r : if this was not the case then two confluences would overlap in e and violate the cactus property. Thus, edge label sets are either equal or disjoint and the maximal edge bag size is 1.
While the class of cactus graphs is restrictive, it can be shown that by adding edges parallel to existing ones the width increases by at most the maximum degree of the graph: Lemma 34. Given an arbitrary graph G r , adding any number of parallel edges (of any direction) for an existing edge does increase the extraction width of G r by at most the maximum degree of G r . This also holds true if instead paths are added instead of edges.
Proof. Consider an extraction order G X r minimizing the width. Let e = (i, j) ∈ E r be an existing edge and assume without loss of generality that the orientation of the edge e is the same in G X r . Now, when adding another edge e = (i, j) or e = (j, i) to E r , we orient the edge the same way as the original edge e. Hence, e would be introduced to E X r as is, and the orientation of e would be reversed. Now, if the node j was previously not the target of a confluence, then by introducing e or e a new confluence was created and the size of the edge bag of node i containing the edge (i, j) ∈ E X r increases by one. However, adding e or e cannot introduce confluences beyond that: the addition of a parallel edge cannot enable a novel confluence to be created. Hence, arbitrarily many parallel edges can be added while increasing the size of an edge bag of the tail of the edge by at most one per outgoing edge. Hence, arbitrarily many parallel edges can be created for any existing edge while increasing the sizes of a single edge bag per node by at most one per outgoing edge. Hence, the extraction width of the resulting graph has increased by at most the maximum degree of the original graph G r .
Lastly, we note that the examples depicted in Figure 1 have small extraction widths. Figure 1 have an extraction width of 2 and 3 respectively.

Observation 35. The example request graphs depicted in
Proof. The request graph depicted on the right of Figure 1 is a cactus graph and hence has width 2 by Lemma 33.
Considering the request graph on the left, we note that when only considering the solid edges, the graph is a cactus and the width is hence 2. By adding the 'parallel' dashed edges, the extraction width increases by at most the maximum degree 3 of the cactus graph according to Lemma 34. However, considering the proof of Lemma 34, we see that for the node LB 1 , only 2 outgoing edges exist (according to the solid edges) and hence the width increases by at most 2. Furthermore, as the node LB 2 is already the target of a confluence, the overall extraction width increases by 1 and the width is hence 3.

Hardness of Computing Extraction Orders
Given the above examples, we now study the computational complexity of finding extraction orders of minimum width. In fact, we prove the N P-hardness of computing optimal extraction orders. Our prove relies on a reduction from vertex cover. As a first step towards this goal, consider the following lemma.
w c w c Figure 6 Depicted is an arbitrarily oriented 'half wheel' (left) together with two extraction orders: The extraction order in the center is rooted at w n/2 and has width 2. The other order on the right is rooted at wc and has a width of at least n/2 (shown below). Lemma 36. Consider the half wheel graph G w depicted in Figure 6 and any extraction order G X w being rooted at w c . Letting VC = {w k ∈ V w |(w k−1 , w k ) ∈ E X r ∨ (w k+1 , w k ) ∈ E X r }, the following holds: ew X (G X w ) = |VC| + 1.

Proof. We denote by
Via induction over the subgraphs G i w it can be seen that the edges e k = (w c , w k ), and Observing that VC n = VC equals the labels introduced in G X w and noting that the edge label sets L X r,ei and L X r,ei+1 overlap for all i ∈ {1, . . . , n − 1}, the root w c must have a single edge bag containing all the labels contained in |VC i |. Hence, ew X (G X w ) ≥ |VC| + 1 follows. Furthermore, only the nodes contained in |VC| can be labels (a node not contained in VC has only a single incoming edge) and the result follows.
By Lemma 36, the following corollary is immediate.
Corollary 37. Consider a wheel graph G w with n outer nodes. Considering any extraction order G X w for which the node w c is chosen to be the root, ew X (G X w ) ≥ n/2 + 1 holds.
The result of Lemma 36 can be generalized in the following sense.
Lemma 38. Given is a connected, undirected graphḠ = (V ,Ē), we define a directed version G V C = (V V C , E V C ) with an additional super noder as follows: V V C =V {r}, and E V C = {(i, j)|{i, j} ∈Ē, i < j} ∪ {(r, i)|i ∈V }. The minimal width of an extraction order G X V C rooted atr equals the size of the minimum vertex cover ofḠ plus one. Proof. Let G X V C be an extraction order of G V C which is rooted atr. The proof of Lemma 36 has shown that whenever a path P in the original graph is considered, all nodes of G X V C with at least one incoming edge (with respect to the original edge set) are labels of the same edge bag of the rootr. As this property holds for any simple path contained inḠ and asḠ is connected, there can only be a single edge bag: if there was more than one edge bag, then there does not exist a path P connecting any of the edges of the first bag to any of the edges in the second bag, refuting the connectivity ofḠ. Applying Lemma 36 for any path P of the original graph, the single edge bag of the rootr must contain any node having at least one incoming edge according to the original edge setĒ. Hence, assuming that G X V C has minimal width, the width of G X V C equals the size of the minimum vertex cover ofḠ plus one.
Lemma 38 is the basis of our proof that computing extraction orders of minimal width is N P-hard via a reduction from vertex cover (cf. Theorem 40). For the proof of our reduction, we require the following lemma.
Lemma 39. Consider a graph G = (V, E) with a corresponding extraction order G X = (V, E X , s). Assume that a node v ∈ V exists that separates a set of nodes U ⊂ V from the root node s. Then any edge incident to v and some node u ∈ U is oriented away from v in the extraction order G X , i.e. (v, u) ∈ E X holds for all u ∈ U .
Proof. Assume for the sake of contradiction that for some node u ∈ U the edge (u, v) is contained in the extraction order. By the definition of the extraction order all nodes must be reachable from the root s. As the node v separates u from the root, all paths from s to u must contain v. Hence, u must be reachable from v and the edge (u, v) hence creates a loop in G X which contradicts the acyclicity of G X . Hence, any edge incident to v and some node u ∈ U must be directed away from v.

Theorem 40. Computing an extraction order of minimum width is N P-hard.
Proof. We give a polynomial time reduction of the vertex cover problem to the problem of finding the extraction order of minimum width. We adapt the construction used in Lemma 38 slightly, to force the mapping of the root node tor. Concretely, we add a half wheel graph (cf. Figure 6) G w with 2 · |V | + 2 outer nodes to the graph G V C and identify the noder with the wheel's node w c , i.e.r = w c . Let G X V C = (V V C , E X V C , s V C ) be an extraction order of minimum width. The extraction order's root s V C must be placed on some outer wheel node: Root s V C is placed on a wheel node w i : We first consider the orientations of edges inside the wheel graph. According to Figure 6 (center) there is an orientation such that the extraction width inside the wheel graph is 2. The noder = w c separates the original graphḠ from the extraction order's root s V C = w i . Thus, by Lemma 39 all edges incident to a node v ∈V and w c must be oriented away from w c . Hence, excluding the outer wheel nodes, the node w c is a root in the corresponding extraction order. Thus, the width of the extraction order G X V C -excluding the outer wheel nodes -equals the size of a minimum vertex cover ofḠ plus one by Lemma 38 and the assumption that G X V C is of minimal width. Lastly, note that no confluence spanning the wheel graph G w and the graphḠ exists. Letting V C denote a minimal vertex cover ofḠ, the width of the extraction order G X V C equals max{2, |V C|} ≤ |V |. Root s V C is placed onr = w c : In this case, the width of the extraction order G X V C is at least |V | + 1 based on Corollary 37. Hence, as the size of a vertex cover ofḠ is always less than |V |, the placement of the root onr contradicts the optimality assumption of G X V C . Root s V C is placed on a node v ∈V : In this case, the width is again at least |V | + 1: as the noder = w c separates the outer wheel nodes from the root s V C , all wheel edges incident to w c are oriented away from w c . As w c is hence a root in the extraction order restricted to the wheel graph, the width is at least |V | + 1 by Lemma 36. Thus, the placement of the extraction's root on any node v ∈V contradicts the optimality of the extraction order G X V C . Now, let V C ⊆V denote a minimum vertex cover ofḠ. If |V C| > 1 holds, then for any optimal extraction order G X V C , ew X (G X V C ) = |V C| + 1 holds. Furthermore, a minimal vertex cover V C can be recovered from any minimum width extraction order G X V C by placing any node v in the cover V C whenever at least two edges are oriented towards it in G X V C . As the cases in which the minimal vertex cover is less or equal to 1 can be trivially identified, computing a minimum width extraction order is N P-hard.

Conclusion
We have presented the first (fixed-parameter tractable) approximation algorithms for the Virtual Network Embedding Problem (VNEP) supporting arbitrary request graphs. To enable the decomposability of general request graphs, we have developed a novel LP formulation whose size is parameterized by a novel graph number: the extraction width and exploring it further will be of great interest for practical applications. Finally, while having focused on the theoretic aspects of approximating the VNEP, we provide the research community with implementations and empirical evaluations at https://vnep-approx.github.io/. Acknowledgements. This work was partially supported by Aalborg University's PreLytics project as well as by the German BMBF Software Campus grant 01IS1205. The authors would like to thank Elias Döhne and Alexander Elvers for proof-reading parts of the paper and contributing significantly to our implementation at https://vnep-approx.github.io/.