Parameterized Complexity of Safe Set

Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Hirotaka Ono, Yota Otachi

研究成果: 書籍/レポート タイプへの寄稿会議への寄与

3 被引用数 (Scopus)

抄録

In this paper we study the problem of finding a small safe set S in a graph G, i.e. a non-empty set of vertices such that no connected component of G[S] is adjacent to a larger component in. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that (1) the problem is W[2]-hard when parameterized by the pathwidth and cannot be solved in time unless the ETH is false, (2) it admits no polynomial kernel parameterized by the vertex cover number unless, but (3) it is fixed-parameter tractable (FPT) when parameterized by the neighborhood diversity, and (4) it can be solved in time for some double exponential function f where is the clique-width. We also present (5) a faster FPT algorithm when parameterized by solution size.

本文言語英語
ホスト出版物のタイトルAlgorithms and Complexity - 11th International Conference, CIAC 2019, Proceedings
編集者Pinar Heggernes
出版社Springer Verlag
ページ38-49
ページ数12
ISBN(印刷版)9783030174019
DOI
出版ステータス出版済み - 2019
外部発表はい
イベント11th International Conference on Algorithms and Complexity, CIAC 2019 - Rome, イタリア
継続期間: 5月 27 20195月 29 2019

出版物シリーズ

名前Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
11485 LNCS
ISSN(印刷版)0302-9743
ISSN(電子版)1611-3349

会議

会議11th International Conference on Algorithms and Complexity, CIAC 2019
国/地域イタリア
CityRome
Period5/27/195/29/19

!!!All Science Journal Classification (ASJC) codes

  • 理論的コンピュータサイエンス
  • コンピュータサイエンス一般

フィンガープリント

「Parameterized Complexity of Safe Set」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル