2024-02-24T08:47:15Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:002173532023-04-27T10:00:04Z01164:02592:10824:10900
Finding shortest non-separating and non-disconnecting pathsFinding shortest non-separating and non-disconnecting pathsenghttp://id.nii.ac.jp/1001/00217245/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=217353&item_no=1&attribute_id=1&file_no=1Copyright (c) 2022 by the Information Processing Society of JapanKyoto UniversityKyoto UniversityNagoya UniversityYasuaki, KobayashiShunsuke, NaganoYota, OtachiFor 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.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.AN1009593X研究報告アルゴリズム（AL）2022-AL-1875152022-03-072188-85662022-03-03