Finding shortest non-separating and non-disconnecting paths

• Item type: SIG Technical Reports(1)
• 公開日: 2022-03-07
• タイトル: Finding shortest non-separating and non-disconnecting paths
• タイトル / 言語: en
• タイトル: Finding shortest non-separating and non-disconnecting paths
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Kyoto University
• 著者所属: Kyoto University
• 著者所属: Nagoya University
• 著者所属(英): en
• 著者所属(英): Kyoto University
• 著者所属(英): en
• 著者所属(英): Kyoto University
• 著者所属(英): en
• 著者所属(英): Nagoya University
• 著者名: Yasuaki, Kobayashi; Shunsuke, Nagano; Yota, Otachi
• 著者名(英): Yasuaki, Kobayashi; Shunsuke, Nagano; Yota, Otachi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: For a connected graph G = (V, E) and s, t ∈ V, a non-separating s-t path is a path P between s and t such that the set of vertices of P does not separate G, that is, G - V (P) is connected. An s-t path is non-disconnected if G - E(P) is connected. The problems of finding shortest non-separating and non-disconnecting paths are both known to be NP-hard. In this paper, we consider the problems from the viewpoint of parameterized complexity. We show that the problem of finding a non-separating s-t path of length at most k is W[1]-hard parameterized by k, while the non-disconnecting counterpart is fixed-parameter tractable parameterized by k. We also consider the shortest non-separating path problem on several classes of graphs and show that this problem is NP-hard even on bipartite graphs, chordal graphs, and planar graphs. As for positive results, the shortest non-separating path problem is fixed-parameter tractable parameterized by k on planar graphs and polynomial-time solvable on chordal graphs if k is the shortest path distance between s and t.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: For a connected graph G = (V, E) and s, t ∈ V, a non-separating s-t path is a path P between s and t such that the set of vertices of P does not separate G, that is, G - V (P) is connected. An s-t path is non-disconnected if G - E(P) is connected. The problems of finding shortest non-separating and non-disconnecting paths are both known to be NP-hard. In this paper, we consider the problems from the viewpoint of parameterized complexity. We show that the problem of finding a non-separating s-t path of length at most k is W[1]-hard parameterized by k, while the non-disconnecting counterpart is fixed-parameter tractable parameterized by k. We also consider the shortest non-separating path problem on several classes of graphs and show that this problem is NP-hard even on bipartite graphs, chordal graphs, and planar graphs. As for positive results, the shortest non-separating path problem is fixed-parameter tractable parameterized by k on planar graphs and polynomial-time solvable on chordal graphs if k is the shortest path distance between s and t.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2022-AL-187, 号 5, p. 1-5, 発行日 2022-03-07
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会