Some news about SMITH

9^th May 2018, 13:00
Paul Spirakis
University of Liverpool

Abstract

The Problem SMITH is a TFNP problem which asks the following : Given a graph with odd degrees and given a Hamilton Cycle C in it , find another Hamilton Cycle C’ (it is guaranteed to exist). The existence of the second Hamilton Cycle was first proved by Cedric Smith for cubic graphs via a non-constructive approach before 1948. The complexity of SMITH is not yet classified. It is a TFNP problem , also in PPA.
In this talk we report partial progress . We discuss the complexity of the problem for random cubic graphs and show polynomial time whp. We discuss the complexity of the lollipop algorithm of Thomasson. We provide a support enumeration technique for SMITH in cubic graphs. We also discuss SMITH for ANY regular graph and present evidence that odd degrees are not needed.


Joint work with : A. Deligkas and G. Mertzios.
Work in progress.