License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2017.18
URN: urn:nbn:de:0030-drops-85623
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8562/
Go to the corresponding LIPIcs Volume Portal

Golovach, Petr A. ; Heggernes, Pinar ; Lima, Paloma T. ; Montealegre, Pedro

Finding Connected Secluded Subgraphs

pdf-format:
LIPIcs-IPEC-2017-18.pdf (0.5 MB)

Abstract

Problems related to finding induced subgraphs satisfying given properties form one of the most studied areas within graph algorithms. Such problems have given rise to breakthrough results and led to development of new techniques both within the traditional P vs NP dichotomy and within parameterized complexity. The Pi-Subgraph problem asks whether an input graph contains an induced subgraph on at least k vertices satisfying graph property Pi. For many applications, it is desirable that the found subgraph has as few connections to the rest of the graph as possible, which gives rise to the Secluded Pi-Subgraph problem. Here, input k is the size of the desired subgraph, and input t is a limit on the number of neighbors this subgraph has in the rest of the graph. This problem has been studied from a parameterized perspective, and unfortunately it turns out to be W[1]-hard for many graph properties Pi, even when parameterized by k+t. We show that the situation changes when we are looking for a connected induced subgraph satisfying Pi. In particular, we show that the Connected Secluded Pi-Subgraph problem is FPT when parameterized by just t for many important graph properties Pi.

BibTeX - Entry

@InProceedings{golovach_et_al:LIPIcs:2018:8562,
  author =	{Petr A. Golovach and Pinar Heggernes and Paloma T. Lima and Pedro Montealegre},
  title =	{{Finding Connected Secluded Subgraphs}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{18:1--18:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Daniel Lokshtanov and Naomi Nishimura},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8562},
  URN =		{urn:nbn:de:0030-drops-85623},
  doi =		{10.4230/LIPIcs.IPEC.2017.18},
  annote =	{Keywords: Secluded subgraph, forbidden subgraphs, parameterized complexity}
}

Keywords: Secluded subgraph, forbidden subgraphs, parameterized complexity
Collection: 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Issue Date: 2018
Date of publication: 02.03.2018

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