  We consider the problem of transforming a given graph $G_s$ into a desired
graph $G_t$ by applying a minimum number primitives from a particular set of
local graph transformation primitives. These primitives are local in the sense
that each node can apply them based on local knowledge and by affecting only
its $1$-neighborhood. Although the specific set of primitives we consider makes
it possible to transform any (weakly) connected graph into any other (weakly)
connected graph consisting of the same nodes, they cannot disconnect the graph
or introduce new nodes into the graph, making them ideal in the context of
supervised overlay network transformations. We prove that computing a minimum
sequence of primitive applications (even centralized) for arbitrary $G_s$ and
$G_t$ is NP-hard, which we conjecture to hold for any set of local graph
transformation primitives satisfying the aforementioned properties. On the
other hand, we show that this problem admits a polynomial time algorithm with a
constant approximation ratio.
