2026-07-26T00:39:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16804 2024-03-06T10:58:22Z ddc:004 open_access

Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets Abhinav, Ankit Bandopadhyay, Susobhan Banik, Aritra Kobayashi, Yasuaki Nagano, Shunsuke Otachi, Yota Saurabh, Saket Non-separating path Parameterized complexity 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 P is non-disconnecting 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 (FPT) 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, split graphs, and planar graphs. As for positive results, the shortest non-separating path problem is FPT parameterized by k on planar graphs and on unit disk graphs (where no s, t is given). Further, we give a polynomial-time algorithm on chordal graphs if k is the distance of the shortest path between s and t. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ankit Abhinav and Susobhan Bandopadhyay and Aritra Banik and Yasuaki Kobayashi and Shunsuke Nagano and Yota Otachi and Saket Saurabh 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.6 urn:nbn:de:0030-drops-168041 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.6 eng https://creativecommons.org/licenses/by/4.0/legalcode