In this Puzzling SE post, there's a maze with infinitely nested inside itself. Inspired by this, consider the following graph problem:

Setup:

1. A graph G with vertices V and undirected edges E
2. And additional set of directed edges F.
3. Starting vertex S
4. Goal vertex Z

We can define the nested maze problem using the above notation by saying you must find a path from state (S, 0) to state (Z, 0), using the edges from E and F as follows:

1. An edge (u, v) in E lets you make the state transitions: (u, n) -> (v, n) or (v, n) -> (u, n) for any n >= 0. This corresponds to ordinary movement in the maze.
2. An edge (u, v) in F lets you make the state transitions: (u, n) -> (v, n + 1) or (v, n + 1) -> (u, n) for any n >= 0. This corresponds to entering/exiting the nested maze, with the second element of the state tracking the "depth".

A path is a sequence of edges (repetitions are allowed!).

Is there an algorithm for solving this problem in general? It seems possible that it's undecidable, but the particular example from the above Puzzling post isn't particularly hard to analyze.

In this Puzzling SE post, there's a maze with infinitely nested inside itself. Inspired by this, consider the following graph problem:

Setup:

1. A graph G with vertices V and undirected edges E
2. And additional set of directed edges F.
3. Starting vertex S
4. Goal vertex Z

We can define the nested maze problem using the above notation by saying you must find a path from state (S, 0) to state (Z, 0), using the edges from E and F as follows:

1. An edge (u, v) in E lets you make the state transitions: (u, n) -> (v, n) or (v, n) -> (u, n) for any n >= 0. This corresponds to ordinary movement in the maze.
2. An edge (u, v) in F lets you make the state transitions: (u, n) -> (v, n + 1) or (v, n + 1) -> (u, n) for any n >= 0. This corresponds to entering/exiting the nested maze, with the second element of the state tracking the "depth".

A path is a sequence of edges (repetitions are allowed!).

Is there an algorithm for solving this problem in general? It seems possible that it's undecidable, but the particular example from the above Puzzling post isn't particularly hard to analyze.

Edit: Thinking about this more, can you discard E by just merging all vertices that are mutually reachable in G. Then, the problem is just one on V and F, where you want to find a path (possibly involving repeated edges) using edges either forwards or backwards, with the number of forward traversals equalling the number of backward traversals. Additionally, the number of forward traversals must be at least the number of backward traversals for all prefixes of the path.

In this Puzzling SE post, there's a maze with infinitely nested inside itself. Inspired by this, consider the following graph problem:

Setup:

1. A graph G with vertices V and undirected edges E
2. And additional set of directed edges F.
3. Starting vertex S
4. Goal vertex Z

We can define the nested maze problem using the above notation by saying you must find a path from state (S, 0) to state (Z, 0), using the edges from E and F as follows:

1. An edge (u, v) in E lets you make the state transitions: (u, n) -> (v, n) or (v, n) -> (u, n) for any n >= 0. This corresponds to ordinary movement in the maze.
2. An edge (u, v) in F lets you make the state transitions: (u, n) -> (v, n + 1) or (v, n + 1) -> (u, n) for any n >= 0. This corresponds to entering/exiting the nested maze, with the second element of the state tracking the "depth".

Is there an algorithm for solving this problem in general? It seems possible that it's undecidable, but the particular example from the above Puzzling post isn't particularly hard to analyze.

In this Puzzling SE post, there's a maze with infinitely nested inside itself. Inspired by this, consider the following graph problem:

Setup:

1. A graph G with vertices V and undirected edges E
2. And additional set of directed edges F.
3. Starting vertex S
4. Goal vertex Z

We can define the nested maze problem using the above notation by saying you must find a path from state (S, 0) to state (Z, 0), using the edges from E and F as follows:

1. An edge (u, v) in E lets you make the state transitions: (u, n) -> (v, n) or (v, n) -> (u, n) for any n >= 0. This corresponds to ordinary movement in the maze.
2. An edge (u, v) in F lets you make the state transitions: (u, n) -> (v, n + 1) or (v, n + 1) -> (u, n) for any n >= 0. This corresponds to entering/exiting the nested maze, with the second element of the state tracking the "depth".

A path is a sequence of edges (repetitions are allowed!).

Is there an algorithm for solving this problem in general? It seems possible that it's undecidable, but the particular example from the above Puzzling post isn't particularly hard to analyze.