Back to Search
Start Over
The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
- Source :
- Discrete Optimzation 30:20-50, 2018
- Publication Year :
- 2016
-
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 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 has applications in secure routing and community detection.<br />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). To appear in Discrete Optimization
Details
- Database :
- arXiv
- Journal :
- Discrete Optimzation 30:20-50, 2018
- Publication Type :
- Report
- Accession number :
- edsarx.1606.09000
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1016/j.disopt.2018.05.002