ACO The ACO Seminar (2014–2015)

Jan. 15, 3:30pm, Wean 8220
Alexander Barvinok, University of Michigan
Computing partition functions in hard problems of combinatorial optimization


Consider an NP-complete problem, such as finding whether a given graph G on n vertices contains a Hamiltonian cycle. First, we attempt to solve an even more general problem: given an n × n non-negative matrix A, interpreted as the matrix of weights on the edges of the complete graph Kn, we consider the sum (partition function) over all Hamiltonian cycles in Kn of the products of weights on the edges of the cycle. Thus if A the adjacency matrix of G, we obtain the number of Hamiltonian cycles in G. Next, we modify A by replacing all zeros with some positive epsilons. It turns out that the partition function becomes efficiently computable, which allows us to distinguish graphs that are far from having a Hamiltonian cycles from graphs that have many Hamiltonian cycles (even when "many" still means that the probability to hit a Hamiltonian cycle at random is exponentially small).

In a joint work with P. Soberon, we attempt to establish the most general framework when this approach appears to work: it concerns computing the partition function of graph homomorphisms with multiplicities, which allows us to handle Hamiltonian cycles, independent sets, dense subgraphs and colorings.

Back to the ACO home page