Finding connected secluded subgraphs

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

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

Problems related to finding induced subgraphs satisfying given properties form one of the most studied areas within graph algorithms. However, 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 Π-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 Π, even when parameterized by k+t. We show that the situation changes when we are looking for a connected induced subgraph satisfying Π. In particular, we show that the CONNECTED SECLUDED Π-SUBGRAPH problem is FPT when parameterized by just t for many important graph properties Π.

Original languageEnglish
Pages (from-to)101-124
Number of pages24
JournalJournal of Computer and System Sciences
Volume113
DOIs
StatePublished - Nov 2020
Externally publishedYes

Keywords

  • Forbidden subgraphs
  • Parameterized complexity
  • Secluded subgraph

Fingerprint

Dive into the research topics of 'Finding connected secluded subgraphs'. Together they form a unique fingerprint.

Cite this