We consider the Hamiltonian cycle problem (HCP) embedded in a controlled Markov decision process. In this setting, HCP reduces to an optimization problem on a set of Markov chains corresponding to a given graph. We prove that Hamiltonian cycles are minimizers for the trace of the fundamental matrix on a set of all stochastic transition matrices. In case of doubly stochastic matrices with symmetric linear perturbation, we show that Hamiltonian cycles minimize a diagonal element of a fundamental matrix for all admissible values of the perturbation parameter. In contrast to the previous work on this topic, our arguments are primarily based on probabilistic rather than algebraic methods.
- Singular perturbation
- Hamiltonian cycle
- Fundamental matrix
- Markov chains
Litvak, N., & Ejov, V. (2009). Markov chains and optimality of the Hamiltonian cycle. Mathematics of operations research, 34(1), 71-82. [10.1287/moor.1080.0351]. https://doi.org/10.1287/moor.1080.0351