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

点击翻译按钮获取中文摘要

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.