Complexity of secure sets

DOI10.1007/S00453-017-0358-5zbMATH Open1391.68047DBLPjournals/algorithmica/BliemW18arXiv1411.6549OpenAlexW2749113736WikidataQ55312596 ScholiaQ55312596MaRDI QIDQ722534FDOQ722534

Authors: Bernhard Bliem, Stefan Woltran 

Publication date: 26 July 2018

Published in: Algorithmica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• 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

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)