  The performance of distributed and data-centric applications often critically
depends on the interconnecting network. Applications are hence modeled as
virtual networks, also accounting for resource demands on links. At the heart
of provisioning such virtual networks lies the NP-hard Virtual Network
Embedding Problem (VNEP): how to jointly map the virtual nodes and links onto a
physical substrate network at minimum cost while obeying capacities.
  This paper studies the VNEP in the light of parameterized complexity. We
focus on tree topology substrates, a case often encountered in practice and for
which the VNEP remains NP-hard. We provide the first fixed-parameter algorithm
for the VNEP with running time $O(3^r (s+r^2))$ for requests and substrates of
$r$ and $s$ nodes, respectively. In a computational study our algorithm yields
running time improvements in excess of 200x compared to state-of-the-art
integer programming approaches. This makes it comparable in speed to the
well-established ViNE heuristic while providing optimal solutions. We
complement our algorithmic study with hardness results for the VNEP and related
problems.

Data Structures and Algorithms;Networking and Internet Architecture