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

  • $\begingroup$ 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. $\endgroup$
    – daniello
    Jan 21, 2016 at 9:52

1 Answer 1


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

enter image description here

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

  • $\begingroup$ Thanks for the answer. I assume you need a higher vertex degree than 3 though? $\endgroup$
    – Listing
    Jan 21, 2016 at 20:17
  • 1
    $\begingroup$ @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. $\endgroup$ Jan 21, 2016 at 21:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.