Parameterized Complexity of Safe Set
| Autor: | Michael Lampis, Ioannis Katsikarelis, Tesshu Hanaka, Rémy Belmonte, Yota Otachi, Hirotaka Ono |
|---|---|
| Přispěvatelé: | autre, AUTRES, Chuo University (Chuo University), Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Department of Mathematical Informatics, The University of Tokyo (UTokyo), Kumamoto Gakuen University, Gakuen University, University of Electro-Communications [Tokyo] (UEC), Nagoya University |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
General Computer Science 0211 other engineering and technologies Vertex cover Parameterized complexity Pathwidth 0102 computer and information sciences 02 engineering and technology Computational Complexity (cs.CC) 01 natural sciences Theoretical Computer Science Vulnerability parameter Combinatorics Set (abstract data type) Polynomial kernel Clique-width 0202 electrical engineering electronic engineering information engineering [INFO]Computer Science [cs] ComputingMilieux_MISCELLANEOUS Mathematics Connected component 021103 operations research Safe set Double exponential function 020206 networking & telecommunications Graph Computer Science Applications Computer Science - Computational Complexity Computational Theory and Mathematics 010201 computation theory & mathematics 020201 artificial intelligence & image processing Geometry and Topology |
| Zdroj: | Algorithms and Complexity, Proceedings 11th International Conference on Algorithms and Complexity (CIAC 2019) 11th International Conference on Algorithms and Complexity (CIAC 2019), May 2019, Rome, Italy. pp.38-49, ⟨10.1007/978-3-030-17402-6_4⟩ Journal of Graph Algorithms and Applications Journal of Graph Algorithms and Applications, Brown University, 2020, 24 (3), pp.215-245. ⟨10.7155/jgaa.00528⟩ Lecture Notes in Computer Science ISBN: 9783030174019 CIAC |
| ISSN: | 1526-1719 |
| DOI: | 10.1007/978-3-030-17402-6_4⟩ |
| Popis: | 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 \(G - S\). 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 \(\mathsf {pw}\) and cannot be solved in time \(n^{o(\mathsf {pw})}\) unless the ETH is false, (2) it admits no polynomial kernel parameterized by the vertex cover number \(\mathsf {vc}\) unless \(\mathrm {PH} = \varSigma ^{\mathrm {p}}_{3}\), but (3) it is fixed-parameter tractable (FPT) when parameterized by the neighborhood diversity \(\mathsf {nd}\), and (4) it can be solved in time \(n^{f(\mathsf {cw})}\) for some double exponential function f where \(\mathsf {cw}\) is the clique-width. We also present (5) a faster FPT algorithm when parameterized by solution size. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|