The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs

René van Bevern, Till Fluschnik, George B. Mertzios, Hendrik Molter, Manuel Sorge, Ondřej Suchý

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

Abstract

This work studies the parameterized complexity of finding secluded solutions to classical combinatorial optimization problems on graphs such as finding minimum s-t separators, feedback vertex sets, dominating sets, maximum independent sets, and vertex Herein, one searches not only to minimize or maximize the size of the solution, but also to minimize the size of its neighborhood. This restriction has applications in secure routing and community detection.

Original languageEnglish
Pages (from-to)20-50
Number of pages31
JournalDiscrete Optimization
Volume30
DOIs
Publication statusPublished - 1 Nov 2018

Keywords

  • Dominating set
  • Feedback vertex set
  • Neighborhood
  • Separator
  • Vertex deletion
  • KERNEL
  • SET
  • VERTEX
  • ENUMERATION
  • SEPARATION

Fingerprint

Dive into the research topics of 'The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs'. Together they form a unique fingerprint.

Cite this