New Analytical Perspectives on the Algorithmic Complexity of the Hamiltonian Cycle Problem

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

Hamiltonian Cycle Problem (HCP), known - in the complexity theory of algorithms -to be NP-hard is proposed for study, from three innovative, separate (yet related) analytical perspectives: singularly perturbed (controlled) Markov chains, that links the HCP with systems and control theories; parametric nonconvex optimization, that links HCP with fast interior point methods of modern optimization and the spectral approach based on a novel adaptation of Ihara-Selberg trace formula for regular graphs. Our mathematical approach to this archetypal complex problem of graph theory and discrete optimization promises to enhance the fundamental understanding - and ultimate "managibility" - of the underlying difficulty of HCP.