Joint Colloquium: Filar -- The Hamiltonian Cycle Problem, Markov Chains and Optimization

Speaker: Prof. Jerzy A. Filar (Flinders University). Link: 

http://www.flinders.edu.au/people/jerzy.filar

Time: Friday, Oct. 21, 2:30--3:30PM, 2011

Room: Carslaw Lecture Theatre 175, Syd. U.  

(HERE IS A SMALL CHANGE!!!!) 

Lunch (COMBINED WITH ALGEBRA SEMINAR LUNCH): meet around 
1PM (INSTEAD OF 12:30PM) at the second floor entrance to 
Carslaw Building and then go to Grandstand (INSTEAD OF 
the Law School restaurant).   

-----------------------------------------------------

Title: the Hamiltonian Cycle Problem, Markov Chains 
and Optimization

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.

-----------------------------------------------------