{'fraction_non_alphanumeric': 0.059351550332719806, 'fraction_numerical': 0.00962763698145264, 'mean_word_length': 3.3457207900079986, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 32, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Rerouting shortest paths in planar graphs

A rerouting sequence is a sequence of shortest st-paths such that consecutive paths differ in one vertex. We study the the Shortest Path Rerouting Problem, which asks, given two shortest st-paths P and Q in a graph G, whether a rerouting sequence exists from P to Q. This problem is PSPACE-hard in general, but we show that it can be solved in polynomial time if G is planar. To this end, we introduce a dynamic programming method for reconfiguration problems.


Introduction
In recent literature, various reconfiguration problems have been studied [11]. For example, Gopalan et al [9] studied the following problem. Given a boolean formula φ, the solution graph G(φ) has as vertex set all solutions, i.e. variable assignments that satisfy φ. Two solutions are adjacent if they differ in exactly one variable. An instance of the Satisfiability Reconfiguration problem consists a boolean formula φ, and two solutions s and t for φ. The question is whether in G(φ), a path from s to t exists. In [9], boolean formulas are classified into those based on tight relations and non-tight relations. It is shown that in the tight case, the Satisfiability Reconfiguration problem can be solved in polynomial time, and in the non-tight case, the problem is PSPACE-complete. A similar dichotomy result is proved in [9] for the problem of deciding whether G(φ) is connected.
Similar results have been obtained for reconfiguration problems based on other combinatorial problems, such as vertex coloring [3,4,5,6], independent set [10,11,14], and more [8,11,12,13]. To obtain reconfiguration versions of these problems, one only needs to define a (symmetric) adjacency relation between solutions. One of the motivations for this research is to study the structure of the solution space of well-studied combinatorial problems, which can explain the performance of various heuristics [4,9]. In addition, similar problems have also occurred in practical applications such as stacking problems in storage spaces [16] and train switchyards (see [15] and references therein). Most of these problems turned out to be PSPACE-complete on general instances.
Various deep hardness results have been proved for reconfiguration problems, such as the first two (independent) PSPACE-hardness results for such problems, on satisfiability reconfiguration [9] and sliding block puzzles [10]. To our knowledge, the other known PSPACE-hardness results on reconfiguration problems have been proved using reductions from these two results. We remark that various PSPACE-complete problems of a similar flavor have been described earlier, such as in the context of local search [17]. An essential difference is however that these are based on asymmetric adjacency relations.
In contrast, very few deep (or even non-trivial) algorithmic results have been obtained for reconfiguration problems. (One of the few exceptions is the result by Cereceda et al [6] on the reconfiguration of vertex colorings using three colors.) A reason for this lack may be that no general algorithmic techniques are known. These two problems impede progress in this area, and might erroneously suggest that reconfiguration problems are only interesting from a complexity theoretic viewpoint. Addressing these problems is the main motivation for the research presented in this paper.
In this paper, we study the Shortest Path Rerouting (SPR) problem, as introduced by Kamiński et al [13]. Given is a graph G, with vertices s, t ∈ V (G), and two shortest st-paths P and Q. Shortest paths are adjacent if they differ in one vertex. The question is whether there exists a rerouting sequence from P to Q, which is a sequence of shortest st-paths Q 0 , . . . , Q k with Q 0 = P , Q k = Q, such that consecutive paths are adjacent.
In [13], instances are described where the minimum length of a rerouting sequence is exponential in n = |V (G)|. Secondly, it is shown that that it is strongly NP-hard to decide whether a rerouting sequence of length at most k exists. In [2], SPR is proved to be PSPACE-complete, and polynomial time algorithms are given for the case where G is claw-free or chordal.
Our main result is that SPR can be decided in polynomial time for planar graphs. Since (rerouting) shortest paths is an important concept in networking, and many networks in practice are planar, this is a relevant graph class for this problem. To obtain this result, we develop a dynamic programming method for reconfiguration problems. Our dynamic programming for SPR returns the correct answer for all instances, but may require more than polynomial time for some. Nevertheless, in appendix D we show that this algorithm is not only useful for deciding planar SPR: in the case where every vertex that lies on a shortest st-path has at most two neighbors closer to s, and at most two neighbors further from s, this dynamic programming algorithm decides SPR in polynomial time as well. Secondly, our results illustrate the importance and strength of searching for central solutions in the solution graph. These algorithmic techniques are discussed in a broader context in Section 6. In the next section, we first give detailed definitions, and then give an outline of the rest of the paper. Because of space constraints, this paper only contains sketches of proofs. Statements for which detailed proofs can be found in the appendix are marked with a star.

Preliminaries
For graph theoretical notions not defined here, and background on results mentioned in this section, we refer to [7]. Walks, paths and cycles in graphs are defined as sequences of vertices. By N (v) we denote the neighborhood of a vertex v. A plane graph is a graph together with an embedding in the plane (without crossing edges). For planar graphs, an embedding can be found in polynomial time, so it suffices to prove our results for plane graphs. If a plane graph is 2connected, then the boundary of every face is a cycle, which is called a facial cycle. Cycles in plane graphs correspond to simple closed curves in the plane, which divide the plane into two regions. For a cycle C in a plane graph G and vertices s, t ∈ V (G), we say C separates s from t if s and t lie in different regions of the curve given by C (and thus s, t ∈ V (C)). Instead of S ∪ {x} and S\{x}, we write S + x and S − x, respectively.
Throughout this paper, s and t denote two (distinct) vertices of an unweighted, undirected, simple, finite graph G, and we will consider shortest stpaths in G. Let d denote the distance from s to t in G. For i ∈ {0, . . . , d}, we define L i ⊆ V (G) to be the set of vertices that lie on a shortest st-path, at distance i from s. The vertex set L i is also called a layer.
Observe that a shortest st-path P contains exactly one vertex of every layer, and that shortest paths are uniquely determined by their vertex set. Therefore, we will denote shortest st-paths P by their vertex set. A vertex set Q ⊆ V (G) such that there exists a shortest st-path P with Q ⊆ P is called a shortest stsubpath. Since we are only concerned with shortest paths in G between two given terminals s and t, we will call these S-paths for short. Shortest st-subpaths will be called S-subpaths. When considering reduced instances, defined by the subgraph induced by all shortest paths between two vertices x and y, these definitions refer to x and y. A rerouting step from an S-path P to Q consists of replacing a vertex a ∈ P by another vertex b in the same layer, such that an S-path results. To be precise, let x, a, y ∈ P such that x ∈ L i−1 , a ∈ L i and y ∈ L i+1 . For any b ∈ L i with {x, y} ⊆ N (b), the rerouting step x, a, y → x, b, y may be applied, which yields Q = P − a + b.
Let G be a graph and s, t ∈ V (G). The rerouting graph SP(G, s, t) has as set of vertices all S-paths in G. Two paths are adjacent if they differ in exactly one vertex. To distinguish vertices of SP(G, s, t) from vertices of G, the former will be called nodes. Subsets S ⊆ V (SP(G, s, t)) will be called sets of S-paths or sets of nodes, depending on the context. In order to prove our results, we need to consider two additional variants of the SPR problem, which are defined by considering different adjacency relations. Call a rerouting step x, a, y → x, b, y a restricted rerouting step if ab ∈ E(G). In the restricted rerouting graph SP R (G, s, t), two S-paths P and Q are adjacent if Q can be obtained from P using a restricted rerouting step.
In the case that G is a plane graph, we can define a third type of rerouting graph. A sequence of four vertices x, a, b, y is called a switch if x, a, y, b, x is a cycle that separates s from t, and for some i, x ∈ L i and y ∈ L i+2 . The vertices x and y are called its (left and right) switch vertices. Together, they are also called a switch-pair. For instance, the graph G 4 shown in Figure 2 contains exactly one switch: 6, 7, 8, 9. (6, 8, 7, 9 is considered to be the same switch.) For readability, in our figures some edges are shown as pairs of half edges in our figures; edges leaving the top of the figure continue on the bottom. A rerouting step x, a, y → x, b, y is called topological if x, a, b, y is not a switch. In the topological rerouting graph SP T (G, s, t), two S-paths P and Q are adjacent if Q can be obtained from P by a topological rerouting step.
Walks in SP(G, s, t), SP R (G, s, t) and SP T (G, s, t) are called rerouting sequences, restricted rerouting sequences, and topological rerouting sequences respectively. Let P be an S-path, and let Q be an S-subpath. We write P G Q to denote that in G, there exists a rerouting sequence from P to an S-path Q ′ with Q ⊆ Q ′ . Similarly, the relations P R G Q and P T G Q are used for the restricted and topological case, respectively. If the graph G in question is clear, the subscript is omitted. If P Q, P R Q or P T Q, we also say that Q is reachable from P . We write P Q to denote that P Q does not hold. The Generalized Shortest Path Rerouting (GSPR) Problem asks, given a graph G with s, t ∈ V (G), an S-path P and an S-subpath Q, whether P G Q. Similarly, for the Restricted SPR (RSPR) Problem and Topological SPR (TSPR) Problem, it should be decided whether P R G Q and P T G Q, respectively. Since Q may be an S-subpath (in all of these problems), GSPR is a generalization of the SPR problem (defined in Section 1). The RSPR Problem in turn generalizes the GSPR Problem: a GSPR instance G, P, Q can easily be transformed to an equivalent RSPR instance by adding edges between every pair of vertices in the same layer. (This may destroy planarity however.) All algorithmic results and reductions presented in this paper for deciding P Q, P T Q or P R Q are constructive, in the following sense: if P Q for an S-subpath Q, then in addition an S-path Q ′ with P Q ′ and Q ⊆ Q ′ can be constructed with the same complexity. (Analog for the topological and restricted case.) For brevity, this is not stated in every lemma and theorem, but this fact is essential for the proofs in Section 5.
Outline In Section 3, we present a dynamic programming algorithm for the RSPR Problem. This algorithm returns the correct answer for all instances, but may require exponential time in some cases. In Section 4 we show however that for instances in a certain standard form, the algorithm always terminates in polynomial time. This is used to prove that TSPR can be solved in polynomial time, by giving a transformation to RSPR instances in standard form. Finally, in Section 5 we show how to handle switches in planar graphs, and give an algorithm for SPR in planar graphs. This algorithm reduces any instance of the problem to a polynomial number of instances of the TSPR Problem.

A Dynamic Programming Algorithm for RSPR
Let P be an S-path in G, and Q be an S-subpath. We want to decide whether P R G Q. For i = 1, . . . , d − 1, we define the graph G i as follows: G i is obtained from G by first removing all vertices in layers L i+1 , . . . , L d−1 , and then adding edges from t to all vertices in L i . By P i and Q i we denote P ∩ V (G i ) and Q∩V (G i ), which clearly are again an S-path and an S-subpath in G i . Figure 1(a) shows an example of G 3 , P 3 and Q 3 (for instance, for the G, P and Q that are shown in Figure 4  Node labels: x: y: z:  Fig. 1. G3, its restricted rerouting graph SP R (G3, s, t), and a contraction H3 of it (with nodes x, y, z), which is the encoding of G3, P, Q. In the nodes of SP R (G3, s, t), the vertices of the corresponding paths are shown, except s and t. In the nodes of H3, the corresponding contracted subgraph of SP R (G3, s, t) is drawn.
The idea is now to compute SP R (G i+1 , s, t) from SP R (G i , s, t), for i = 0, . . . , d − 2. In the end, this will yield SP R (G d−1 , s, t) = SP R (G, s, t), and we can decide whether in this graph a path from P to Q exists. The problem is of course that the graphs SP R (G i , s, t) may be exponentially large compared to G. We solve this problem by instead considering a graph H i that is obtained from a component of SP R (G i , s, t) by contracting connected subgraphs into single nodes, and using node labels to keep track of essential information about the corresponding path sets.
For two S-paths R and R ′ in G i , we define R ∼ i R ′ if and only if there exists a restricted rerouting sequence from R to R ′ that does not change the vertex in L i (so R ∩ L i = R ′ ∩ L i ). Clearly, ∼ i is an equivalence relation. Furthermore, if S is an equivalence class of ∼ i , then S induces a connected subgraph of SP R (G i , s, t). These are exactly the subgraphs of SP R (G i , s, t) that we will contract to obtain H i . The following definition is illustrated in Figure 1 Note that the encoding H i defined this way is unique. We first observe that this definition serves the main purpose of allowing us to decide whether P R Q. Next, we study how the encoding H i+1 of G i+1 , P, Q is related to the encoding H i of G i , P, Q. The objective is that we wish to construct H i+1 from H i without considering SP R (G i+1 , s, t). An example of this construction is shown in Figure 2. For every v ∈ L i+1 , let X v be the set of nodes of H i that correspond to neighbors of v. Formally, we denote the subgraph of H i induced by these nodes. This graph may have multiple components, even though H i is connected. For v ∈ L i+1 and x ∈ V (H i ), by S x ⊕ v we denote the set obtained by adding v to every path in S x , so S x ⊕ v = ∪ R∈Sx (R + v). We will use this notation for the case where v is adjacent to l(x), so then S x ⊕ v is a set of S-paths in G i+1 .
Lemma 3 (*) Let H i and H i+1 be the encodings of G i , P, Q and G i+1 , P, Q, respectively. For any v ∈ L i+1 and component C of The previous two lemmas give all the information that is necessary to compute H i+1 from H i , including the node labels l, p and q. The essential fact that will guarantee a good complexity bound is that for this computation, knowledge of the path sets S x for x ∈ V (H i ) is unnecessary. This yields a dynamic programming algorithm for deciding P R Q (Proposition 2).
...... Theorem 5 shows that the RSPR problem can be solved in polynomial time if the size of the encodings H i remains polynomially bounded. However, since the problem is PSPACE-hard [2], we should not expect this to be true for all graphs. Indeed, there exist examples where the size of the encoding grows exponentially. The example shown in Figure 3 shows that this even true for the case of planar graphs of maximum degree 6 (4 when ignoring edges not on S-paths). It can be verified that for i = 4k − 1, the encoding H i is a star with 2 k leaves.
However, there are many nontrivial instances for which this algorithm is polynomial. For instance, we remark (without proof) that this holds for the class of instances described by Kamiński et al [13], where any rerouting sequence from P to Q has exponential length. (Provided that s and t are swapped.) Next, we prove that H i remains polynomially bounded for instances in a certain standard form, which is closely related to planar graphs. In Appendix D, we show that this also holds for instances where every vertex has at most two neighbors in both the previous and the next layer. Figure 3 shows that this result is sharp; the condition cannot be replaced by maximum degree 4.

A Polynomial Complexity Bound for TSPR
In this section, we show that if G, P, Q is a (reduced) TSPR instance, then in polynomial time it can be decided whether P T Q. To this end, we define a standard form for RSPR instances, and show for these that the algorithm from Section 3 terminates in polynomial time. Subsequently we show how TSPR instances can be transformed to equivalent RSPR instances in standard form. Figure 4(b) illustrates the following definition.
Definition 6 Consider a graph G and vertices s, t ∈ V (G) that are part of an RSPR instance. Then G is in standard form if the following properties hold: Theorem 7 (*) Let G, P, Q be an RSPR instance in standard form. Then in polynomial time, it can be decided whether P R Q.
Proof sketch: Theorem 5 shows that it suffices to show that for every i, the size of encoding H i of G i , P, Q remains polynomially bounded in |V (G)|. By Lemma 4(i), l is a homomorphism from H i to G[L i ], for every i. Using Properties (ii) and (iii) of Definition 6, it can be proved by induction over i that l is in fact locally injective. Then, using Property (i), it follows that H i has maximum degree at most 2 as well, so it is a path or a cycle. For Since H i is a path or a cycle, and the labels l form a locally injective homomorphism to the path or cycle G[L i ], it can be shown that for any u ∈ L i+1 and any component C a of H u i , all vertices in N (u) ∩ L i occur as labels in C a , unless H i is a path and C a contains one of its end vertices. There are at most two end vertices, so max i+1 ≤ max i + 2 follows. An easy induction proof then shows that for all The objective is to apply the above result for TSPR instances G, P, Q. To this end, we will give a polynomial transformation from to an equivalent instance G ′ , P, Q of RSPR, and prove that the latter instance is in standard form. In the case of TSPR and GSPR, it will be useful to work with reduced instances. An instance G, P , Q of GSPR or TSPR is reduced if: 1. Every vertex and edge of G lies on an S-path, 2. G contains no cut vertices, and 3. G contains no neighborhood-dominated vertices, which are vertices z for which there exists a vertex z ′ with N (z) ⊆ N (z ′ ). We remark that, even though the above definition is useful for both GSPR and TSPR, only in the case of GSPR we can give a polynomial time procedure that can transform every instance to a set of equivalent reduced instances. This procedure is straightforward: we may simply delete all vertices and edges not on S-paths. As long as there exists a neighborhood-dominated vertex z, we may delete z, and replace occurrences of z in P and Q by the corresponding vertex z ′ . When a cut vertex v is present, the instance basically consists of two independent instances: one induced by all shortest sv-paths, and one induced by all shortest vt-paths.  For . We assume that G, P, Q is reduced, so every vertex and edge of G lies on an Spath. It follows that for every edge uv, it holds that |dist s (u) − dist s (v)| = 1. Furthermore, G is 2-connected. So for every face f of G and vertex v incident with f , v has exactly two incident edges uv and vw that are also incident with Now we can define the transformation from the TSPR instance G to the RSPR instance G ′ . This transformation is illustrated in Figure 4, and consists of the following two steps.
1. For every face f of G, we do the following. Let u and v be the local minimum . , x ℓ−1 , drawn in the face f , and ℓ edges such that u, x 1 , . . . , x ℓ−1 , v is a path of length ℓ, drawn in face f . Clearly, this preserves planarity. Call the vertices and edges introduced this way new vertices and edges. The vertices and edges that were already present in G are called original vertices and edges. 2. For every face f in the resulting graph, we do the following. Note that f still has a unique local minimum u and local maximum v. Furthermore, for every edge xy, |dist s (x) − dist s (y)| = 1. It follows that for every i ∈ {dist s (u)+1, . . . , dist s (v)−1}, there are exactly two vertices a and b incident with f in layer L i . Between every such pair of vertices a and b, we can add an edge ab, drawn in the face f , without destroying planarity. Call the new edges layer edges. Call the resulting plane graph G ′ . It can be shown that G ′ , P, Q is an RSPR instance in standard form. Since G contains no neighborhood-dominated vertices, for any topological rerouting step x, a, y → x, b, y, it holds that x, a, y, b, x is a facial cycle. So it can be replaced by two restricted rerouting steps x, a, y → For the converse, it can be shown that rerouting steps in a restricted rerouting sequence for G ′ can be grouped in pairs x, a, y → x, z, y → x, b, y where only z is a new vertex. Hence x, a, y, b, x is a facial cycle of G, and x, a, y → x, b, y is a topological rerouting step. We conclude that P T G Q if and only if P R G ′ Q. The above transformation is polynomial, so applying Theorem 7 gives: Theorem 10 (*) Let G, P, Q be a reduced TSPR instance. In polynomial time, it can be decided whether P T G Q.

Switches, general rerouting and the main theorem
As shown in Figure 3, the presence of switches in a plane graph G may cause our dynamic programming algorithm to take exponential time. However, in this section we show that switches also give a lot of structural information, which can be used to obtain a polynomial time algorithm. If x, a, b, y is a switch in G, then in many cases we can reduce the problem to two smaller subproblems, defined as follows: G sy is the subgraph of G induced by all vertices that lie on a shortest sy-path, and G xt is the subgraph of G induced by all vertices that lie on a shortest xt-path. For an S-subpath Q, we denote Q xt = Q ∩ V (G xt ), and Q sy = Q ∩ V (G sy ). We remark that the rerouting sequences that we consider in G sy (G xt ), consist of shortest sy-paths (resp. xt-paths). We are now ready to state the key lemma for reducing the GSPR problem, when switches are present.
Lemma 11 (*) Let G, P, Q be a plane reduced GSPR instance, such that x, y is a switch pair with {x, y} ⊆ P , and Q is one of the following: (i) an S-path that contains x and y, Then P G Q if and only if both P sy Gsy Q sy and P xt Gxt Q xt .
Theorem 12 Let G, P, Q be a plane reduced GSPR instance, where Q is a set containing a switch pair or a single vertex of G. Then in polynomial time it can be decided whether P Q.
Proof: First, compute whether P T Q, which can be done in polynomial time (Theorem 10). If yes, then clearly P Q holds as well, and an S-path Q ′ with P Q ′ and Q ⊆ Q ′ can be computed. (Recall that, as discussed in Section 2, all of our algorithms are constructive.) If P T Q, then for every switch pair x, y, we compute whether P T {x, y}, and if so, compute the corresponding reachable S-path that contains x and y. Since the number of switch pairs in G is polynomial (linear in fact), this can again be done in polynomial time (Theorem 10). If no switch pair is reachable, then we may conclude that P Q. Now consider a switch pair x, y with P T {x, y}. Let P ′ be the S-path with P T P ′ and {x, y} ⊆ P ′ that has been computed. Clearly, P T P ′ implies P P ′ and P ′ P . Therefore, P Q if and only if P ′ Q. By Lemma 11, P ′ Q if and only if both P ′ xt Q xt and P ′ sy Q sy hold. We decide the latter two properties recursively. This way, we can decide whether P Q. It remains to consider the complexity of this algorithm. We argued that the complexity of the above procedure, not counting the recursive calls, can be bounded by a (monotone increasing) polynomial poly(n), where n = |V (G)|. Recall that d denotes the distance between the end vertices s and t. If there are no switch pairs (which is true in particular when d ≤ 3), then the entire procedure terminates in time poly(n).
For d ≥ 3, we prove by induction over d that the complexity of the algorithm can be bounded by ( 4 3 d−3)·poly(n). We have just proved the induction basis (d = 3), so now assume d ≥ 4. In that case, the algorithm may consider a switch pair x, y, and reduce the problem to two instances G sy and G xt . Then the distance between the end vertices of these instances is d ′ and d − d ′ + 2, respectively, for some 3 ≤ d ′ ≤ d − 1. Using the induction assumption and the fact that both G sy and G xt contain at most n vertices, we can bound the total complexity by · poly(n). Finally, we are able to prove the main result of this paper.
Theorem 13 (*) Let G be a plane graph, and let P and Q be S-paths in G. In polynomial time, it can be decided whether P Q.
Proof sketch: By Theorem 8, we may assume that the instance is reduced. The proof is similar to the proof of Theorem 12. The difference is that now, for every switch pair x, y, we decide whether P {x, y} and Q {x, y}, which can be done in polynomial time (Theorem 12). If the answer differs for P and Q, then we may conclude P Q. If both P {x, y} and Q {x, y}, then the problem can be reduced using Lemma 11(i), and decided recursively. If P {x, y} and Q {x, y} for every switch pair x, y, then it suffices to decide whether P T Q (Theorem 10).

Discussion
In Section 3, we introduced a dynamic programming method for reconfiguration problems, that can informally be summarized as follows: identify subgraphs G i , that are separated from the rest of the graph by small separators L i (in our case, the distance layers). For deciding the reconfiguration problem, detailed information about all solutions is not necessary. So based on how solutions intersect with L i , one can identify large connected subgraphs (equivalence classes) in the solution graph of G i , which may be contracted. This method can be applied to all kinds of reconfiguration problems, and different sets of separators, in particular small separators given by tree decompositions [1]. The challenge is however proving that the resulting encodings stay polynomially bounded. In our case, exponentially large star-like structures ( Figure 3) could be avoided by restricting to the topological version of the problem. There may however be different approaches, such as based on reduction rules for the encodings.
Exploring this method seems useful for answering the following interesting open question: Are there reconfiguration problems that are PSPACE-hard for graphs of bounded tree width? Or are there PSPACE-hard reconfiguration problems that can be solved in polynomial time for graphs of treewidth k, for every fixed k? In contrast to the abundance of positive results on NP-complete problems for bounded treewidth [1], to our knowledge, not a single positive or negative result is known for reconfiguration problems on bounded treewidth graphs! Furthermore, our proofs in Section 5 demonstrated the following simple but strong technique: Instead of trying to reconfigure P directly to Q, one should try to reconfigure both P and Q simultaneously to a 'common central solution' in the solution graph SP(G, s, t). Central solutions for this problem turn out to be paths that contain many switch pairs. Once both P and Q are reconfigured to paths that contain a maximum number of switch pairs, deciding whether P Q amounts to simply checking topological reachability. This paradigm, based on identifying central solutions in the solution graph, seems very useful for many reconfiguration problems.

A Proofs omitted from Section 3
Throughout this section, we will use u, v and w to refer to vertices in G, x, y and z to refer to nodes of H i , and a, b and c to refer to nodes of H i+1 .
, the component that contains P also contains an S-path Q ′ with Q ⊆ Q ′ . This is the component that is contracted into H d−1 , so H d−1 contains a node x with Q ′ ∈ S x , and thus q(x) = 1.
On the other hand, if H d−1 contains a node x with q(x) = 1, then S x contains an S-path Q ′ with Q ⊆ Q ′ . Since H d−1 is obtained by contracting the component of SP R (G d−1 , s, t) that contains P , SP R (G d−1 , s, t) has a component that contains both P and Q ′ , so P R Q.

A.1 The proof of Lemma 3
We prove the lemma in two steps.
Proof: For y ∈ V (C) and any two S-paths R 1 , R 2 ∈ S y , there exists a restricted rerouting sequence from R 1 to R 2 that uses only paths from S y . Because H i is a minor of SP R (G i , s, t), for any edge yz ∈ E(H i ), there exist paths R y ∈ S y and R z ∈ S z that are adjacent in SP R (G i , s, t). In particular, this holds for edges of the component C as well. Since C is connected, we can combine these two observations to conclude that for any two paths R, R ′ ∈ ∪ x∈V (C) S x , there exists a restricted rerouting sequence in SP R (G i , s, t) from R to R ′ that uses only paths in ∪ x∈V (C) S x . Since C is a component of H v i , all of these paths contain a vertex of L i that is adjacent to v ∈ L i+1 . So adding v to all of these paths yields a restricted rerouting sequence from R + v to R ′ + v in which every path contains v, which proves that ∪ x∈V (C) (S x ⊕ v) is a subset of an equivalence class of ∼ i+1 .
To conclude the proof, we show that any equivalence class of ∼ i+1 that intersects with S a is a subset of S a . Consider a restricted rerouting sequence R 0 , . . . , R k (consisting of S-paths in G i+1 ), that does not change the vertex v ∈ L i+1 . We have to show that if R 0 ∈ S a , then R k ∈ S a as well. Removing v from every path in this rerouting sequence gives a sequence of paths R ′ 0 , . . . , R ′ k . It suffices to show that these are all in ∪ x∈V (C) S x . Indeed, for any j and y ∈ V (C), if R ′ j ∈ S y and R ′ j+1 is obtained from R ′ j by a rerouting step in a layer other than L i , then by definition of S y , R ′ j+1 ∈ S y as well. On the other hand, if R ′ j+1 is obtained from R ′ j by a rerouting step in L i , then there exists a node z ∈ V (H i ) that is adjacent to y with R ′ j+1 ∈ S z . Furthermore, l(z) ∈ N (v), since R j+1 is a path. So z is part of the component C as well. We may conclude that all paths R j in the rerouting sequence are part of S a .
In various proofs in the appendix, we will construct sequences of S-paths such that consecutive paths either differ in one vertex, or are the same. Clearly, these can be made into rerouting sequences by removing all paths that are the same as the previous path in the sequence. In other words, by removing duplicates.
Proposition 15 Let H i and H i+1 be the encodings of G i , P, Q and G i+1 , P, Q, respectively. For every a ∈ V (H i+1 ), there exists a component Proof: For every S-path R ∈ S a , there exists a restricted rerouting sequence from P i+1 to R, since H i+1 is obtained by contracting the component of SP R (G i+1 , s, t) that contains P i+1 . Consider a restricted rerouting sequence from P i+1 to R. Deleting the vertices from L i+1 in these paths gives a restricted rerouting sequence from P i to R − v in G i (after removing duplicates). So R − v is part of the component of SP R (G i , s, t) that has been contracted to obtain H i , and therefore there exists a node y ∈ V (H i ) with R − v ∈ S y . This node y is part of H v i . Let C a denote the component of H v i that contains y. By Proposition 14, is an equivalence class of ∼ i+1 . Considering the S-path R, we see that this equivalence class intersects with the equivalence class S a , so they are in fact the same.

A.2 The proof of Lemma 4
We prove the lemma in two steps. (Recall that a minor of a graph G is a graph that can be obtained from a subgraph of G by a sequence of contractions.) Proof: H i+1 is a minor of SP R (G i+1 , s, t), so ab ∈ E(H i+1 ) if and only if there exist S-paths R a ∈ S a and R b ∈ S b such that R a and R b are adjacent in SP R (G i+1 , s, t).
Suppose that such adjacent paths R a ∈ S a and R b ∈ S b exist. Since H i+1 is obtained by contracting maximal connected subgraphs consisting of S-paths that all have the same L i+1 -vertex, it follows that l(a) = l(b). So R a and R b differ in their L i+1 -vertex. They differ in one vertex, so , which therefore is nonempty. In addition, the adjacency of R a and R b in SP R (G i+1 , s, t) implies l(a)l(b) ∈ E(G), by definition. This proves the first direction.
On the other hand, if V (C a ) ∩ V (C b ) = ∅ and l(a)l(b) ∈ E(G), then we can choose a path R ∈ S x for some x ∈ V (C a )∩V (C b ), and add the respective vertices l(a) and l(b) to R, to obtain two S-paths that are adjacent in SP R (G i+1 , s, t).
(Note that G has no loops, so l(a) = l(b).) It follows that this procedure yields a graph H ′ that contains the encoding H i+1 as subgraph. However, H ′ is not necessarily connected, even though H i+1 is. (Recall that the encoding H i+1 is obtained by contracting a component of SP R (G i+1 , s, t).) Nevertheless, from Proposition 16 we may conclude that a node a ∈ V (H ′ ) is part of H i+1 if and only if it lies in the same component as the unique node b with p(b) = 1. This shows how H i+1 can be computed from H i for every i.
After constructing all of these encodings, the algorithm terminates by concluding that P R Q if and only if H d−1 contains a node a with q(a) = 1, which is correct by Proposition 2.
It is easy to extend this algorithm such that it is constructive, i.e. such that it also returns an S-path Q ′ of G with Q ⊆ Q ′ , in case P R Q. This is done by storing a single representative S-path Q a of G i with Q i ⊆ Q a , for every H i and every a ∈ V (H i ) with q(a) = 1. By Proposition 17, if q(a) = 1 then the component C a of H i−1 contains at least one node x with q(x) = 1. Adding l(a) to the representative S-path Q x for x then gives a representative S-path for a.
It remains to consider the complexity. There are d − 1 steps where H i+1 is constructed, using as input H i and G, P and Q, and one step where we verify whether H d−1 contains a node a with q(a) = 1. It is easy to see that every such step can be done in polynomial time in the input size. Therefore the total complexity can be bounded by n O(1) · m O(1) , with m = max i∈{1,...,d−1} |V (H i )|.

B.1 The proof of Theorem 7
A locally injective homomorphism is called a LIH for short. Throughout, denote by H i the encoding of G i , P, Q (Definition 1). By Proposition 16, for every i, l is a homomorphism from H i to G[L i ]. Our first goal is to prove that in the case of instances in standard form, this homomorphism is locally injective.
Lemma 18 Let G, P, Q be an RSPR instance in standard form, with distance d from s to t. For i ∈ {0, . . . , d − 1}, let H i be the encoding of G i , P, Q. Then for every i, the node labels l form a LIH from H i to G[L i ].
Proof: We prove the statement by induction over i. For i = 0, the statement is trivial. For i = 1, G i is a K k with k = |L 1 |, so H i has k nodes, and l is a bijection to L i . This proves local injectivity. Now for the induction step, suppose l is a LIH from H i to G[L i ], with i ≥ 1. We prove that l is a LIH from H i+1 to Consider a ∈ V (H i+1 ), and the corresponding component C a of H v i , where v = l(a). As a first step, we prove that C a contains no two nodes with the same label. Suppose to the contrary that it does. Consider a shortest path R = x 0 , x 1 , . . . , x p in C a between two nodes of the same label, so l(x 0 ) = l(x p ). By the induction assumption, l is a LIH from H i to G[L i ], so p ≥ 3. For j ∈ {0, . . . , p−1}, define v j = l(x j ). (By definition of H v i , for every j, v j ∈ N (v) holds.) Since we chose R to be a shortest path between two nodes of the same label, v 0 , . . . , v p−1 are all distinct. Since in addition l is a LIH from H i to G[L i ], it follows that v 0 , . . . , v p−1 is a path in G[L i ]. Finally, since x p−1 and x p are adjacent and l(x p ) = l(x 0 ) = v 0 , it follows that v p−1 is adjacent to v 0 . But then v 0 , . . . , v p−1 , v 0 is a cycle in G[L i ], consisting of neighbors of v, which contradicts Definition 6(ii). We conclude that all labels in C a are distinct, for every a ∈ V (H i+1 ).
Using this fact, we can prove that l is a LIH from H i+1 to G[L i+1 ]. Suppose not, so there exists a node a ∈ V (H i+1 ) with neighbors b, c ∈ V (H i+1 ) such that l(b) = l(c). Let u = l(a) and v = l(b) = l(c). This means that there exist nodes x ∈ V (C b ) ∩ V (C a ) and y ∈ V (C c ) ∩ V (C a ), and uv ∈ E(G) (Proposition 16). By Definition 6(iii), u and v share at most one neighbor w in the previous layer L i . So l(x) = w and l(y) = w. Because we showed above that all labels in C a are distinct, it follows that x = y. But this contradicts that C b and C c are distinct components of H v i .

Corollary 19
Let G, P, Q be an RSPR instance in standard form, with distance d from s to t. For i ∈ {1, . . . , d − 1}, the encoding H i of G i , P, Q is a path or a cycle.
Proof: Every layer G[L i ] has maximum degree at most 2 (Definition 6(i)). For every i, l is a LIH from H i to G[L i ] (Lemma 18). So H i has maximum degree at most 2 as well. By definition, encodings are connected, so H i is a path or a cycle.
For v ∈ L i , we denote by n i (v) the number of nodes Using the previous lemma and corollary, we can show that max i grows at most linearly with i, which is done in the next lemma. From this it will follow that for every i, the size of H i is polynomially bounded.
Proof: The proof of this lemma is illustrated in Figure 5. We will prove the statement by showing for an arbitrary vertex u ∈ L i+1 that n i+1 (u) ≤ max i + 1 holds. It suffices to prove that H u i has at most max i + 1 components (Proposition 15).
By Definition 6(i), G[L i ] has maximum degree 2, so every component is a path or a cycle. By Definition 6(ii), the neighbors of u in L i induce a path, so they are all part of the same component C of G[L i ]. Number the vertices of this component C as v 0 , . . . , v p−1 , along the path or cycle. (To be precise: such that v 0 , . . . , v p−1 is a path, or such that v 0 , . . . , v p−1 , v 0 is a cycle, respectively.) If C is a cycle, then we choose these labels such that in addition, v p−1 ∈ N (u), which is possible since G[N (u) ∩ L i ] is a path, so at least one vertex of the cycle C is not included in N (u). Let y ∈ {0, . . . , p − 1} be the lowest index such that v y ∈ N (u). Observe that N (u) Since H i is a path or a cycle (Corollary 19), we may similarly number its nodes x 0 , . . . , x q−1 , such that this sequence is a path. (If H i is a cycle, then in addition x q−1 x 0 ∈ E(H i ). We may also assume that q ≥ 2, otherwise the lemma follows immediately.) We will now show that there is at most one component C a of H u i that contains no node with label v y . Let C a be such a component. Let j be the lowest index such that C a contains a node x with l(x) = v j . So by choice of C a , j ≥ y + 1, and x has no neighbor Lemma 18) and v j has at most one neighbor other than v j−1 (Definition 6(i)), it follows that x has degree at most 1. So H i is a path, and x is one of its end vertices. W.l.o.g. we may assume x = x 0 . Using again that l is a LIH, we conclude that l(x 1 ) = v j+1 mod p , l(x 2 ) = v j+2 mod p , etc. In particular, if l(x q ) = v j ′ (with j ′ ≥ 1), then l(x q−1 ) = v j ′ −1 . From these facts we may conclude that for any component C a of H u i that contains no node with label v y , it holds that x 0 ∈ V (C a ). So there is at most one such component. It follows that n i+1 (u) ≤ n i (v y ) + 1 ≤ max i + 1.

Theorem 7 Let G, P, Q be an RSPR instance in standard form. Then in polynomial time, it can be decided whether P R Q.
Proof: Let n = |V (G)|. We apply the dynamic programming algorithm from Section 3 to this instance to decide whether P R Q. This algorithm computes encodings H i of G i , P, Q for every i. A simple induction proof based on Lemma 20 shows that for every i, max i ≤ i, so H i contains at most i nodes with the same label. Therefore, it contains at most i · |L i | ∈ O(n 2 ) nodes in total. So the algorithm terminates in time n O(1) (Theorem 5).

B.2 The proof of Theorem 8
Recall that an instance G, P , Q of GSPR is called reduced if: 1. Every vertex and edge of G lies on an S-path, 2. G contains no cut vertices, and 3. G contains no neighborhood-dominated vertices, which are vertices z for which there exists a vertex z ′ with N (z) ⊆ N (z ′ ).
Given an instance consisting of a (possibly plane) graph G, and S-path P and an S-subpath Q, we obtain a set of reduced instances by applying the following three reduction rules exhaustively. The following proposition is trivial.

Proposition 21 (Rule 1) Let G, P, Q be a GSPR instance, and let G ′ be obtained from G by deleting all vertices and edges that do not lie on an S-path. Then
-G, P, Q is again a GSPR instance, and -P G Q if and only if P G ′ Q.
Next, we want to ensure that G contains no cut vertex. In a graph G where every vertex lies on an S-path, it is easily seen that every cut vertex v separates s from t, i.e. s and t lie in different components of G − v (so v = s, t). In addition, v is the only vertex in its layer. This motivates the following definition: if v is a cut vertex of G, then splitting the instance at v yields two instances G sv , P sv , Q sv and G vt , P vt , Q vt , defined as follows: G sv is the subgraph of G induced by all vertices that lie on a shortest sv-path, and G vt is the subgraph of G induced by all vertices that lie on a shortest vt-path.
Thus for every S-path P ′ in G, P ′ ∩ V (G sv ) is a shortest sv-path, and P ′ ∩V (G vt ) is a shortest vt-path. Using these observations, the following proposition follows easily.

Proposition 22 (Rule 2) Let G, P, Q be a GSPR instance in which every vertex lies on an S-path. If G contains a cut vertex v, then
splitting at v yields GSPR instances G sv , P sv , Q sv and G vt , P vt , Q vt , and -P G Q if and only if both P sv Gsv Q sv and P vt Gvt Q vt .
Finally, we can reduce neighborhood-dominated vertices z simply by deleting them, and adjusting P and Q appropriately. The next proposition is again trivial. (We note however that the analog statement does not hold for TSPR, which explains why Theorem 8 is only formulated for GSPR.) Proposition 23 (Rule 3) Let G, P, Q be a GSPR instance, and let z, z ′ be a pair of vertices with N (z) ⊆ N (z ′ ) and z = s, t. Let G ′ = G − z, and let P ′ and Q ′ be obtained from P and Q respectively by replacing every occurrence of z by By applying the above three reduction rules exhaustively to a given GSPR instance G, P, Q, we obtain a set of reduced instances in polynomial time, on which it suffices to solve the problem. Proof: First, delete all vertices and edges of G that do not lie on S-paths (Rule 1). Next, as long as there exists a neighborhood-dominated vertex z, delete it and adjust the paths P and Q appropriately (Rule 3). Finally, if there is a cut vertex v, split the instance at v (Rule 2). Continue splitting the resulting instances as long as there are cut vertices. The resulting instances are reduced: Applying Rule 2 and 3 maintains the property that all vertices and edges lie on S-paths. Applying Rule 2 maintains the property that there are no neighborhooddominated vertices.

Theorem 8 Let G, P, Q be a GSPR instance. In polynomial time, a set of reduced GSPR instances can be constructed such that P G Q if and only if for every reduced instance
By Propositions 21-23, the result is a set of GSPR instances that are all YES-instances if and only if the original instance G, P, Q is a YES-instance. We also argue that this reduction is constructive, as discussed in Section 2: It is easily seen that an S-path Q ′ with Q ⊆ Q ′ and P G Q is obtained by taking the union of the corresponding S-paths Q ′ i for the reduced instances, and subsequently, replacing z ′ by z for every neighborhood-dominated vertex z ∈ Q (with z and z ′ defined as in Proposition 23).
Finally, note that applying these rules exhaustively can be done in polynomial time, that the total number of edges does not increase, and that a possible plane embedding can be maintained. Proof: Let v 0 , v 1 , . . . , v k , v 0 be the facial cycle corresponding to f . By considering a vertex incident with f with maximum s-distance, we see that there is at least one local maximum (as observed above, adjacent vertices cannot have the same s-distance). Now suppose that there are at least two local maxima, say w.l.o.g. v 0 and v ℓ are local maxima for f . So ℓ ≥ 2 and ℓ ≤ k − 1. Let x be a vertex with minimum s-distance among v 1 , . . . , v ℓ−1 , and let y be a vertex with minimum s-distance among v ℓ+1 , . . . , v k . Then max{dist s (x), dist s (y)} < min{dist s (v 0 ), dist s (v ℓ )}. By combining a shortest path from s to x and a shortest path from s to y, we find a path P in G from x to y in which all sdistances are at most max{dist s (x), dist s (y)}. Similarly, by combining shortest paths to t, we find a path P ′ from v 0 to v ℓ in which all s-distances are at least min{dist s (v 0 ), dist s (v ℓ )}. Thus P and P ′ are disjoint. Considering the order of v 0 , x, v ℓ , y along the facial cycle of f , this contradicts that G is planar. An analog argument shows that there is at most one local minimum.
With a similar argument, we can prove the following claim, which is illustrated in Figure 6

t of G is a local maximum or local minimum for all incident faces except two.
Proof: Let v ∈ L i . Call neighbors of v in L i−1 in-neighbors, and neighbors in L i+1 out-neighbors. Since every vertex lies on a shortest st-path, it is clear that both neighbor sets are non-empty. That both the in-neighbors and the outneighbors are consecutive in the clockwise order around v follows by the following argument: for any two out-neighbors o 1 and o 2 of v, using shortest paths from o 1 and o 2 respectively to t, we can easily construct a cycle C + containing o 1 , v, o 2 , in which v is the unique vertex with the lowest s-distance. Similarly, for any two in-neighbors i 1 and i 2 of v, we can construct a cycle C − containing i 1 , v, i 2 , in which v is the unique vertex with the highest s-distance. Since the cycle C − and C + share only the vertex v, it follows that the vertices o 1 , o 2 and i 1 , i 2 lie in a non-crossing order around v.
Next, since G is 2-connected, there is a bijective correspondence between incident faces and consecutive neighbor pairs. Therefore, the previous statement immediately implies that every vertex v = s, t of G is a local maximum or local minimum for all incident faces except two.
The transformation in Section 4 from a TSPR instance G, P, Q to an RSPR instance G ′ , P, Q is defined in terms of faces. Using Proposition 24, we can see how this transformation changes the neighborhood of every vertex of the graph. The following observations are summarized in Figure 6. Consider a vertex v = s, t, with v ∈ L i . Consider a face f of G incident with v, and let w and w ′ the two (consecutive) neighbors of v such that vw and vw ′ are also incident with f . (Recall that G is 2-connected, so there are exactly two such neighbors, and : original vertex : new vertex  they are consecutive.) Note that in the construction of G ′ , v receives exactly one new neighbor u that is drawn in f , and thus u appears between w and w ′ in the clockwise order around v. Furthermore, if w, w ′ ∈ L i−1 then u ∈ L i−1 . If w, w ′ ∈ L i+1 then u ∈ L i+1 . If w and w ′ are in different layers, then u ∈ L i , and thus uv is a layer edge. Using Proposition 24, we can now conclude that every v = s, t is incident with exactly two layer edges. We will first argue that G ′ , P, Q is an RSPR instance in standard form (Lemma 25). Afterwards, we will show that P T G Q if and only if P R G ′ Q (Lemma 26 below). We remark that it may not be immediately obvious that G ′ is simple: we might have added a layer edge between a vertex pair a, b twice, for different faces. The simplicity of G ′ is also shown in the next proof.
Lemma 25 Let G, P, Q be a reduced TSPR instance, and let G ′ , P, Q be the instance that results from the transformation given in Section 4. Then G ′ , P, Q is in standard form, and G ′ is simple.
Proof: We prove that the properties (i)-(iii) from Definition 6 hold for G ′ .
(i) We prove that for every i ∈ {1, . . . , d− 1}, every vertex in G ′ [L i ] has degree 2. For every i, all edges of G ′ [L i ] are layer edges. As observed above (see Figure 6), every original vertex is incident with exactly two layer edges. By construction, the same holds for every new vertex. (ii) We will now prove that for every i ∈ {1, . . . , ] is a path. If i = 1 the statement is clear, so assume i ≥ 2. First we will show that G ′ [L i−1 ] is a cycle. We showed above that G ′ [L i−1 ] is 2-regular, so it is a set of cycles. Consider the set of simple closed curves in the plane corresponding to these cycles. Every S-path contains exactly one vertex from L i−1 , so the corresponding simple curve from s to t crosses exactly one of these curves. (That it actually crosses the curve, and not just touches it, follows again by considering the local structure around the vertex; see Figure 6.) Hence G ′ [L i−1 ] has exactly two faces, one containing s and one containing t, and therefore it is in fact a single cycle. Next, we prove that for every i and Suppose it is not connected and consider two neighbors x, y in different is a cycle, we can choose vertices x ′ and y ′ on this cycle that are not adjacent to v, and that lie in different components of C 1 − x − y. Consider a cycle C 2 that is obtained by combining a shortest sv-path through x with a shortest svpath through y. The curve given by C 2 divides the plane into two regions; call the region that contains t that outside and the other region the inside. Then one of x ′ and y ′ lies inside C 2 , and one lies outside. W.l.o.g. assume that x ′ lies inside. Consider a shortest path P from x ′ to t, and let z be the vertex in L i on this path (the first vertex after x ′ ). The path P must cross C 2 . Since v is the only vertex in a layer higher than i − 1 in C 2 , it follows that v = z, contradicting that . We conclude the proof by observing that there exists at least one vertex in L i−1 that is not adjacent to v. Indeed, if v is adjacent to j original vertices in L i−1 , then it is adjacent to j − 1 new vertices in L i−1 (see Figure 6). But G ′ [L i−1 ] is a cycle in which every edge is incident with exactly one new vertex and one original vertex, so it contains an equal number of original vertices and new vertices. So there is at least one new vertex in L i−1 that is not adjacent to v, and thus G[L i−1 ∩ N (v)] is a path. (iii) Finally, we have to show that for any two u, v ∈ L i with uv ∈ E(G ′ ), it holds that |N (u) ∩ N (v) ∩ L i−1 | ≤ 1. This follows easily since uv is a layer edge, so exactly one of u and v is a new vertex, which by construction has only one neighbor in L i−1 .
Now it follows easily that G ′ is simple: G is reduced and therefore 2-connected, so every layer L i in G with 1 ≤ i ≤ d − 1 contains at least two vertices. As showed above, in G ′ , L i contains exactly twice as many vertices, and G[L i ] is a cycle. So it is a cycle of length at least 4, and therefore no multi-edges are introduced during the construction of G ′ .
Lemma 26 Let G, P, Q be a reduced TSPR instance, and let G ′ , P, Q be the RSPR instance obtained from it by the transformation given in Section 4. Then P T G Q if and only if P R G ′ Q.
Proof: Suppose P T G Q, and consider a corresponding topological rerouting sequence in G. For any rerouting step x, a, y → x, b, y in this sequence, C = x, a, y, b, x is a cycle in G that does not separate s from t. If there is at least one vertex z that is separated from s and t by C, then since every vertex and edge of G lies on an S-path, z is part of the same layer as a and b, and N (z) = {x, y}. But then N (z) ⊆ N (a), which contradicts that G, P, Q is a reduced instance. Therefore, C is a facial cycle. Let f be the corresponding face. Then in G ′ , a new vertex z is added in f , with N (z) = {x, a, b, y}. So in G ′ , the rerouting step x, a, y → x, b, y can be replaced by two rerouting steps x, a, y → x, z, y → x, b, y, which are both admissable in SP R (G ′ , s, t) (since az, bz ∈ E(G ′ )). Adapting every rerouting step in the sequence this way gives a rerouting sequence from P to Q in SP R (G ′ , s, t), so P R G ′ Q. Next, we prove the converse. Suppose P R G ′ Q, so we may consider a restricted rerouting sequence Q 0 , . . . , Q k with Q 0 = P and Q k = Q. We will transform this to a topological rerouting sequence from P to Q in SP T (G, s, t). This requires the following claim.
Claim: If a path Q i in this sequence contains vertices w 1 , w 2 , w 3 in layers L i−1 , L i and L i+1 respectively, such that w 2 is a new vertex, then w 1 and w 3 are original vertices, and there exists an original vertex w ′ 2 in L i that is adjacent to both w 1 and w 3 .
This claim holds because it is not possible that a change x, a, y → x, b, y is made where x or y is a new vertex, since new vertices have exactly one neighbor in previous and next layers. For this reason, we can map every path Q j in the sequence to a path Q ′ j in G: replace every new vertex w 2 by an original vertex w ′ 2 with N (w 2 ) ⊆ N (w ′ 2 ) (as described in the above claim). To be precise, these paths have to be modified in increasing order of j, such that if w 2 ∈ Q j ∩ L i is a new vertex, then it should be replaced by the original vertex w ′ 2 ∈ Q ′ j−1 ∩ L i . Observe that then the resulting sequence Q ′ 0 , . . . , Q ′ k yields a rerouting sequence for G from P to Q (after removing duplicates). It remains to prove that this is a topological rerouting sequence. Since all layer edges are between one new vertex and one original vertex, every rerouting step x, a, y → x, b, y in the new sequence corresponds to a pair of rerouting steps x, a, y → x, z, y → x, a, y in the original sequence, where z is a new vertex that is adjacent to both the original vertices a and b. Such a vertex exists only if x, a, y, b, x is a facial 4-cycle in G. Hence x, a, b, y is not a switch, and therefore the rerouting sequence from P to Q in G is a topological rerouting sequence. Now we can prove Theorem 10.
Theorem 10 Let G, P, Q be a reduced TSPR instance. In polynomial time, it can be decided whether P T G Q.
Proof: The transformation that constructs G ′ , P, Q can be done in polynomial time. By Lemma 25, G ′ , P, Q is an RSPR instance in standard form. Lemma 26 shows that P T G Q if and only if P R G ′ Q. Theorem 7 shows that the latter can be decided in polynomial time.
C Proofs omitted from Section 5

C.1 The proof of Lemma 11
Recall the following definition.
Definition 27 Let x, y be a switch pair in G, with x ∈ L i and y ∈ L i+2 for some i. Then G sy is the subgraph of G induced by all vertices that lie on a shortest sy-path, and G xt is the subgraph of G induced by all vertices that lie on a shortest xt-path. For an S-subpath Q, we denote Q xt = Q ∩ V (G xt ), and Q sy = Q ∩ V (G sy ).
We remark that the rerouting sequences that we consider in G sy (G xt ), consist of shortest sy-paths (resp. xt-paths), which are called S-paths in the respective graphs. Let x ∈ L i . Note that the fact that x, y is a switch pair implies for instance that L j ⊆ V (G xt ) holds for all j ≥ i + 2. In addition, every vertex in L i+1 is part of at least one of G sy and G xt .
Definition 28 Let x, y be a switch pair, and let P be an S-path that contains x and y. For any S-path Q, we define the vertex set P xt (Q) to firstly contain all vertices of Q xt . Secondly, for every i with Q xt ∩ L i = ∅, it contains the vertex P ∩ L i . Similarly, the vertex set P sy (Q) contains all vertices of Q sy . In addition, for every i with Q sy ∩ L i = ∅, it contains the vertex P ∩ L i .
Proposition 29 Let x, y be a switch pair and let P be an S-path that contains x and y. For any S-path Q, both P xt (Q) and P sy (Q) are S-paths.
Proof: Let x ∈ L i and y ∈ L i+2 . We prove the statement for P xt (Q). By definition, it contains exactly one vertex from every layer. It remains to show that its vertices in subsequent layers are adjacent. Most cases follow easily from the definitions. The only nontrivial case is where Q∩L i = {x}, and Q∩L i+2 = {y}. In that case, since x, a, y, b, x is a cycle in G that separates s from t, Q must contain a or b. Therefore P xt (Q) contains this vertex as well (since {a, b} ⊆ V (G xt )). This shows that the vertices of P xt (Q) in the layers L i , L i+1 and L i+2 indeed form a path.
We are now ready to prove the Lemma 11 1 .
Lemma 11 Let G, P, Q be a plane reduced GSPR instance, such that x, y is a switch pair with {x, y} ⊆ P , and Q is one of the following: (i) an S-path that contains x and y, Then P G Q if and only if both P sy Gsy Q sy and P xt Gxt Q xt .
Proof: First of all, we observe that P sy is a shortest sy-path in G sy , and Q sy is a shortest sy-subpath. Hence the notation P sy Gsy Q sy is well-defined. (Q sy may however be empty, in which case the statement is trivially true.) An analog statement holds for the paths in G xt . In the remainder of this proof we will omit the subscripts and simply write e.g. P Q.
We first prove that P Q implies P sy Q sy . Consider a rerouting sequence Q 0 , . . . , Q k with Q 0 = P and Q k = Q. Then after removing duplicates from the sequence, P sy (Q 0 ), . . . , P sy (Q k ) gives a rerouting sequence from P to P sy (Q) (Proposition 29). This in turn gives a rerouting sequence from P sy to Q sy in G sy , so P sy Q sy . Analogously, it follows that for G xt , P xt Q xt holds. Now suppose that both P sy Q sy and P xt Q xt hold. We prove that P Q follows, by considering three cases. Case 1: Suppose that Q sy = Q or Q xt = Q holds. (This covers in particular the case |Q| = 1.) W.l.o.g. assume Q = Q xt . Then there exists a rerouting sequence from P xt to a shortest xt-path Q ′ in G xt with Q ⊆ Q ′ . Apply the rerouting steps from this sequence to the shortest st-path P in G. This results in a shortest st-path in G that contains Q, which implies P Q. Case 2: Next, consider the case where Q is an S-path that contains x and y. Similar to Case 1, the rerouting sequence from P xt to Q xt in G xt yields a rerouting sequence from P to P xt (Q) in G. Denote P ′ = P xt (Q). Since P ′ contains both x and y again, we can subsequently apply rerouting steps from a rerouting sequence from P sy to Q sy in G sy to the path P ′ , which results in the path P ′ sy (Q) = Q (Here we apply Definition 28 with P ′ in the role of P ). Case 3: In the remaining case, Q = {x ′ , y ′ } where x ′ , y ′ is a switch pair, but neither Q ⊆ V (G sy ) nor Q ⊆ V (G xt ) holds. Let x ′ ∈ L j and y ′ ∈ L j+2 , and x ∈ L i and y ∈ L i+2 . From the fact that x, a, b, y is a switch, it follows that layer i + 2 and all subsequent layers are included entirely in G xt , so j ≤ i + 1. Analogously, j ≥ i − 1 follows. If j = i + 1, then x ′ ∈ V (G xt ) implies that y is the unique neighbor of x ′ in L i+2 = L j+1 (using again that x, a, b, y is a switch). But this contradicts that x ′ , y ′ is a switch pair. By excluding the case j = i − 1 analogously, it follows that j = i. So x and x ′ are part of the same layer but distinct, and the same holds for y and y ′ . The cycle x, a, y, b, x separates s from t, so the only possible common neighbors of x ′ and y ′ are a and b. Since x ′ , y ′ is a switch pair, they have at least two common neighbors, so we conclude that N (x ′ ) ∩ N (y ′ ) = {a, b}. In other words, x ′ , a, b, y ′ is the switch that makes x ′ , y ′ a switch pair. This implies that for every z ∈ L i+1 \{a, b}, either N (z) = {x, y ′ } or N (z) = {x ′ , y}. Both are strict subsets of N (a), so since G is reduced, such a vertex z does not exist. We conclude that L i+1 = {a, b}.
Using this information, we can conclude the proof analogously to the previous cases: P xt Q xt with Q xt = {y ′ } implies that there exists a rerouting sequence in G xt from P xt to a shortest xt-path that contains y ′ . Apply the rerouting steps from this rerouting sequence to P , to obtain a rerouting sequence that ends with a shortest st-path Q ′ in G that contains both x and y ′ . Subsequently, consider a rerouting sequence from P sy to a path in G sy that contains x ′ . Every path in this sequence contains y. Since N (y) ∩ L i+1 = {a, b} = N (y ′ ) ∩ L i+1 , we can replace y by y ′ in every path in the sequence, which gives a sequence of shortest sy ′ -paths in G. The first path of this sequence coincides with (is a subset of) Q ′ . Therefore, applying these rerouting steps to Q ′ ends with a shortest st-path in G that contains both x ′ and y ′ . We conclude that P Q.

C.2 The proof of Theorem 13
Theorem 13 Let G be a plane graph, and let P and Q be S-paths in G. In polynomial time, it can be decided whether P Q.
Proof: By Theorem 8, we may assume that the instance is reduced. First, we decide whether P T Q, which can be done in polynomial time (Theorem 10).
If not, then for every switch pair x, y, we decide whether P {x, y} and Q {x, y}. By Theorem 12, and using the fact that the number of switches is polynomial, this can be done in polynomial time. Furthermore, if the answer is affirmative, then corresponding paths containing x and y are computed, that are reachable from P and Q respectively. Clearly, if there exists a switch pair x, y such that P {x, y} but Q {x, y} or vice versa, then P Q, so we may answer negatively. So now assume that the same set of switch pairs is reachable from both P and Q. If no switch pair is reachable, then we may conclude that P Q. (Indeed, if P Q, then either this is a topological rerouting sequence, or it contains a rerouting step x, a, y → x, b, y where x, a, b, y is a switch. When considering the first such rerouting step, it holds that P T {x, y}, and thus P {x, y}.) In the remaining case, there exists a switch pair x, y that is reachable from both P and Q. Furthermore, corresponding S-paths P ′ and Q ′ have been computed with P P ′ , {x, y} ⊆ P ′ , Q Q ′ and {x, y} ⊆ Q ′ . Note that P Q if and only if P ′ Q ′ . Then we reduce to the SPR instances G sy , P ′ sy , Q ′ sy and G xt , P ′ xt , Q ′ xt . By Lemma 11, it now suffices to decide whether P ′ sy Gsy Q ′ sy and P ′ xt Gxt Q ′ xt . This is done recursively. It remains to consider the complexity of this algorithm. We argued that the complexity of the above procedure, not counting the recursive calls, can be bounded by a (monotone increasing) polynomial poly(n), where n = |V (G)|. Analogously to the proof of Theorem 12, an induction proof over the distance d between the end vertices s and t now shows that that the entire algorithm terminates in time ( 4 3 d − 3) · poly(n) if d ≥ 3, and poly(n) if d ≤ 2. (Of course the function poly(n) is different in the current proof; its degree is higher.)

D A polynomial complexity bound for low degree instances
In this section, we assume that G, P, Q is an instance of RSPR in which every vertex v = s, t has at most two neighbors in the previous layer, and at most two neighbors in the next layer. We call such an instance a low degree instance. We will show that for low degree instances, the dynamic programming procedure from Section 3 terminates in polynomial time, by showing that for every i, the encoding H i of G i , P, Q satisfies |V (H i )| ≤ i · |L i |. The proof is similar to the proof of Theorem 7. Define a layer edge uv with u, v ∈ L i to be useless if N (u) ∩ N (v) ∩ L i−1 = ∅. The reason for this is that clearly, no rerouting step in a (restricted) rerouting sequence will change u to v or v to u. So in this case, for G ′ = G − uv it holds that SP R (G, s, t) = SP R (G ′ , s, t). Hence it suffices to prove the statement for low degree instances without useless edges, which is what we will assume for G throughout this section.
Proposition 30 Let G, P, Q be a low degree RSPR instance without useless edges, with distance d from s to t. Then for every i ∈ {2, . . . , d − 1}, G[L i ] has maximum degree at most 2.
Proof: Consider u ∈ L i . The vertex u has at most two neighbors in L i−1 . Each neighbor of u in L i−1 has at most one other neighbor in L i+1 , so it follows that there are at most two vertices v, w ∈ L i+1 that share a neighbor with u.
Throughout, denote by H i the encoding of G i , P, Q (Definition 1). By Proposition 16, for every i, l is a homomorphism from H i to G[L i ]. Our first goal is to prove that in the case of low degree graphs, this homomorphism is locally injective.
Lemma 31 Let G, P, Q be a low degree RSPR instance without useless edges, with distance d from s to t. For i ∈ {0, . . . , d − 1}, let H i be the encoding of G i , P, Q. Then for every i, the node labels l form a LIH from H i to G[L i ].
Proof: We prove the statement by induction over i. For i = 0, the statement is trivial. For i = 1, G i is a K k with k = |L 1 |, so H i has k nodes, and l is a bijection to L i . This proves local injectivity. Now for the induction step, suppose l is a LIH from H i to G[L i ], with i ≥ 1. We prove that l is a LIH from H i+1 to G[L i+1 ].
Consider a ∈ V (H i+1 ), and the corresponding component C a of H v i , where v = l(a). Since v has at most two neighbors in L i , nodes in C a have at most two different labels l (because these labels are chosen from N (v) ∩ L i ). Since C a is connected and by the induction assumption, no node in H i has different neighbors with the same label l, it follows that |V (C a )| ≤ 2, and all nodes x ∈ V (C a ) have different labels l(x).
Using this fact, we can prove that l is a LIH from H i+1 to G[L i+1 ]: Suppose not, so there exists a node a ∈ V (H i+1 ) with neighbors b, c ∈ V (H i+1 ) such that l(b) = l(c). Let w = l(b) = l(c). This means that there exist nodes x ∈ V (C b ) ∩ V (C a ) and y ∈ V (C c ) ∩ V (C a ) (Proposition 16). But above we argued that C a consists of a single node, or two adjacent nodes. Hence x = y, or xy ∈ E(H i ). This contradicts that C b and C c are distinct components of the induced subgraph H w i . Recall that for v ∈ L i , we denote by n i (v) the number of nodes x ∈ V (H i ) with l(x) = v. Define max i := max v∈Li n i (v).
Using the previous lemma and corollary, we can show that max i grows at most linearly with i, which is done in the next lemma. From this it will follow that for every i, the size of H i is polynomially bounded.
Proof: We will prove the statement by proving for an arbitrary vertex u ∈ L i+1 that n i+1 (u) ≤ max i + 1 holds. Recall that all nodes a of H i+1 with l(a) = u correspond to components of H u i (Proposition 15), although since H i+1 should be connected, not every component of H u i corresponds to a node. We first handle two easy cases. Suppose i = 1. Clearly max 1 = 1. Since u ∈ L 2 has at most two neighbors in L 1 , H u 1 has at most two components, which proves that n 2 (u) ≤ 2 = max 1 + 1. So now we may assume that i ≥ 2. If u has only one neighbor v in L i , then clearly the number of nodes in H i+1 with label u is at most the number of nodes with label v in H i , so n i+1 (u) ≤ max i . So now we may assume that N (u) ∩ L i = {v, w}.
In this case, nodes of H i with label v and w cannot be adjacent either (Proposition 16), so every component of H u i consists of a single node. Consider a ∈ V (H i+1 ) with l(a) = u, and suppose that the single node x in C a has label l(x) = v. Since v has at most one other neighbor u ′ in L i+1 , a has at most one neighbor b in H i , which would have l(b) = u ′ (Proposition 16). The same argument applies if the single node in C a has label w. So we conclude that all nodes a ∈ V (H i+1 ) with l(a) = u have degree 1. Since H i+1 is a path or a cycle (Corollary 32), there can be at most two such nodes, which is at most max i + 1, so this proves the claim in this case.
Consider the component C of G[L i ] that contains v and w. By Proposition 30, this component has maximum degree at most 2 (since i ≥ 2), hence it is a path or a cycle. Number the vertices of C as v 0 , . . . , v p such that v = v j and w = v j+1 for some j, and such that v 0 , . . . , v p is a path. (In case C is a cycle, v 0 v p ∈ E(G).) Since H i is a path or a cycle (Corollary 32), we may similarly number its nodes x 0 , . . . , x q , such that this sequence is a path. (If H i is a cycle, then x q x 0 ∈ E(H i ).) To bound the number of nodes a ∈ V (H i+1 ) with l(a) = u, we argue that every node in H i with label w is adjacent to a node with label v, except possibly one. Consider a node x ∈ V (H i ) with l(x) = w, and suppose it has no neighbor with label v. Since l is a LIH from H i to G[L i ], and w = v j+1 has at most one neighbor in G[L i ] other than v = v j (which would be v j+2 mod (p+1) ), this implies that x has degree at most one. Hence w.l.o.g. it follows that x = x 0 (x 0 and x q are the only vertices in H i that can have degree less than 2). Furthermore, from the fact that l is a LIH we can conclude that l(x 0 ) = v j+1 , l(x 1 ) = v j+2 mod (p+1) , etc. Continuing this way, we see that even if the other end node x q of the path has again label l(x q ) = v j+1 = w, then l(x q−1 ) = v j = v. We conclude that there is at most one node in H i with label w without a neighbor with label v. Therefore, the subgraph H u i , which is induced by the set of nodes with label v and w, has at most one component that contains no node with label v. We conclude that it has at most n i (v) + 1 components, which proves that n i+1 (u) ≤ n i (v) + 1 ≤ max i + 1.
Theorem 34 Let G, P, Q be a low degree RSPR instance. Then in polynomial time, it can be decided whether P R Q.
Proof: Let n = |V (G)|. As observed in the beginning of this section, we may assume that G contains no useless edges. We apply the dynamic programming algorithm from Section 3 to this instance to decide whether P R Q. This algorithm computes encodings H i of G i , P, Q for every i. A simple induction proof based on Lemma 33 shows that for every i, max i ≤ i, so H i contains at most i nodes with the same label. Therefore, it contains at most i · |L i | ∈ O(n 2 ) nodes in total. So the algorithm terminates in time n O(1) (Theorem 5).
For the special case of GSPR (see Section 2), the above theorem implies the following result.
Corollary 35 Let G, P, Q be a GSPR instance, such that every vertex that lies on an S-path has at most two neighbors in the previous layer, and at most two neighbors in the next layer. Then in polynomial time, it can be decided whether P Q.