Complexity of a graph-rewriting problem I recently came across the following problem which seems to fall in the context of graph rewriting problems:

Input: A graph $G=(V,E)$ with maximum degree 3, an edge $e_0 \in E$ and pairs of graphs $(A_1,B_1),\ldots,(A_k,B_k)$ where both $A_i$ and $B_i$ are subgraphs of the complete graph with vertex set $V$ and $A_i$ is isomorphic to $B_i$ for $i=1,\ldots,k$.

Question:  Is there a sequence $a_1,\ldots,a_n$ such that successively replacing the subgraphs $A_{a_i}$ with $B_{a_i}$ in $G_{i-1}$ (where $G_0=G$) to obtain $G_i$ yields a graph $G_n$ with $e_0 \in E(G_n)$.

Note that one can only replace $A_{a_i}$ with $B_{a_i}$ in $G_{i-1}$ if $E(A_{a_i}) \subseteq E(G_{i-1})$.

Is anything about the complexity of this problem known (in particular is it NP-hard?).
I don't know if it has been studied before, but after a quick look I think it should be PSPACE complete.

We can build a reduction using the Nondeterministic Constraint Logic model of computation (NCL). 

I quick idea is the following (I assume you're familiar with the NCL model): given an NCL graph $G$, you can replace red and blue directed edges with a suitable gadget (with undirected edges) that "marks" the direction of the edge.

Then build the $A_i \to B_i$ subgraphs in such a way that if $A_i$ is a  subgraph of $G$ that represents an NCL  node with valid incoming/outgoing edge constraints, then it can be replaced with $B_i$ which represents a valid flip of one of those edges.

The $A_i / B_i$s should be isomorphic; but this is not a problem for the OR gadget: just add 2 dum nodes "D" so that every node $u$ of the NCL, in the resulting graph has degree 5 with 3 incoming (blue) edges and 2 outgoing (red) edges.

The AND gadget is a little bit more complex, but you can use a "circle" (green edges in the figure) that forces the correct correspondence between the flip of the 2 red edges and the flip of the blue edge (on the opposite side).



If I have enough time I'll give more details about the proof.