Safe sets in graphs: Graph classes and structural parameters

Raquel Águeda (), Nathann Cohen (), Shinya Fujita (), Sylvain Legay (), Yannis Manoussakis (), Yasuko Matsui (), Leandro Montero (), Reza Naserasr (), Hirotaka Ono (), Yota Otachi (), Tadashi Sakuma (), Zsolt Tuza () and Renyu Xu ()
Additional contact information
Raquel Águeda: Universidad de Castilla-La Mancha
Nathann Cohen: University Paris-Sud
Shinya Fujita: Yokohama City University
Sylvain Legay: University Paris-Sud
Yannis Manoussakis: University Paris-Sud
Yasuko Matsui: Tokai University
Leandro Montero: University Paris-Sud
Reza Naserasr: University Paris-Diderot
Hirotaka Ono: Nagoya University
Yota Otachi: Kumamoto University
Tadashi Sakuma: Yamagata University
Zsolt Tuza: MTA Rényi Institute
Renyu Xu: Shandong University

Journal of Combinatorial Optimization, 2018, vol. 36, issue 4, No 7, 1242 pages

Abstract: Abstract A safe set of a graph $$G=(V,E)$$ G = ( V , E ) is a non-empty subset S of V such that for every component A of G[S] and every component B of $$G[V {\setminus } S]$$ G [ V \ S ] , we have $$|A| \ge |B|$$ | A | ≥ | B | 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.

Keywords: Safe set; Graph algorithm; Graph class; Parameterized complexity (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-017-0205-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:36:y:2018:i:4:d:10.1007_s10878-017-0205-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-017-0205-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().