# 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?).

• It should not be too hard to reduce from circuit sat and prove this NP-hard (make gadgets for or/and gates, and for setting variables to true/false. Put the edge $e_0$ at the output gate). Based on this I wouldn't be to surprised if this problem is pspace complete. Jan 21 '16 at 9:52

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.

• Thanks for the answer. I assume you need a higher vertex degree than 3 though? Jan 21 '16 at 20:17
• @Listing: yes, but I think that each node can be replaced by a long enough "circle" (with some markups on it to distinguish it from the other gadgets) so that the max degree of the resulting graph can be reduced to 3 ... let me know if you need a more formal proof. Jan 21 '16 at 21:14