Complexity of secure sets

DOI10.1007/S00453-017-0358-5MaRDI QIDQ722534zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Bernhard Bliem, Stefan Woltran

Publication date 26 July 2018

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1411.6549

zbMATH Keywords

treewidthparameterized complexitycomplexity analysisparameterized algorithmssecure set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: A secure set $S$ in a graph is defined as a set of vertices such that for any $XsubseteqS$ the majority of vertices in the neighborhood of $X$ belongs to $S$. It is known that deciding whether a set $S$ is secure in a graph is co-NP-complete. However, it is still open how this result contributes to the actual complexity of deciding whether for a given graph $G$ and integer $k$, a non-empty secure set for $G$ of size at most $k$ exists. In this work, we pinpoint the complexity of this problem by showing that it is $Sigm{a}_2^P$-complete. Furthermore, the problem has so far not been subject to a parameterized complexity analysis that considers structural parameters. In the present work, we prove that the problem is $W[1]$-hard when parameterized by treewidth. This is surprising since the problem is known to be FPT when parameterized by solution size and "subset problems" that satisfy this property usually tend to be FPT for bounded treewidth as well. Finally, we give an upper bound by showing membership in XP, and we provide a positive result in the form of an FPT algorithm for checking whether a given set is secure on graphs of bounded treewidth.

Recommendations

• Complexity of secure sets
• Parameterized complexity of secure sets
• Secure set algorithms and complexity
• Computing secure sets in graphs using answer set programming
• Secure sets and their expansion in cubic graphs
• SECURE DOMINATING SETS AND SECURE DOMINATION POLYNOMIALS OF CYCLES
• On the communication complexity of secure computation
• The possible cardinalities of global secure sets in cographs
• The Exact Round Complexity of Secure Computation

Cites work

• scientific article; zbMATH DE number 5917571 (Why is no real title available?)
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 6862107 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• All structured programs have small tree width and good register allocation
• Capacitated Domination and Covering: A Parameterized Perspective
• Complexity of Finding Embeddings in a k-Tree
• Complexity of clique coloring and related problems
• Complexity of secure sets
• Generalizations of matched CNF formulas
• Global defensive alliances in graphs
• Global secure sets of grid-like graphs
• Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
• Graph minors. III. Planar tree-width
• Narrowness, pathwidth, and their application in natural language processing
• Parameterized algorithms
• Parameterized complexity of secure sets
• Parametrized complexity theory.
• Rooted secure sets of trees
• Security in graphs
• The D-FLAT system for dynamic programming on tree decompositions
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Treewidth computations. I: Upper bounds
• Treewidth. Computations and approximations

Cited in

(12)

• Secure sets and their expansion in cubic graphs
• Secret sets and applications
• Defensive alliances in graphs of bounded treewidth
• On the security number of the Cartesian product of graphs
• Complexity of secure sets
• scientific article; zbMATH DE number 7758317 (Why is no real title available?)
• Problems hard for treewidth but easy for stable gonality
• Secure set algorithms and complexity
• The possible cardinalities of global secure sets in cographs
• Parameterized complexity of safe set
• Parameterized complexity of secure sets
• Computing secure sets in graphs using answer set programming

Describes a project that uses

Uses Software

• ComputeTW

This page was built for publication: Complexity of secure sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q722534)