• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Theory and application of models of computation >A Dichotomy for k-Regular Graphs with {0,1}-Vertex Assignments and Real Edge Functions
【24h】

A Dichotomy for k-Regular Graphs with {0,1}-Vertex Assignments and Real Edge Functions

机译：具有{0,1}-顶点分配和实边功能的k正则图的二分法

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

摘要

We prove a complexity dichotomy theorem for a class of Holant Problems over k-regular graphs, for any fixed k. These problems can be viewed as graph homomorphisms from an arbitrary k-regular input graph G to the weighted two vertex graph on {0,1} denned by a symmetric function h. We completely classify the computational complexity of this problem. We show that there are exactly the following alternatives, for any given h. Depending on h, over k-regular graphs: Either (1) the problem is #P-hard even for planar graphs; or (2) the problem is #P-hard for general (non-planar) graphs, but solvable in polynomial time for planar graphs; or (3) the problem is solvable in polynomial time for general graphs. The dependence on h is an explicit criterion. Furthermore, we show that in case (2) the problem is solvable in polynomial time over k-regular planar graphs, by exactly the theory of holographic algorithms using matchgates.
机译：我们证明了对于任意固定k的一类关于k正则图的Holant问题的复杂性二分法定理。这些问题可以看作是图形同态，从任意k正则输入图G到由对称函数h限定的{0,1}上的加权两个顶点图。我们将这个问题的计算复杂度完全分类。我们表明，对于任何给定的h，都存在以下完全正确的选择。根据h，在k个正则图上：（1）即使对于平面图，问题也是＃P-hard；或（2）对于一般（非平面）图，该问题是＃P-hard，但对于平面图，该问题在多项式时间内可解决；或（3）对于一般图形，该问题可以在多项式时间内解决。对h的依赖是一个明确的标准。此外，我们证明，在情况（2）中，通过使用匹配门的全息算法的理论，该问题在k正则平面图的多项式时间内是可解决的。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号