Research Article: Complexity of Secure Sets

Date Published: August 14, 2017

Publisher: Springer US

Author(s): Bernhard Bliem, Stefan Woltran.

http://doi.org/10.1007/s00453-017-0358-5

Abstract

A secure set S in a graph is defined as a set of vertices such that for any documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}\$\$Xsubseteq S\$\$end{document}X⊆S 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 documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}\$\$mathrm {text {co-}NP}\$\$end{document}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 documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}\$\$mathrm {Sigma ^P_2}\$\$end{document}Σ2P-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 documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}\$\$mathrm {W[1]}\$\$end{document}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 documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}\$\$mathrm {XP}\$\$end{document}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.

Partial Text

The objective of many problems that can be modeled as graphs is finding a group of vertices that together satisfy some property. In this respect, one of the concepts that has been quite extensively studied [31] is the notion of a defensive alliance [20], which is a set of vertices such that for each element v at least half of its neighbors are also in the alliance. The name “defensive alliance” stems from the intuition that the neighbors of such an element v that are also in the alliance can help out in case v is attacked by its other neighbors. Notions like this can be applied to finding groups of nations, companies or individuals that depend on each other, but also to more abstract situations like finding groups of websites that form communities [18].

All graphs are undirected and simple unless stated otherwise. We denote the set of vertices and edges of a graph G by V(G) and E(G), respectively. We denote an undirected edge between vertices u and v as (u, v) or equivalently (v, u). It will be clear from the context whether an edge (u, v) is directed or undirected. Given a graph G, the open neighborhood of a vertex documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}\$\$v in V(G)\$\$end{document}v∈V(G), denoted by documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}\$\$N_G(v)\$\$end{document}NG(v), is the set of all vertices adjacent to v, and documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}\$\$N_G[v] = N_G(v) cup {v}\$\$end{document}NG[v]=NG(v)∪{v} is called the closed neighborhood of v. Let documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}\$\$S subseteq V(G)\$\$end{document}S⊆V(G). We abuse notation by writing documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}\$\$N_G(S)\$\$end{document}NG(S) and documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}\$\$N_G[S]\$\$end{document}NG[S] to denote documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}\$\$bigcup _{v in S} N_G(v)\$\$end{document}⋃v∈SNG(v) and documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}\$\$bigcup _{v in S} N_G[v]\$\$end{document}⋃v∈SNG[v], respectively. If it is clear from the context which graph is meant, we write documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}\$\$N(cdot )\$\$end{document}N(·) and documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}\$\$N_G(cdot )\$\$end{document}NG(·) and documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}\$\$N_G[cdot ]\$\$end{document}NG[·], respectively.

This section is devoted to proving the following theorem:

In this section we study the parameterized complexity of the Secure Set problem when treewidth is the parameter.

In this work, we have solved a complexity problem in graph theory that, to the best of our knowledge, has remained open since the introduction of secure sets [11] in 2007. We have shown that the problem of deciding whether, for a given graph G and integer k, G possesses a non-empty secure set of size at most k is documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}\$\$mathrm {Sigma ^P_2}\$\$end{document}Σ2P-complete. We moreover obtained documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}\$\$mathrm {Sigma ^P_2}\$\$end{document}Σ2P-completeness for seven further variants of this problem.

Source:

http://doi.org/10.1007/s00453-017-0358-5