Shortest Path Reconfiguration with Relaxed Constraints

• Item type: SIG Technical Reports(1)
• 公開日: 2024-01-13
• タイトル: Shortest Path Reconfiguration with Relaxed Constraints
• タイトル / 言語: en
• タイトル: Shortest Path Reconfiguration with Relaxed Constraints
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Graduate School of Information Sciences, Tohoku University
• 著者所属: Graduate School of Information Sciences, Tohoku University
• 著者所属: Graduate School of Information Sciences, Tohoku University
• 著者所属: Graduate School of Information Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University
• 著者名: Naoki, Domon; Akira, Suzuki; Yuma, Tamura; Xiao, Zhou
• 著者名(英): Naoki, Domon; Akira, Suzuki; Yuma, Tamura; Xiao, Zhou
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: The shortest path problem is the most classical and fundamental problem in the field of graph algorithm. Recently, its reconfiguration variant, namely the Shortest Path Reconfiguration problem, has received a lot of attention. In this paper, we study the complexity of k-SPR, which generalizes the Shortest Path Reconfiguration problem, with respect to k. In k-SPR, we are allowed to replace at most k consecutive vertices of the current shortest path at a time. We first show that, for any fixed rational numbers c and ε such that c > 0 and 0 < ε ≦ 1, k-SPR with k = cn1-ε is polynomially solvable if ε = 1 and c < 1; otherwise, PSPACE-complete. This intractability holds even when given graphs are restricted to bipartite graphs and r-th power graphs, where r is any positive integer. Furthermore, when we restrict 0 < ε < 1, the PSPACE-completeness holds for graphs with maximum degree 3. Then, we design an FPT algorithm parameterized by μ = n/2 - k ≧ 0 that runs in O(m + 6.730μμ4n) time. Finally, we show that, for any k, k-SPR can be solved in linear time for K2,3-minor-free graphs.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The shortest path problem is the most classical and fundamental problem in the field of graph algorithm. Recently, its reconfiguration variant, namely the Shortest Path Reconfiguration problem, has received a lot of attention. In this paper, we study the complexity of k-SPR, which generalizes the Shortest Path Reconfiguration problem, with respect to k. In k-SPR, we are allowed to replace at most k consecutive vertices of the current shortest path at a time. We first show that, for any fixed rational numbers c and ε such that c > 0 and 0 < ε ≦ 1, k-SPR with k = cn1-ε is polynomially solvable if ε = 1 and c < 1; otherwise, PSPACE-complete. This intractability holds even when given graphs are restricted to bipartite graphs and r-th power graphs, where r is any positive integer. Furthermore, when we restrict 0 < ε < 1, the PSPACE-completeness holds for graphs with maximum degree 3. Then, we design an FPT algorithm parameterized by μ = n/2 - k ≧ 0 that runs in O(m + 6.730μμ4n) time. Finally, we show that, for any k, k-SPR can be solved in linear time for K2,3-minor-free graphs.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2024-AL-196, 号 6, p. 1-7, 発行日 2024-01-13
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会