Hamiltonian cycle problem and Markov chains. (Q663172)

This research monograph summarizes a line of research that maps certain classical problems of discrete mathematics and operations research -- such as the Hamiltonian cycle (HCP) and the Travelling Salesman (TSP) problems -- into convex domains where continuum analysis can be carried out. Arguably, the inherent difficulty of these, now classical, problems stems precisely from the discrete nature of domains in which these problems are posed. The convexification of domains underpinning the reported results is achieved by assigning probabilistic interpretation to key elements of the original deterministic problems. The authors begin with considering spaces of probability transition matrices of Markov chains induced by a given graph \(G\) and certain associated random variables such as first return times to given vertices. They show that the variances of the latter are minimised precisely at those Markov chains that are induced by Hamiltonian cycles. Furthermore, they show that the perturbed variance functional differentiates between all Hamiltonian and non-Hamiltonian graphs of a given order, by means of the size of the gap between minimal values of that functional over the space of doubly stochastic probability transition matrices induced by \(G\). The next step is built on a technique that embeds the aforementioned problems into a structured singularly perturbed Markov decision process. The unifying idea is to interpret subgraphs traced out by deterministic policies (including Hamiltonian cycles, if any) as extreme points of a convex polyhedron in a space filled with randomized policies. There are some algorithmic approaches to solve the HCP described in greater detail as well: Linear Programming based algorithms, including the branch and fix method, and the Wedged-MIP heuristic. Two recent algorithms that exploit two modern trends in optimisation in the context of the stochastic embedding of the HCP are briefly discussed: the interior point method and the importance sampling method. All presented algorithms are supplemented with thorough theoretical justification and analysis and with lots of numerical results. The final chapters of the book exhibit another characteristic structure -- self-similarity -- of the class of all cubic graphs that stems from the spectra of their adjacency matrices. It appears that structure defined on points with coordinates given by the mean and variance of certain simple functions of graph eigenvalues has a fractal threadlike appearance. However, the above results and algorithms are dispersed over more than fifteen research papers appearing in journals catering to disparate audiences such as: Mathematics of Operations Research, Random Structures and Algorithms, SIAM Journal on Discrete Mathematics, Optimization, Journal of Mathematical Analysis and Applications and some others. Furthermore, because of the evolution of this topic and specific orientation of these journals, the published manuscripts are often written in a very terse manner and use disparate notation. As such it is difficult for new researchers to make use of the many advances reported in these papers. Hence the main purpose of this book is to present a concise and yet, well written, synthesis of the majority of the theoretical and algorithmic results obtained so far. In addition the book will discuss numerous open questions and problems that arise from this body of work and which are yet to be fully solved. The authors believe that their approach casts the HCP and TSP in a mathematical framework that permits analytical concepts and techniques, not used hitherto in their context, to be brought to bear to further clarify both the underlying difficulty of NP-completeness of these problems and the relative exceptionality of truly difficult instances. Finally, the material is arranged in such a manner that the introductory chapters require very little mathematical background and discuss instances of graphs with interesting structures that motivated a lot of the research in this topic. More difficult results are introduced later but, unlike the research manuscripts where they were originally proved, are illustrated with numerous examples. The authors succeeded in their effort to provide a highly valuable book. I would strongly recommend it to interested readers.