• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >Two edge modification problems without polynomial kernels
【24h】

Two edge modification problems without polynomial kernels

机译：没有多项式内核的两个边缘修改问题

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

摘要

Given a graph G and an integer k, the Π Edge Completion/Editing/Deletion problem asks whether it is possible to add, edit, or delete at most k edges in G such that one obtains a graph that fulfills the property Π. Edge modification problems have received considerable interest from a parameterized point of view. When parameterized by k, many of these problems turned out to be fixed-parameter tractable and some are known to admit polynomial kernelizations, i.e., efficient preprocessing with a size guarantee that is polynomial in k. This paper answers an open problem posed by Cai (IWPEC 2006) [11], namely, whether the Π Edge Deletion problem, parameterized by the number of deletions, admits a polynomial kernelization when Π can be characterized by a finite set of forbidden induced subgraphs. We answer this question negatively based on the framework for kernelization lower bounds of Bodlaender et al. (ICALP 2008, JCSS 2009) [15] and Fortnow and Santhanam (STOC 2008, JCSS 2011) [16]. We present a graph H on seven vertices such that H-free Edge Deletion and H-free Edge Editing do not admit polynomial kernelizations, unless NPa??coNP/poly. The application of the framework is not immediate and requires a lower bound for a Not-1-in-3 SAT problem that may be of independent interest.
机译：给定一个图G和一个整数k，“ Edge边完成/编辑/删除”问题询问是否有可能在G中最多添加，编辑或删除k个边，从而获得满足特性的图。从参数化的角度来看，边缘修改问题引起了极大的兴趣。当用k进行参数化时，许多问题证明是固定参数可处理的，并且已知一些问题允许多项式核化，即有效的预处理，且大小保证是k的多项式。本文回答了Cai（IWPEC 2006）提出的一个开放性问题，即由删减次数参数化的Edge边删除问题是否允许a可以由有限的一组禁止的诱导子图来表征时是否允许多项式核化。 。我们基于Bodlaender等人的内核化下限框架否定地回答了这个问题。 （ICALP 2008，JCSS 2009）[15]和Fortnow和Santhanam（STOC 2008，JCSS 2011）[16]。我们在七个顶点上给出一个图H，使得无H边删除和无H边编辑不允许多项式核化，除非NPa ?? coNP / poly。该框架的应用不是即时的，需要对Not-in-3 SAT问题（可能具有独立利益）下限。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号