Safe sets in graphs: Graph classes and structural parameters

Águeda, R. and Cohen, N. and Fujita, S. and Legay, S. and Manoussakis, Y. and Tuza, Zsolt (2018) Safe sets in graphs: Graph classes and structural parameters. JOURNAL OF COMBINATORIAL OPTIMIZATION, 36 (4). pp. 1221-1242. ISSN 1382-6905

Text Agueda2018_Article_SafeSetsInGraphsGraphClassesAn.pdf Restricted to Registered users only Download (1MB) | Request a copy

Abstract

A safe set of a graph (Formula presented.) is a non-empty subset S of V such that for every component A of G[S] and every component B of (Formula presented.), we have (Formula presented.) whenever there exists an edge of G between A and B. In this paper, we show that a minimum safe set can be found in polynomial time for trees. We then further extend the result and present polynomial-time algorithms for graphs of bounded treewidth, and also for interval graphs. We also study the parameterized complexity. We show that the problem is fixed-parameter tractable when parameterized by the solution size. Furthermore, we show that this parameter lies between the tree-depth and the vertex cover number. We then conclude the paper by showing hardness for split graphs and planar graphs. © 2017 Springer Science+Business Media, LLC, part of Springer Nature

Actions (login required)

Edit Item