...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >Parameterized Aspects of Strong Subgraph Closure
【24h】

Parameterized Aspects of Strong Subgraph Closure

机译：子图强闭合的参数化方面

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Motivated by the role of triadic closures in social networks, and the importance of finding a maximum subgraph avoiding a fixed pattern, we introduce and initiate the parameterized study of the Strong F-closure problem, where F is a fixed graph. This is a generalization of Strong Triadic Closure, whereas it is a relaxation of F-free Edge Deletion. In Strong F-closure, we want to select a maximum number of edges of the input graph G, and mark them as strong edges, in the following way: whenever a subset of the strong edges forms a subgraph isomorphic to F, then the corresponding induced subgraph of G is not isomorphic to F. Hence the subgraph of G defined by the strong edges is not necessarily F-free, but whenever it contains a copy of F, there are additional edges in G to destroy that strong copy of F in G.We study Strong F-closure from a parameterized perspective with various natural parameterizations. Our main focus is on the number k of strong edges as the parameter. We show that the problem is FPT with this parameterization for every fixed graph F, whereas it does not admit a polynomial kernel even when F =P_3. In fact, this latter case is equivalent to the Strong Triadic Closure problem, which motivates us to study this problem on input graphs belonging to well known graph classes. We show that Strong Triadic Closure does not admit a polynomial kernel even when the input graph is a split graph, whereas it admits a polynomial kernel when the input graph is planar, and even d-degenerate. Furthermore, on graphs of maximum degree at most 4, we show that Strong Triadic Closure is FPT with the above guarantee parameterization k - mu(G), where mu(G) is the maximum matching size of G. We conclude with some results on the parameterization of Strong F-closure by the number of edges of G that are not selected as strong.
机译：由于三合会闭包在社交网络中的作用以及寻找避免固定模式的最大子图的重要性，我们引入并启动了强F闭包问题的参数化研究，其中F是固定图。这是强三合会闭包的推广，而它是无F边删除的放松。在“强F闭包”中，我们要选择输入图G的最大边数，并通过以下方式将其标记为强边：每当强边的子集形成与F同构的子图时， G的诱导子图与F不是同构的。因此，由强边定义的G子图不一定是无F的，但是只要包含F的副本，G中就会有其他边来破坏F中的强F的副本。 G.我们从具有各种自然参数设置的参数化角度研究了强F闭包。我们主要关注强边的数量k作为参数。我们表明问题是对于每个固定图F都具有此参数化的FPT，而即使F = P_3，它也不容许多项式核。实际上，后一种情况等效于“强三合闭”问题，这促使我们对属于众所周知的图类的输入图进行研究。我们显示，即使输入图是分裂图，强三合会闭合也不允许多项式核，而当输入图是平面甚至d退化时，它就允许多项式核。此外，在最大度数为4的图形上，我们显示强三合会闭锁是FPT，具有上述保证参数化k-mu（G），其中mu（G）是G的最大匹配大小。我们得出以下结论：通过未选择为强的G边的数量对强F闭包进行参数化。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号