|Date: Friday, February 07, 2014
Location: 3866 East Hall (4:10 PM to 5:00 PM)
Title: On testing Hamiltonicity of graphs
Abstract: Given a directed graph on n vertices, it is an NP-complete problem to determine whether the graph contains a Hamiltonian circuit, that is, a closed walk that visits every vertex exactly once. The problem remains NP-complete if we ask whether one can add at most 0.001n new edges to the graph so that the new graph contains a Hamiltonian circuit. It is also an NP-hard problem to find out if the graph contains at least (0.001)^n n! Hamiltonian circuits. For any epsilon>0, I present a polynomial time algorithm which tells apart a directed graph on n vertices with at least (epsilon)^n n! Hamiltonian circuits from a directed graph on n vertices which does not acquire a Hamiltonian circuit unless some new epsilon n edges are added to it. The algorithm is based on a simple concentration result for permanents of dense matrices.
Speaker: Alexander Barvinok