TY - GEN
T1 - On the Routing Problems in Graphs with Ordered Forbidden Transitions
AU - Kumakura, Kota
AU - Suzuki, Akira
AU - Tamura, Yuma
AU - Zhou, Xiao
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
PY - 2024
Y1 - 2024
N2 - 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.
AB - 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.
KW - Forbidden transitions
KW - Graph algorithms
KW - NP-completenss
UR - http://www.scopus.com/inward/record.url?scp=85180541084&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85180541084&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-49190-0_26
DO - 10.1007/978-3-031-49190-0_26
M3 - Conference contribution
AN - SCOPUS:85180541084
SN - 9783031491894
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 359
EP - 370
BT - Computing and Combinatorics - 29th International Conference, COCOON 2023, Proceedings
A2 - Wu, Weili
A2 - Tong, Guangmo
PB - Springer Science and Business Media Deutschland GmbH
T2 - 29th International Computing and Combinatorics Conference, COCOON 2023
Y2 - 15 December 2023 through 17 December 2023
ER -