NP-Hardness Boundary of Virtual Network Embedding With Node Location Constraints

Virtual network embedding (VNE) is the optimization problem of finding the minimum cost mapping between virtual and substrate networks. Although most VNE variants are NP-hard, some variants are not. VNE is polynomially solvable if the substrate network supports splittable routing and each virtual node has only one candidate substrate node due to location constraints. However, it is unknown to what extent, this polynomial region can be enlarged. This letter clarifies the boundary by showing that we cannot enlarge the polynomial region unless P = NP. VNE is NP-hard, even if each virtual node has just two candidate substrate nodes.