Back to Search
Start Over
Parameterized Complexity of Safe Set
- Source :
- 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
- Publication Year :
- 2019
- Publisher :
- HAL CCSD, 2019.
-
Abstract
- 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.
- Subjects :
- 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
Subjects
Details
- Language :
- English
- ISBN :
- 978-3-030-17401-9
- ISSN :
- 15261719
- ISBNs :
- 9783030174019
- Database :
- OpenAIRE
- Journal :
- 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
- Accession number :
- edsair.doi.dedup.....7b8497e3a41c3a66724823544eb1a251