Second Hamiltonian Paths

Professor Jack Edmonds
19 October (2.00pm, 045 International Building)

A theorem of K.Berman,1986, says If a graph G with Hamiltonian path P is such that G minus the edges of P is connected, then G contains another Hamiltonian path P' with the same endpoints as P.

We would hope to prove this by an easy (i.e. polynomial-time) algorithm for finding some P'. So far no easy algorithm is known. I describe an algorithm for proving Berman's theorem which is a variation of Andrew Thomason's beautiful "lollipop method". Kind of like the simplex method for linear programming, it has not yet been shown whether or not there is a non-exponential way to do the algorithm. K.Cameron shows that the lollipop method itself is exponential.

A theorem is called "existentially polytime" (EP) if it asserts the existence of something which is easy to recognize when you have it. Very often an EP theorem can be proved by a polynomial-time algorithm which finds an instance of what it says exists. However, Berman's theorem is one of many EP theorems which has not yet been proved by a provably easy algorithm.

The book "Digraphs" by Bang-Jensen and Gutin has many theorems related to Hamiltonian paths. It's interesting to study which theorems in the book can be put into an EP form, and which of them have proofs which are essentially polynomial-time algorithms for finding an instance of what is asserted to exist.