• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >The complexity of finding harmless individuals in social networks
【24h】

The complexity of finding harmless individuals in social networks

机译：在社交网络中寻找无害个人的复杂性

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this paper, we introduce a domination-related problem called Harmless Set: given a graph G = (V, E), a threshold function t: V → N and an integer k, find a subset of vertices V′ ? V of size at least k such that every vertex v in V has less than t(v) neighbors in V′.Westudy its parameterized complexity and the approximation of the associated maximization problem. When the parameter is k, we show that the problem is W[2]-complete in general and W[1]-complete if all thresholds are bounded by a constant. Moreover, we prove that, if P ?= NP, the maximization version is not n ~(1/2?ε)-approximable for any ε > 0 even when all thresholds are at most two. When each threshold is equal to the degree of the vertex, we show that Harmless Set is fixed-parameter tractable for parameter k and the maximization version is APX-complete. We give a polynomial-time algorithm for graphs of bounded treewidth and a polynomial-time approximation scheme for planar graphs. Finally, we show that the parametric dual problem (n?k)-Harmless Set is fixed-parameter tractable for a large family of threshold functions.
机译：在本文中，我们介绍了一个与控制有关的问题，称为无害集：给定一个图G =（V，E），阈值函数t：V→N和整数k，找到顶点V'？的子集。 V的大小至少为k，因此V中的每个顶点v在V'中的邻居都少于t（v）个。对它的参数化复杂度和相关的最大化问题进行近似计算。当参数为k时，我们证明问题一般是W [2]-完全的，如果所有阈值都由常数限制，则问题是W [1]-完全的。而且，我们证明了，如果P≥NP，则即使所有阈值都为两个以上，对于任何ε＞ 0，最大值也不是n〜（1 /2πε）可近似的。当每个阈值等于顶点的度数时，我们表明无害集对于参数k是固定参数易处理的，并且最大化版本是APX完全的。我们给出了有界树宽图的多项式时间算法和平面图的多项式时间逼近方案。最后，我们证明了参数对偶问题（n？k）-无臂集对于较大的阈值函数族是固定参数可处理的。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号