Counting Hamiltonian Cycles on Quartic 4-Vertex-Connected Planar Graphs
Tóm tắt
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$$.
Tài liệu tham khảo
Aldred, R.E.L., Thomassen, C.: On the maximum number of cycles in a planar graph. J. Graph Theory 57(3), 255–264 (2007)
Barish, R.D., Suyama, A.: Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs. In: Online collection of abstracts for the 20th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG3), pp. 129–130. http://www.jcdcgg.u-tokai.ac.jp/ (2017). Accessed 30 Sept 2017
Barish, R. D.: Personal communication (2017)
Bondy, J.A., Jackson, B.: Vertices of small degree in uniquely Hamiltonian graphs. J. Combin. Theory Ser. B 74(2), 265–275 (1998)
Briquel, I., Koiran, P.: A dichotomy theorem for polynomial evaluation. In: Proceedings of the 34th annual symposium on Mathematical Foundations of Computer Science (MFCS), pp. 187–198 (2009)
Chiba, N., Nishizeki, T.: The Hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs. J. Algorithms 10(2), 187–211 (1989)
Dyer, M., Goldberg, L.A., Greenhill, C., Jerrum, M.: The relative complexity of approximate counting problems. Algorithmica 38(3), 471–500 (2004)
Fleischner, H.: Uniquely Hamiltonian graphs of minimum degree 4. J. Graph Theory 75(2), 167–177 (2014)
Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237–267 (1976)
Garey, M.R., Johnson, D.S., Tarjan, R.E.: The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5(4), 704–714 (1976)
Karp, R. M., Luby, M.: Monte-Carlo algorithms for enumeration and reliability problems. In: Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS), pp. 56–64 (1983)
Liśkiewicz, M., Ogihara, M., Toda, S.: The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes. Theor. Comput. Sci. 304(1–3), 129–156 (2003)
Menger, K.: Zur allgemeinen kurventheorie. Fundamenta Mathematicae 10(1), 96–115 (1927)
Meredith, G.H.J.: Regular n-valent n-connected nonHamiltonian non-n-edge-colorable graphs. J. Combin. Theory Ser. B 14(1), 55–60 (1973)
Petersen, J.: Die theorie der regulären graphs. Acta Math. 15, 193–220 (1891)
Sheehan, J.: The multiplicity of Hamiltonian circuits in a graph. In: Recent Advances in Graph Theory. Proceedings of the 2nd Czechoslovak Symposium, Prague, 1974, pp. 477–480 (1975)
Steinitz, E.: Polyeder und raumeinteilungen. Encyklopädie der mathematischen Wissenschaften 3(part 1.2, B)), 1–139 (1922)
Tait, P.G.: Listing’s topologie. Philosophical Magazine (5th ser.) 17, 30–46 (1884)
Thomassen, C.: A theorem on paths in planar graphs. J. Graph Theory 7, 169–176 (1983)
Tutte, W.T.: On Hamiltonian circuits. J. Lond. Math. Soc. 21, 98–101 (1946)
Tutte, W.T.: A theorem on planar graphs. Trans. Am. Math. Soc. 82, 99–116 (1956)
Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8(2), 189–201 (1979)
Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410–421 (1979)
Whitney, H.: A theorem on graphs. Ann. Math. 32(2), 378–390 (1931)
Zanko, V.: \(\#P\)-completeness via many-one reductions. Int. J. Found. Comput. Sci. 2(1), 77–82 (1991)
Zuckerman, D.: On unapproximable versions of NP-complete problems. SIAM J. Comput. 25(6), 1293–1304 (1996)