BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260912T235240Z
UID:Seminar-EcCo-575@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20180509T130000
DTEND:20180509T140000
SUMMARY:Economics and Computation Series
DESCRIPTION:Paul Spirakis: Some news about SMITH\n\nThe 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.\nIn 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.\n\n \nJoint work with : A. Deligkas and G. Mertzios.\nWork in progress.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=575
LOCATION:
END:VEVENT
END:VCALENDAR