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

Bevern, R.V.; Fluschnik, T.; Mertzios, G.B.; Molter, H.; Sorge, M.; Suchý, O.

Abstract

This work studies the parameterized complexity of finding secluded solutions to classical combinatorial optimization problems on graphs such as finding minimum - 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.

Citation

Bevern, R., Fluschnik, T., Mertzios, G., Molter, H., Sorge, M., & Suchý, O. (2018). The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs. Discrete Optimization, 30, 20-50. https://doi.org/10.1016/j.disopt.2018.05.002

• Journal Article Type: Article
• Acceptance Date: May 21, 2018
• Online Publication Date: Aug 16, 2018
• Publication Date: Nov 1, 2018
• Deposit Date: May 22, 2018
• Publicly Available Date: Aug 16, 2019
• Journal: Discrete Optimization
• Print ISSN: 1572-5286
• Electronic ISSN: 1873-636X
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 30
• Pages: 20-50
• DOI: https://doi.org/10.1016/j.disopt.2018.05.002
• Public URL: https://durham-repository.worktribe.com/output/1358452
• Related Public URLs: https://arxiv.org/abs/1606.09000