On the Routing Problems in Graphs with Ordered Forbidden Transitions

Finding a path between two vertices of a given graph is one of the most classic problems in graph theory. Recently, problems of finding a route avoiding forbidden transitions, that is, two edges that cannot be passed through consecutively, have been studied. In this paper, we introduce the ordered variants of these problems, namely the Path Avoiding Ordered Forbidden Transitions problem (PAOFT for short) and the Trail Avoiding Ordered Forbidden Transitions problem (TAOFT for short). We show that both the problems are NP-complete even for bipartite planar graphs with maximum degree three. Since the problems are solvable for graphs with maximum degree two, the NP-completeness results are tight with respect to the maximum degree of a graph. Furthermore, we show that TAOFT remains NP-complete for cactus graphs. As positive results of PAOFT, we give a polynomial-time algorithm for bounded treewidth graphs and a linear-time algorithm for cactus graphs.