## René van Bevern, Till Fluschnik, George B. Mertzios, Hendrik Molter, Manuel
Sorge, and Ondřej Suchý.
Finding secluded places of special interest in graphs.
In *Proceedings of the 11th International Symposium on
Parameterized and Exact Computation (IPEC'16), Aarhus, Denmark*, volume 63 of
*Leibniz International Proceedings in Informatics (LIPIcs)*, pages
5:1–5:16. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017.

Finding a vertex subset in a graph that satisfies a
certain property is one of the most-studied topics
in algorithmic graph theory. The focus herein is
often on minimizing or maximizing the size of the
solution, that is, the size of the desired vertex
set. In several applications, however, we also want
to limit the "exposure" of the solution to the rest
of the graph. This is the case, for example, when
the solution represents persons that ought to deal
with sensitive information or a segregated
community. In this work, we thus explore the
(parameterized) complexity of finding such secluded
vertex subsets for a wide variety of properties that
they shall fulfill. More precisely, we study the
constraint that the (open or closed) neighborhood of
the solution shall be bounded by a parameter and the
influence of this constraint on the complexity of
minimizing separators, feedback vertex sets, F-free
vertex deletion sets, dominating sets, and the
maximization of independent sets.

[ bib |
DOI |
http ]
Back

*This file was generated by
bibtex2html 1.98.*