Counting Hamiltonian Cycles on Quartic 4-Vertex-Connected Planar Graphs

We show that counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs is \(\#P\)-complete under many-one counting (“weakly parsimonious”) reductions, and that no Fully Polynomial-time Randomized Approximation Scheme (FPRAS) can exist for this integer counting problem unless \(NP = RP\).