<h1>PSPACE-completeness</h1>
<p>As suggested by Tim <a href="https://cstheory.stackexchange.com/questions/50373/complexity-of-can-we-get-a-cycle-by-stacking-directed-bipartite-graphs#comment111061_50378">here</a>, the problem can be shown to be PSPACE-hard by reduction from the <a href="https://en.wikipedia.org/wiki/List_of_PSPACE-complete_problems#cite_ref-51" rel="noreferrer">Corridor Tiling Problem</a>:</p>
<p><strong>Instance</strong>: a finite set of <a href="https://en.wikipedia.org/wiki/Wang_tile" rel="noreferrer">Wang tiles</a> <span class="math-container">$\mathcal{T}=\{T_1,\ldots,T_h\}$</span>, a special Wang tile <span class="math-container">$T_0$</span>, and a width <span class="math-container">$n\in\mathbb{N}$</span> given in unary notation.</p>
<p><strong>Question</strong>: is there any height <span class="math-container">$m\in\mathbb{N}$</span> such that an <span class="math-container">$n\times m$</span> rectangle with all borders tiled by <span class="math-container">$T_0$</span> can be tiled by elements of <span class="math-container">$\mathcal{T}$</span>?</p>
<p>Example: <span class="math-container">$n=4$</span>, <span class="math-container">$\mathcal{T}$</span> and <span class="math-container">$T_0$</span> as in the figure. This is a yes-instance for the Corridor Tiling Problem, as shown by the rectangle on the right.</p>
<p><a href="https://i.sstatic.net/NZNUd.jpg" rel="noreferrer"><img src="https://i.sstatic.net/NZNUd.jpg" alt="Wang tiles" /></a></p>
<p>Let <span class="math-container">$c$</span> denote the total number of colors of the tiles in <span class="math-container">$\{T_0\}\cup\mathcal{T}=\{T_1,\ldots,T_h\}$</span>.
We construct <span class="math-container">$3 + (n-2)h$</span> bipartite graphs: 3 bipartite graphs <span class="math-container">$G_0^S,G_0^I,G_0^E$</span> for <span class="math-container">$T_0$</span> (<span class="math-container">$T_0$</span>-gadget) and <span class="math-container">$(n-2)$</span> bipartite graphs <span class="math-container">$G_i^1,\ldots,G_i^{n-2}$</span> for each tile <span class="math-container">$T_i$</span> of <span class="math-container">$\mathcal{T}$</span> (<span class="math-container">$T_i$</span>-gadget).
In the figure, the graphs associated with the example above are shown; graph <span class="math-container">$G_i^j$</span> is formed by all the black and the orange edges if <span class="math-container">$j=1$</span>, by all the black and the cyan edges if <span class="math-container">$j=2$</span>.</p>
<p><a href="https://i.sstatic.net/6gnzm.jpg" rel="noreferrer"><img src="https://i.sstatic.net/6gnzm.jpg" alt="graph associated with Wang tiles" /></a></p>
<p>Each graph has <span class="math-container">$(c + 2)(n - 1)$</span> nodes in <span class="math-container">$V$</span> (and the same number in <span class="math-container">$V'$</span>) whose purpose is summarized as follows:</p>
<ol>
<li>edges from/to nodes <span class="math-container">$1,\ldots,c$</span> of graph <span class="math-container">$G^\bullet_i$</span> (first row of colored nodes in the figure) represent the horizontal color-constraints of tile <span class="math-container">$T_i$</span>, i.e., the constraints that force the colors of the adjacent faces of two horizontally-juxtaposed tiles to be the same;</li>
<li>for all <span class="math-container">$j\in\{1,\ldots,n-2\}$</span>, edges from/to nodes <span class="math-container">$j(c+1)+1,\ldots,j(c+1)+c$</span> of graph <span class="math-container">$G_i^j$</span> (second and third rows of colored nodes in the figure) represent the vertical color-constraints for tile <span class="math-container">$T_i$</span> placed in the <span class="math-container">$(j+1)$</span>-th horizontal place (column) of the <span class="math-container">$n\times m$</span> rectangle;</li>
<li>for all <span class="math-container">$j\in\{1,\ldots,n-2\}$</span>, edge <span class="math-container">$((n-1)(c+1)+j,[(n-1)(c+1)+j+1]')$</span> of graph <span class="math-container">$G_i^j$</span> (from/to black nodes in the figure) represents the fact that tile <span class="math-container">$T_i$</span> is placed in the <span class="math-container">$(j+1)$</span>-th horizontal place (column) of the <span class="math-container">$n\times m$</span> rectangle;</li>
<li>the edges from/to the remaining nodes (white nodes in the figure) are auxiliary.</li>
</ol>
<p>In particular, graph <span class="math-container">$G_0^S$</span> (resp. <span class="math-container">$G_0^E$</span>) models the vertical color-constraints given by the tiles at the bottom (resp. top) face of the rectangle, and they are forced to be placed at the leftmost (resp. rightmost) place in the stack, by construction.
Graph <span class="math-container">$G_0^I$</span> models the horizontal color-constraints given by the tiles at the lateral faces of the rectangle, and they are forced (by the edges from/to black nodes) to be placed at positions <span class="math-container">$n+j(n-1)$</span> in the stack, for all <span class="math-container">$j\in\{0,\ldots,m-4\}$</span>.
For all <span class="math-container">$j\in\{1,\ldots,n-2\}$</span>, <span class="math-container">$G_i^j$</span> can only be placed at positions <span class="math-container">$1+j+k(n-1)$</span> in the stack, for all <span class="math-container">$k\in\{0,\ldots,m-3\}$</span> (because of the edges from/to black nodes).</p>
<p>By construction, the tiles of the instance of Corridor Tiling Problem can form a <span class="math-container">$n\times m$</span> rectangle if and only if the associated bipartite graphs can be stacked to form a <span class="math-container">$[(n-1)(m-2)+2]$</span>-partite graph containing a cycle.
Thus, the problem is PSPACE-hard.
Since the problem belongs to PSPACE (as shown in Tim's answer), then it is PSPACE-complete.</p>

CC BY-SA 4.0
2021-08-24T18:16:46.220Z
2021-08-24T18:16:46.220Z
Davide Zorzenon
<p><strong>Update:</strong> Davide showed that this problem is PSPACE-hard <a href="https://cstheory.stackexchange.com/a/50400/27113">here</a>, settling PSPACE-completeness.</p>
<h1>NP-hardness</h1>
<p>This is NP-hard by reduction from 3SAT.
Let's consider a formula in <span class="math-container">$k$</span> variables.
Below is the construction for the formula <span class="math-container">$(x_1\lor x_2\lor x_3)\land(x_1\lor \neg x_2\lor x_3)\land(\neg x_1\lor x_2\lor \neg x_4)$</span> with <span class="math-container">$k=4$</span>.
I have drawn only the vertices that have incident edges.</p>
<p><a href="https://i.sstatic.net/FKWGn.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/FKWGn.png" alt="Directed cycle reduction instance." /></a></p>
<p>The idea is to create a graph <span class="math-container">$G_L$</span> (pictured on the left) that consist of two edges per clause and has the only upward pointing edge of all the <span class="math-container">$G_\bullet$</span>, so any cycle must use that edge.
For each variable <span class="math-container">$x_i$</span>, create a variable gadget consisting of two bipartite graphs <span class="math-container">$G_i$</span> and <span class="math-container">$G_i'$</span>.
<span class="math-container">$G_i$</span> consists of the blue and black edges, and <span class="math-container">$G_i'$</span> consists of the red and black edges.
For each clause, each variable gadget contains two black edges, and a blue edge if the corresponding variable appears positively, or a red edge if the variable appears negatively in the clause.
The variable gadgets are constructed such that for the rightmost bipartite graph in the stack to be relevant, <span class="math-container">$G_1$</span> or <span class="math-container">$G_1'$</span> must be placed right of <span class="math-container">$G_L$</span>, and <span class="math-container">$G_{i+1}$</span> or <span class="math-container">$G_{i+1}'$</span> must be placed right of <span class="math-container">$G_i$</span> or <span class="math-container">$G_i'$</span>.
This ensures that any cycle can use only <span class="math-container">$G_i$</span> or <span class="math-container">$G_i'$</span>, but not both.
It is clear that if the formula is satisfiable, you can pick <span class="math-container">$G_i$</span> and <span class="math-container">$G_i'$</span> based on the satisfying assignment, in such a way that the resulting graph has a cycle.
Conversely, if a stacked graph has a cycle, then the graphs <span class="math-container">$G_i/G_i'$</span> visited by that cycle give a satisfying assignment.
Hence, the problem is NP-hard.</p>
<h1>PSPACE membership</h1>
<p>To show that the problem lies in PSPACE, it suffices to show that it lies in NPSPACE. For this, a non-deteministic turing machine can guess an arbitrarily long sequence <span class="math-container">$\{i_1,\dots,i_p\}$</span> whose stack contains a cycle that uses an edge of the rightmost graph in the stack.
Let <span class="math-container">$H_k:=\bigotimes_{j=1}^k G_{i_j}$</span> be the substack consisting of the first <span class="math-container">$k$</span> graphs of the sequence.
The rightmost boundary of <span class="math-container">$H_k$</span> contains <span class="math-container">$n$</span> vertices.
Let <span class="math-container">$R_0$</span> be the empty graph.
For <span class="math-container">$k&gt;0$</span>, let <span class="math-container">$R_k$</span> be the directed graph on <span class="math-container">$n$</span> vertices, such that there is an edge from vertex <span class="math-container">$u$</span> to <span class="math-container">$v$</span> if and only if <span class="math-container">$H_k$</span> contains a directed path from <span class="math-container">$u$</span> to <span class="math-container">$v$</span>.
We can in polynomial time compute <span class="math-container">$R_0$</span>, and also <span class="math-container">$R_k$</span> given <span class="math-container">$R_{k-1}$</span> and <span class="math-container">$i_k$</span>.
Hence, a non-deterministic Turing machine can compute <span class="math-container">$R_{p-1}$</span>.
Given <span class="math-container">$R_{p-1}$</span> and <span class="math-container">$i_p$</span>, we can in polynomial time test whether <span class="math-container">$H_p$</span> contains a cycle based, so the problem lies in NPSPACE and hence PSPACE.
This algorithm also shows that the problem is fixed-parameter tractable in <span class="math-container">$n$</span>: the number of relevant graphs <span class="math-container">$R_i$</span> is at most the number of graphs on <span class="math-container">$n$</span> vertices.</p>

CC BY-SA 4.0
2021-08-20T16:24:44.510Z
Very elegant reduction, thanks! The only missing piece is to find out whether it belongs to NP.
Davide Zorzenon
CC BY-SA 4.0
2021-08-21T00:06:02.543Z
I haven't looked into this too deeply, but perhaps the problem is PSPACE-complete by reduction from something like the Corridor Tiling Problem. [Wikipedia](https://en.wikipedia.org/wiki/List_of_PSPACE-complete_problems#cite_ref-51) defines this problem as follows. Given a set of Wang tiles, a chosen tile $T_0$ and a width $n$ given in unary notation, is there any height $m$ such that an $n\times m$ rectangle can be tiled such that all the border tiles are $T_0$?
Tim
CC BY-SA 4.0
2021-08-23T14:23:23.093Z
You are right, I think I found a reduction from Corridor Tiling Problem. Later I'll write down the reduction in a separate answer, and I'll accept yours.
Davide Zorzenon
CC BY-SA 4.0
2021-08-20T15:36:46.040Z
2021-08-24T19:40:42.067Z
2021-08-24T19:40:42.067Z
Tim
<h2>Preliminaries</h2>
<p>We consider directed bipartite graphs of the form <span class="math-container">$G = (V,V',E)$</span>, in which the nodes are partitioned into <span class="math-container">$V = \{1,\ldots,n\}$</span> and <span class="math-container">$V'=\{1',\ldots,n'\}$</span>, with <span class="math-container">$|V|=|V'|=n$</span>, and <span class="math-container">$E\subseteq (V\times V')\cup (V'\times V)$</span> is the set of directed arcs.</p>
<p>The &quot;stacking operation&quot; <span class="math-container">$\otimes$</span> between two directed bipartite graphs of this form <span class="math-container">$G_1$</span>, <span class="math-container">$G_2$</span> (having the same number of nodes) returns the directed tripartite graph <span class="math-container">$G_1\otimes G_2$</span> obtained by merging nodes <span class="math-container">$\{1',\ldots,n'\}$</span> of <span class="math-container">$G_1$</span> with nodes <span class="math-container">$\{1,\ldots,n\}$</span> of <span class="math-container">$G_2$</span>, as shown in the figure below (where <span class="math-container">$n=5$</span>). Operation <span class="math-container">$\otimes$</span> can be naturally extended to stack <span class="math-container">$h$</span>- and <span class="math-container">$k$</span>-partite graphs, for all <span class="math-container">$h,k\geq 2$</span>, as shown in the fourth column of the same figure; the resulting graph is an <span class="math-container">$(h+k-1)$</span>-partite graph.</p>
<p><a href="https://i.sstatic.net/TN8qQ.jpg" rel="noreferrer"><img src="https://i.sstatic.net/TN8qQ.jpg" alt="Stacking operation" /></a></p>
<h2>Problem</h2>
<p>I am trying to find the complexity of the following problem:</p>
<p><strong>Instance</strong>: <span class="math-container">$m$</span> bipartite graphs <span class="math-container">$G_1=(V,V',E_1),\ldots,G_m=(V,V',E_m)$</span> defined as above, each with <span class="math-container">$2n$</span> nodes.</p>
<p><strong>Question</strong>: is there a sequence <span class="math-container">$i_1,\ldots,i_p\in\{1,\ldots,m\}$</span>, with <span class="math-container">$p\in\mathbb{N}$</span>, such that graph <span class="math-container">$\bigotimes_{j=1}^p G_{i_j}$</span> contains a cycle?</p>
<h2>Example</h2>
<p><span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span> form a no-instance for this problem. On the other hand, <span class="math-container">$G_1$</span>, <span class="math-container">$G_2$</span> and <span class="math-container">$G_3$</span> (see figure below) form a yes-instance, since graph <span class="math-container">$G_1\otimes G_3\otimes G_1\otimes G_1\otimes G_2\otimes G_1\otimes G_3$</span> contains a cycle (highlighted in red in the figure).</p>
<p><a href="https://i.sstatic.net/OfRIl.jpg" rel="noreferrer"><img src="https://i.sstatic.net/OfRIl.jpg" alt="yes-instance" /></a></p>
<h2>What I already know</h2>
<p>It is not hard to show that the problem can be solved in polynomial time when there are exactly two arcs for each graph <span class="math-container">$G_i$</span>, using the following algorithm:</p>
<ul>
<li>create a directed graph <span class="math-container">$\mathcal{G}$</span> with <span class="math-container">$m$</span> nodes and such that there is an arc from node <span class="math-container">$i$</span> to node <span class="math-container">$j$</span> if and only if, given <span class="math-container">$s,t,p,q\in\{1,\ldots,n\}$</span> such that <span class="math-container">$E_i = \{(s,t'),(p',q)\}$</span>, then there exist <span class="math-container">$u,r\in\{1,\ldots,n\}$</span> such that <span class="math-container">$E_j = \{(t,u'),(r',p)\}$</span> (here <span class="math-container">$E_i$</span> and <span class="math-container">$E_j$</span> indicate the arc sets of graphs <span class="math-container">$G_i$</span> and <span class="math-container">$G_j$</span>, respectively);</li>
<li>denote by <span class="math-container">$V_s$</span> (start-nodes) the set of all the nodes <span class="math-container">$i$</span> in <span class="math-container">$\mathcal{G}$</span> such that there exist <span class="math-container">$p,q,r\in\{1,\ldots,n\}$</span> for which <span class="math-container">$E_i=\{(p,q'),(r',p)\}$</span>;</li>
<li>denote by <span class="math-container">$V_e$</span> (end-nodes) the set of all the nodes <span class="math-container">$i$</span> in <span class="math-container">$\mathcal{G}$</span> such that there exist <span class="math-container">$p,q,r\in\{1,\ldots,n\}$</span> for which <span class="math-container">$E_i=\{(p,q'),(q',r)\}$</span>;</li>
<li>find if there exists a path from a node in <span class="math-container">$V_s$</span> to any node in <span class="math-container">$V_e$</span>. <span class="math-container">$G_1,\ldots,G_m$</span> form a yes-instance of the problem if and only if at least one of such paths exists.</li>
</ul>
<p>I am not sure whether this procedure can be extended to a polynomial algorithm also when considering graphs without a fixed number of arcs, since the number of nodes in <span class="math-container">$\mathcal{G}$</span> can be higher than <span class="math-container">$m$</span> in this case.
For instance, the graph <span class="math-container">$\mathcal{G}$</span> associated to the example above is</p>
<p><code> 1_1 -&gt; 3_1 -&gt; 1_2 -&gt; 1_3 -&gt; 2 -&gt; 1_4 -&gt; 3_2</code></p>
<p>which has <span class="math-container">$7&gt;m=3$</span> nodes.</p>
<h2>Question</h2>
<p>Is the complexity of the general problem (in which the number of arcs in each graph <span class="math-container">$G_i$</span> is not fixed) known? Any reference on similar problems would be useful.</p>

CC BY-SA 4.0
2021-08-20T15:28:28.617Z
Do you know whether the problem is in NP?  Do you know whether, for every instance that has a solution, there is a solution whose length is polynomial in the input size?
Neal Young
CC BY-SA 4.0
2021-08-20T15:52:58.260Z
Unfortunately no. But I have the impression that the problem is at least decidable.
Davide Zorzenon
CC BY-SA 4.0
2021-08-20T17:20:52.890Z
Surely it's in EXPTIME (time $2^{\text{poly}(n)}$)?  There are only $2^{2n^2}$ possible "reachability configurations" (where each configuration specifies for each $i$ and $j$ whether there is a path from $i$ to $j$), and WLOG you can restrict to solutions that don't repeat a reachability configuration...
Neal Young
<cc.complexity-theory><graph-theory><graph-algorithms><co.combinatorics><bipartite-graphs>
Complexity of "can we get a cycle by stacking directed bipartite graphs?"
Davide Zorzenon
# Complexity of "can we get a cycle by stacking directed bipartite graphs?"

(Asked by: username_0 on 2021-08-19)

## Preliminaries

We consider directed bipartite graphs of the form $G = (V,V',E)$, in which the nodes are partitioned into $V = \{1,\ldots,n\}$ and $V'=\{1',\ldots,n'\}$, with $|V|=|V'|=n$, and $E\subseteq (V\times V')\cup (V'\times V)$ is the set of directed arcs.

The "stacking operation" $\otimes$ between two directed bipartite graphs of this form $G\_1$, $G\_2$ (having the same number of nodes) returns the directed tripartite graph $G\_1\otimes G\_2$ obtained by merging nodes $\{1',\ldots,n'\}$ of $G\_1$ with nodes $\{1,\ldots,n\}$ of $G\_2$, as shown in the figure below (where $n=5$). Operation $\otimes$ can be naturally extended to stack $h$- and $k$-partite graphs, for all $h,k\geq 2$, as shown in the fourth column of the same figure; the resulting graph is an $(h+k-1)$-partite graph.

[![Stacking operation](https://i.sstatic.net/TN8qQ.jpg)](https://i.sstatic.net/TN8qQ.jpg)

## Problem

I am trying to find the complexity of the following problem:

**Instance**: $m$ bipartite graphs $G\_1=(V,V',E\_1),\ldots,G\_m=(V,V',E\_m)$ defined as above, each with $2n$ nodes.

**Question**: is there a sequence $i\_1,\ldots,i\_p\in\{1,\ldots,m\}$, with $p\in\mathbb{N}$, such that graph $\bigotimes\_{j=1}^p G\_{i\_j}$ contains a cycle?

## Example

$G\_1$ and $G\_2$ form a no-instance for this problem. On the other hand, $G\_1$, $G\_2$ and $G\_3$ (see figure below) form a yes-instance, since graph $G\_1\otimes G\_3\otimes G\_1\otimes G\_1\otimes G\_2\otimes G\_1\otimes G\_3$ contains a cycle (highlighted in red in the figure).

[![yes-instance](https://i.sstatic.net/OfRIl.jpg)](https://i.sstatic.net/OfRIl.jpg)

## What I already know

It is not hard to show that the problem can be solved in polynomial time when there are exactly two arcs for each graph $G\_i$, using the following algorithm:

* create a directed graph $\mathcal{G}$ with $m$ nodes and such that there is an arc from node $i$ to node $j$ if and only if, given $s,t,p,q\in\{1,\ldots,n\}$ such that $E\_i = \{(s,t'),(p',q)\}$, then there exist $u,r\in\{1,\ldots,n\}$ such that $E\_j = \{(t,u'),(r',p)\}$ (here $E\_i$ and $E\_j$ indicate the arc sets of graphs $G\_i$ and $G\_j$, respectively);
* denote by $V\_s$ (start-nodes) the set of all the nodes $i$ in $\mathcal{G}$ such that there exist $p,q,r\in\{1,\ldots,n\}$ for which $E\_i=\{(p,q'),(r',p)\}$;
* denote by $V\_e$ (end-nodes) the set of all the nodes $i$ in $\mathcal{G}$ such that there exist $p,q,r\in\{1,\ldots,n\}$ for which $E\_i=\{(p,q'),(q',r)\}$;
* find if there exists a path from a node in $V\_s$ to any node in $V\_e$. $G\_1,\ldots,G\_m$ form a yes-instance of the problem if and only if at least one of such paths exists.

I am not sure whether this procedure can be extended to a polynomial algorithm also when considering graphs without a fixed number of arcs, since the number of nodes in $\mathcal{G}$ can be higher than $m$ in this case.
For instance, the graph $\mathcal{G}$ associated to the example above is

`1_1 -> 3_1 -> 1_2 -> 1_3 -> 2 -> 1_4 -> 3_2`

which has $7>m=3$ nodes.

## Question

Is the complexity of the general problem (in which the number of arcs in each graph $G\_i$ is not fixed) known? Any reference on similar problems would be useful.

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, co.combinatorics, bipartite-graphs

> **Comments:**
> **username_1**: Do you know whether the problem is in NP?  Do you know whether, for every instance that has a solution, there is a solution whose length is polynomial in the input size?  
> **username_0**: Unfortunately no. But I have the impression that the problem is at least decidable.  
> **username_1**: Surely it's in EXPTIME (time $2^{\text{poly}(n)}$)?  There are only $2^{2n^2}$ possible "reachability configurations" (where each configuration specifies for each $i$ and $j$ whether there is a path from $i$ to $j$), and WLOG you can restrict to solutions that don't repeat a reachability configuration...  

---

## 2 answers

### Answer by username_2 on 2021-08-20. Score: 6 | Accepted answer

**Update:** Davide showed that this problem is PSPACE-hard [here](https://cstheory.stackexchange.com/a/50400/27113), settling PSPACE-completeness.

# NP-hardness

This is NP-hard by reduction from 3SAT.
Let's consider a formula in $k$ variables.
Below is the construction for the formula $(x\_1\lor x\_2\lor x\_3)\land(x\_1\lor \neg x\_2\lor x\_3)\land(\neg x\_1\lor x\_2\lor \neg x\_4)$ with $k=4$.
I have drawn only the vertices that have incident edges.

[![Directed cycle reduction instance.](https://i.sstatic.net/FKWGn.png)](https://i.sstatic.net/FKWGn.png)

The idea is to create a graph $G\_L$ (pictured on the left) that consist of two edges per clause and has the only upward pointing edge of all the $G\_\bullet$, so any cycle must use that edge.
For each variable $x\_i$, create a variable gadget consisting of two bipartite graphs $G\_i$ and $G\_i'$.
$G\_i$ consists of the blue and black edges, and $G\_i'$ consists of the red and black edges.
For each clause, each variable gadget contains two black edges, and a blue edge if the corresponding variable appears positively, or a red edge if the variable appears negatively in the clause.
The variable gadgets are constructed such that for the rightmost bipartite graph in the stack to be relevant, $G\_1$ or $G\_1'$ must be placed right of $G\_L$, and $G\_{i+1}$ or $G\_{i+1}'$ must be placed right of $G\_i$ or $G\_i'$.
This ensures that any cycle can use only $G\_i$ or $G\_i'$, but not both.
It is clear that if the formula is satisfiable, you can pick $G\_i$ and $G\_i'$ based on the satisfying assignment, in such a way that the resulting graph has a cycle.
Conversely, if a stacked graph has a cycle, then the graphs $G\_i/G\_i'$ visited by that cycle give a satisfying assignment.
Hence, the problem is NP-hard.

# PSPACE membership

To show that the problem lies in PSPACE, it suffices to show that it lies in NPSPACE. For this, a non-deteministic turing machine can guess an arbitrarily long sequence $\{i\_1,\dots,i\_p\}$ whose stack contains a cycle that uses an edge of the rightmost graph in the stack.
Let $H\_k:=\bigotimes\_{j=1}^k G\_{i\_j}$ be the substack consisting of the first $k$ graphs of the sequence.
The rightmost boundary of $H\_k$ contains $n$ vertices.
Let $R\_0$ be the empty graph.
For $k>0$, let $R\_k$ be the directed graph on $n$ vertices, such that there is an edge from vertex $u$ to $v$ if and only if $H\_k$ contains a directed path from $u$ to $v$.
We can in polynomial time compute $R\_0$, and also $R\_k$ given $R\_{k-1}$ and $i\_k$.
Hence, a non-deterministic Turing machine can compute $R\_{p-1}$.
Given $R\_{p-1}$ and $i\_p$, we can in polynomial time test whether $H\_p$ contains a cycle based, so the problem lies in NPSPACE and hence PSPACE.
This algorithm also shows that the problem is fixed-parameter tractable in $n$: the number of relevant graphs $R\_i$ is at most the number of graphs on $n$ vertices.

> **Comments:**
> **username_0**: Very elegant reduction, thanks! The only missing piece is to find out whether it belongs to NP.  
> **username_2**: I haven't looked into this too deeply, but perhaps the problem is PSPACE-complete by reduction from something like the Corridor Tiling Problem. [Wikipedia](https://en.wikipedia.org/wiki/List_of_PSPACE-complete_problems#cite_ref-51) defines this problem as follows. Given a set of Wang tiles, a chosen tile $T_0$ and a width $n$ given in unary notation, is there any height $m$ such that an $n\times m$ rectangle can be tiled such that all the border tiles are $T_0$?  
> **username_0**: You are right, I think I found a reduction from Corridor Tiling Problem. Later I'll write down the reduction in a separate answer, and I'll accept yours.  

---

### Answer by username_0 on 2021-08-24. Score: 5

# PSPACE-completeness

As suggested by username_2 [here](https://cstheory.stackexchange.com/questions/50373/complexity-of-can-we-get-a-cycle-by-stacking-directed-bipartite-graphs#comment111061_50378), the problem can be shown to be PSPACE-hard by reduction from the [Corridor Tiling Problem](https://en.wikipedia.org/wiki/List_of_PSPACE-complete_problems#cite_ref-51):

**Instance**: a finite set of [Wang tiles](https://en.wikipedia.org/wiki/Wang_tile) $\mathcal{T}=\{T\_1,\ldots,T\_h\}$, a special Wang tile $T\_0$, and a width $n\in\mathbb{N}$ given in unary notation.

**Question**: is there any height $m\in\mathbb{N}$ such that an $n\times m$ rectangle with all borders tiled by $T\_0$ can be tiled by elements of $\mathcal{T}$?

Example: $n=4$, $\mathcal{T}$ and $T\_0$ as in the figure. This is a yes-instance for the Corridor Tiling Problem, as shown by the rectangle on the right.

[![Wang tiles](https://i.sstatic.net/NZNUd.jpg)](https://i.sstatic.net/NZNUd.jpg)

Let $c$ denote the total number of colors of the tiles in $\{T\_0\}\cup\mathcal{T}=\{T\_1,\ldots,T\_h\}$.
We construct $3 + (n-2)h$ bipartite graphs: 3 bipartite graphs $G\_0^S,G\_0^I,G\_0^E$ for $T\_0$ ($T\_0$-gadget) and $(n-2)$ bipartite graphs $G\_i^1,\ldots,G\_i^{n-2}$ for each tile $T\_i$ of $\mathcal{T}$ ($T\_i$-gadget).
In the figure, the graphs associated with the example above are shown; graph $G\_i^j$ is formed by all the black and the orange edges if $j=1$, by all the black and the cyan edges if $j=2$.

[![graph associated with Wang tiles](https://i.sstatic.net/6gnzm.jpg)](https://i.sstatic.net/6gnzm.jpg)

Each graph has $(c + 2)(n - 1)$ nodes in $V$ (and the same number in $V'$) whose purpose is summarized as follows:

1. edges from/to nodes $1,\ldots,c$ of graph $G^\bullet\_i$ (first row of colored nodes in the figure) represent the horizontal color-constraints of tile $T\_i$, i.e., the constraints that force the colors of the adjacent faces of two horizontally-juxtaposed tiles to be the same;
2. for all $j\in\{1,\ldots,n-2\}$, edges from/to nodes $j(c+1)+1,\ldots,j(c+1)+c$ of graph $G\_i^j$ (second and third rows of colored nodes in the figure) represent the vertical color-constraints for tile $T\_i$ placed in the $(j+1)$-th horizontal place (column) of the $n\times m$ rectangle;
3. for all $j\in\{1,\ldots,n-2\}$, edge $((n-1)(c+1)+j,[(n-1)(c+1)+j+1]')$ of graph $G\_i^j$ (from/to black nodes in the figure) represents the fact that tile $T\_i$ is placed in the $(j+1)$-th horizontal place (column) of the $n\times m$ rectangle;
4. the edges from/to the remaining nodes (white nodes in the figure) are auxiliary.

In particular, graph $G\_0^S$ (resp. $G\_0^E$) models the vertical color-constraints given by the tiles at the bottom (resp. top) face of the rectangle, and they are forced to be placed at the leftmost (resp. rightmost) place in the stack, by construction.
Graph $G\_0^I$ models the horizontal color-constraints given by the tiles at the lateral faces of the rectangle, and they are forced (by the edges from/to black nodes) to be placed at positions $n+j(n-1)$ in the stack, for all $j\in\{0,\ldots,m-4\}$.
For all $j\in\{1,\ldots,n-2\}$, $G\_i^j$ can only be placed at positions $1+j+k(n-1)$ in the stack, for all $k\in\{0,\ldots,m-3\}$ (because of the edges from/to black nodes).

By construction, the tiles of the instance of Corridor Tiling Problem can form a $n\times m$ rectangle if and only if the associated bipartite graphs can be stacked to form a $[(n-1)(m-2)+2]$-partite graph containing a cycle.
Thus, the problem is PSPACE-hard.
Since the problem belongs to PSPACE (as shown in username_2's answer), then it is PSPACE-complete.


---

