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

This work studies the parameterized complexity of finding secluded solutionsto classical combinatorial optimization problems on graphs such as findingminimum s-t separators, feedback vertex sets, dominating sets, maximumindependent sets, and vertex deletion problems for hereditary graph properties: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 hasapplications in secure routing and community detection.Comment: Compared to the previous version, this version additionally shows that Small Secluded s-t-Separator is fixed-parameter tractable parameterized by the combination of the solution size and the open neighborhood size (Theorem 3.5