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

我们已经成功地完成了ISGCI数据库中所有类图的精确计数、近似计数和枚举哈密顿循环、哈密顿路径、简单循环和简单路径的计算复杂性的完整表征，其中复杂性结果已知为哈密顿循环决策问题（1,246类）或哈密顿路径决策问题（1,214类）。我们在出版物中报告了部分结果，其中我们使用新技术证明了4-规则4顶点连接平面图上的硬度结果。为了理解这项工作的意义，我们可以观察到，对于这类图，所有顶点对都由哈密顿路径连接，而且，哈密顿循环可以在线性时间内找到。这使得相关的哈密顿循环计数问题非常接近整数计数问题（多项式时间可处理的整数计数问题）与Valiant的类#P完整的整数计数问题之间奇怪的尖锐边界。因此，可以合理地说，我们的发现不一定是图论或理论计算机科学界所期望的。关于开放猜想的结果，我们报告了奇偶计数问题的全新使用，以约束Barnette著名的1969猜想。我们还证明了三个著名的Sheehan， Bondy & Jackson和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.