The Hamiltonian Cycle Problem, Markov Chains and Optimization

by Professor Jerzy A. Filar

Institution: Flinders University
Date: Mon 18th March 2013
Time: 9:00 AM
Location: Room 309, Doug McDonell Building

Abstract: We consider the famous Hamiltonian cycle problem (HCP) embedded in a Markov decision process (MDP). More specifically, we consider the HCP as an optimization problem over the space of occupational measures induced by the MDP’s stationary policies. In recent years, this approach to the HCP has led to a number of alternative formulations and algorithmic approaches involving researchers from a number of countries. In this lecture we focus on a specific embedding due to E. Feinberg from SUNY at Stony Brook. The latter leads to a suitably constructed parametrized polytope of discounted occupational measures that can be used as a domain where Hamiltonian solutions can be sought. It is known that whenever a given graph possesses Hamiltonian cycles, these correspond to certain extreme points of that polytope. It can be demonstrated that a relatively small number of additional constraints and a judicious choice of the value of the discount parameter can ensure that Hamiltonian solutions are no longer rare among extreme points of this modified sub-polytope of occupational measures. The latter observation leads to a promising random walk algorithm on the extreme points of that sub-polytope. We present a conjecture concerning the algorithmic complexity of this algorithm. In addition, we consider the limiting - parameter free - polyhedral region that can serve as a basis for determining non-Hamiltonicity of cubic graphs. Numerical results indicate that determining non-Hamiltonicity of a great majority of non-Hamiltonian cubic graphs is likely to be a problem of polynomial complexity despite the fact that HCP is known to be NP-complete already for cubic graphs.

For More Information: This is a joint seminar with the Applied Probability Group.

To find the location of the Doug McDonell building, click:

http://maps.unimelb.edu.au/parkville/building/168