<p>I don't know if it has been studied before, but after a quick look I think it should be PSPACE complete.</p>

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

<p>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.</p>

<p>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.</p>

<p>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.</p>

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

<p><a href="https://i.sstatic.net/WJNuM.jpg" rel="noreferrer"><img src="https://i.sstatic.net/WJNuM.jpg" alt="enter image description here"></a></p>

<p>If I have enough time I'll give more details about the proof.</p>

CC BY-SA 3.0
2016-01-21T20:17:57.857Z
Thanks for the answer. I assume you need a higher vertex degree than 3 though?
Listing
CC BY-SA 3.0
2016-01-21T21:14:28.327Z
@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.
Marzio De Biasi
CC BY-SA 3.0
2016-01-21T10:15:03.553Z
2016-01-21T10:15:03.553Z
Marzio De Biasi
<p>I recently came across the following problem which seems to fall in the context of <a href="https://en.wikipedia.org/wiki/Graph_rewriting">graph rewriting</a> problems:</p>

<p><strong>Input:</strong> 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$.</p>

<p><strong>Question:</strong>  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)$.</p>

<p>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})$.</p>

<p>Is anything about the complexity of this problem known (in particular is it NP-hard?).</p>

CC BY-SA 3.0
2016-01-21T09:52:54.260Z
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.
daniello
<graph-theory><np-hardness><graph-isomorphism><grammars><program-verification>
Complexity of a graph-rewriting problem
Listing
# Complexity of a graph-rewriting problem

(Asked by: username_0 on 2016-01-20)

I recently came across the following problem which seems to fall in the context of [graph rewriting](https://en.wikipedia.org/wiki/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?).

**Tags:** graph-theory, np-hardness, graph-isomorphism, grammars, program-verification
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2016-01-21. Score: 5 | Accepted answer

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](https://i.sstatic.net/WJNuM.jpg)](https://i.sstatic.net/WJNuM.jpg)

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

> **Comments:**
> **username_0**: Thanks for the answer. I assume you need a higher vertex degree than 3 though?  
> **username_2**: @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.  

---

