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 NPcomplete problem to determine whether the graph contains a Hamiltonian circuit, that is, a closed walk that visits every vertex exactly once. The problem remains NPcomplete 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 NPhard 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.
Files:
Speaker: Alexander Barvinok
Institution: UM
Event Organizer:
