Bliem Bernhard, Woltran Stefan
Institute of Information Systems 184/2, TU Wien, Favoritenstrasse 9-11, 1040 Vienna, Austria.
Algorithmica. 2018;80(10):2909-2940. doi: 10.1007/s00453-017-0358-5. Epub 2017 Aug 14.
A secure set in a graph is defined as a set of vertices such that for any the majority of vertices in the neighborhood of belongs to . It is known that deciding whether a set is secure in a graph is -complete. However, it is still open how this result contributes to the actual complexity of deciding whether for a given graph and integer , a non-empty secure set for of size at most exists. In this work, we pinpoint the complexity of this problem by showing that it is -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 -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 , 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.
图中的安全集被定义为一组顶点，使得对于任意顶点，其邻域中的大多数顶点都属于该集合。已知判定一个集合在图中是否为安全集是NP完全问题。然而，对于给定的图(G)和整数(k)，判定是否存在大小至多为(k)的非空安全集，该结果如何影响此判定的实际复杂度仍是未解决的问题。在这项工作中，我们通过证明它是W[2]完全问题来确定该问题的复杂度。此外，到目前为止，该问题尚未进行考虑结构参数的参数化复杂度分析。在当前工作中，我们证明当以树宽为参数时，该问题是W[2]难的。这很令人惊讶，因为已知当以解的大小为参数时该问题是固定参数可处理的，并且满足此属性的“子集问题”通常对于有界树宽也倾向于是固定参数可处理的。最后，我们通过证明其属于W[2]给出一个上界，并且我们给出一个肯定性结果，即一个用于检查给定集合在有界树宽图上是否安全的固定参数可处理算法。
