Analysis of counting and enumeration problems pertaining to physically realistic biological systems

我们已经成功地完成了对ISGCI数据库中所有类图的精确计数、近似计数和枚举Hamilton圈、Hamilton路径、简单圈和简单路径的计算复杂性的充分表征，其中复杂性结果已知用于Hamilton圈判定问题（1，246类）或Hamilton路径判定问题（1，214类）。我们在该出版物中报告了部分结果，其中我们使用新的技术来证明4-正则4-顶点连通平面图上的硬度结果。为了理解这项工作的意义，我们可以观察到这类图的所有顶点对都由一条哈密顿路连接，而且可以在线性时间中找到哈密顿圈。这使得相关的汉密尔顿循环计数问题非常接近多项式时间可处理的整数计数问题和Valiant类#P完整的整数计数问题之间奇怪的尖锐边界。因此，可以合理地说，我们的发现不一定是那些图理论或理论计算机科学界所期望的。关于开放猜想的结果，我们报告了完全新颖的使用奇偶计数问题来约束巴内特著名的1969年猜想。我们还表明，三个著名的Sheehan，邦迪和杰克逊，和Fleischner是真的，当且仅当减少存在从#SAT的哈密尔顿循环决策问题。

We have successfully finished fully characterizing the computational complexity of exactly counting, approximately counting, and enumerating Hamiltonian cycles, Hamiltonian paths, simple cycles, and simple paths for all classes of graphs in the ISGCI database where complexity results are known for the Hamiltonian cycle decision problem (1,246 classes) or the Hamiltonian path decision problem (1,214 classes). We reported a part of the results in the publication, wherein we used novel techniques to prove hardness results on 4-regular 4-vertex-connected planar graphs. To understand the significance of this work, we can observe for this class of graphs that all pairs of vertices are connected by a Hamiltonian path, and moreover, that Hamiltonian cycles can be found in linear time. This places the relevant Hamiltonian cycle counting problem very close the oddly sharp boundary between integer counting problems that are polynomial time tractable and those that are complete for Valiant's class #P. Accordingly, it is reasonable to state that our findings were not necessarily those that were expected by the graph theoretic or theoretical computer science communities.Concerning results for open conjectures, we report the entirely novel use of parity counting problems to constrain Barnette's famous 1969 conjecture. We also show that three well-known open conjectures of Sheehan, Bondy & Jackson, and Fleischner are true if and only if a reduction exists from #SAT to the Hamiltonian cycle decision problem.