...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >Turing Kernelization for Finding Long Paths in Graphs Excluding a Topological Minor
【24h】

Turing Kernelization for Finding Long Paths in Graphs Excluding a Topological Minor

机译：图灵内核化，用于在图形中查找不包括拓扑次要项的长路径

获取原文
   

获取外文期刊封面封底 >>

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

摘要

The notion of Turing kernelization investigates whether a polynomial-time algorithm can solve an NP-hard problem, when it is aided by an oracle that can be queried for the answers to bounded-size subproblems. One of the main open problems in this direction is whether k-PATH admits a polynomial Turing kernel: can a polynomial-time algorithm determine whether an undirected graph has a simple path of length k, using an oracle that answers queries of size k^{O(1)}? We show this can be done when the input graph avoids a fixed graph H as a topological minor, thereby significantly generalizing an earlier result for bounded-degree and K_{3,t}-minor-free graphs. Moreover, we show that k-PATH even admits a polynomial Turing kernel when the input graph is not H-topological-minor-free itself, but contains a known vertex modulator of size bounded polynomially in the parameter, whose deletion makes it so. To obtain our results, we build on the graph minors decomposition to show that any H-topological-minor-free graph that does not contain a k-path has a separation that can safely be reduced after communication with the oracle.
机译：Turing内核化的概念研究了多项式时间算法是否可以解决NP-hard问题，如果该算法可以通过可查询有界子问题的答案的预言进行辅助。此方向上的主要开放问题之一是k-PATH是否允许多项式Turing内核：多项式时间算法是否可以使用回答大小为k ^ {的查询的oracle，来确定无向图是否具有长度为k的简单路径。 O（1）}？我们表明，当输入图避免将固定图H作为拓扑次要图时，可以做到这一点，从而显着推广了有界度图和无K_ {3，t}次图的早期结果。此外，我们表明，当输入图本身并非非H-拓扑次要形式时，k-PATH甚至允许多项式Turing内核，但在参数中包含一个已知的多项式大小为顶点的顶点调制器，其删除使得它成为事实。为了获得我们的结果，我们在图次要分解的基础上证明，任何不包含k路径的H拓扑次要无图，其间距可以在与甲骨文通信后安全地减小。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号