Complexity of "can we get a cycle by stacking directed bipartite graphs?"

Question

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.

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

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.

Answer 1

Update: Davide showed that this problem is PSPACE-hard here, 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.

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.

Answer 2

PSPACE-completeness

As suggested by Tim here, the problem can be shown to be PSPACE-hard by reduction from the Corridor Tiling Problem:

Instance: a finite set of Wang tiles $\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.

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

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 Tim's answer), then it is PSPACE-complete.