• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE Annual Symposium on Foundations of Computer Science >The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems
【24h】

The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems

机译：计数边缘着色的复杂性和某些高域Holant问题的二分法

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

摘要

We show that an effective version of Siegel's Theorem on finiteness of integer solutions for a specific algebraic curve and an application of elementary Galois theory are key ingredients in a complexity classification of some Holant problems. These Holant problems, denoted by Holant(f), are defined by a symmetric ternary function f that is invariant under any permutation of the k >= 3 domain elements. We prove that Holant(f) exhibits a complexity dichotomy. The hardness, and thus the dichotomy, holds even when restricted to planar graphs. A special case of this result is that counting edge k-colorings is #P-hard over planar 3-regular multigraphs for all k >= 3. In fact, we prove that counting edge k-colorings is #P-hard over planar r-regular multigraphs for all k >= r >= 3. The problem is polynomial-time computable in all other parameter settings. The proof of the dichotomy theorem for Holant(f) depends on the fact that a specific polynomial p(x, y) has an explicitly listed finite set of integer solutions, and the determination of the Galois groups of some specific polynomials. In the process, we also encounter the Tutte polynomial, medial graphs, Eulerian partitions, Puiseux series, and a certain lattice condition on the (logarithm of) the roots of polynomials.
机译：我们表明，针对特定代数曲线的整数解有限性的Siegel定理的有效版本以及基本Galois理论的应用是某些Holant问题的复杂度分类的关键要素。由Holant（f）表示的这些Holant问题由对称三元函数f定义，该对称三元函数在k> = 3域元素的任何排列下均不变。我们证明Holant（f）表现出复杂性二分法。即使限于平面图，也保持硬度，从而保持二分法。此结果的一个特殊情况是，对于所有k> = 3，在平面3个正则多图上计算边缘k着色是＃P-hard。实际上，我们证明在平面r上计算边缘k-着色是＃P-hard。所有k> = r> = 3的正则多重图。问题是在所有其他参数设置中可以多项式时间计算。 Holant（f）二分法定理的证明取决于以下事实：特定的多项式p（x，y）具有明确列出的有限整数解集，以及某些特定多项式的Galois组的确定。在此过程中，我们还遇到了Tutte多项式，中间图，欧拉分区，Puiseux级数以及多项式根（的对数）上的某些晶格条件。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号