License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2022.6
URN: urn:nbn:de:0030-drops-168041
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16804/
Go to the corresponding LIPIcs Volume Portal

Abhinav, Ankit ; Bandopadhyay, Susobhan ; Banik, Aritra ; Kobayashi, Yasuaki ; Nagano, Shunsuke ; Otachi, Yota ; Saurabh, Saket

Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets

pdf-format:
LIPIcs-MFCS-2022-6.pdf (0.9 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{abhinav_et_al:LIPIcs.MFCS.2022.6,
  author =	{Abhinav, Ankit and Bandopadhyay, Susobhan and Banik, Aritra and Kobayashi, Yasuaki and Nagano, Shunsuke and Otachi, Yota and Saurabh, Saket},
  title =	{{Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{6:1--6:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16804},
  URN =		{urn:nbn:de:0030-drops-168041},
  doi =		{10.4230/LIPIcs.MFCS.2022.6},
  annote =	{Keywords: Non-separating path, Parameterized complexity}
}

Keywords: Non-separating path, Parameterized complexity
Collection: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Issue Date: 2022
Date of publication: 22.08.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI